Design a URL shortener
One byte in, a redirect out — but the redirect happens a hundred times for every byte you write. The whole design falls out of that asymmetry: this is a read system pretending to be a write system.
0. Interview hinge
The hinge is the moment the prompt stops being generic and the architecture becomes forced. Here it is the read/write ratio. A naive candidate spends the interview on code generation — base62, Snowflake IDs, collision handling. A strong candidate spends thirty seconds on that, then says: "writes are 3 req/s; reads are 10,000 req/s; so the design lives or dies on cache hit rate, and I'm going to spend my time there." Everything that follows derives the cache, then derives the keyspace, then protects the hot path.
1. Clarify the contract
Treat the prompt as a product contract before a box diagram. The system must:
- Shorten — accept a long URL, return a short code (optionally a custom alias, optionally a TTL).
- Redirect — resolve a code to its long URL with the lowest possible latency, returning an HTTP redirect.
- Count — record click analytics without ever slowing the redirect.
- Defend — refuse to send users to malware/phishing destinations, and support takedown of a bad link.
And — just as important for scoping — what it need not do: it is not a general key-value store, it does not need transactions across multiple links, it does not need strong read-after-write consistency on analytics (a click counter that is eventually correct is fine), and it does not need to be writable at scale. Naming the non-goals is what frees you to cache aggressively.
2. Put numbers on the shape
Back-of-envelope, with explicit arithmetic — these numbers drive the design, they aren't decoration.
Write rate & storage. 100M new URLs/year. That is 100\,000\,000 / (365 \cdot 86400) \approx 3.2 writes/s — trivially small. At ~500 bytes/row (long URL + metadata), one year is 100\text{M} \cdot 500\text{B} = 50 GB; a decade is ~0.5 TB. The database of record is small enough to fit on one beefy node and easily on a modest shard set. Writes are not the problem.
Read rate. At 100:1, the redirect path runs at ~320 req/s steady-state — but shorteners are bursty (a link in a TV ad, a viral tweet), so size for a peak of 10,000 redirect QPS. This is the load that costs money.
The keyspace — why 7 characters is derived, not chosen. Base62 (a–z, A–Z, 0–9) gives 62 symbols per position. A 7-character code yields 62^7 \approx 3.5 \times 10^{12} — 3.5 trillion codes. At 100M URLs/year you exhaust it in 3.5\times10^{12} / 10^{8} = 35{,}000 years. Six chars (62^6 \approx 56.8\text{B}) lasts ~568 years — also fine, but a random-code scheme needs sparsity to keep collision probability low, and the extra character buys three orders of magnitude of headroom for one byte on the wire. So 7 is the smallest length that is comfortably future-proof under random allocation — a derived choice, not a round number.
Cache hit rate is the only knob that matters
Here is the load-bearing calculation. At 10,000 redirect QPS, the QPS that reaches the database of record is \text{origin QPS} = \text{read QPS} \cdot (1 - h) where h is the cache hit rate. The hit rate is not a detail — it is a multiplier on your entire backend bill:
| Cache hit rate h | Origin QPS = 10k·(1−h) | What that means for the DB |
|---|---|---|
| 0% (no cache) | 10,000 | Needs a sharded, replicated KV fleet just to serve reads. |
| 90% | 1,000 | One primary + a couple of read replicas handles it. |
| 95% | 500 | Comfortable on a single replicated KV store. |
| 99% | 100 | The DB is nearly idle; it exists mostly for durability and cold misses. |
| 99.9% | 10 | Origin is a rounding error; spend your money on cache, not DB. |
Read that table as a design directive: going from 90% to 99% cuts origin load 10×. Because click traffic is heavily Zipfian — a tiny fraction of links carry most clicks — a modest LRU cache of the hottest codes gets you well past 95% almost for free. This is why the shortener is a cache problem. We defer the mechanics of cache eviction, write-through vs. write-around, and TTL choice to lesson 06; here the point is only that hit rate is the dominant cost variable, and the cache hierarchy (browser → CDN/edge → app-tier cache → DB) is the architecture.
3. Define the surface area
Keep the API small and expressive of the product, not the internals. The redirect endpoint is the entire product to 99% of traffic; the rest is administrative.
| API / operation | Why it exists |
|---|---|
POST /links {long_url, alias?, ttl?} | Create a code. Low QPS, can afford a synchronous abuse pre-check and a DB write. Returns the short code. |
GET /{code} → 301/302 | The hot path. Resolve code → long_url and redirect. Must be cache-served and must never block on analytics. (See lesson 03 for why the redirect verb itself is part of the contract.) |
GET /links/{code}/stats | Read aggregated click analytics. Served from the analytics store, never the hot redirect store. |
DELETE /links/{code} / takedown | Flip the link to disabled/blocked. The hard part is cache + browser invalidation, not the DB write. |
4. Model the data
The data model is the first architecture. The redirect store is a textbook point-lookup index: one key (the code), one value (the long URL + a few flags), accessed by exact-match only — never a range scan, never a join. That is DDIA Ch. 3's canonical case for a hash-keyed store: you don't need a B-tree's ordered structure, you need O(1) get-by-key, which is exactly what a KV store (or a hash index) gives you. The flags travel with the row so the hot path needs a single lookup, not a fan-out:
Analytics is a separate store with a different shape: an append-only event stream (code, ts, ip-hash, referrer, ua) feeding an aggregation, never co-located with the redirect KV. Mixing them is the classic mistake — it couples a 10k-QPS latency-critical read path to a high-volume write path. We'll see why that boundary is sacred in the analytics dive.
5. Linearized design
Walk a request and an event through the system in the order they actually move. The hot read path and the async analytics tee are two different stories sharing one entry point.
- 1. Create: validate & canonicalize the long URL, run a synchronous abuse pre-check (cheap blocklist + reputation), allocate a code, write the row to the KV store of record. Low QPS, so this can be careful and slow.
- 2. Redirect (the hot path): request hits the edge. If the code is in the edge/app cache → emit the redirect immediately, no origin touch.
- 3. On a cache miss, read the row from the KV store, check
status, populate the cache, then redirect. This is the only step that costs origin resources, and only (1-h) of traffic reaches it. - 4. Tee the analytics: as the redirect is sent, fire a click event to a queue/log — fire-and-forget, off the critical path. The redirect does not wait for it.
- 5. An offline consumer aggregates events into per-code counts for
/stats. Lag of seconds-to-minutes is fine. - 6. Abuse scanning runs out of band, writing only a compact
statusflag the hot path reads inline — no extra lookup.
The first bottleneck this exposes is not the database — it's the cache miss path under correlated load. A single cold code that suddenly goes viral sends its entire miss traffic to the origin at once. That's the senior question, handled in the next section.
6. Deep dives
Deep dive 1 — 301 vs 302: you are trading control for cost
This looks like an HTTP trivia question; it is actually the central trade-off of the whole system, and it ties straight back to the caching warning above.
A 301 Moved Permanently tells the browser (and every cache in between) "this mapping never changes — remember it." The browser caches it, often indefinitely, and on the next click does not contact your service at all. That is wonderful for cost: a viral link that's been clicked once per device is served entirely from browser cache, dropping your origin QPS toward zero. It is the cheapest possible redirect.
The catastrophe arrives at takedown. Suppose a link turns out to point at malware and you flip its status to blocked. With a 301, every browser that already cached it keeps redirecting to the malware — you have no way to reach those caches; the redirect lives in the user's machine, not yours. You also see almost no clicks for that link, so your analytics under-count by exactly the most-cached (most popular) links — the ones you most want to measure. You have optimized yourself out of both control and visibility.
A 302 Found says "temporary — ask me again next time." The browser does not durably cache it, so every click returns to your service. Now a takedown is instant (the next click reads the flipped status), and analytics are complete. The cost is real origin traffic: 302 trades the 301's free browser-cache hits for the ability to change your mind and to count every click. Most production shorteners choose 302 precisely because takedown and analytics are core product requirements, and they recover the lost cost at the edge/CDN cache (which they can invalidate) rather than the browser (which they can't). The decision rule: 301 when destinations are immutable and you don't need per-click data; 302 whenever you need takedown control or accurate analytics.
Deep dive 2 — sequential vs random codes: compactness vs. enumeration
Sequential codes come from a monotonic counter (or an ID-allocator block; see C04) base62-encoded. They are maximally compact (you use the keyspace densely, so codes stay short longest), uniqueness is free (the counter never repeats), and they are cache-friendly because consecutive codes cluster. The fatal cost is that they leak your volume and let anyone enumerate every link: if POST returns aZ3kP8 and a minute later aZ3kP9, a competitor reads your growth rate off the codes, and a scraper walks ...P0, P1, P2... to harvest every destination — a privacy and abuse disaster for a public service.
Random codes draw 7 base62 characters at random. They are enumeration-resistant (the space is 3.5T-wide and sparse, so guessing is hopeless) and leak nothing about volume. The cost is collision handling: two random draws can collide, so the write path must "generate, attempt insert-if-absent, retry on conflict." With 62^7 = 3.5\text{T} slots and 100M used, occupancy is 10^8 / (3.5\times10^{12}) \approx 3\times10^{-5}, so a collision is a 0.003\% event — one cheap retry on the low-QPS write path, never on the hot read path. That tiny insert-if-absent cost is the entire price of enumeration resistance, which is why a public shortener almost always picks random. Sequential is right only for internal/low-abuse systems where compactness and cache locality matter more than secrecy.
Deep dive 3 — the analytics boundary is an async event stream
Analytics must never sit synchronously in the redirect path: a redirect that blocks on an analytics write inherits the analytics store's latency and failure modes, and a 10k-QPS read path cannot afford either. The correct shape is DDIA Ch. 11's stream processing: the redirect tees a click event to a durable log (Kafka/Kinesis) and returns immediately; a separate consumer aggregates the stream into per-code, per-day counts at its own pace. This decouples the two completely — the analytics pipeline can lag, batch, sample, or even fall over, and redirects keep flowing at full speed. It also matches the read-pattern: /stats is a low-QPS dashboard read that tolerates seconds of lag, so there's no reason to pay for synchronous counting. The boundary is sacred: the redirect's only job is to redirect; counting is somebody else's problem, downstream, asynchronously.
7. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Random vs sequential code | enumeration resistance, no volume leak | collision handling (cheap insert-if-absent) | public-facing service (the default) |
| 302 vs 301 | instant takedown, complete analytics | real origin/edge traffic per click | you need control or per-click data (usually) |
| Cache hot links vs cache everything | 95%+ hit rate for tiny memory | cold codes still miss to origin | Zipfian click traffic (always) |
| Async vs synchronous abuse scan | fast creation path | brief window before a bad link is flagged | most cases; sync only for high-risk public submissions |
The sharpest of these is 302-over-301. It looks like you're choosing the "worse" redirect — you're deliberately giving up free browser caching and accepting real traffic on every click. But the read/write asymmetry already told you the system is a cache problem, and you'd rather solve that at a cache layer you control (the edge/CDN, which you can invalidate on takedown) than one you don't (the user's browser). 302 keeps the control and the data; you buy back the cost at the edge. Choosing 301 to "save load" is the trap — it saves load by surrendering the two things the product actually needs.
8. Failure modes
| Failure | Mitigation |
|---|---|
| Viral link not in cache (thundering herd) | Request coalescing / single-flight at the edge: one origin fetch serves the whole herd (see the senior Q below). Pre-warm known campaigns. |
| Database of record outage | Serve cached redirects with a stale-while-revalidate policy; fail closed for uncached codes (better a 503 than redirecting to an un-vetted destination). |
| Custom alias squatting / collision | Reserve system namespaces, enforce ownership, insert-if-absent so two creators can't claim the same alias. |
| Analytics pipeline overload | Sample or shed click events before they touch the redirect path — the tee is fire-and-forget by design, so dropping events degrades stats, never redirects. |
| Stale 301 after takedown | You can't recall browser caches — this is why public shorteners default to 302. Mitigate existing 301s by short cache TTLs and edge invalidation. |
9. Interview Q&A
- A link goes viral at 200k rps and it's NOT in cache — describe the millisecond. (senior answer) Without protection, all 200k requests miss simultaneously and stampede the origin — the DB gets 200k concurrent identical reads and falls over, taking every other link with it. The fix is request coalescing / single-flight at the edge: the first miss for a code acquires a per-code lock and issues one origin fetch; the other 199,999 concurrent requests for that same code wait on that in-flight fetch rather than each issuing their own. When the single fetch returns, it fills the cache and unblocks the whole herd, which is now served from cache. The origin saw exactly one read. This collapses an O(herd) stampede into O(1) origin load — it's the single most important mechanism on the read path, and it's why "what happens on a cold viral link" separates senior from junior answers.
- Why is this a cache problem and not a database problem? (senior answer) Writes are ~3 req/s and the dataset is sub-TB — the DB is trivial. Reads peak at 10k QPS, and origin QPS = read QPS·(1−h), so cache hit rate is a 10× cost multiplier from 90% to 99%. Click traffic is Zipfian, so a small hot-set cache buys 95%+ almost free. The architecture is the cache hierarchy; the DB is just durability behind it. (Mechanics of eviction/TTL: lesson 06.)
- Why 7 characters? (senior answer) It's derived, not chosen. 62^7 ≈ 3.5T codes; at 100M/yr that's ~35,000 years to exhaust. Six chars (~57B) also lasts centuries but leaves a random-allocation scheme with less sparsity (higher collision rate). 7 is the smallest length with comfortable headroom for random codes, at the cost of one byte.
- 301 or 302? (senior answer) 302 by default. 301 is cheaper (browsers cache it and never come back) but you lose takedown control — a blocked malware link keeps redirecting from browser caches you can't reach — and your analytics under-count exactly the most popular links. 302 keeps every click coming to you, so takedown is instant and counts are complete; recover the cost at the edge/CDN cache, which you can invalidate. 301 only when destinations are immutable and you don't need per-click data.
- Sequential or random codes? (senior answer) Random for any public service. Sequential is compact and cache-friendly but lets anyone enumerate every link and read your volume off consecutive codes. Random at 3×10⁻⁵ occupancy collides ~0.003% of the time — one cheap insert-if-absent retry on the low-QPS write path — to buy full enumeration resistance.
- How do you count clicks without slowing redirects? (senior answer) You don't count on the redirect path at all. The redirect tees a fire-and-forget event to a durable log and returns; an offline consumer aggregates the stream (DDIA Ch. 11). The pipeline can lag, batch, sample, or fail and redirects never notice. Synchronous counting would couple a 10k-QPS latency-critical path to a high-volume write store — the canonical mistake.
- The database is down — what does a redirect do? (senior answer) Cached codes keep redirecting (stale-while-revalidate). Uncached codes fail closed — return 503 rather than guess — because a shortener that redirects to an un-vetted destination during an outage is an abuse vector. The high cache hit rate means most traffic survives the outage untouched, which is the upside of having made this a cache problem.
- How do you stop your shortener from being a malware launderer? (senior answer) Synchronous reputation/blocklist check at creation for high-risk submissions, continuous async re-scanning, and a compact
statusflag the redirect reads inline (no extra lookup). The 302 default is what makes takedown actually effective — flip the flag and the next click is blocked.
Related foundation lessons
This case leans on four foundations, each for a specific reason. Caching (lesson 06) owns the hit-rate → origin-load mechanics, eviction, and TTL — we used the result here and deferred the how. API design (lesson 03) covers why the redirect verb and idempotent create belong in the contract. Rate limiting & the edge (lesson 15) is where request coalescing and edge admission control live in full — the single-flight answer above is its application to the viral-link herd. Async messaging (lesson 11) is the click-event stream: the queue/log that lets analytics lag without ever touching the redirect.