Requirements

Functional Requirements

1. Generate a short URL for a given long URL
2. Redirect a short URL to a long URL

Non-Functional Requirements

1. Horizontally scalable
2. Available
3. Low latency for redirection under 50ms

API Design

1. Creating short URL

Sample Request

POST /shorten

{

"long_url" : "https://example/some/long/url"

}

Sample Response

{

"short_url" : "https:/short/url,

"long_url" : "https://example/some/long/url"

}

1. Redirect to long URL

GET /short_url

Response

301 - Moved permanently

302 - Moved temporarily

404 - Not Found (the long url was not found)

High-Level Design

Key Components

1. URL Generation Service

URL generation service is the service which will write to our DB. It has to be responsible for generating unique URLs and taking care of collisions, if any.

1. URL Redirection Service

URL redirection service reads our DB to fetch the long URL associated with the short URL clicked by the user. Since this can be a read heavy system, URL redirection has to be quick. We can add cache layer to avoid querying the database everytime.

1. Database to store URL mappings

Since it is a key value type data with no complex JOINs, we shall go with NoSQL database like DynamoDB

URL Mappings Table

"short_url" : "",

"long_url" : "",

"created_at" : ,

"expires_at" :

"short_url" will be the primary key

Detailed Component Design

1. Create Short URL

Given a long URL, we can compute its hash using cryptographic hash function (for eg. md5Sum) which gives a 128 bit sequence for each long URL. To generate short URL, we can trim this sequence to 6-7 length and then do Base 62 encoding. This will give us some short code. The con here is collisions. We can handle collision by adding a counter to the code and re hashing until a unique code is obtained.

1. Redirect to Long URL

For an application which has 100:1 read to write ratio, our redirection has to be pretty quick (in under 50ms). To achieve this, we add a cache layer to access frequently clicked URLs. Only in case of a cache miss, we will go the database and query and further add the entry to the cache.