System requirements

Functional:

1. when user gives a long url, the system returns a short url
2. when user access a short url, the system redirects the user to the corresponding long url
3. a short url expires after one year. After expiration, the same short url may be used to map to a new long url

Non-Functional:

1. Availability: it's ok for the system to have short down time
2. Consistency: for the same short url during its lifetime, it shall always redirect to the same long url

We choose consistency over availability when we need to make a design choice.

Capacity estimation

Assume write RPS = 10, read QPS = 200.

To store one year of short urls:

10 * 86400 * 365 = 320 M short urls.

Assume we use base 62 (10 digits plus lower and upper case english letters).

Log(320 M) / Log(62) = 5. We need 5 characters for the short url key.

For read QPS 200, that's 5 ms per request, or 1-2 ms per request at peak. We need multiple servers to handle read request.

For write QPS 10, that's 100 ms per request, or 20-40 ms per request at peak. We need one server at non-peak hours and multiple servers at peak hours.

API design

Write:

POST /

payload is long url

response payload contains the short url created.

Read:

GET /

This happens when user visits the website, e.g., bit.ly/

Response is an http redirect to the corresponding long url

Database design

320 M pairs of short and long url pairs to store.

http urls have a limit of 2000 characters. Assume the average long url length is 500 characters.

Storage need for one year (5 short characters, 500 long characters, and timestamp of creation):

320 M * (5 + 500 + 8) = 165 GB

Data is small. And due to its highly relational nature, we choose SQL.

High-level design

See diagram.

Request flows

Write:

1. user visits the service server
2. user sends a request to create a short url by providing a long url
3. service creates a new short url
4. service stores the pair of short and long url to DB
5. service responds to user the created short url

Read:

1. user visits the short url
2. service receives user's http get request
3. service looks up the corresponding long url from cache, or from DB on a cache miss
4. service redirects user to the long url if the short url record exists, or gives an error if the short url does not exist or is expired

Detailed component design

Short URL generation algorithm

We have a few choices:

1. Calculates a hash, e.g., sha1 sum, of the long url string.
   1. Pros: the same long url will always yield the same short url
   2. Cons: adds hash computation latency in the write service. Also, even though the same long url results in the same short url, without additional caching or lookup, this info does not save any other steps in the diagram. To avoid duplicate hash computation, we need an extra lookup table (which stores already known long urls) that the write service can query, which adds additional latency
2. Random generator.
   1. Pros: does not need pre-lookup if the long url already has a short url created.
   2. Cons: as the number of url pairs grow, chances of collision grow dramatically. We need to check collision on every generation, which adds latency, especially unacceptable when the number of url pairs grow high.
3. Pre-generated sequence. This will change the initial design diagram: instead of letting the write service to generate a short url on the fly on every request, we have a background short url generator to pre-generate short url characters and store them in pool for the write service to grab.
   1. Pros: This background service can be run independently and async from other services.
   2. Cons: if the generation is in sequence, then the short url characters become predictable. However, we can easily use random generation to avoid this. Although random generator requires collision check and resolve, this is not a big issue because the service runs async in the background, and thus does not add extra latency to the main write service, as long as we ensure this generator service pre-generate enough available tokens ahead of time.

Expiration

We have a few choices:

1. The diagram shows the expiration service runs in background on schedule.
   1. Pros: it's not critical for a url to be expired precisely at the one-year mark; a little extra lifetime is ok. Running expiration async can reduce stress on the main service.
   2. Cons: there may be a potential race condition that a user wants to visit a short url, at the same time the expiration service kicks in and retires that record. When the read service tries to get the long url, it may or may not get it. This is generally ok, as the time difference comparing to the one-year lifetime is small.
2. We can also let the read service to expire old records on the fly.
   1. Pros: this is lazy expiration, which is less complicated than the async background design.
   2. Cons: adds a little more latency on read service. We could possibly add a queue to queue up the lazy expiration requests, which adds a bit more complexity.

Trade offs/Tech choices

See details in "Detailed component design"

Failure scenarios/bottlenecks

Service failure

Both write and read service may fail. We may need leader-followers architecture for the services. All writes go to the leader, and all reads go to the followers. If a leader fails, the followers will elect a new leader.

With this design, we need carefully store all write requests to a log on each server, so that if leader fails, we can compare the log and identify any discrepancy before making the new leader up running.

Also, consider read-after-write and cross-device read-after-write. The same user's read after write is better be routed via the leader to avoid fake data discrepancy.

DB sharding and replication

One single database can store all the data, but may be slow to process all requests. We can partition based on the beginning characters of the short urls, especially useful when the short url keys are generated randomly, so they can distribute randomly to different partitions. Each partition can act as its own main replica, and as others' secondary replica. Using replica so that if one partition is down, other partition can still be used for read and write.

Load balance

Load balancer should take account for the above server and database scaling.

Future improvements

Larger amount of data

If the data is much larger, we need a very careful sharding and replication database design, as well as distributing traffic load between servers more wisely.

User account

We may add user account system to allow registered users to have their short urls be associated with their account and manage them.