Design a URL Shortener

Every new link needs a code that no other link already uses — 400 of them a second at peak, and the plan says 15B links after five years. Whatever generates them must make a duplicate impossible, not just unlikely: if two links share a code, one visitor silently lands on the wrong page, and no error shows up anywhere.

Before choosing how to generate codes, choose how long the code is, because length sets the size of the space we pick from. Codes are written in base62: counting with sixty-two symbols instead of ten — the digits 0–9, then a–z, then A–Z — which packs the largest number into the fewest URL-safe characters. Six characters give 62⁶ ≈ 57B possible codes: the plan fits, but the space is already 26% full by year five — and for randomly generated codes, that also means roughly one in four new codes would hit an existing one by then. Seven characters give 62⁷ ≈ 3.5T codes, and the same plan fills less than half a percent of it. One extra character removes the problem entirely, so the code is seven characters.

The tempting one is to hash the long URL and keep seven characters of the result. The same URL always produces the same code, so someone submitting the same URL twice gets the same link for free, and there is nothing to coordinate. This is where most engineers start, and at full hash length it is a fine idea. The problem hides in “keep seven characters.” A full hash almost never collides, but a truncated one does — and the birthday bound says how soon. In a space of 3.5T, random values start colliding at even odds around the square root of the space: about 2M codes, not trillions. We plan for 15B links, so truncated-hash collisions are not a risk, they are a certainty — and every one of them quietly sends someone's visitors to someone else's page, with no error anywhere. Free deduplication is not worth an undetectable wrong-page bug. Hashing is out.

That leaves two live options, and the real choice between them is simple: pay a small coordination cost once, or pay an existence check on every create, forever.

Random codes generate seven random base62 characters. Any app server does this alone — nothing shared, nothing coordinated — and the codes can't be guessed, so nobody can walk through your link space. But random means collisions are only unlikely, not impossible, so every create must first ask the store “is this code taken?” — a read on your busiest write path — and retry in the rare case the answer is yes. You can make that check nearly free with a bloom filter, but it never goes away, and past 2M links the retry path has to actually work.

A counter keeps one number that goes up by one for every link ever created; a link's code is that number, written in base62. This makes uniqueness automatic — the counter never produces the same number twice, so no two links can ever share a code, and nothing needs to be checked. There is no existence read on the write path at all. The cost is that a counter is one shared thing that some service has to own, and that codes handed out in order are guessable: from one code, anyone can guess the next code exists and walk your links one by one.

Counter → base62. When one option's cost can be engineered away and the other's is permanent, take the first. The random option's existence check is a read 400 times a second on the write path, forever, bloom filter or not. The counter's coordination cost, as the mechanics below show, can be made almost zero — and its guessability is fixed by scrambling the number before it becomes a code. Uniqueness stops being a probability and becomes arithmetic: no check, no retry, no read on the write path. And the space lasts: 3.5T codes at 400 creates a second — the peak, held forever, which real traffic never does — runs out in roughly 300 years.

