System requirements

Functional:

Users should be able to generate short URLs

Users should be able to be redirected to original URLs by visiting the short URLs

Non-Functional:

The system should scale to supprt 1million DAUs, with each DAU on average generating 5 urls/day and 10 accesses/url

Writes must result in unique short urls

The system should be highly available, prioritizing availability over consistency

Capacity estimation

Traffic:

The system should handle 1million DAU * 5URLS = 5million URL gens/day = 5*10^6/100k = 5*10^6/10*5 = 5*10 = 50requests/second

The system should handle 1millionDAU * 5URLS * 10accesses/URL = 50 million redirection requests/day = 500requests/second

Storage:

26+10=36 char options

36^n = 5mil*365*1000. Let's say 400 for simplicity, so 2000*mil*1000= 2000bil = 2Tril

we want n s.t. 36^n>= 2Tril possibilities

log(a^b) = b*log(a),

and log(a*b) = log(a)+log(b)

so...

log(36^n) = log(2*10^12)

n*log(36) = log(2)+log(10^12)

n*2*log(6) = log(2)+12

n = 12.something/(2*.something) = 6 ish? Let's say 7.

So let's say 7 chars*2Trillion = 14TB storage for the next 1,000 years worth of urls

+ another 30chars*2Trillion = 60TB

so 74TB total to store once. Let's say we want to replicate for high availability so if we add 2 replicas, roughly 210TB total.

Memory:

Using pareto principle, 80% of requests are made for 20% of data.

50mil redirection requests/ day * 30 chars for long url *0.2 = 1500mil = 1.5*0.2*10^3*10^6 ~= 0.4GB to cache redirect urls

API design

POST /v1/create

body: {

"url": string

}

httponly, same-site cookie with id (and session token of course)

GET /{short-url} -> 302 orig. url

Database design

Users Table:

DBid: smallint

UserId: int

Email: string

PasswordHash (e.g. argon2id, pbkdf2): string

Primary Key DBid, UserID

Links Table:

Short: string Primary Key

Long: string

DBid: smallint

UserID: int

High-level design

Client: users interact with server over https via UI

Server: horizontally scalable fleet of application servers

Cache: Redis LRU cache (using cach-aside strategy) for reading frequent link redirects

Database: SQL DB for persistent storage/ cache misses. Sharded via consistent hashing through DB lbs. Not shown in diagram, but coordination of LBs/ shards would be managed by Zookeeper.

Request flows

Request Redirect:

1. Client requests short url
2. App looks up long url in cache and returns redirect if cache hit, else
3. looks up long url in db and returns redirect (or 404 if not found)

Generate url:

1. Client passes session token and long url in header
2. App verifies auth token and forwards user ID (retrieved from auth token verification), truncated salted SHA of long url and user ID, and long url to DB to be written

Detailed component design

To handle collisions on short url generation we can use a stored procedure on the db, which increments by 1 (and wrap around if needed) until an untaken short url is found.

Trade offs/Tech choices

I chose single-leader replication as opposed to leaderless or multi-leader replication in order to guarantee to generated urls are unique and not overwritten on collision. Because reads are prioritized over writes, a B-Tree would be optimal over an LSM+SSTable implementation so SQL in general is a good choice here. I just chose postgres as the SQL DB out of personal preference but something else like MySQL should work just as well.

An in-memory KV store is perfect for our caching use case. Redis is a typical option here.

I chose hashing as opposed to base32 encoded autoincrementing IDs because the bottleneck of occasional probing should be less frequent than locking the sequence for ID generation when generating short URLs.

Failure scenarios/bottlenecks

An issue with the probing stored procedure mentioned earlier is that it's technically possible for probing to loop through possibilities for a very long time in a dense range of short urls. This is, from a probability perspective, very unlikely though.

Future improvements

If probing became a legitimate bottleneck, we could, instead of hashing, utilize Autoincrementing IDs and base 32 encode them for the short URLs.