Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Redirections
• Custom short links
• Deletion
• Expiration time

Non-Functional Requirements:

• Availability
• Scalability
• Readability
• Latency
• Upredictability

Capacity Estimation

Assuptions:

• 100M new URL shortening links per month
• Read/Write ratio 100:1
• 1 DB entry - 500B
• Max expiry time is 5 years

Storage:

5 * 12 * 100M * 500B = 6000M * 500B = 3TB

QPS:

• Read = 100M * 100 / (30 * 86 400) = 100M/3000 000 = 3,8K URL's/ s
• Write = Read / 100 = 38 URL's / s

Network:

• Read = 3,8K * 500 * 8 = 15 Mb/s
• Write = Read / 100 = 150 Kb/s

Cache:

• 80 / 20 rule
• 3,8K * 86 400 * 500B * 20 % = 33 GB

API Design

• POST /{shortened_url}

header JWT | session token

body

{

original_url,

custom_alias,

expiration_date

}

• GET/{shortened_url}

header JWT | session token

301 redirect

302 redirect

• DELETE/{shortened_url}

High-Level Design

I have 2 scenarios:

1. We don't have such link - create scenatio
2. We already have saved URL

For the first case:

The Client sends request to Load Balancer(LB) and LB routes it to one of Application server nodes(AS). AS tries to find it in cache or DB and if it can't do it then call Short URL Generator service, which returns a valid short URL to AS and AS saves mapping of Short-Long URLs to DB and return it to the client.

For the second case:

If AS doesn't find short URL in cache but find it in DB then AS saves url mapping record to the cache.

Database Design

For Storage I would select a NoSQL DB with Key-Value storage like DynamoDB, MongoDB, or Cassandra because it is better in horizontal scaling.

For Cache I would select Redis

Entity:

ShortURL -> (LongURL, UserId(Optional), Expiry)

Detailed Component Design

Short URL Generator principle:

Distributed Unique ID Genarator + Base 64

Generate Unique ID: 64 bits: 2^64-1. We can use SnowFlake algorithm by Twitter: 2^63-1.

And after that, apply Base64: 0-9,A-Z,a-z,+,/. Output example: Aa87BzE

Non Functional requirements

Availability

If one of App servers is down then it is not a problem because we have additional App server nodes.

The same thing as with DB, because we will use multiple DB servers with partitions with replication as well.

Scalability

We can just add more servers as well for scaling purposes how for

Applications so for DB's and Cache's.

Readability

We transform our ID's to base 64 system, it is a human readable industry standard.

Latency

We have Cahe for Read heavy loading and NoSQL give us milliseconds guaranties in read operations.

Upredictability

It is hard to predict ID's based on our algorithm.