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 milliseconds.
• The service should be highly available with minimal to no down time.
• Application should be scalable to handle changing traffic.

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. Load balancer to direct traffic
2. Containers running application logic
3. Server side caching using Redis
4. A database to store our data
5. 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. Load balancer routes the request to a container
3. Application checks the cache for the URL, if found, it return immediately
4. In case of a cache miss, container queries DB and returns the result

Example flow of a createShortURL request -

1. User makes a request
2. Load balancer direct request to a container
3. Application creates a random 16 character short URL, checking for collision and retrying if needed.
4. Application writes the short URL, long URL and other metadata to the database
5. Application returns the short URL.

Highly popular URLs can be cached in CDNs to improve performance with updates once every week.

We will use Redis for caching and Dynamo DB as our database as its a key value store perfect for our use case.

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 the overhead of checking for collisions. In case of a collision we regenerate the short URL. The likelihood of a second collision is very slim.

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 -

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 database and implement robust monitoring and alarms to notify engineers before anything breaks.

Scaling - We can scale the application easily by deploying multiple containers of the server logic. We can also deploy read replicas of the database to reduce load and remove single point of failure on the database. We will use an ELB to direct traffic evenly to the application containers.

Caching logic -

We have two caches essentially, first the Redis cache on our servers and a second CDN cache which will store geographically very popular URLs. We will use least recently used replacement policy in both the caches. The CDN cache can be updated less frequently (every week) as popular URLs from a region do not change that often.