System requirements

Functional:

1. Users input long URLs and the system returns short URLs (long URL to short URL must be 1:1)
2. Users click short URLs and the system redirects to corresponded long URLs
3. APIs for conversations

Non-Functional:

1. High availability
2. Low latency
3. High scalability (system and storage)

Capacity estimation

DAU: 1M users; write 1 url/user on average, read 10 url/user on average

Read QPS: 1M * 10 / 10**5 = 100

Write QPS: 1M / 10**5 = 10

Read Peak QPS: ~300

Storage: 1M * 10 * 100B = 1MB per day, 365MB per year, 1.5T for 5 years

API design

Read: GET /<short URL id>

Write: POST /api/shorten

Database design

User Table:

• user_uuid (primary key)
• username
• email
• password
• register_at

Short URL Table:

• short URL (primary key) (create index)
• long URL (create index)
• created_by (user_uuid)
• create_at

High-level design

Several components:

Memcached for read operation enhancement.

The Lookup Service looks up whether a long URL exists in DB and will directly return the corresponded short URL to the user. If not, then insert a new long to short URL table entry and cache it aside.

The Redirection Service looks up whether the given short URL exists and will return the related long URL to the user. If not, throw an webpage error.

Request flows

Same as above.

Detailed component design

Each component contains several machines and are distributed. For example, Memcached, NoSQL database here are all distributed systems. This can prevent single point failure causing huge losses and multiple replica can help recover failed components.

The Lookup Service contains an short URL ID generator. We use Base62 as the encoding method. If a non-existed long URL comes, the system uses MD5 to encode (the long URL ++ the current time stamp). Since we want the short URL has a total of 7 characters, so in total this can represent 62**7 different short URLs. We convert the MD5 hex result to Base62 and only take the last 7 characters. If there exists such short URL already we retry the process.

When a request comes, there would be a load balancer first to balance the QPS and dispatch the QPS to different servers. Also in-between servers and Memcached/DB layers, we also need load balancers.

Trade offs/Tech choices

1. NoSQL vs SQL: in this question our QPS is low so SQL could handle. However, we may need to write sharding logic on our own, deal with distributed logic on our own, etc. We choose NoSQL like MongoDB here since we may have to scale (becomes a distributed service, sharding horizontally, etc.)

Failure scenarios/bottlenecks

1. Single point failure: each critical component are distributed to reduce the loss of single point failures.
2. If the QPS gradually increases over time, we may use LRU cache mechanism to cache frequently used short URLs and frequently added long URLs in the cache system. (long tail distribution in the URL usage) Also, add more machines to the places that bottleneck happens.
3. Horizontally sharding the tables in the database into different nodes can reduce the QPS on a single point.
4. Use CDN to cache the requested URLs to speed up.

Future improvements