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...

Consistency

As we can't have two long URLs with the same short URL and we intend to use the same unique id to generate the key, it is essential that we go for consistency over availability in the event of a network partition. Since Cassandra is leaderless, we need to ensure a decent quorum.

Assume Replication factor is 4. We can keep read quorum as 3 and write quorum as 3 ensuring -> read quorum + write quorum > replicas number.

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.

Rate limiting

Rate limiting will be done by using a Kong / Apisix Application gateway. Requests will be based on Token Bucket algorithm. In the event of burst traffic, since the number of tokens is predetermined based on our capacity to handle , requests will be rejected if tokens are not available

URL update

URL update or delete is not supported. However, after the expiry of the URL it will get deleted from the DB and from cache ( no need to separately remove from cache as it has a TTL )