System requirements

Functional:

1. System should be able to provide two APIs
   1. Takes a long URL and return the short URL
   2. Takes a short URL and redirects to it's respective long URL
   3. URL analytics is out of scope

Non-Functional:s

1. Availablity
2. Scalability
3. Fault tolerant

Capacity estimation

Let's consider the following requirements

1. Traffic volume: 100 million URLs per day
2. Character allowed in short URL: [A-Za-z0-9]
3. Shortened URLs cannot be updated or deleted

URLs per second: 100 * 1000000/10000 = 1000 URLs/sec (24 hr -> 86400 ~ 10K)

Write operations: 1000 URLs/sec

Read operations: 10 reads: 1 write -> 10,000 reads/sec

Storage:

1. short URL max length: 56 bytes (56 characters)
2. Long URL max length: 200 bytes (200 characters)
3. Life time of service: 10 years
4. Total records to store: 100 mill * 365 * 10 = 365 billion records
5. Storage required: 365 B * 256 bytes =~ 94 TB

API design

This service will primarily have two APIs

1. api/v1/short
   1. request type: POST
   2. request body: { url: long_url }
   3. response: { url: short_url }
2. api/v1/shorturl
   1. request type: GET
   2. response: 301 redirect with Long URL

301 response code means URL has been permanently moved to Long URL and browser will cache it, subsequent requests for the same URL will be redirected to Long URL by the browser itself.

302 response code means URL has been temporarily moved to Long URL and sebsequent requests will be sent to our service by browser. Since we're not tracking any analytics like click rates, we will stick to 301 response code.

Database design

Good choice for this usecase is NoSQL database. We're planning to use cassandra.

Two table will be created

1. short_urls
   1. short_url (index)
   2. long_url
   3. created_at
   4. updated_at
2. long_urls
   1. long_url(index)
   2. short_url

We will create a hash for each long url and store the details in the first table and add another record in long_urls. Second table is for duplicate URLs check.

For hash we're choosing base62 encoding of long_url and hash length of 7 is enough to create 62^7 ~ 3 Trillion URLs.

High-level design

When Client will make a request a loabalancer and it will get forwarded to one of the servers.

When client makes a request with long URL. Server will assign a key to the longurl and store it in the database. This key will be base62 encoded and return a short URL. The encoded URL will be stored in cache with some TTL asynchronously.

When client makes a request with short URL. Server will first check in cache and return long URL else it will fetch from DB, store it cache asynchronously and return the long URL.

Request flows

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

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?