System requirements

Functional:

I can create a short URL given a long URL.

I can visit the long URL by visiting a short URL.

Non-Functional:

The system should have high availability.

The system should have low latency.

Capacity estimation

Estimate the scale of the system you are going to design...

1M users * 1 short URL creation daily = 1M short URL generated -> 1M write

1M users * 10 short URL visit daily = 10M short URL visit -> 10M read

Write QPS = 1M / 86400 = 11.57 QPS

Read QPS = 10M / 86400 = 115.7 QPS

Extra space: 80B * 1M = 80MB extra data daily

API design

string create_short_url(string long_url);

Database design

SQL database

short_url string -> index

long_url string

create_date date

High-level design

1. Server:
2. The user interacts with the frontend to input long URLs and receive short URLs
3. Cache:
4. The cache will store long to short URL conversion
5. Load Balancer:
6. This is a component which balance requests to servers to reduce load
7. Database:
8. This is a component which stores the short to long conversion
9. Redirection Service:
10. Once original long URL is retrieved, the redirection service will forward the short URL for client.

Request flows

When creating long url, the client will send a create request to the load balancer. LB will try to find a server that is available. The server will accept the request. It will check in the cache whether it the long URL exists in the cache. It will return short URL if it exists in cache. Otherwise, it will create a short URL and write database. The long URL will be cached and send back to the client.

For reading, it will again forward the traffic to the server first. It will go to cache to check if the short URL is held in cache. If not, it will go to database and search for the short URL to retrieve the long URL. The long URL will be sent to redirection service and send back to the client.

Detailed component design

Each server will use a self incremental id as short url. Whenever it needs to create a short url, it will increment the id. The id will be converted to base of 62 for 5 digits. The first character will be the id of the server.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?