How to design a URL shortener

A URL shortener is a read-mostly key-value store, and two numbers drive the whole design: lifetime link volume fixes the code length, and the 10:1 read:write ratio makes the cache the architecture.

Numbers and terms

• Load: 100 M new links/day (~1,000 QPS write, ~3,000 peak); 1 B clicks/day (~10,000 QPS read, ~30,000 peak). Round a day to 100,000 s.
• Keyspace: distinct codes a format can express (62^L). Collision: same code handed to two URLs. Density: fraction of keyspace used; sparse = expensive to guess.
• Three product pulls: short (costs keyspace), unguessable (costs characters/density), permanent (codes never reused, scheme never rewritten).
• Load-bearing assumptions (getting them wrong = a rewrite): 10:1 read:write, Zipf skew, p99 < 50 ms, links durable but clicks droppable, 365 B lifetime volume.

Code length: base 62

• 10-year demand = 100 M × 365 × 10 = 365 billion codes.
• Base 62 = 0-9 A-Z a-z. L chars hold 62^L.

• Answer: 7 chars. Headroom is spent later on allocator waste and guessing sparseness.
• Base 64: / and + break URL paths; still 7 chars. Base 58: drops misread glyphs, still 7. Base 36: case-insensitive, needs 8.

Codes: permuted counter, not hash

• Hash-and-truncate: stateless, free dedupe, but collides by birthday bound (~sqrt(M) draws). At 62^7, first collision ~32 min after launch; ~5.2% of writes collide; needs an 8th char to be honest.
• Dense counter: zero collisions, full keyspace, but ordered — enumerable, leaks daily volume and link age.
• Fix: encrypt the counter with a keyed Feistel network (bijection, so cannot collide) over 42 bits, cycle-walk overshoots back into 62^7 (~1.25 encryptions/code). Keeps zero-collision guarantee, destroys order, and is invertible so GET /{key} decrypts straight to the primary key (no index).
• Enumeration cost rises from 1 req/hit to ~9.6. Still obscurity, not security. Cipher key can never rotate; custom aliases still need a lookup table.
• Reject Snowflake ID: 22 bits on node+sequence makes it sparse → 11-char code.

(left, right) -> (right, left XOR f(right))   x4 rounds

Storage and API

• ~200 B/link (131 B payload + 68 B engine overhead): 20 GB/day → 73 TB in 10 yr, 219 TB at RF 3, ~8–20 boxes. Not the constraint.
• Click log grows 2.5× faster (50 GB/day) → queue it, roll up to per-link/per-hour counters, keep raw 30 days, then columnar cold storage.
• Key-value point-lookup workload: hash-partition on short_key via consistent hashing (modulo remaps ~94% on resize; ring moves ~6%). Weak consistency: high W, R=1 (a link never changes, so copies only disagree on existence).
• API: POST /v1/urls (201, 409 alias taken, 422 bad/unsafe); GET /{key} (302, 410 deleted/expired, 404 never issued). Use 410 not 404 for dead links. Use an idempotency_key, not global dedupe by URL (two users want two counters).
• No click_count column on the row — it makes a viral link a hot key on one shard, and adding shards cannot help.

Cache: the non-linear payoff

• Immutable values, deletion is the only invalidation (short TTL + explicit purge). Write-through on create to make read-your-writes free.
• Zipf rule of thumb (K = 100 M): h = log10(m) / 8. Every 10× memory buys 1/8 hit rate.

• 10 GB cuts DB from 3,750 → 376 QPS: hit rate rises with the log of memory, DB load falls as the reciprocal of the miss rate. Depends entirely on Zipf — uniform popularity gives only 2×. Provision on the pessimistic ~2,000 QPS.
• Extensions: push the 1 M-entry (200 MB) copy to every edge PoP (biggest latency win); keep a small in-process LRU to absorb hot keys (a hot key is never least-recently-used).

Gotchas

• 302, not 301. 301 is cacheable → hides exactly the repeat clicks (uncorrectable undercount) and cannot be revoked (breaks takedown). Use Cache-Control: no-store.
• Safety is a read-time control. A clean link can turn malicious later. Redirect path checks an in-memory bloom filter blocklist (~12 MB/process for 10 M domains at 1% false positive) — never a network call per redirect.
• SSRF trap: the scan fetcher must refuse private/link-local addresses (e.g. 169.254.169.254) or it leaks cloud credentials. Reject non-http(s) schemes (stored XSS) and self-referential links.
• Rate-limit GET by IP and creation per account (makes bulk phishing uneconomic — a correctness control, not cost).
• Allocator is a ticket server handing out blocks; block size 10,000 → ~5.6 min peak runway if it dies, burns only headroom to ~9.19×. Persist a high-water mark so a restore-from-backup never reissues codes.
• Purge must fan out to edge + in-process caches, not just the DB.