A URL shortener takes a giant link and hands back a tiny one that bounces visitors to the original. It looks trivial — a lookup table with a redirect — but the interesting design lives in how you mint short keys, which redirect you choose, and how you serve a billion of them a day.
Pick any classic interview problem and this is the one everybody starts with — because it hides real depth behind a one-line spec: "make short links." The whole job is two operations, write a mapping and read it back, but the read side runs a hundred times harder than the write side, and that imbalance shapes every decision.
We'll size the thing first — how many links, how short can the key be, how much traffic. Then we'll mint the keys two different ways and weigh them. We'll choose a redirect (it matters more than it looks). We'll pick a store, put a cache in front of it, and finally handle the unglamorous lifecycle: expiry, custom aliases, analytics, and the abuse that any link service attracts.
Before any boxes-and-arrows, count. A service like this does almost nothing on the way in — store one row — and a great deal on the way out — look that row up every time someone clicks the short link. People create a link once and share it widely, so for every link written you get roughly a hundred reads. That write-to-read ratio of about 1:100 is the single most important number here: it tells us to optimize ruthlessly for the read path and not sweat the write path.
Put numbers on it. Say we mint 100 million new URLs per day. That's a write rate of 100M / 86,400s ≈ 1,160 writes/sec. At a 1:100 ratio, reads land near 116,000 reads/sec — and you size for peak, so call it a few hundred thousand QPS at the busy hour. Writes you can almost ignore; reads are the whole game.
Now the key length. If we keep this up for about ten years, that's 100M × 365 × 10 ≈ 3.65 × 10¹¹ URLs — roughly 365 billion. We encode each key in base62 (the characters a–z A–Z 0–9, the URL-safe alphabet). How many characters do we need? Each character carries one of 62 values, so n characters give 62ⁿ distinct keys:
So 7 base62 characters is the answer: 62⁷ ≈ 3.5 trillion combinations, ten times our worst-case demand, with headroom to spare. That one figure — seven characters — is the spine of the whole design, and it falls straight out of the sizing.
We need a short string nobody else is using. There are two honest ways to get one, and they trade off against each other.
Run the long URL through a hash function like MD5 or SHA-256. That gives a big fixed-length fingerprint; take the first 7 base62 characters and call it the key. The appeal: it's stateless (any server can compute it without coordination) and it deduplicates for free — the same URL always hashes to the same key, so you never store it twice.
The problem is the chopping. Once you throw away most of the hash, two different URLs can land on the same 7 characters. That's a collision, and you must handle it: when you go to store the key and find it already points to a different URL, either retry with the next slice of the hash, or append a few extra characters and try again. Collisions are rare at first and grow as the table fills (we'll watch that curve in a moment), so the retry logic has to be there even if it seldom fires.
Keep a single number that only ever goes up — a monotonic counter. Each new URL gets the next integer (1, 2, 3, …), and you encode that integer in base62 to get the key. ID 125 becomes "21", ID 3,521,614,606,207 becomes a 7-character string. Because every ID is unique by construction, the keys are unique by construction — no collisions, ever, no retry loop.
The catch is the opposite of A's: a plain counter is predictable (keys come out in order, so anyone can guess the next one and walk your whole catalog), and it does not dedupe — paste the same URL twice and you get two different keys. The predictability is fixable (scramble the integer before encoding, or hand out IDs in non-obvious blocks), but it's a real consideration.
The tradeoff in one line:
Most production designs lean toward the counter approach for its guaranteed uniqueness, then solve the coordination problem with the service in the next section.
The counter scheme is clean until two app servers ask for "the next ID" at the same millisecond and both get the same number. The fix is to make ID handout someone's job: a small dedicated service whose only purpose is to give out unique keys, one at a time, never twice. Call it the Key Generation Service, or KGS.
The neat trick is to do the work offline, ahead of time. When traffic is quiet, the KGS pre-computes a big batch of unique 7-character keys and parks them in a table marked unused. When an app server needs a key, it doesn't compute anything — it just asks the KGS to hand one over. The KGS moves that key from the unused table to the used table and returns it. Because keys were generated once, upfront, in a single place, they're guaranteed distinct; no request ever has to check for collisions on the hot path.
Two details make it safe under load:
When someone visits your short link, your server doesn't show them a page — it tells the browser "the thing you want is actually over there" and the browser goes there. That instruction is an HTTP redirect, and you get to pick between two flavors. The choice quietly decides whether you ever see the click.
So it's not "which is correct" — it's "what do you want." Optimizing for cost and speed on links that truly never change? 301. Running a product that lives on click data, expiry, and control? 302. Most commercial shorteners choose 302 precisely because the analytics and control are the business.
Two worries haunt the hash-then-truncate scheme: the chance that two URLs land on the same short key (a collision), and the day you've used every key (exhaustion). Both are just counting. Collisions follow the birthday paradox — in a space of N keys, you start seeing collisions once you've stored roughly √N of them, far sooner than intuition expects. Exhaustion is simpler: divide the total keyspace by how many you burn per day. Drag the sliders and watch both.
The data is almost embarrassingly simple. One record per short link:
There are no joins, no relationships, no transactions across rows. Every operation is "given this one key, fetch this one row" (or "store this one row"). That access pattern — a huge number of independent lookups by a single key — is exactly what a key-value / NoSQL store is built for. A relational database would work too, but you'd be paying for relational features (joins, multi-row transactions) you never use, and it's harder to spread across many machines.
The natural partition key is the short key itself. Hash it to decide which machine owns the row, and every read goes straight to the one shard that holds it — no fan-out, no coordination. Because keys come out roughly uniformly (especially from a hash or a scrambled counter), the data spreads evenly across shards with no natural hotspot. This is the sharding story from Chapter 1, made easy by a key that was random to begin with.
Reads outnumber writes 100 to 1, and reads are nearly all of your traffic — so the read path is where you win or lose. The good news from the last section: link records never change after they're created, so you can cache them aggressively. Put a fast in-memory store (Redis) in front of the database and run cache-aside: check the cache; on a hit return immediately; on a miss fall through to the database, stash the result, and return it.
The traffic is wildly skewed. A handful of links — a viral tweet, a campaign URL — get clicked millions of times, while the long tail barely moves. This hot-URL skew is a gift: cache the hot few and you absorb most of the traffic from a tiny slice of memory. When the cache fills, evict the least recently used (LRU) entries — the cold long-tail links nobody is clicking right now.
Do the hit-ratio math. If 90% of clicks hit the cache, only 10% reach the database — you've cut DB load tenfold. Push it to 99% and the DB sees 1 read in 100. At our peak of ~200,000 reads/sec, a 99% hit ratio means the database fields only ~2,000 reads/sec, which one modest replica handles easily. The cache isn't a nice-to-have here; it's what makes the numbers fit on affordable hardware.
For the truly ultra-hot links, go one level further out: serve the redirect from a CDN at the edge, near the user, so the click never even reaches your region. (CDN + cache-aside, both from Chapter 1, doing the heavy lifting again.)
The happy path is done; the unglamorous parts are what separate a toy from a product.
Links can carry a TTL (time-to-live) via that expiry column. When a request arrives for an expired link, you treat it as gone — return a 404 or a "link expired" page — rather than redirecting. A background cleanup job periodically sweeps expired rows out of the store and frees their keys to be reused, so storage doesn't grow forever with dead links. (A lazy variant: just leave them and let the on-read check do the work; sweep occasionally.)
Let users ask for a vanity key — shrt/launch instead of a random string. Now collisions return with teeth: two users both want launch. Treat the custom key as a unique-key insert; the first writer wins, the second gets "that alias is taken, pick another." Custom aliases live in the same table as generated keys, so a vanity request must also check it doesn't clash with an auto-generated one.
If you chose 302, every click flows through you, so you can record it — timestamp, referrer, rough geography, device. Don't do this on the hot path: emit a click event onto a queue and let workers aggregate it asynchronously, exactly the producer/consumer pattern from Chapter 1, so analytics never slows the redirect.
Short links are catnip for spammers and phishers — the short form hides the real destination. So you screen submitted URLs against malware/phishing blocklists at creation time, re-check on click, and refuse or warn on bad ones. And you cap how fast any one client can create or resolve links with a rate limiter — the token-bucket machinery from Chapter 5 — to stop a single abuser from minting millions of links or hammering your resolver.
Here's the whole design as a checklist:
The heart of the counter scheme is the encode/decode pair. Encoding peels digits off a number with repeated divmod 62, building the string from the bottom up; decoding folds the characters back into a number. Both are pure — no I/O, no shared state — which is exactly why any server can run them without coordination. Flip between the two languages; the shape is identical.