Functional requirements

• Turn a long URL into short URL
• Short URL should redirect to the original source URL

Assume no users and authentication.

Non functional requirements

• Shortened URL redirection should happen within 1 second
• Redirection service must be highly available, so users could trust the service.
• Limit of 3,000 characters for the original URL to prevent abuse.
• Shortened URL identifier is alphanumeric.

Capacity estimation

Assuming there lifespan of URL would be 3 years.

Assuming there would be 100k new URLs each day.

Assuming there would be 100 million visits each day.

There should be about 109.5 million unique shortened URLs at a given time.

If we're storing about 110 million rows of shortened URLS while storing identifier, URL and a timestamp.

So assuming all of the URLs are using maximum number of chars (3,000) which should be around 3KB.

Assuming a timestamp should be up to 13 bytes.

Let's see how long the identifier should be if we have a total of 110 shortened urls and uses alphanumeric characters.

That leaves as with 62 characters.

62^5 = 916,132,832

5 characters would allows to have almost a billion unique shortened URL and that's above estimated URLs that we're going to have, allowing us to have extra capacity for increased load.

5 characters = 5 bytes.

so in total let's round up to each row being up to 3KB.

That leaves us around 110M * 3KB = 110 * 3GB = 330GB

Expected maximum database capacity is 330GB.

API Design

Let's go with a simple REST API as we basically just have two simple endpoints.

Database design

Since we prefer availability over consistency, I'm suggesting going with NoSQL database and specifically MongoDB which would allow us to have unique index to prevent shortened URL identifier clash but also ability to change to requirements fast and most importantly scale horizontally easily.

The database schema could look like this:

Collection:

Document structure:

Unique index over

TTL index to delete old URLs over 3 years old.

Sharding

We can use sharding to horizontally scale this collection.

could be a sharding key