Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• System should be able to support 100k QPS
• System should be horizontally scalable
• System should have four 9s availability
• It should have low latency preferably below 100ms
• It should be available to multiple data center
• Might provide an analytics dashboard for URL hits.

API Design

System will expose 2 APIs

1. API to register long URL and get the short URL in return. --> /api/short
   1. Request Method - POST
   2. Request {"longurl":""}
   3. Response{"shorturl":""}
2. API to get the long url when hit the short url. /api/{shorturl}
   1. Request Method - GET
   2. Response Text long url with Response Http code 304 move temporarily. This way browser will redirect to long url.

High-Level Design

1. Admin Client:- This system will offer a UI to client to register it's websites long url.
2. User Client:- After registered long url available in the system, User to the website can request the website using short url to this system. This system will store the mapping between short url and long url in a NO SQL db.
3. Entry Lyer :- this will help to redirect the request to a specific instance of read epi. LB will help in distributed the load horizontally. for 100k QPS one instance of cache and POD can support that. We can have new pods spinning up, when QPS reaches to 90K.
4. Server :- Server will be connected with NOSQL db and a distributed cache to improve the latency. NOSQL DB will help to support the huge volume of read heavy calls.
5. Server will have a method to generate unique short url for each client and store it in the NO SQL DB as part of registration process.
6. Server offers 2 separate APIs, while the registration API will not be resource intensive as The QPS will be less for registration. Read API which will send the short url and get the long url in return with redirection code 304, will have QPS in the range of 100k.
7. Registration API can use a Hashing to generate unique short url for each long url. Since we are using a NOSQL DB to register the long URL, collisions can be detected and resolved while registration.
8. Cache will support the LRU eviction policy to support 95% of cache hit. In case of cache miss, we will read from NOSQL DB. and cache the response.

Detailed Component Design

1. Short url generation :- We can have pre-generated short url and assign them to long url. I this way we can generate multiple short url for same long urls as well. Batch URL generation is going to be a distributed batch job, which can generate more unique short urls periodically. Distributed nature of this job will solve the split brain problem as well.
2. We can have a batch component which can generate short urls and update that in the NOSQL db, where we can just update the long url and provide the short url. Batch components can solve the potential conflict as well as it will have access to all the generated short urls at the same time. It can sort them and remove the duplicates as well.
3. Data Model will be looking like shorturl | longurl | expTS
4. For High availability We can have multiple read replica of this DB with Async writes supported to all replicas. As a fallback We can also use Unique ID generated by distributed DB and base 64 encoding on it, to provide short url in case of batch job failures.
5. We can use LRU cache eviction strategy to keep the cache vacant for new entries.
6. Depending on Usage we can set the TTL as well, which will help in getting rid of stale data. We can set few hours of TTL to balance the performance and data freshness.
7. To refresh the updated entries in the cache, every DB update will also delete the entry from the cache so that it can be refreshed in the next get request.
8. To mitigate the hotspots problem Data can be sharded into based on generated short urls, Eg. 100M urls will be in one shard and 10 shards can have 1B short urls. Now keeping this information in some kind of zookeeper, we can redirect the requests to individual shard and avoid hotspot.
9. At last Rate limiting will be also introduced at API gateway level to avoid bot attacks.