System requirements

Functional:

Service should be able to take a long URL input and generate a unique,shortened alias for it .

When accessing the short URL we should be redirected to the original URL

Analytics

Periodic URL cleanup lets say after 3 years .

What kind of users do we expect the users to visit

1. Logged in ?
2. Anonymous
3. API users
4. Admin users

Non-Functional:

1. Security -- Do we need to care about malicious link?
2. Scalable _ how many users do we expect our system to have ?
3. Availability - 99.9%
4. Latency - ?

Capacity estimation

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

Let us say we have 1 billion users to support

Out of which we have 100 million daily active users

We expect each user to create 2 urls every day

QPS calculation = 100 * 10^6 * 2/ 10^5 = 20k urls/second

Peak QPS = 2 *QPS = 40k urls/second

If the read to write ration is 3:1

Incoming requests for read will be 120 requests/second

Storage estimates

100 million * 10 KB = 1 PB/day

For 1 year

12 PB/Year

For 3 years we will need

36 PB

API design

We will need 3 API's to support the shorten the URL

1. Create short url

/api/v1/shorten_url -- POST -- Will send a 201 when creating , we will need to send the user_id, expiry date and also the url to be shortened in the payload

1. Get Long url - GET - This API is used to fetch the long url from the short url , will recieve 404 if thURL does not exist , wills end a 302 if the URL exists
2. Delete URL - DELETE - Used to delete the URL

Database design

We will need 2 tables

1. To store user data , this will have user_id, email , name ss their fields . In this we will use user_id as the primary key
2. We will have url table which will have url_id , long_url and the shortened_url as the fields

High-level design

flowchart TD

Browser --> LoadBalancer

LoadBalancer --> ApplicationServer1

LoadBalancer --> ApplicationServer2

LoadBalancer --> ApplicationServer3

ApplicationServer1 --> DocumentDB

ApplicationServer2 --> DocumentDB

ApplicationServer3 --> DocumentDB

Request flows

Usecase 1

The user enters the long url in the browser then the request is forwarded to the loadbalancer which then calls the shorten_url api endpoint to shorten the URL . Once the URL is shortened the shortened URL is stored in the DB and the response it sent back to the client .

Usercase 2:

User enters the short url , we now call the get_url method , we try fetch the url from the DB , if the URL is found we give back th url with 302 method and if the url is not found we return 404 .

Detailed component design

Lets talk about how we generate the alias

We will use alphanumeric characters to generate the URL , we will use base 62 encoding to create the URL ths is because [a-z,A-Z,0-9] and then we can get a url like

www.google.com - biturl.com/wer456

Now to generate the keys we can either create them on the fly but however this will slow down the system as we have to lookup the key in DB whether it exists or not before we create the alias. We also need to make sure that we do not create the same alias if the smae URL is used by 2 users . We can append a random char but this still does not solve the problem of key clashing.|

Instead we will use a key generation API which will generate the keys separately and store it in a separte DB called key gen DB.

Every time a request comes the app server will call the key gen API which will give it a unique key as soon as the key is used by API we will mark it a used.

We will also have a service which will periodically purge the keys from the DB after 3 years

Trade offs/Tech choices

We have used document DB to optimize for read and write , we will lose the ACID properties.

Failure scenarios/bottlenecks

The document DB which hold the URL can come under heavy load and can struggle , we can put a cache in front of it to reduce the read load on the DB.

We will also need a replica of the DB to ensure we have backup incase the main DB fails and we can rollover to the secondary replica.

If we use cache we ill need ro ensure we are regularly purging the cache , we will use LRU , FIFO tactics to ensure the cache does not grow too big.

The key generation DB will also need a replica to store all the keys

Future improvements

1. Add cache
2. Add replicas to the DB
3. Add rate limiting middleware to prevent DDOS
4. Add cache infront of DB to reduce the load
5. Perform sharding on DB if the table goes too big. We can use the url_id to determine the sharding.