Something has to store the mapping from each short code to its long URL — and before picking a store, work out its size from a single row up. One row is a seven-character code, a long URL of a couple hundred bytes, two timestamps, plus per-row and index overhead — call it 500 bytes in total. 15B rows after five years is about 8 TB. So: 8 TB, written 400 times a second, read one row at a time by its code, and every row must stay safe for years. (Reads are drowning this store right now — that is the next use case's problem, and its fix works the same whichever store sits here.) Which kind of store fits that shape?

The fastest-sounding answer is to serve everything from memory — an in-memory store like Redis as the primary. Every lookup is a memory access, and there is almost nothing to operate at the start. But look at what it means for this store: it holds the only copy of every promise the product ever made — 15B links that must keep working for years — and memory is designed to throw data away under pressure. The day memory pressure evicts a key, a link someone paid for stops working, and nothing reports it. Keeping all 8 TB in RAM to prevent that would cost more than the rest of this design combined. Memory is the right place for the popular links — but that is a cache in front of the store, which the next use case builds, not the store itself. In-memory-as-primary is out.

That leaves two real stores, and it is honestly a judgment call between them.

DynamoDB is a managed key-value store. “Code in, URL out” is literally its API, and throughput, replication, and operations are the provider's problem — the read explosion becomes someone else's migration to run. The cost is that you commit on day one to a partition key — the one field the store uses to split rows across its machines — and everything that is not a plain key lookup (listing a user's links, scanning by date, changing the schema) gets harder from then on.

Postgres is an ordinary relational database. Looking up one row by its primary key is the thing it does fastest, and 400 inserts a second doesn't move the needle. Its durability story — backups, restores, point-in-time recovery — has been solid for decades, which is exactly what a store whose job is keeping promises for years wants. The cost is that when load outgrows one node, scaling it is your job, not a provider's.

Postgres. The workload is single-node sized — 8 TB fits one machine's disk, 400 writes a second is nothing, and the reads will be absorbed by the next use case's cache whichever store sits behind it. When the numbers don't force a distributed store, the ordinary store that keeps every future option open — ad-hoc queries, listings, migrations — beats the one that demands a data-model commitment up front. Choose DynamoDB when the team, not the workload, is the constraint: paying a provider to run the store instead of running it yourself is a legitimate trade.

At peak, 40k redirects a second each need a lookup, and the store answers about 10k indexed lookups a second before it falls behind — the read path is overloaded four times over. Before picking a fix, look at the shape of the load, not just its size. It is not 40k different links a second. Link traffic is heavily skewed: a few links are popular right now, and a huge number are quiet. During a spike, a single viral link can be 70% of peak by itself. The right fix has to match that shape.

The reflex when a store runs out of capacity is to shard it — split the table across several nodes so each holds a part. That is the standard answer when data outgrows one machine, and this board really does shard a store two decisions from now. But it is the wrong tool here, and the reason is precise: sharding splits the data, and our problem is not the amount of data. The store fits on one machine — 8 TB after five years — and the load is a read spike concentrated on a few links. Every read of the viral link carries the same code, the same code always hashes to the same shard, so that one shard is still past its ceiling while the others sit idle. Split it six ways or sixty: you'd run a sharded system and still be overloaded on the one hot shard. Sharding is for a write or size problem, not a hot-key read spike.

A more honest fix is read replicas — full copies of the database, with reads spread across them. Five replicas bring each node's share of 40k/s comfortably under its ceiling, and there is no new kind of component, just more of the database you already run. It genuinely clears the number. But price it: every replica stores all 15B rows in order to serve a popular set that would fit in one cache node's memory, every lookup is still at database speed rather than memory speed, and a replica always runs slightly behind the primary — so a link created a moment ago may not exist on the replica yet, and its very first visitor, the one the creator is watching for, gets a 404. Replicas are the right tool when reads are spread evenly across the data. Ours concentrate in a small popular set.

That skew is the whole answer. The popular set is small, so a small cache — the popular links' answers held in memory, in Redis, in front of the store — absorbs about 90% of every redirect, and the store only sees the misses: a tenth of the traffic, comfortably inside its 10k/s ceiling. The same skew that broke the store now saves it. One cache node buys what five replicas would, and answers from memory instead of disk.

One question remains, and it is really “who answers repeat clicks — our servers or the visitor's browser?” Answer a redirect with 302, the temporary redirect, and every click comes back to us: we can re-point the link tomorrow, and we count every click today. Answer with 301, the permanent redirect, and browsers remember it themselves — repeat visitors skip us entirely, which is strictly less traffic at no extra cost. The 301 is cheaper and it works, but the word permanent is the catch: a destination you later need to change is stuck in caches you don't control, and every click a browser answers by itself is a click your servers never see. Because this product counts clicks, that undercount is disqualifying.

Cache the hot set — serve 302. A cache the size of the popular set does the work: it absorbs 90% of redirects from memory, the store sees only the misses, and answering 302 keeps every click coming back to us — countable today, re-pointable tomorrow.

Right now every redirect writes its click straight to the store and moves on. When the store has a bad moment — a timeout, a deploy — those clicks are simply lost, and the counts creators see are wrong. Fix the counts without slowing the redirect: the time budget is 100 ms per redirect, the promise is exact counts, and the volume is one event per redirect — 40k a second at peak, indefinitely.

The instinct that stops a dropping counter in most codebases is to make the insert synchronous — the redirect isn't done until the click row is written. Now the counts can't be wrong, and the change is one line. But it ties your fastest path to your slowest component: every redirect now waits for the store, including during the store's worst moments. A store at its limit doesn't answer in its usual few milliseconds — it answers when its queue of waiting writes clears, which near the limit is about a full second. The whole redirect budget is 100 ms, so one synchronous write spends it ten times over. The honest instinct, pointed at the wrong victim.

The other tempting shortcut is to sample — store one click in ten and multiply. A tenth of the stream fits anywhere, and sampling is genuinely how the web's biggest analytics products survive their own volume. But it answers a cost problem we don't have, and it breaks a promise we do have. A creator whose link got a few dozen clicks would see an estimate that changes on every refresh — off by tens, noise where they wanted a number. The requirements let counts lag; they never let counts be wrong, and sampled counts are wrong at exactly the scale our paying users live at.

The shape every serious event pipeline lands on is a queue — a durable, append-only log (Kafka) between the redirect and the store, drained by a pool of workers. The redirect appends the click to the log and gets an acknowledgment in under a millisecond, then finishes; a separate set of workers reads the log and writes to the store in batches, at the store's own pace. The intake is never the worry: a single Kafka-class log broker sustains around 100k appends a second, and our 40k/s stream runs at under half of that. Nothing is lost, and counts run a few seconds behind.

A Kafka queue, drained by ingest workers. Separate the two paths: the redirect pays one sub-millisecond acknowledged append to a durable log and finishes, and the ingest workers drain that log into the store in batches at the store's own pace. Loss turns into lag — the one thing the requirements allow. Be clear about what the log buys, though: honesty, not throughput. Whether the store can actually drain what arrives is a separate question about its own ceiling — the next decision on this board.

Now the store the ingest workers write into. Size it first: a click event is small — code, creator id, timestamp, country — about 100 bytes, but there are 40k of them a second at peak. At an average of a quarter of peak, that is roughly 90 GB of new data a day, about 30 TB a year. The write rate is the harder limit: one Cassandra node takes about 10k writes a second, and the stream peaks at 40k. No single node can take this, so the store has to be split across several: 40k ÷ 10k = 4 nodes minimum; use 6 for headroom. Splitting one table across nodes is called sharding — each node (each shard) owns a part of the rows, and a rule decides which shard every row goes to. The rule is the decision: which column carries the split? Ask two things of each candidate — when a click lands, which value decides its shard, and can that value pile up on one shard?

Split by time — created_at — fails immediately. Every click happening now carries the same hour, so the newest shard takes the entire 40k/s while the others do nothing. Old data would drop a whole shard at a time, which is genuinely nice, and a day's range scan would stay on one shard — but “now” is always a single bucket, and a live write stream can't have a permanent hot spot. Time-based splits are for reading history, not for absorbing a live stream.

Split by owner — creator_id — is more tempting: a creator's whole dashboard reads from one shard, and each account's data lives in one place. It fails on real traffic rather than in theory. Write volume follows virality, and virality concentrates on a few creators. Run our own last hour of traffic through this split and the two busiest creators happen to land on the same shard, which then carries 61% of all writes while the others sit idle. There is no way to rebalance out of it, because the key itself concentrates the load. Great for reads, wrong for a write-heavy stream.

Split by the link — short_code — is the one that holds. Every event already carries its code, so working out the shard is one hash calculation, no lookup anywhere. Dozens of links are active in any given hour, so hashing the code spreads writes flat across the shards. And one link's count conveniently lives on exactly one shard, so reading a single link's total is one shard's job. The cost is that one creator's links end up spread across several shards, so a per-creator dashboard collects from several places — but the ingest workers already add those per-creator numbers up as they drain the queue, a small price for a store with no hot spot.

short_code. Split by the value every click already carries and no single account can pile up: the route is one hash with no lookup, dozens of active links share each hour so the writes spread flat, and one link's count lives on exactly one shard.

The board is built. Before trusting it, try to kill it: one part of this design, failing on its own, takes every redirect down with it. Which part is it — the one you cannot afford to lose?

Kill each one and trace a redirect. Kill the balancer: dead at the first hop — nothing downstream even hears the click. Real and total, but also the failure everyone already plans for; balancer pairs are standard, solved infrastructure. Kill Postgres: the trace shows something surprising — the redirect path no longer goes through it. The cache answers 90% of clicks without asking the store; only cache misses and brand-new links suffer until the standby takes over. A bad hour and real damage — but not the box that takes every redirect down. Kill the cache: with no cache there is no absorption, and the full 40k/s lands on a store built for 10k/s. The path doesn't fail cleanly — the store is instantly buried under four times its capacity, and everything behind the cache goes down with it.

The cache. The cache stopped being an optimization the day it started answering 90% of the reads — whatever absorbs the traffic IS the path. Give it a live twin, pair the balancer in front of everything, and keep the store's standby. Protection should follow the traffic, not the org chart.