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:

• Our system will have many more redirect endpoint calls than create short URL calls.
• The create short URL endpoint can take some time to create and return, let's say < 10 seconds.
• The redirect endpoint needs to be quick, returning in < 50 ms.

API Design

We will have two endpoints:

1. createShortURL: takes a long URL, userId and optionally other metadata like TTL and returns a shortened URL
2. redirect: takes in short URL and returns the original long URL

High-Level Design

We will have the following components:

1. Server running the application logic
2. Server side caching implemented using Redis
3. A database to store our data
4. Optionally we can cache geographically popular URLs on CDNs

Example flow of a redirection request through the system -

1. User makes a redirection request
2. K8s orchestration routes the request to a pod
3. Application checks the cache for the URL, if found it return immediately
4. In case of a cache miss, pod queries DB and returns the result

Detailed Component Design

createShortURL logic -

We can use two approaches here hashing or random generation. We can use hashing algorithms like SHA256 to create a unique hash of the long URL and return it. This presents a problem on the length of the short URL which is now fixed to the output length of the hashing algorithm. Instead we can use a random number generator to randomly generate a 16 character short URL. In this we will have to check that the generated URL is not already being used, if a collision is detected we will regenerate the short URL.

redirect logic -

Given that we will have to store data for millions of URL, querying the DB for the original URL becomes the bottleneck quickly. Since we will be searching based on the short URL it makes sense to partition the DB on it. The random nature of the short URL ensures that a single partition does not get overloaded. Additionally we can build secondary indexes on userId to speed up lookups.

fault tolerance and scaling -

We can not afford downtime as it will negatively affect our reputation and may lead to monitory loss. So we will need to keep replicas of the DB. Also the application logic is stateless so we can easily containerize the app and use k8s to orchestrate multiple containers to serve demand.