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

Caching

In order to speed thing ups in redirect service, let's cache redirects in Redis.

Do TTL of 1 day, so the cache will be invalidated after the day. Assuming it's OK, for the deleted URLs to still work for a day.

High level design

So, in order to make things things more scalable, as there will be magnitudes more traffic to redirection service rather than creating the URLs, we can separate these two.

To make the system really scalable let's use kubernetes: api gateway to route http requests to either redirect service or shortening service.

Let's have MongoDB as a sharded cluster outside kubernetes.

Let's have Redis Cluster also outside kubernetes.

Before API Gateway let's have an load balancer (ingress) that would talk to the api gateway.

Redirect service and shortening service would use HPA to horizontally scale by spinning up new pods.

Redirect service would talk to MongoDB cluster directly, while Shortening service would talk to caching (redis) first if there's no hit, then talk to mongo db, thus allowing us to fetch URLs fast.