Chapter 8 · System Design Fundamentals
Design a URL Shortener
A short, satisfying design that reuses the unique-ID ideas from Chapter 7 and turns a long link into seven characters. It is the classic interview warm-up — small enough to finish, deep enough to show how you think about read paths, identifiers, and trust.
▶ Open the companion slidesThe whole product is two endpoints: one that mints a short code for a long URL, and one that redirects a visitor back to it. Everything interesting hides in the ratios — roughly 100 reads for every write — and in two old questions wearing new clothes: how do we generate an identifier that is unique, short, and hard to guess? You answered most of that in Chapter 7; here we spend it.
Alex Xu, System Design Interview (Vol. 1), Chapter 8. Companion deck: slides — jump to any slide with the Slide N chips. Go deeper: the System Design Primer.
What we're building Slide 2
Nail the scope before drawing boxes. The functional surface is tiny — shorten and redirect, with optional custom aliases, expiry, and click counts — but the non-functional requirements are where the design lives. The redirect is the hot path: it must be fast, always up, and read-optimised.
Functional
Shorten a long URL into one rooted at our domain, redirect the short URL to its target, plus optional custom alias, expiration, and basic click analytics.
Non-functional
Read-heavy (~100:1), low-latency redirects, four-nines availability (a dead link breaks every place it was shared), strict uniqueness, and unpredictable codes.
The two request flows Slide 4
Two paths carry the entire system. The write path runs once per link and can afford to be careful; the read path runs a hundred times more often and must be brutally fast. Read the diagram first — the asymmetry is the whole design.
Back-of-envelope numbers Slide 3
Pick numbers you can defend, then multiply — the goal is the order of magnitude, not precision. Start from 30 million daily users writing ~3 links each, at a 100:1 read-to-write ratio.
reads/day = 90M × 100 = 9B → ~104,000 rps (peak ~3× → ~310k rps)
storage/5yr = 90M × 365 × 5 × 500B = ~82 TB (with indexes/replicas → ~250 TB)
A hundred thousand redirects per second and multi-petabyte storage over a decade. One Postgres won't carry it — you need a shard plus an aggressive cache, which is exactly what the rest of the design builds.
Public API Slide 4
Two endpoints carry the whole product. Keep the surface small — every extra knob is something to version, document, and defend.
| Endpoint | Does | Returns |
|---|---|---|
| POST /api/v1/shorten | Create a short link from long_url (+ optional alias, expiry) | 201 with short_url · 409 alias taken · 422 blocked target |
| GET /:short_code | Redirect a browser to the original target | 302 with Location · 404 unknown · 410 expired |
Data model Slide 5
One main table does almost everything. Lean on the primary key for the only query that matters on the hot path: lookup by short code. The table is small and key-value-shaped on purpose — joins and per-click analytics live elsewhere.
| Column | Type | Notes |
|---|---|---|
| short_code | VARCHAR(10) | Primary key. 7 base62 chars in practice. |
| long_url | TEXT | Up to ~2 KB; stored verbatim, not normalised. |
| owner_id | BIGINT, null | FK to users; NULL for anonymous links. |
| expires_at | TIMESTAMP, null | NULL means never. Indexed for the reaper job. |
| is_blocked | BOOLEAN | Set by the abuse scanner — short-circuits redirect. |
Sharded by hash of short_code; a secondary index on owner_id serves a
user's "my links" page. Per-click rows go to a separate columnar store, never this hot table.
How many characters do we need? Slide 6
Short codes are drawn from base62 — digits 0-9, lowercase a-z, uppercase A-Z, 62 symbols. Each character carries log₂(62) ≈ 5.95 bits, so n characters give you 62n codes. The job is to pick the smallest n with comfortable headroom for every link we'll ever issue.
| Length n | Capacity 62n | Verdict |
|---|---|---|
| 5 | ~916 million | Fits today, corners us in a few years. |
| 6 | ~56.8 billion | Comfortable now; tight over a decade. |
| 7 | ~3.5 trillion | Our choice — overkill on purpose. |
| 8 | ~218 trillion | One more character we never need to type. |
Don't underbuy: adding a character later is a flag day for every cached link. Trillions of codes is overkill for one product's lifetime — and that is exactly the point.
Approach A — hash & resolve collisions Slide 7
Run the long URL through a cryptographic hash, truncate to ~42 bits, base62-encode into 7 characters, and hope the slot is free. If the row is missing, insert it. If it already maps to the same URL, return it. If it maps to a different URL, that is a collision — perturb the input with a salt and try again, a loop bounded by a small retry cap.
What it gets you
Stateless workers — any server can shorten without coordinating. Re-shortening the same URL naturally returns the same code, so idempotency is free.
What it costs
Every write does a read-before-write to check uniqueness; as the key space fills, the retry rate creeps up. Codes look pseudo-random — good for privacy, awkward to debug.
Approach B — counter + base62 Slide 8
Hand each new link a unique integer id, then base62-encode it. No collisions and no retries, by construction — every id is distinct, so every code is distinct. The id can come from a sharded counter, ticket batches (each worker grabs 1,000 ids at a time), or a Snowflake-style generator straight out of Chapter 7.
A bare counter produces adjacent, enumerable codes — a competitor can scrape your neighbouring links and read off your traffic volume, and "private" links become trivially discoverable. Mitigate by pushing the id through a fixed bijection (XOR with a secret, or multiply mod 2n) before base62-encoding, so the output looks random while staying collision-free.
The cost is coordination: the id source is a point of contention you must scale, exactly the tradeoff Chapter 7 explored. The win is simplicity: one write per shorten, zero collision logic.
Approach A vs Approach B Slide 8
The same identifier problem, scored on the things an interviewer pushes on.
| Dimension | A · hash + collision | B · counter + base62 |
|---|---|---|
| Collision risk | Possible — needs retries | None — unique by construction |
| Coordination | None — stateless workers | Central id source to scale |
| Writes per shorten | Read-before-write (≥1 read) | One write |
| Guessable? | No — looks pseudo-random | Yes, unless you obfuscate |
Rule of thumb: want stateless writers and free idempotency, accept retries → hashing. Want guaranteed uniqueness and one clean write, accept a contended id service → the counter. Pick the failure mode you would rather operate.
Caching the read path Slide 9
Redirects follow a power law — a handful of viral links serve most of the traffic — so push those rows as close to the user as possible. Three tiers absorb the load in turn: the CDN catches the viral tail, Redis catches the warm body, and the DB sees only the cold misses.
CDN at the edge
With a cacheable redirect, a hot short URL is answered at the edge and never touches our servers. Best for the long-lived viral tail.
Redis at the app tier
Hash-partitioned by short_code, storing code → long_url with LRU eviction and a ~24 h TTL — long enough to ride spikes, short enough to pick up edits and revocations.
Negative caching
Cache 404s for a minute or two so scrapers probing random codes can't torch the DB.
Invalidation
When a link is blocked or edited, delete it from Redis and purge the CDN; the TTL is the safety net if either delivery fails.
301 vs 302 — permanent vs temporary Slide 10
Both status codes redirect the browser. The difference is who remembers — and that decides whether you ever see another click. This is the highest-signal tradeoff in the whole design.
| Aspect | 301 · permanent | 302 · temporary |
|---|---|---|
| Browser | Caches the mapping, often forever; later visits skip your server. | Treats each visit as fresh; hits your service every time. |
| Server load | Lower — fewer clicks reach you once a link goes viral. | Higher — every click touches origin. |
| Analytics | You see roughly the first click, then nothing — counts under-report. | You see every click — accurate counts. |
| Editing / revoke | Painful — stale caches keep hitting the old target for months. | Trivial — the next click sees the new target. |
The textbook answer is "302 for shorteners," because analytics, abuse takedowns, and editability matter more than shaving a hop — it is why bit.ly and friends default to 302. The honest answer is "302 unless you have measured server load and decided you'd rather lose analytics than scale the redirect tier."
Keeping bad actors out Slide 11
A shortener is a redirection oracle for the open web — phishing kits, malware drops, and scam funnels all want to hide behind your domain. Defence is a layered pipeline, never a single switch.
Scan on create
On POST /shorten, check the target against Safe Browsing, PhishTank, and internal blocklists; reject known-bad outright.
Scan again, async
Re-scan in the background as feeds update — yesterday's clean URL can be today's compromised host.
Rate-limit creators
Token bucket per IP, key, and user on /shorten only; reads stay unrated so viral content isn't punished.
Reports & interstitials
User reports trip a soft-block; medium-confidence risk shows a "may be unsafe" click-through page before forwarding.
Five principles Slide 12
Read paths win the argument
At 100:1 reads, every microsecond on the redirect dominates total cost. Design the lookup first; the writer can be slower.
Hash vs counter is about coordination
Hashing buys stateless workers and pays in retries; counters buy guaranteed uniqueness and pay in a contended id service.
Cache aggressively, in layers
CDN catches the viral tail, Redis the warm body, the DB only the cold misses — each with its own TTL and invalidation story.
302 unless you've measured
Temporary redirects keep analytics honest and let you revoke abusive links. A 301's load saving is hypothetical until dashboards prove it.
Short codes are public — design for it
Anyone holding the URL can follow it. Don't lean on obscurity; randomise enough that adjacent codes don't reveal each other.
Active recall
Cover the answers. Say each one out loud before you tap to check.