System requirements

Functional:

• Create a short url from a long url
  • Optionally support custom short url
  • Optionally support expiration time
• Be redirected from the short url to the long URL

Non-Functional:

• Low Latency on redirects (< 100ms)
• Scale to support 100M DAU and 1T urls over all time
• Ensure uniqueness of short urls
• High availability, eventual consistency

Capacity estimation

Traffic:

(100*10^6 DAU/10^5 seconds per day) * 5 redirects/DAU * 10 for peak traffic = 5*10^4 = 50k redirects/sec (i.e. we'll want to horizontally scale server). ~10k generation requests assuming 1 gen per DAU

Memory:

Using 80/20 caching rule (Pareto principle), roughly 80% of requests should be for 20% of redirects.

100MDAU * 5 redirects/DAU * 0.2 = 5*10^8 * 2/10 = 10*10^7 = 100GB (i.e. we'll probably want to shard cache)

Storage:

1T URLS * (8byte short url + 100byte long url + 8 byte optional expiration + 4byte user ID) ~= 10^12*120 = 120TB (i.e. we'll want to shard DB)

API design

// create a short url from a long url

POST /api/v1/create -> short url

Req Body: {

long url

alias?

expiration?

}

Req Header:

Cookie: session=token

// be redirected from the short url to the long url

GET /{short url} -> 302 long url

Database design

URLs table:

• short url/custom alias (Primary Key)
• long url
• expiration time
• User ID

Users table:

• User ID
• ... additional user data (not relevant to this system design)

High-level design

Server:

application logic for generating short urls and returning redirects. Based on 50k requests/second capacity estimation, would need roughly 50 servers during peak hours (assuming ~1,000 requests/second). Servers would be behind a load balancer.

Database:

• Because we want to guarantee url uniqueness, this pretty much rules out multi-leader & leaderless replication, which leaves single-leader replication
• As reads are more frequent than writes, B-Trees are preferable over LSM tree + SStable db engines
• As such, Postgres is a good choice here. The db should be sharded to handle the storage volume. It may also be a good idea to include read replicas for each shard, but may also be overkill given that traffic should already be havily offloaded by the cache, and the remaining traffic should be relatively evenly distributed by the shards (50k req/s * 0.2)/(120TB/5TB) = 10k req/s / 24 shards = roughly 400 reqests/second/shard, which should be manageable even without read replicas.

Cache:

Although 100GB could be vertically scaled into a single cache instance, that's a high amount of memory for a single machine and if it were to fail it would have a much more significant impact than if just one smaller instance within a sharded cache were to fail. For these reasons, a Redis cluster partitioned by short url is a good strategy. Redis will be used as a LRU cache and written to using the cache-aside strategy.

Not shown in diagram for simplicity:

Server, Database and Cache are all behind LBs to distribute traffic. Server LB is just a typical Application LB; could use round robin, or something more involved like least connection if desired. Database and cache both use consistent hashing; partitions are managed by Zookeeper.

Request flows

Redirects:

1. Client calls /{short url}
2. Server checks cache for corresponding long url
3. If cache miss, server checks db
4. Return 302 with long url (or 404 if not found)

Create short url:

1. Client calls /api/v1/create
2. Server generates short url (or optionally validates custom short url instead).
3. Server stores short url, long url, user ID, and optional expiration in db row.
4. If short url validation fails, or custom url is not unique return error to client

Detailed component design

Ensuring uniqueness of short URLs:

Assuming 10k req/s/ 24 shards = roughly 400 req/s/shard at peak, a counter appended to a shard ID is a completely viable option for generating unique URLs without any repercussions from locking. That said, there are additional downsides to using a counter in that it is guessable (even if we encode with a hashid/sqid), and we probably want to avoid issues with link enumeration. For this reason, I'm going to choose a randomly generated ID. This has the downside of the randomly generated value not guaranteeing to be unique, but a stored procedure on the db can be used to probe for a random value after the fact in the event of a collision. The stored procedure will only probe within the range of valid values as defined by its partition range. The search space (36 lower + 36 upper + 10 numeric)^8 will be sufficiently large such that probing should rarely be necessary and therefore not become a bottleneck. In the event the user is using an alias, probing will not be called, it will just attempt an insert and return an error if the short url already exists.

Optionally supporting expirations:

Logically, reads only need to check if expiration time is < now, in which case the record is ignored. In the background, a simple cron job service can run on each db shard to delete these expired records on an hourly basis. Additionally, redis supports TTL, so this can be managed automatically on the Redis side if an expirable short url is cached.

Trade offs/Tech choices

This is already discussed at length in the sections above.

Failure scenarios/bottlenecks

This is already discussed at length in the sections above.

Future improvements

This is already discussed at length in the sections above.