Design a URL shortener
Work the canonical shortener end to end: estimate it, choose a code scheme with the base62 arithmetic, and defend one database against the urge to shard.
A URL shortener stores a mapping from a seven-character code to a long URL and redirects on lookup. That is the whole functional surface, which is why it is the standard warm-up and the best test of whether a candidate can resist over-engineering. The arithmetic below lands at three writes per second, and everything after it follows from that number.
Step 1 — Requirements
In scope:
- Shorten a long URL and return a short one.
- Redirect the short URL to the original.
- Optional custom alias (
echo.gg/launchrather thanecho.gg/k3Bq9zR). - Optional expiry date on a link.
- Click analytics: a count plus a coarse breakdown by day and referrer.
Out of scope, and worth saying out loud so the interviewer knows it is a decision and not an oversight: user accounts, and editing a link's destination after creation. Immutability is not a convenience — it is what makes the cache story trivial later.
The non-functional requirements that actually constrain the design:
- Redirect latency is the one number users feel. Target p99 under 50 ms of server time; the mean hides the tail, and the tail is what people call slow.
- Redirect availability matters more than create availability. A failed shorten is a retry; a failed redirect is a dead link in someone's published post.
- Codes never get reused. A recycled code sends old traffic to a new destination — an open redirect handed to whoever registers next.
See functional vs non-functional requirements for why this split is asked first.
Step 2 — The estimate
Assume 100 million new URLs per year and a 100:1 read:write ratio.
Writes
100,000,000 / year
365 x 86,400 s = 31,536,000 s per year
100M / 31.5M ≈ 3.2 writes/sec → call it 3
Reads
100 x 3.2 ≈ 320 reads/sec average
peak at 3x average ≈ 1,000 reads/sec, ~10 writes/sec
Storage (5 years)
5 x 100M = 500M rows
row: code 7 B + long_url ~200 B + timestamps 16 B
+ index and page overhead ≈ 500 B all-in
500M x 500 B = 250 GB
Egress
320/sec x ~500 B ≈ 160 KB/s
A single commodity Postgres box handles roughly 5,000 simple QPS. Our five-year steady state is 320 reads/sec — 6% of one machine — and 3 writes/sec, or 0.06%. 250 GB fits on one SSD with an order of magnitude to spare, and the primary key index fits in RAM. Little's Law shows how idle this is: at the 1,000 reads/sec peak with a 2 ms service time, concurrency = 1,000 x 0.002 = 2 requests in flight, so a connection pool of 20 is generous by a factor of ten.
This is a single-database problem. A candidate who reaches for consistent hashing and a shard map at 3 writes/sec has failed the judgment test, and the interviewer will not tell them. Sharding is not wrong in the abstract; it is wrong at this volume, and the estimate step exists to find that out before anything gets designed.
What changes it: a 100x increase to 32,000 reads/sec. Then add read replicas before sharding, because 100:1 is the shape replicas exist for — one leader taking 300 writes/sec, followers absorbing the reads.
API sketch
POST /v1/links
{ "url": "https://example.com/very/long/path?utm=...",
"alias": "launch", // optional
"expires_at": "2027-01-01T00:00:00Z" } // optional
201 { "code": "k3Bq9zR", "short_url": "https://echo.gg/k3Bq9zR" }
409 if alias already taken
400 if url fails scheme/length validation
GET /{code}
302 Found, Location: <long url>, Cache-Control: no-cache
404 if unknown
410 Gone if expired
GET /v1/links/{code}/stats?from=&to=
200 { "clicks": 18422, "by_day": [...], "by_referrer": [...] }
The redirect deliberately sits at the domain root rather than under /v1/: every path character is one the user types.
Data model
CREATE TABLE links (
code VARCHAR(16) PRIMARY KEY, -- 7 chars generated, up to 16 custom
long_url TEXT NOT NULL,
created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
expires_at TIMESTAMPTZ NULL,
is_custom BOOLEAN NOT NULL DEFAULT false
);
CREATE TABLE click_rollups (
code VARCHAR(16) NOT NULL,
hour TIMESTAMPTZ NOT NULL,
referrer TEXT NOT NULL DEFAULT '',
clicks BIGINT NOT NULL,
PRIMARY KEY (code, hour, referrer)
);
One table, one primary key, no join on the redirect path. Counts live separately so a click never touches the row a redirect reads.
The key decision — generating the short code
Base62 uses [0-9a-zA-Z], so a seven-character code addresses:
62^5 = 916,132,832
62^6 = 56,800,235,584
62^7 = 3,521,614,606,208 ≈ 3.5 trillion
Five years of traffic is 500 million codes, or 0.014% of the seven-character space. Six characters would also fit — 500M into 56.8 billion, 0.9% occupancy — but leaves less headroom for a growth surprise, and the seventh character costs nothing. Three ways to fill that space.
(a) Hash the URL, truncate to seven base62 characters. SHA-256 the long URL, keep 42 bits, encode. Stateless and deterministic, and it fails twice. Truncation collides: expected colliding pairs among n codes in a space of N is roughly n² / 2N, here (5 x 10⁸)² / (2 x 3.52 x 10¹²) ≈ 35,000 over five years. So a uniqueness check before insert is mandatory anyway, and the resolution — salt and re-hash — destroys the determinism that was the only reason to hash. Determinism is also a bug here: two people shortening the same URL share a row, so one person's expiry deletes the other's link and their click counts merge.
(b) Random seven-character base62, insert with a unique constraint, retry on conflict. At 500 million rows the chance that a fresh random code is already taken is 5 x 10⁸ / 3.52 x 10¹² ≈ 1 in 7,000. At 3 writes/sec we do about 259,000 inserts a day, so roughly 37 inserts a day retry once, each costing one extra database round trip of 0.5 ms. The unique constraint is doing the collision detection, not application code, so there is no window where two hosts both believe they own a code.
(c) A counter encoded in base62, optionally range-allocated so each host claims a block of 10,000 IDs from a coordination service and hands them out locally. Collision-free, and range allocation removes per-write coordination — at 3 writes/sec across four hosts each block lasts about four hours. The failure mode is not throughput, it is disclosure. Sequential codes are enumerable: a scraper at 1,000 requests/sec walks 86 million codes a day, reading the entire first year of links in three days, including every link someone assumed was private because it was unguessable. Counters also leak volume — subtract two codes issued a week apart and you have the weekly growth rate. Permuting the counter through a keyed Feistel network fixes both, which is cryptographic machinery bolted on to solve a problem option (b) never had.
Winner: (b), random base62 with a unique constraint and retry. No coordination service, no enumerable namespace, and the collision handling is a constraint the schema needed regardless. Option (c) wins once the retry round trip dominates — call it 10,000 writes/sec, three orders of magnitude away. Naming the volume at which you would switch is what separates a decision from a preference.
Custom aliases need no new mechanism: the alias goes in the same code column, the same unique constraint rejects duplicates, the API returns 409. Reserve a denylist of application routes (api, login, static).
The read path
The lookup. Clicks are heavy-headed — a campaign link takes millions of hits in a week while the median link gets three, ever. Caching the 10 million hottest codes costs 10M x ~300 B ≈ 3 GB, one Redis node. At a 90% hit rate the database sees 32 reads/sec instead of 320, and p99 improves because a memory reference is 100 ns against a 100 µs SSD random read.
This is the rare cache with no invalidation problem. Links are immutable by requirement, so an entry can only become wrong by expiring; set the Redis TTL to min(link expiry, 24 hours) and you are done. Had we kept editing in scope we would owe a write-through or explicit-delete story here — see caching strategies for what that costs.
Cache misses too. A scanner probing random codes at 1,000 requests/sec becomes 1,000 database queries/sec — three times our real traffic — unless "not found" is itself cached for 60 seconds. Pair that with rate limiting per source IP.
Latency budget for a cached redirect: a 0.5 ms in-datacenter round trip to Redis plus application time lands near 1-2 ms of server time, while a user in Mumbai hitting a US-East origin pays ~200 ms of network. The network dominates the datastore by two orders of magnitude, so an anycast edge buys more p99 than any database tuning will.
301 vs 302
A 301 Moved Permanently tells the browser to cache the redirect, often indefinitely. Every subsequent click then resolves inside the browser and never reaches us, which kills three things at once: click counts stop after the first visit per browser, an expired link keeps resolving, and an abusive link cannot be revoked because the victims' browsers no longer ask.
A 302 Found — or 307, which also preserves the request method — asks every time. Send it with Cache-Control: no-cache so no intermediary decides to be helpful.
The cost is quantifiable. A 301 with a 90% browser cache hit rate would cut origin traffic from 320 reads/sec to about 32, so we pay roughly 290 requests/sec for analytics and revocability — 6% of one Postgres box against 0.6%. An obvious trade here; at 300,000 requests/sec, worth arguing about. See HTTP semantics.
Analytics belongs off the redirect path
The naive version is one statement:
UPDATE links SET clicks = clicks + 1 WHERE code = $1;
It breaks twice. It converts a 3 writes/sec system into a 323 writes/sec system, and every one takes a row lock — a viral link at 500 clicks/sec serializes all 500 on one row, and lock wait lands directly in redirect p99. Worse, it couples redirect availability to write availability: the leader goes read-only during a failover and every redirect fails, to record a number nobody reads in real time.
Instead the redirect emits an event and returns. A worker consumes the topic, aggregates in memory, and flushes every 10 seconds: 320 events/sec × 10 s = 3,200 events collapsing into a few hundred (code, hour, referrer) upserts. Analytics write load drops from 320/sec to about 30/sec of batched work, off the critical path entirely. Message queues covers the delivery guarantees.
State one consequence before the interviewer does: queues deliver at-least-once, at-least-once means duplicates, and duplicates mean idempotency is required. Either carry an event ID and deduplicate in the worker, at the cost of a set membership check per event, or accept counts approximate to within a fraction of a percent, which a marketing dashboard can live with. Either is defensible; choosing the second by accident is not.
Expiry
Check expires_at on read and return 410 Gone; a nightly batch deletes expired rows. Do not build a per-link timer — at 100 million links a year that is 100 million timers replicating a comparison the read path already performs.
Consistency posture
The create path needs a single leader: the unique constraint on code is only meaningful if one node arbitrates it, and two nodes inserting independently will eventually both hand out k3Bq9zR. At 3 writes/sec that leader is never the bottleneck. The read path takes the opposite position. In CAP terms, when a partition separates a follower from the leader we choose availability: a redirect served from a 30-second-stale row beats a 503 on a link someone published. PACELC covers the rest of the time — Else, we prefer latency over consistency, which is what reading from Redis and from followers means.
That has one visible consequence, and it is the one interviewers probe. A link created and clicked within replication lag can 404 from a follower — the user's own creation appears not to exist. Write the entry into the cache at creation time so the first read hits regardless of replication, or route reads for codes younger than 60 seconds to the leader. The first is cheaper and survives a follower outage. Consistency models has the general treatment.
Trade-offs
| Decision | Chosen | Rejected | Why the rejection |
|---|---|---|---|
| Code generation | Random 7-char base62, unique constraint, retry | Hash-and-truncate | ~35,000 collisions at 500M rows, so it needs the uniqueness check anyway; determinism merges two users onto one row |
| Code generation | Random 7-char base62 | Base62 counter, range-allocated | Enumerable and leaks growth rate; only pays off above ~10,000 writes/sec |
| Code length | 7 chars, 3.5 trillion space | 6 chars, 56.8 billion | 0.9% occupancy vs 0.014%, for one saved character |
| Database topology | One leader, one follower, one cache | Sharded by code hash | 320 reads/sec is 6% of a 5,000 QPS box |
| Redirect status | 302 with no-cache | 301 permanent | Browser caching removes analytics, expiry enforcement, and revocation |
| Click recording | Async event to a queue, batched rollups | Synchronous counter update | Adds 320 writes/sec of hot-row contention to the read path |
| Expiry | Lazy check on read plus nightly sweep | Per-link scheduled deletion | 100M timers a year for a timestamp comparison the read already does |
In an interview
What is being tested is not whether you can design a hash map. It is whether the estimate changes what you build. Almost every candidate draws a cache in front of a database; the separator is the one who computes 3 writes/sec, says "this fits on one machine", and defends it against the follow-up.
Say the numbers before you draw anything. "100 million a year over 31.5 million seconds is about 3 writes per second, 320 reads at 100:1, 250 GB over five years. One Postgres primary handles about 5,000 QPS, so we are at 6% of one box." That sentence buys you the rest of the interview. Then give the code-generation comparison with its arithmetic — 62⁷ is 3.5 trillion, five years fills 0.014% of it, random plus a unique constraint retries about 37 times a day. Naming the failure mode of each rejected option is what shows you evaluated them rather than recalled a blog post.
The specific mistake that loses points: sharding, or proposing a coordination service for counter ranges, at 3 writes/sec. It reads as pattern-matching to "scalable system" instead of to the requirements you were just given, and you cannot un-say it. The runner-up is the synchronous click counter, which looks harmless and puts a hot-row lock on the only path with a latency budget. If the interviewer then scales the problem 100x, do not discard the design — add replicas, then a shard map, and name the replica-lag consequence before you are asked.
Check yourself
1. The interviewer raises the target to 10 billion new URLs per year, keeping 100:1. Does the code length still work, and does the topology?
Writes become 10¹⁰ / 31.5M ≈ 320/sec, reads ≈ 32,000/sec. Length is fine: five years is 50 billion codes against 3.5 trillion, 1.4% occupancy, and the retry rate rises only to about 1 in 70 inserts. Topology is not fine. 32,000 reads/sec is over six times one box, so the cache tier plus read replicas become mandatory, and 50 billion rows at 500 B is 25 TB, past a single node. Now shard by hash of
code— every access is a single-key lookup, so there are no cross-shard queries.
2. One link goes viral at 20,000 clicks/sec while the rest of the system is idle. Which component fails first, and what is the fix?
Not the database — the code is one Redis key, served from memory, and the database sees nothing. Not the redirect service, which scales horizontally behind a load balancer. The click pipeline is the pressure point: 20,000 events/sec into one topic partition, and if that partition is keyed by
codeall 20,000 land on one consumer. Key click events by something with cardinality instead — a random key, orcodeplus a bucket suffix — and sum the partials at rollup time. It is the same hot-key problem the synchronousUPDATEwould have had, moved somewhere a stalled consumer costs delayed analytics rather than failed redirects.