System requirements

Functional:

1. Given a long URL, return a short URL. This should be 1-1 mapping.
2. Click on the short url will redirect the user to the long URL.
3. Users can create customized short url.
4. Maximum length of the short url is 16.
5. Links expire after a default amount of time, this can also be overwritten by the user at the time of short URL creation.

Non-Functional:

1. The result must be accurate.
2. System should be highly available, low latency.
3. Short URL should not be predictable.

Capacity estimation

Assume 1M DAU, each user creates 1 short url on average per day. Assume read write ratio is 100:1.

TPS = 10M/24/60/60 = 30

QPS = 3000

Assume we store the data for 5 years by default.

5 years * 1M * 30 days * 12 month = 1.8B records

Assume each record is 2KB, the total size is around 3600GB.

API design

• createURL(long_url, short_url, user_id, expiration_time) - return short url, error if short url already exists
• getURL(short_url, user_id) - return long url

Database design

We can use NoSQL since we only need to store a key value with some metadata. This also scales better given the high TPS and memory usage.

• long url (2kb)
• short url (17b)
• expiration time (8b)
• created at (8b)
• last updated at (8b)
• user id (32b)

High-level design

Request flows

Write - The client fires a createURL request to the server, the server first checks if a short URL exists in redis, if so, returns it, otherwise creates one and inserts to the database. If a customized short url is provided, the server uses that if no duplicate exists, otherwise returns errors.

Read - The client fires a getURL requests to the server, the server first checks if a short URL exists in redis, if so, returns it, otherwise reads from the database and updates redis.

Detailed component design

The server uses MD5 to hash the long URL, if the result already exists, append a 5 digit random string and retry.

Clean up service scan through the database and redis daily to remove records that expire.

As in the capacity calculation section, the total memory we need for 5 years is 3600GB, should fit into one single NoSQL database, thus we can replicate the entire database to scale up.

Trade offs/Tech choices

• Use NoSQL instead of SQL since we only need to store a key value with some metadata. This also scales better given the high TPS and memory usage.

Failure scenarios/bottlenecks

• To ensure accuracy, we have to consider the use case where multiple requests are sent for the same long url, we can have the server grabs a redis lock on the long url at the time of creation.

Future improvements