High level functions:
Assumption: 100M DAU
Read/Write ratio: 100: 1
Writes per day: 1M per day
QPS:
Storage:
assumptions: max Url size - 200
16 bit string - 2 bytes
400 bytes per url * 1M writes per day = 400 MB per day * 365 = ~150 GB per year
750 GB for 5 years, we can assume 1 TB in the worse case
GET /urls/{encoded_url}
returns original url if exists otherwise 404
POST /urls
body:
Returns 201 Created on success, 400 if request not valid (empty url, not valid url, exceeds max size etc)
Path: client request -> API Gateway (authentication, request deduplication, load balancing) -> URL Service (replicated) -> cache -> DB (if cache miss)
URL generation: autoincrementing global counter
Data storage: a durable key-value store mapping short code → long URL. Written once at create time, read only on cache miss.
We can use a simple columnar DB like Cassandra with original url and encoded url. For cache layer we can use encoded url as a key and original url as value.
For the DB we can partition by url short coded. Short code would be the primary key.
Write path: QUORUM write before returning the code, so creation is durable. Redirect path: read at ONE from any replica — a few ms of lag only risks a transient 404.
ID generator:
We decided to go with a simple autoincremental counter, which might a bottleneck and a potentially insecure solution. It is very easy to guess the previous/next urls and people might not want other people see their urls even if they are globally accessible. A better solution could include some kind of transformation, for example using hashing with salting + some randomness to generate the encoded url. We can always check in DB if given key exists. We can use write-if-absend on database to ensure we only add unique short codes. If the write fails we can regenerate the short code on the service's side.
Hot spots in cache: