Design a URL Shortener
1. The problem
A service like tinyurl / bit.ly:
put in: https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long
get back: https://tinyurl.com/zn9edcu
click it: browser is REDIRECTED to the original long URLTwo functional requirements, that's all:
- Given a long URL → create a short one (shortening)
- Given a short URL → send the user to the long one (redirecting)
Book's scope answers: 100M new URLs/day; code as short as possible; allowed characters 0–9, a–z, A–Z (62 characters — remember this number); no delete/update (simplification).
2. Back-of-envelope (drives everything)
writes: 100M / 86,400 s ≈ 1,160 writes/sec
reads: assume 10:1 read:write ≈ 11,600 reads/sec ← READ-HEAVY
rows: 100M × 365 × 10 years = 365 billion
storage: 365B × ~100 bytes ≈ 36.5 TBCode length from the row count: an n-character code addresses 62^n
URLs, so 7 is ceil(log62(rows)) — not a convention. Smallest power of 62
that clears 365B:
62^6 = 56,800,235,584 0.16× need ✗
62^7 = 3,521,614,606,208 9.6× need ✓ → 7 charactersTwo conclusions to say out loud: (1) read-heavy → optimise the redirect path, put a cache on it; (2) 7-character codes.
3. High-level design
3.1 API (REST)
POST /api/v1/data/shorten body {longUrl} → {shortUrl}
GET /api/v1/{shortUrl} → 301 or 302 redirect to the long URL3.2 How a redirect works (mechanics)
The server does NOT send a page back. It sends an HTTP status code + a Location header (a response field holding a URL); the browser sees the status, reads Location, and automatically fires a second request there.
3.3 301 vs 302 — pick per BUSINESS GOAL, out loud
| Code | Meaning | Consequence | Use when |
|---|---|---|---|
| 301 | moved permanently | browser CACHES the hop → next click skips your server entirely | you want minimum server load |
| 302 | moved temporarily | every click comes to your server first | you want click ANALYTICS (a link business lives off this data) |
3.4 Data model
Don't hand-wave a giant in-memory hash table — 36.5 TB. A plain table:
urls( id, shortURL, longURL ) + url_hash (see §6)4. Deep dive: making the 7 characters (the chapter's core)
Two designs; recite both, recommend the second.
4.1 Option A — hash + collision resolution
Hash the long URL (CRC32 / MD5 / SHA-1), keep the first 7 characters.
- Problem: truncation → different URLs can produce the same 7 chars (collision)
- Fix: on collision, append a predefined string to the long URL and re-hash; repeat until unique
- Cost: every attempt = a DB query to check existence. A Bloom filter (in-memory "definitely not present / maybe present" structure — see KV notes) pre-answers most checks without touching the DB
- Genuine pro: deterministic — same long URL always → same code (dedup free); also a con when two users want distinct links to the same page
4.2 Option B — base62 conversion (recommended)
Don't derive the code from the URL at all. Give each URL a unique number (ch.7 Snowflake generator), then rewrite the number in base 62.
Base conversion = writing the same number with a different digit alphabet
(like decimal ↔ binary). Base 62's digits: 0–9 → '0'–'9',
10–35 → 'a'–'z', 36–61 → 'A'–'Z'.
Worked example — 11157 → base 62 (divide, keep remainders, read bottom-up):
11157 ÷ 62 = 179 r 59 → 'X'
179 ÷ 62 = 2 r 55 → 'T'
2 ÷ 62 = 0 r 2 → '2' read bottom-up → "2TX"Book's real-size example: ID 2009215674938 → zn9edcu.
Full write path:
longURL in → seen before? ── yes → return existing shortURL
│
no → unique ID (Snowflake) → base62(ID) → store row → returnCollisions are IMPOSSIBLE by construction: unique number → unique base62 string. The whole checking loop from Option A vanishes.
4.3 The comparison table (asked directly — memorise)
| Hash + collision resolution | Base 62 conversion |
|---|---|
| Fixed code length | Length grows with the ID |
| No ID generator needed | Needs a unique ID generator (ch.7) |
| Collisions possible → resolve loop | Collisions impossible |
| Next code not guessable | Next code predictable if IDs are dense → security concern |
On that last row (senior point): sequential/dense IDs are enumerable — a scraper walks code after code, and your ID stream leaks total volume to competitors (same leak as DB auto_increment in ch.7). Mitigations: Snowflake IDs are sparse (timestamp + machine bits leave huge gaps); the production fix is a keyed bijection (a reversible, key-dependent scramble of the ID — e.g. a Feistel network) applied before base62: uniqueness preserved, predictability destroyed.
5. "But IDs aren't incremental across servers!" (common confusion #1)
Correct — and they don't need to be. Base62 needs UNIQUE, not CONSECUTIVE.
- Gaps in the number line are harmless: nobody iterates IDs; each one exists only to become a code
- "Incremental" was a property of the REJECTED single-DB auto_increment
- Snowflake servers never talk to each other: different machine bits → collisions impossible even in the same millisecond
- What you get is k-sortable (roughly time-ordered) — which is all the DB wanted: inserts land near the END of the B-tree index (fast), not at random spots (slow). Perfect sequence buys nothing extra.
Honest wrinkle the book glosses over: a FULL 64-bit Snowflake is ~10^18, and base62 of that is up to 11 characters, not 7. The book's example (2×10^12) fits 7 because 62^7 ≈ 3.5×10^12. If strict 7 chars matters: tune the Snowflake bit budget (recent epoch, fewer timestamp bits) or use a range/segment allocator (each server leases a block like 5,000,000–5,999,999 from a central table it visits rarely). Naming this mismatch in the interview is a strong moment.
6. Two lookup directions, two indexes (common confusion #2)
The same table is queried in OPPOSITE directions:
| Direction | Query | Served by |
|---|---|---|
| Redirect (hot, 11,600 rps) | short → long | shortURL is the PRIMARY KEY → single key lookup; cache absorbs most |
| Dedup ("seen before?") | long → short | can't index a ~2 KB longURL column → store url_hash = MD5(longURL), index THAT (16 bytes), then confirm the candidate row by comparing the full string |
- Bloom filter in front of dedup answers "definitely never seen" with zero DB queries (most requests)
- Dedup is OPTIONAL SCOPE: many real shorteners skip it — two users shortening the same article WANT different codes for separate analytics. Dropping dedup deletes this whole query path. Say: "I'd confirm dedup is even a requirement."
- Sharding wrinkle: shard the DB by short code → redirect routes to exactly one shard, but a url_hash query doesn't know which shard → fan out to all, keep a separate small url_hash→code mapping, or drop dedup. The hot redirect path stays clean either way.
7. The read path at 11,600 reads/sec
client → load balancer → stateless web servers → CACHE (hot mappings)
└─ miss → DB → fill cache
unknown code in both? → 404 — never invent a redirect- Load balancer: spreads incoming requests across servers
- Stateless web tier: servers hold no per-user state → scale by adding boxes
- Cache: short→long mappings in RAM; read-heavy 10:1 means it absorbs most redirects; DB stays the source of truth
- Mentioning the 404 branch is a small correctness point interviewers notice
8. Wrap-up talking points (book's step 4)
- Rate limiter on POST /shorten — filter abusive IPs (= chapter 4)
- Web tier scaling — stateless → add/remove servers behind the LB
- DB scaling — replication for reads; shard 36.5 TB by short code using consistent hashing (= chapter 5)
- Analytics — clicks, timing, referrers; ties back to choosing 302. Senior add-on: emit click events ASYNCHRONOUSLY (stream → columnar store), never block the redirect on an analytics write
- Custom aliases (user-picked codes): a UNIQUE constraint on the code column is the authoritative race-condition guard; app-level retry is just an optimisation
- Availability / consistency / reliability as standing concerns
9. Interview script
1. clarify example flow, 100M/day, 62-char set, no delete/update
2. estimate 1,160 wps · 11,600 rps · 365B rows · 36.5 TB → 62^7 → 7 chars
3. API POST /shorten, GET /{code}
4. redirect Location-header hop; 301 (cheap) vs 302 (analytics) — business call
5. data model id | shortURL | longURL | url_hash
6. shortening hash+truncate (collisions, Bloom) vs base62(unique ID) → table
7. security dense codes enumerable → sparse IDs / keyed bijection ← unprompted
8. lookups two directions: PK for redirect, url_hash index for dedup;
offer to scope dedup OUT ← unprompted
9. read path LB → stateless tier → cache → DB; 404 on unknown
10. wrap-up rate limiter, scaling, async analytics10. The lines that earn the most
- "Reads are 10:1 — the redirect path is the product: cache it, keep analytics async, and let 301-vs-302 be a business decision, not a default."
- "base62 of a Snowflake ID makes collisions impossible by construction — the checking loop just disappears."
- "62^7 is 3.5 trillion against 365 billion needed → 7 characters with 10× headroom."
- "The ID never needed to be incremental — only unique; k-sortable is enough to keep the B-tree happy."
- "Dense sequential codes are enumerable and leak volume — I'd scramble the ID with a keyed bijection before encoding."
- "There are two lookup directions: primary key for redirects, an indexed hash of the long URL for dedup — and dedup itself is negotiable scope."
11. Numbers to remember
| Thing | Value |
|---|---|
| Traffic | 100M URLs/day → 1,160 wps, 11,600 rps (10:1) |
| 10-year rows / storage | 365 billion / ~36.5 TB |
| Character set | 62 = 10 digits + 26 lower + 26 upper |
| 62^6 / 62^7 | ~57 B / ~3.5 T → 7 chars |
| Book's example | ID 11157 → "2TX"; ID 2009215674938 → "zn9edcu" |
| Full 64-bit ID in base62 | up to 11 chars (the 7-char fine print) |
| Redirect codes | 301 permanent+cached, 302 temporary+analytics |
| url_hash | MD5 = 16 bytes indexed instead of ~2 KB string |
12. Common follow-ups
| Follow-up | Answer skeleton |
|---|---|
| Expiring links | add expires_at; lazy-delete on read + background sweep |
| Custom aliases | UNIQUE constraint = the race guard; check-then-insert alone is racy |
| Hot link (viral tweet) | it's one cache key — CDN / cache handles it; no DB impact |
| Abuse (spam/phishing) | rate limiter on shorten; blocklist check; status column (active/banned) |
| Analytics at scale | async events to a stream; never on the redirect path |
| Delete/update support | soft-delete via status flag (book scoped it out; say how you'd add it) |
| DB choice | any KV/wide-column fits: the access pattern IS key→value (ch.6!) |
13. When NOT to go deep
If the shortener is a sub-component of a bigger design ("design Twitter" — t.co links), one sentence:
"Links go through a shortener: base62 of a Snowflake ID, cache-fronted lookups, 302s so we keep the click analytics."
Go deep only when the shortener IS the question.
14. Glossary (A–Z, one line each)
| Term | Meaning |
|---|---|
| 301 / 302 | HTTP redirect codes: permanent (browser caches the hop) / temporary (every click hits the server) |
| 404 | HTTP "not found" — the correct answer for an unknown short code |
| base conversion | rewriting the same number with a different digit alphabet (decimal ↔ binary ↔ base62) |
| base62 | digit alphabet of 62 chars: 0–9, a–z, A–Z; 62^7 ≈ 3.5 trillion codes at 7 chars |
| Bloom filter | in-memory structure answering "definitely not present / maybe present"; never a false "no" |
| cache | RAM copy of hot short→long mappings so most redirects skip the DB |
| collision | two inputs producing the same short code (only possible in the hash+truncate design) |
| CRC32 / MD5 / SHA-1 | common hash functions; here used for code candidates (A) or url_hash (dedup) |
| dedup | returning the existing code when the same long URL is shortened again — optional scope |
| enumerable codes | codes a scraper can walk by counting — the danger of dense sequential IDs |
| Feistel network | classic construction for a keyed, reversible scramble of a fixed-width number |
| k-sortable | roughly ordered by creation time (see ID-generator notes) |
| keyed bijection | 1:1 reversible mapping parameterised by a secret key — kills predictability, keeps uniqueness |
| Location header | HTTP response field carrying the URL the browser should go to next |
| load balancer | front component spreading requests across web servers |
| primary key | the indexed column a table is organised around — here the short code; fastest possible lookup |
| range/segment allocator | servers lease blocks of IDs from a central table — alternative ID source for small codes |
| rate limiter | caps requests per client (per IP etc.) — guards POST /shorten (ch.4) |
| read-heavy | reads ≫ writes (10:1 here) → design and cache the read path first |
| redirect | status code + Location header; the browser automatically re-requests |
| secondary index | extra index on a non-key column — here on url_hash for the dedup direction |
| sharding | splitting the table across machines — by short code, via consistent hashing (ch.5) |
| Snowflake ID | 64-bit time+machine+sequence unique number (ch.7) — the input to base62 |
| stateless web tier | servers keep no per-user state → any server can handle any request → trivial horizontal scaling |
| UNIQUE constraint | DB-enforced uniqueness on a column — the authoritative guard for custom-alias races |
| url_hash | indexed MD5 of the long URL: find dedup candidates via 16 bytes instead of a 2 KB string |