System requirements

Functional:

1. the client is able to create a tinyURL from a input long URL.
2. when the client access using a tinyURL, the system redirects it back to the long URL

Non-Functional:

1. availability - highly available
2. durability - the data shouldn't be lost or corrupted, the system should not redirect to the wrong URL
3. low latency

Capacity estimation

1. DAU - 1 million user per day
2. 0.2 new tinyURL generated per day -> 200k generate request per day -> 2.5 write average, so estimate 5 write TPS
3. 20 million redirections per day -> 500 read TPS.
4. we want to store the tinyURL and long URL mapping for one year, estimate each row is about 500 character in length total, so 0.5 KB for one mapping. since we have 200k new tinyURL per day, we should have 40 GB of storage.

API design

we will have two APIs

1. put(longURL): this generate the tinyURL that will redirect to the long URL in the input. (Note, for customizable TTL, we should add a expiration parameter).
2. get(tinyURL): this will redirect the http request to the long URL stored.

Database design

We will have a database, where the schema has two columns: tinyURL (or just the generated ID), and longURL (i.e. the url to redirect to).

We can shard the database by the generated ID.

High-level design

we will have a api gateway and a load balancer to distribute the request to corresponding service: generationService, and redirectionService. generationService handles the put request; redirectionService handles the get request.

we will also need a unique ID generator for the for the ID.

A database storing the mapping.

Caching layer for the redirection service -> storing 'hot' tinyURL to reduce latency and DB read.

Request flows

say a user wants to create a tinyURL for a long URL. she sends a put request. The request first handle by an API gateway and forward the request to the load balancer. The request is then forwarded to the generation service where a unique ID is generated, then the mapping is store in the DB.

now the user enters the tinyURL to the browser, the browser sends a get request to the API gateway and forward to the load balancer, then to the redirection service. The redirection service checks if the tinyURL is in the cache, if it is, then the api gateway sends a 301 http response with the long URL. If the mapping is not found in the cache, the service then access the DB.

Detailed component design

let's deep dive into the unique ID generator.

First of all, what should the length of the ID be? Because we are storing 100M URL. Let's use base-62 to convert int -> string. We need 5 character.

we can use timestamp to create unique ID, and for each node we append a node ID to the timestamp so it ensures each ID is unique. Then we use base-62 encoding to transform the ID to string of 5 alphanumeric characters.

Trade offs/Tech choices

1. I think one tradeoff I want to mention is the database type. Here I would much prefer the NoSQL database type over a traditional SQL type DB. The reason is that we do not require any SQL queries. A simple key-value store is good to achieve what we need here. It is also extensible so that later on if we want to include TTL configuration we don't need to update SQL schemas.
2. consistency or availability?

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?