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:

• High availability
• Horizontal scalability
• Readability
• Low redirect 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

ID Generation

For solve generation ID servers downs we can present new service - coordination service like zookeeper or etcd. On start every generator server request unique worker_id from Zookeeper. If server is down and up again, it gives new worker_id.

Caching

Virus-links

We use two-level cache. On Edge level we adjust CDN with caching 302 redirects (Micro-caching with Cache-Control: max-age=10). On application level we use Redis for storing popular urls.

Cache misses

We are using cache-aside algo to solve Thundering Herd problem.

Cache invalidation

If business logic not uses long url changing after creation, an invalidation is not needed (urls are immutable). If modification is available, during updating DB, application must do a sync key DEL in the Redis.

Eviction policy

We setting up LRU (Least Recently Used) in Redis. We adjust base ttl to 24h.

Partitioning

For protecting DB partitions from data skew we are using Consistent Hashing with Virtual Nodes.

Rate Limiting

We use Token Bucket or Sliding Window Log algo on Redis.

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.