System requirements

Functional:

1. generate a short url based on long url input
2. short url should redirect to original long url
3. analytics on times a url is used
4. option to create custom short url
5. url validation
6. user authentication
7. set expiration( with default expiration)
8. rate limiting to prevent abuse

Non-Functional:

1. need to support high traffic - 10000 qps
2. the redirection logic should be persistent
3. need to handle hash collision for consistency
4. need to be available and reliable 99.9% uptime
5. secure user data and urls
6. logging and monitoring for errors and performance
7. data should not be lost

Capacity estimation

1. storage. number of requests per day: 10000 * 60 * 60 *24. each request takes 100 space. This is storage increase per day.
2. Retention 5 years, so we can calculate total storage needed. previous result * 365 * 5
3. Number of servers based on qps: 10000/1000 = 10, add 2 more for redundancy and fault tolerance
4. number of load balancers. 10000/5000 = 2, add 1 for redundancy. 2 load balancers could be put in different region to support users from different locations.
5. number of connections: 10000 * 0.01 = 100 peak time: 150 connections, with connection pooling: 150/5 = 30
6. read : write = 10 : 1
7. 2 database instance to prevent SPF

API design

Rest API:

GET short_url/v1/{short_url}

response: 301 header: Location: long_url

POST short_url/v1/create

body: {long_url}

response: {"generated": short_url} 204 created

Database design

Use NoSQL. E.g. DynamoDB

key: short_url : string

value: long_url : string

High-level design

Client -> Load Balancer -> Server -> Cache -> Database

Request flows

generate url: User paste original long url and click generate short url. a POST request is made and sent to load balancer, load balancer redirects request to a server, server checks if long url exists in cache, if not, check if exists in db, if not, generate short url using base 62, store short url in database and send response 204 with short url;

use short url: user enters short url in browser, GET request sent to load balancer, load balancer redirect the request to server, server checks if short url exits in cache, then check if in db, if not return 404 not found, if yes returns 301 redirection with original long url, browser visits original long url after receiving 301 response.

Detailed component design

To improve performance and reduce db load, we can add a cache between server and db because when a short url is created it is likely to be used often, we can use LRU cache. When a short url is created we perform write through as we need to ensure db operation is successful so that we don't lose short urls. When a short url is being used we perform read through.

we can add redundancy to load balancers to avoid single point of failure. Multiple servers are added to handle traffic load and we can add redundancy to servers for failover. we can add multiple DBs for fail over and recovery.

Trade offs/Tech choices

For the server logic, we can use hash function CRC32 to generate hash value and use predefined string to avoid collision, this will generate same length short url but complexes the system. Or we can use random number generator to generate unique id and generate string with base 62 conversion, this is simple and won't have collision but will generate different length of string. Or we can just use a random string generator to generate a string and assign it to long url this is optimal.

Failure scenarios/bottlenecks

If we can't find short url return 404. If url is invalid, return 400 error.

If load balancer fails, use another one, if server or db fails, recover with redundancy.

If all the short url is used out, increase one character.

Future improvements

Create user login function so that we can help the user to manage generated url, e.g. update and delete. We can also use authentication to make it more secure.

Add rate limiter to prevent bad actors. (by IP, by machine id)

use 302 redirection so the server can collect usage of short url for analytics.