Back to System design
Design a URL Shortener (TinyURL / bit.ly)
mediumA URL shortener looks like a hash map with a web server in front, and interviewers use it precisely because that first impression is wrong. The storage is trivial. The interesting parts are key generation under concurrency, a read path two orders of magnitude hotter than the write path, and what "delete" means once a link is in someone's SMS history.
Scale10K writes/s sustained; 1M reads/s peak
Storage~500 B/URL × 100B = 50-200 TB lifetime
Key Concepts
1
Read and write are different systems. Assume 10M new links a day and 100 redirects per link over its
life. Writes: 10M / 86,400 = 116 per second, call it 350 at peak. Reads: 1B / 86,400 = 11,600 per
second, and a link that lands on a popular post will do that on its own. A 100:1 ratio means you can
spend real money on the read path and almost nothing on the write path. Say this before you draw
anything; it justifies caching, read replicas and edge placement in one move.
Read and write are different systems.116 per second11,600 per
second
2
Key generation is the actual question. Three approaches, and the interviewer wants to hear why you
rejected two of them.
Key generation is the actual question.
3
Hash the URL and truncate. Deterministic, so the same URL yields the same key — pleasant until two
different URLs collide, and at 7 base-62 characters you have 62^7 = 3.5 x 10^12 keys. Birthday maths says
collisions become likely around the square root of that, roughly 1.9M keys, which you pass in two months
at 10M a day. You need a collision check on every write, which is a read before every write.
4
Random key, check for existence. Same read-before-write, but no clustering, and the check gets cheaper
as you shard.
5
A counter, base-62 encoded. No collision check at all, because uniqueness is structural. The cost is
that keys are sequential and therefore enumerable — anyone can walk your entire corpus. Fix by encoding
the counter through a bijective transform, or by handing each server a block of IDs so ordering is only
local.
6
Sequential IDs leak more than you think. Two links created a minute apart sit next to each other in
key space. If one is a public marketing link and the next is an unlisted document, enumeration finds the
document. This is the security answer the question is really fishing for, and it comes up more often than
the sharding one.
Sequential IDs leak more than you think.
7
301 versus 302 is a product decision, not a technical one. A 301 is cached by the browser, so the
second click never reaches you — cheap, but your analytics go dark. A 302 costs a round trip every time
and keeps the click data. Shorteners that sell analytics use 302 and pay for it. Say which one you are
choosing and why; the trade-off is the answer.
301 versus 302 is a product decision, not a technical one.
8
Expiry is a lie you should not tell. Short links leak into screenshots, chat backups and printed
posters. Deleting the row breaks those forever, so real systems tombstone the key and serve an explanatory
page. Reusing an expired key for a new destination is the failure mode to name: the old audience lands on
the new target.
Expiry is a lie you should not tell.
9
What the interviewer is probing.
What the interviewer is probing.
10
1. "Design a URL shortener." Probing: do you separate read and write paths before designing? Stalls: one box, one table, one index. Moves up: the 100:1 ratio first, then a design shaped by it.
1. "Design a URL shortener."
11
2. "How do you generate the key?" Probing: whether you know why hashing needs a collision check. Stalls: "MD5 and take the first 7 characters." (Then: what about collisions? "Unlikely." It is not.) Moves up: naming all three options and picking one with its cost.
2. "How do you generate the key?"
12
3. "The keys are sequential. Any problem with that?" Probing: security instinct. Stalls: "It's fine, they're short." Moves up: enumeration exposes unlisted links; fix with a bijection or per-server blocks, not with obscurity.
3. "The keys are sequential. Any problem with that?"
13
4. "A link goes viral. What breaks?" Probing: cache behaviour under a hot key. Stalls: "Add more replicas." Moves up: one key on one shard is a hot key; the CDN or an in-process cache absorbs it, and the origin sees one request per TTL per edge.
4. "A link goes viral. What breaks?"
14
5. "301 or 302?" Probing: whether you connect a status code to the product. Stalls: "301, it's permanent." Moves up: 301 kills your analytics because the browser stops asking; 302 keeps the data and costs a round trip. Choose out loud.
5. "301 or 302?"
High-level design
Write path: client → API gateway → URL service → key generator → KV store → return short URL.
Read path: client → CDN/edge (cache check) → API gateway → URL service → KV store → 302 redirect.
Async: click events → Kafka → aggregator → analytics store.
Abuse: URL submission → safe browsing check → tag/block as needed.
Edge: CDN caches both the create response and the redirect.
Components
- API gateway with rate limiter (per IP, per API key).
- Key generator service (counter or hash).
- KV store (DynamoDB, Cassandra, or sharded Postgres) keyed by short alias.
- Edge cache (Cloudflare, Fastly) on the 302 redirect.
- Redis warm-tier cache for very hot links.
- Kafka + analytics pipeline (Spark / Flink → ClickHouse).
- Abuse / phishing filter (Safe Browsing API).
- Admin tools: revoke, expire, search.
Capacity, worked
Assumptions stated so you can substitute your own.
New links per day 10,000,000 Redirects per link over its life 100 Retention 5 years --------------------------------------------------------- Writes 10M / 86,400 = 116 per second Writes at 3x peak = 350 per second Reads 1B / 86,400 = 11,600 per second Reads at 3x peak = 35,000 per second
Row: key 7 B + URL ~200 B + owner, timestamps ~100 B
= ~310 bytes
Rows in 5 years 10M x 365 x 5 = 18,250,000,000
Raw storage 18.25B x 310 B = ~5.7 TB
With indexes and replication (x3) = ~17 TBKey space, 7 chars base-62 62^7 = 3.5 x 10^12 keys Used after 5 years = 0.5% of space
What the numbers decide:
- 35k reads/s is a cache problem, not a database problem. At a 95% hit
rate the database sees 1,750 reads/s, which one replica handles.
- 5.7 TB does not need exotic storage. It needs one sharded table.
- 0.5% key usage means 7 characters is right; 6 (56 billion) would be
tight, 8 wastes a character on every link ever printed.
Key generation compared
Three options and the cost of each.
Hash + truncate (MD5/SHA, take 7 chars)
Collision odds rise with sqrt(key space): ~1.9M keys before collisions
become likely. At 10M/day that is under two months.
Needs: read-before-write on every insert.
Gets you: the same short link for a repeated URL, which users like. Random 7 chars, check existence
Needs: read-before-write, same as above, but no clustering under load.
Gets you: unguessable keys. Counter, base-62 encoded
Needs: nothing per write. Uniqueness is structural.
Costs: keys are enumerable in creation order.
Fix: encode the counter through a bijection (e.g. multiply by a large
coprime modulo 62^7), or hand each writer a block of 10,000 IDs so the
global sequence is never visible. Distributed counters without a single point:
- Zookeeper/etcd hands out ranges: one round trip per 10,000 links.
- Per-server prefix (server 03 owns keys starting 03) removes
coordination entirely at the cost of one character.Failure modes in production
Hot key after a viral share
Symptom: one shard's CPU saturates while the rest idle.
Cause: traffic concentrates on a single key, and sharding spreads keys,
not requests to one key.
Fix: edge cache with a short TTL; the origin then sees one request per
edge per TTL rather than the full flood.
Cache stampede when that key expires
Symptom: latency spike exactly at TTL boundaries.
Cause: every edge misses simultaneously and asks the origin at once.
Fix: jittered TTLs, and serve-stale-while-revalidate. Expired key reissued to a new owner
Symptom: users following an old poster or screenshot reach a stranger's
destination.
Cause: keys returned to the free pool on expiry.
Fix: tombstone permanently. The key space is 3.5 x 10^12; you are not
short of keys. Open redirect abuse
Symptom: your domain appears in phishing filters.
Cause: anyone can point your trusted domain at anything.
Fix: scan destinations on write, re-scan asynchronously, and keep a
takedown path that responds in minutes rather than days.