Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

1. Create shortURL from longURL
2. Redirect to longURL using shortURL

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

1. low latency
2. availabilty is important and eventual consistency can be acheived
3. Shorten URL should be unique
4. 15m DAU, 100M short URLs created/ day and 10B redirects.

Capacity Estimation

1. 15m DAU, 100M short URLs created/ day and 10B redirects.

API Design

1. POST - v1/url/createShortURL -> Short URL in the response

1. GET - v1/url/{shortURL} -> Redirect to longURL

High-Level Design

1. Client will send the request to create short URL using POST - v1/url/createShortURL with longURL in the request body.
2. The service will use MD5 algorithm to encrypt the longURL. Just pick the intial 6 characters from the encrypted code, scan the DB if the id does not exist, store it as a id and longURL in the DB.
3. If the Id already exist, run the encyption algorithm again, pick the intial 6 characters from the encrypted code, scan the DB if the id does not exist, store it as a id and longURL in the DB
4. But this will increase the latency, so we can maintain the counter in the service, we can pass counter to the encryption algorith along with longURL, this will make sure that we always get unique shortURL.
5. But the possible problem with counter is if we get miliions of request it's difficult maintain the counter and if the system fails the counter will start again at 0 which can give us duplicate id.
6. To avoid this we need to scale the system. So to scale further we must go for horizontal scaling.
7. We can have multiple servers with load balancer. The load balancer will redirect the request using round robin algorithm and each server will have it's own counter. But again if the counter value is same, there is possibility that we can have duplicate encrypted id. So, we can store the counter globally.
8. To store the counter globally, we can use Redis cache. We can store the counter in Redis cache and each replica of server will call Redis to get the counter and use it in encryption algorithm.
9. With this approach we won't get any duplicates. If the redis fails then that could be the issue.
10. In this case, we can use zookeeper and snowflakeId, for each server there will be workerId in the zookeeper, so we can use that workerId in the snowflakeId and with this approch, we will never get duplicate encrypted code as we are only taking first 6 initials. and even if zookeeper fails we will have workerId, we only need zookeeper to configure new server.
11. We can separate the concerns, so as per NFR, there are approx 100M new short URLs created per sec. We can have seperate server for createURL. We can have seperate server for GET endpoint. because the redirects per sec are very high we can scale that server independently by having multiple replicas. Also to reduce the latency of redirection request we can have Redis cache, if the longURL exist in Redis we will return the response from Redis else we will hit the DB. This overall approach is highly scalable and high latency.

Database Design

Postgresql can be used.

1. The encrypted id and the original URL should be stored in the database table.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.