Requirements

Functional Requirements:

1. Users will be able to create shortcode of any given long url, and then retrieve the long URL.

Non-Functional Requirements:

1. This will be a read heavy system so we need low latency for URL retrieval
2. we need redundancy in the database layer, due to possible high volume of reads.
3. we can achieve high availability through multiple app servers under a load balancer. for a read heavy system a single DB can be a bottleneck so we will have a cache layer like redis in front of it to reduce the load from the DB and we should have at least two read replicas spanned accross multiple AZs where we will split the read and write traffic. writes will be handled by the primary databases and reads will be covered by the replicas
4. security
5. scalability

Capacity Estimation

for around 1M writes per day and around 1B reads per day.

so it turns out around 12 writes per second and 11000 reads per second

estimating a size of 500 bytes per write entry in the database we have total of 182.5 GB storage in a year. so for the upcoming 10 years we need around 1.8 TB of storage.

API Design

POST /api/shorten

response code will be 201 created and the shortcode.

body : {

shortcode : ,

timestamp : ,

res : 201

}

GET /api/shortcode?code= 200 OK and the long url as the part of the response then 301 redirect which will redirect the user to the corresponding long URL

body : {

longURL : ,

res : 200

}

High-Level Design

the user's request will hit a CDN layer first for global distribution. the frontend of the application will be stored inside an object storage layer and all the static contents will be distributed globally by the CDN. It will be attached or linked with the load balancer as well.

The application load balancer will inspect the HTTP request header and based on the request method it will correctly route the traffic to the appropriate API endpoint.

For the shortcode generation we will use counting strategy. we will have a global counter and when a new write request comes we will assign the number in the global counter to the corresponding source URL, shuffle the counter number to randomize the shortcodes and maintain uniqueness. Then we will base64 encode the shuffled number. we will make sure the shortcode is no longer than 6-7 characters.

then the app servers running in backend will take the request and make API calls which will then forwarded to the database layer.

there we have redis as a caching layer. If the data user requesting is already present in redis then it's a cache hit and it will be directly served from cache instead of hitting the DB. when it's a cache miss then it will be forwarded to the DB where based on the request method it will take it's route. If it's a POST call it means a write request which will be handled by the primary DB and for any GET calls it will forwarded to the read replicas.

And before it get's back to the users it will get stored inside redis.

and redis will also store some hot keys which are the frequently accessed links.

Database Design

Detailed Component Design

App servers : They will remain stateless which will allow us to horizontally scale them when needed.

Redis : This will work as a caching layer reducing the DB calls for hot keys.

but we can also face situations like cache eviction. where a multiple hot keys or a single hot key expiration will overwhelm the DB with thousands of request. to solve this we need add jitteriness or randomness in key expiration for redis. also we need some sort of rate limiting on redis as well. when a hot key expires instead of forwarding thousands of requests directly towards the database we will only allow the first request to hit the DB while the others will wait in behind. once the first request get processed it will store the data in redis first before sending the response so that from the next request onwards redis can handle the data instead of the DB.

Database Partitioning : For data storage we can shard the database into four shards, as per our previous calculation for storage size we are considering roughly 2 TB of DB storage for upcoming 10 years. so each shard will store nearly 500 GB of data. we will use the shortcode as the primary index for fast & low latency search queries and if we need to add or remove shards from our existing system we will use consistent hashing to reduce the engineering overhead. each shard will act as the primary DB and can have at least two replicas spanned across multiple AZs.

we can also maintain WAL archive per shard inside object storage like S3 in case a particular shard and it's replicas died we can replay the WAL log to get all the data back.

Cache Invalidation : For data updates which are still not expired we need cache invalidation to prevent serving stale data to the users. we can invalidate on write where the system will look is the data is already present or not in the cache if it gets an update request. if yes then it will invalidate the cache first to store fresh and new data before serving to the end user.

Generator Failure : for this we will use a circuit breaker to block any incoming request from hitting counter service, once the counter service becomes healthy the circuit breaker will start allowing requests.