BOOKS DEEP-READ · SYSTEM DESIGN INTERVIEW VOL 1 · CH 8
System Design Interview Vol 1 · Ch 8 · Alex Xu · 2020
When you paste a monstrously long link into a social app, what comes out the other side is usually a seven-or-eight-character stub. Chapter 8 of System Design Interview asks you to build that service from scratch: turn a long address into a short one, and send whoever clicks it back to the original. The problem statement is small enough to look like homework, but its skeleton is the clearest in the book — one lookup table, one number issuer, one cache layer. All three big pieces of a large system, in miniature.
Think of a coat check at a theater. You hand over a bulky coat (the long URL) and get back a small numbered tag (the short URL). The tag carries no information about the coat — it is a thin slip of cardboard. Everything depends on the ledger behind the counter that pairs each number with each coat. So the whole business comes down to two things: the rule for handing out numbers, and a ledger you can never afford to lose.
The difficulty is that three requirements have to hold at once. The tag must be short enough to copy by hand (about seven characters). Over ten years, hundreds of billions of tags must include no duplicate number, ever. And the several counters handing out tags should not have to consult each other — every round trip costs time.
There is also a property that is easy to miss: this business is write once, read many, in the extreme. A link is registered once and may be clicked tens of thousands of times. So the design weight naturally falls on the click side, not the creation side.
The first: take a fingerprint of the coat. Compute a characteristic value from the long URL and keep the first seven characters as the tag. Fast — but two different coats can fingerprint to the same value, and when that happens you tweak the input and recompute until it stops colliding.
The second: take a sequence number, then rewrite it. The counter hands out 1, 2, 3, and so on, and you rewrite that decimal number in a more compact notation that uses 62 symbols — 0-9, a-z, A-Z. (This is the same trick as writing a decimal number in hexadecimal: more symbols means fewer digits.) Seven positions over 62 symbols covers roughly three and a half trillion tags, which lasts centuries.
Since roughly ten thousand clicks follow every one registration, the counter does not need to open the ledger every time. Keep a copy of the most frequently requested number-to-coat pairs within arm's reach; almost everyone gets an answer on the spot, and only the obscure numbers require a trip to the ledger. That stack is the cache — and the fraction of requests it can answer is very nearly your server bill.
When you send someone on their way, you can say one of two things. Say "this address moved permanently" and the browser remembers it — next time the visitor flies straight there without passing through you, and you save machines. But you also never get to count that click. Say "go over there for now" and every click still comes through you, so you can record exactly who clicked what and when — at the cost of carrying all of that traffic yourself. Data or cheap servers: pick one.
And one honest cost: you have to keep that ledger alive forever — the day the service shuts down, every short link scattered across the internet dies at once.
A URL shortener is fundamentally a ledger you cannot lose: tags must be short and never repeat, reads vastly outnumber writes so the cache decides the cost, and saying "permanent" versus "temporary" on the redirect is a straight choice between cheaper servers and click data.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
The point of this problem is not "how do you make it short": it is the smallest complete instance of "one key-to-value table + one ID issuer + one cache layer". Put the numbers on the table — 100 million links a day, a 10:1 read-to-write ratio, 365 billion rows over ten years — and the code length, the need for a cache and the sharding plan all fall out of the arithmetic. Meanwhile the single status code you return, 301 or 302, decides whether you save servers or keep your click data.
tiny.url/2TX) that carries none of the original address's information. It is only a key into a lookup table.Location header, telling the browser "the real thing is over there, go fetch it yourself."301 / 302: two redirect status codes. 301 means moved permanently (the browser may cache the redirect); 302 means temporary (the browser asks you again every time).0-9 a-z A-Z. More symbols means fewer digits for the same value — the same idea as writing decimal in hexadecimal.This chapter belongs to Part II, "System Case Studies", and follows directly from Chapter 7 on distributed unique IDs — the IDs issued there are exactly the raw material this chapter encodes into short codes. It is also the best small problem for running the four-step framework end to end (clarify requirements, high-level design, deep dive, wrap up) before the larger problems in Chapters 11 and 12. In the real world it maps to link services like bit.ly and t.co, and to the internal go/ links companies run on their own networks.
The first move is turning the prompt into numbers, and that step is the real skeleton of the chapter. The book's assumptions: 100 million short URLs created per day, a read-to-write ratio of 10:1, at least 10 years of service, and about 100 bytes per record. From those:
1,160/s; read QPS ≈ 11,600/s.365 billion records.36.5 TB.Each number forces a constraint you cannot dodge. 365 billion sets the minimum addressable space for the short code (the next section shows 6 characters fall short and 7 fit). 11,600 reads per second, all primary-key point lookups, makes a cache layer mandatory. 36.5 TB means one machine will not hold it, so you shard.
Skip this step and you will guess "six characters ought to do" and hit exhaustion somewhere past the fifteen-billionth link, or point 11,600 QPS straight at the database and buy ten times the hardware for something a cache gives away. It looks like a hash-function question; it is a capacity-estimation question.
The service exposes exactly two endpoints: POST /api/v1/data/shorten (takes a long URL, returns a short one) and GET /api/v1/{shortUrl} (takes a short URL, returns a redirect). The write path runs 100 million times a day; the read path runs a billion. The two paths differ by an order of magnitude in frequency, and your design attention should differ by an order of magnitude too.
The code uses base62 — 0-9 a-z A-Z, 62 symbols. Why not base64? Because base64's + and / must be percent-escaped inside a URL, which makes the result longer and harder to copy by hand.
What remains is arithmetic. You need 365 billion distinct codes. 62⁶ ≈ 56.8 billion — not enough. 62⁷ ≈ 3.5 trillion — enough, with nearly ten times the headroom. So the code is 7 characters. That 7 is not a guess; it is read back off the ten-year capacity figure.
Route A: hash plus collision resolution. Run CRC32 / MD5 / SHA-1 over the long URL and keep the first 7 characters. The trouble is collisions: different long URLs can truncate to the same string. The book's fix is to append a predefined string to the long URL and rehash, looping until the code is free. That means every issued code costs a database lookup to confirm it is unused — which is precisely where a Bloom filter earns its keep, absorbing the overwhelming majority of lookups that were never going to find anything.
Route B: unique ID converted to base62. Ask the ID generator (Snowflake, from the previous chapter) for a globally unique ID and convert it to base62. Collisions cannot happen, so no lookup is needed and the write path is a single insert. The price: IDs increase monotonically, so the codes are enumerable, and their length grows with the ID rather than staying a tidy 7.
There is one more detail the book raises in its deep-dive flow, and interviewers love to press on it: if the same long URL is submitted twice, should you return the same code? Route A is idempotent for free (identical input, identical hash). Route B only gets there by maintaining an extra long URL → code reverse index, which costs storage and one more write per creation.
The read-side load profile could hardly be friendlier: primary-key point lookups, values that essentially never change, and heavily skewed access (a small number of links absorb most clicks). Because a mapping is immutable once written, you can set a very long expiry and simply evict cold entries by LRU — no cache-invalidation problem to speak of.
Do the arithmetic and the layer's value is obvious. At 11,600 read QPS, a 90% hit ratio leaves the database 1,160 QPS. Let the ratio slip to 50% and the database is suddenly carrying 5,800 QPS — same hardware, 40 points of hit ratio, five times the database load. The cost curve of a URL shortener is basically that hit-ratio curve.
301 or 302: one status code, two businessesThis is the choice most often dismissed as a detail, and it decides the business model. 301 tells the browser the move is permanent, so the browser caches the redirect — from the second click on, the request never reaches your server. Load drops sharply, and you lose every subsequent click. 302 says the redirect is temporary, so each click comes back to you and you capture the full click stream — timestamp, referrer, geography — while carrying every bit of that traffic.
Rate limiting. Leave the create endpoint unthrottled and a script will eat your code space and your storage within the hour; limiting per IP or per API key is the standard answer in this chapter's wrap-up. Stateless scaling. The web tier holds no session, so you add machines; the only genuinely stateful pieces are the ID generator and the database. Sharding. 36.5 TB does not fit on one machine, and hashing on the short code is enough — every read is a point lookup and nothing needs a range scan, which makes this among the easiest workloads to shard.
Table 1 · Two ways to issue a code: truncated hash vs unique ID in base62
| Hash + collision resolution | Unique ID → base62 | |
|---|---|---|
| Code length | Fixed at 7, uniform | Grows with the ID: short early, longer later |
| Write cost | A lookup per issue to confirm the code is free (a Bloom filter absorbs most) | No lookup; a single insert |
| Collisions | Must be handled: append a fixed string, rehash, repeat | Impossible — the ID is already unique |
| Guessability | Codes are scattered and not sequentially guessable | Monotonic IDs make codes enumerable; the next one is derivable |
| Idempotence | Free: one long URL always maps to one code | Needs an extra long URL → code reverse index |
| Dependencies | Only a hash function | A working distributed ID generator (Ch 7) |
Table 2 · 301 vs 302: one status code, two businesses
301 permanent | 302 temporary | |
|---|---|---|
| Browser behaviour | Caches the redirect; never asks you again | Comes back to your server on every click |
| Server load | Drops sharply, most of all on popular links | You absorb every click |
| Click analytics | Largely lost — only the first click is counted | Full click stream: time, referrer, geography |
| Changing the target | Hard — cached browsers may not come back for a long time | Change any time; effective on the next click |
| Fits | Internal go/ links, pure navigation, no analytics need | Commercial shorteners, marketing campaigns, abuse monitoring |
tiny.url/mycompany introduces namespace contention and squatting, and needs its own reservation and moderation path. The book's baseline design does not include that layer.The URL shortener is among the most frequently asked "small" interview problems, and what it tests is not small at all: the interviewer is watching whether you derive the design from the numbers, not whether you can recite base62. It is also one of the few problems that fits a complete four-step pass into 45 minutes and still has real trade-offs to dig into.
In production this skeleton is the core of link services such as bit.ly and t.co: one enormous mapping table, one high-hit-ratio cache, one ID issuer, and an analytics business built on the click stream. And the most underrated property is that a short link's entire value rests on the durability of that table — the code itself carries no information, so once the service stops, the link is just a meaningless string.
10% — collisions are not rare events but something you hit roughly once every ten issues. Collision handling is the main path, not an edge case.301 is hard to take back. Browsers may hold the cached redirect for a long time, so later changes of target, or a safety interstitial you want to add, will never reach those users.36.5 TB is bare records; the primary-key index, and the long URL → code reverse table route B needs, are both extra.1. A URL shortener is, at bottom, a code → long URL table. The code carries none of the original address, so the entire value rests on that table's durability.
2. Every design decision is derived from the estimate: 100M/day → 1,160 write QPS; 10:1 read ratio → 11,600 read QPS; 365 billion rows over ten years; 36.5 TB.
3. Seven characters is computed, not chosen: 62⁶ ≈ 56.8 billion is too small, 62⁷ ≈ 3.5 trillion fits. base62 rather than base64 because + and / must be escaped in URLs.
4. Two issuing routes: truncated hash with collision resolution (fixed length, idempotent for free, a lookup every time) vs unique ID in base62 (no collisions, no lookup, but enumerable and variable-length).
5. The read path is the ideal cache workload — point lookups, immutable values, skewed access; letting the hit ratio slide from 90% to 50% multiplies database load by five.
6. 301 vs 302 is the chapter's most overlooked business decision: cheaper servers or click data, pick one.
7. Three wrap-up items: rate limit the create endpoint, keep the web tier stateless so it scales by addition, and shard by code hash to hold 36.5 TB.
8. The biggest misconception is treating the code as a secret — by construction a shortener offers no confidentiality, and security must come from the destination's own authorization.