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.

Fronend server could use the first character to determine which server to route the short URL to long URL request.

When the client comes with a long URL that has already existed in the cache, it will immediately return the short URL. If it does not exist, it will next generate the short URL. As we are using self incremental id, the URL will be unique in each server.

Database could use master slave to accelerate DB read. Base this is read heavy system, we can use master slave architecture to accelerate.

Trade offs/Tech choices

Here we are chooing to use many to one mapping. Many short URL to one URL mapping. The advantage is that because we are using the cache, we can quickly find the short URL in mapping if cache exists. If cache miss, there will only be one DB write.

Disadvantage is that it will use more space.

The other approach is to use 1-v-1 mapping. Disadvantage is that there will be 2 db writes when creating URL. Advantage is that space is saved.

Failure scenarios/bottlenecks

We need to validate whether the input long URL is valid.

We also need to make sure the server can handle if the short URL is not valid.

When server is running out of incremental ids, there will be collisions.

DOS attacks. Some programic planned attack and try to exhaust short URLs in short time.

Future improvements

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

We can add throttling exception to requests.

Have a blacklist of URLs where fraud could happen.