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.

We can use TTL strategy of 1 day for the cache eviction.

We can ignore cache invalidation since cache eviction can cover these cases.

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 and shortening services expose the metrics to prometheus.

Thus, this will allow HPA to horizontally scale by spinning up new pods.

We could use CPU and memory metrics for HPA to base autoscaling rules.

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.

Detailed component design

Failure scenarios

If MongoDB shard goes down, then some of the URLs that are in that particular shard and are not cached will not be redirected. Service is available but not fully, so degradation but it's not single point of failure.

If whole MongoDB cluster goes down, then URLs that aren't cached will not be available. Again, degradation but not full downtime.

If Redis node or cluster goes down, we'll have a fail switch in redirect service, so the requests will go straight to the database. The service most likely will become slower but still available.

If shortening service goes down, the K8S will try to self heal and launch pods that are healthy. If they fail, the shortening service will be down, but redirect service will not be affected. Thus, system is still available with degradation.

If redirect service goes down, the K8S will try to self heal and launch pods that are healthy. If they fail, the redirect service will be down, but redirect service will not be affected. Thus, system is still available with degradation.