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:

• High availability - Since people have only the tiny URL and need to navigate to the actual URL using our service the redirect functionality needs to be always available
• Scalability - It is possible for around multiple people to be referring to a redirect API at the same time.Hence the redirect service should be capable of handling at least 50000 requests at the same time.
• Consistency - The hashing function to assign tiny URL should be very robust. No two URLs should be assigned the same tine URL hash
• Horizontal scalability- In the event of scaling due to heavy load, we should be able to add more application servers and handle the load without any stickiness. We should be able to add more instances of the DB ( shading / partitioning. ) and increase performance without any stickiness
• Redirect latency - 200 - 300 milliseconds for at least 95% of the requests. Latency is measured from the time the user clicks on the short URL till the long URL is fully loaded. Average latency should be 200 ms and peak latency should not exceed 300 ms
• Create TinyURL latency - Creation of tinyURL should be done in 300 - 500 ms for 95% of the requests. Average latency should be around 300 ms and during peak time, latency should not exceed 500ms

API Design

PUT : /api/v1/longURL

Request body : { longURL: <>}

Response : {shortURL:<>}

Code : 201

GET : /api/v1/shortURL/

Response: {redirect://

code:301

High-Level Design

Redirect flow

The Client uses Web browser to access the given tiny url. It reaches our load balancer / API gateway. This would be Nginx. Nginx routes the request to one of the API servers based on load. API server would load the corresponding long URL from Cassandra DB. The DB would be partitioned based on the tiny URL as key. API server returns redirect with long URL to the browser and User is redirected to the corresponding long URL

Create TinyURL flow

The client uses PostMan or any REST client to call our create tiny URL API. Call is routed to nginx ( load balancer ). Nginx routes it to API Server. API server uses hashing logic and creates a tiny URL. The tiny URL and the long URL are stored in Cassandra DB as key value pairs and the tiny URL is returned as response to the user.

Identifier Generation strategy

we will go for a 7 character key consisting of [A-Z][a-z][0-9] and no special characters.This should be roughly 3 trillion keys. We will use base62 encoding for the hashing. Following is the process

1. CHeck in db if the long url is already present
2. If present, return the corresponding short url
3. Else, Generate a unique id using UUID for the long URL. if Id already exists, try generating new UUID till unique id is found
4. with the given unique id, use base62 encoding to generate a new tinyurl and return to user
5. If there is any colliss

Data model

{

id long,

tinyURL string,

longURL string

}

Caching

There will be a caching layer between the DB and APP server. This will be an LRU cache. so we retrieve from cache, if it's not available, we retrieve from DB and update in cache. While writing we write directly to cache

Note: I am not considering expiry time as of now

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, and any relevant algorithms or data structures. Consider drawing detailed diagrams to enhance your explanation...

Caching

Use a redis cache cluster. I will have multiple nodes . Additionally, I will maintain a local in memory cache for each app server which will have the hot key. Identification of the hot key can be done by using Redis --hotkeys. Additionally, we can keep the hotkeys in all the nodes and read from any replica. Write should be to all the replicas

We go in this order local cache -> global redis cluster -> DB

In case of cache miss we go in the above order and populate the caches with the value retrieved from DB

Cache invalidation is not a major concern, since we don't support URL update. User needs to create a new tiny url with the updated URL. IN case of deletion or take down of the site, the TTL of cache should help. We can keep a TTL of 1 month to ensure that.

Since it's LRU cache, the older entries will get flushed out to make way for new ones.