Scale & cachingFoundation
A URL shortener that is mostly a read problem
The interview classic, and the reason it is asked: almost everyone designs the write path, and almost all of the traffic is on the read path.
The brief
Take a long URL, return a short one. Visiting the short one redirects to the long one.
Links never expire unless the creator deletes them. Anyone can create one without an account.
Requirements
Functional
- Create a short link for a URL
- Redirect a short link to its target
- Let the creator delete a link they made
Non-functional
- A redirect is on the critical path of somebody else's page load — treat its latency as a budget, not a target
- Losing a link is worse than briefly failing to create one
- Short codes must not be guessable in bulk if anyone will use this for anything private
Back-of-envelope
Assume
- 1 million new links a day — this is the number to argue with first
- 100 reads per write, which is the ratio that decides the whole design
- 500 bytes stored per link: the target URL, the code, an owner, a timestamp
Therefore
- Writes: 1e6 / 86,400 ≈ 12 per second. This is not a scaling problem. A single database handles it.
- Reads: 12 × 100 ≈ 1,200 per second, and this is where the design goes.
- Storage: 1e6 × 500 B ≈ 500 MB a day, ≈ 180 GB a year. Fits on one machine for years; plan sharding for when it does not, not now.
- A short code from 62 characters: 62^7 ≈ 3.5e12. At a million a day that is over 9,000 years of codes.
Notice what the arithmetic did: it removed the write path from the discussion entirely. If your reads-per-write assumption were 2 instead of 100, this would be a different design — which is why the assumption is written down rather than folded into a total.
The interface
POST /links → 201 { code, shortUrl }Twelve of these a second. Nothing about this endpoint needs to be fast, and designing it as though it did is the mistake the summary warns about.
GET /{code} → 302 Location: <target>This is the product. No body, no JSON, no content negotiation — a redirect that returns anything else is doing work on the one path that has a latency budget.
DELETE /links/{code} → 204Owner only. The route is trivial; what it has to do to the cache is the part worth designing, and the components section says so.
What is stored
links
The entire read pattern is one point lookup by primary key, so the table wants no other index. Every index you add is a write cost paid to speed up a path that is one percent of the traffic.
code (primary key, 7 chars) · target · ownerId (nullable) · createdAtThe entire read pattern is one point lookup by primary key, so the table wants no other index. Every index you add is a write cost paid to speed up a path that is one percent of the traffic.
deleted codes
A tombstone rather than a removed row, so a code is never re-issued. Re-issuing means an old link quietly starts pointing at a stranger's URL, which is the worst failure this system has and leaves no trace in any log.
code (primary key) · deletedAtA tombstone rather than a removed row, so a code is never re-issued. Re-issuing means an old link quietly starts pointing at a stranger's URL, which is the worst failure this system has and leaves no trace in any log.
The design
The redirect pathCache in front of the store, keyed by short code. A link's target essentially never changes, so this is the rare cache where a long TTL is honest rather than a risk.
The code generatorEither a counter encoded to base62, or random bytes with a uniqueness check. The choice is not about performance; see the decisions below.
The storecode → target, owner, created-at. A single table with the code as the primary key. Point lookups by primary key is the entire read pattern.
The delete pathA delete must invalidate the cache, and that is the one place the long TTL bites. Decide whether a deleted link may keep redirecting for the rest of its TTL, and write the answer down.
The decisions
Each of these could go the other way. The choice, the reason, and what it costs — a design that lists only what it chose teaches the choice; one that lists what it gave up teaches the judgement.
Sequential counter, or random code?Chose — Random, for anything a stranger can createBecause — A base62 counter is shorter, needs no uniqueness check, and is trivially enumerable — anyone can walk the whole corpus by counting. That is fine for internal links and a privacy incident for user-submitted ones.Random needs a collision check on insert, which is a read before every write. At 12 writes a second nobody notices; at 12,000 you would use a pre-generated key pool instead.
301 or 302 for the redirect?Chose — 302Because — 301 is cached by the browser, so the second visit never reaches you. That is a latency win and a total loss of click analytics, plus a link you can no longer delete from anyone who has already followed it.Every visit costs a request. If you genuinely have no analytics and no deletes, 301 is the better answer, and saying so is a stronger response than defaulting to 302.
Cache-aside or write-through?Chose — Cache-asideBecause — Writes are rare and reads are hot. Write-through would spend cache capacity on links nobody visits, and most links are visited once or never.The first read of each link is a miss. With a 100:1 read ratio that is one slow request per hundred, which is exactly the trade the ratio was measured for.
What breaks first
In order. Each names what you would actually observe, and each fix carries its cost.
A cold cache, right after a restart or a deploySymptom — Redirect latency jumps for a few minutes and the database sees the full 1,200 reads a second instead of the one percent it normally sees.Fix — Warm the cache from the most-recently-read codes before the node takes traffic, and stagger restarts across nodes.A warm-up window during which the node is running but not serving, and a list of hot codes that is itself state to maintain.
One viral linkSymptom — A single cache key is most of your traffic, so one cache node is saturated on network while the rest of the fleet is idle. Adding nodes does not help, because the key does not move.Fix — Replicate the hot key to every node, or push it to a CDN and let the edge answer.More copies to invalidate on delete, which is the exact weakness the long TTL already introduced. The hottest link is now the slowest one to take down.
About 180 GB, which is a year inSymptom — Not queries — backups. A primary-key lookup on a billion rows is still fast; taking and restoring a backup of that table is what stops being routine first.Fix — Archive links whose code has not been resolved in a long time to cold storage, resolved on miss.A miss on an archived link is slow rather than absent, and you now have two stores to keep a code unique across.
When something fails
The cache is down entirelyEvery redirect goes to the database at 1,200 a second. Because the read is a primary-key lookup, one primary can absorb that — which is the payoff for keeping the schema boring, and worth saying out loud rather than discovering.
The database primary is downRedirects continue from cache and from a read replica; creation fails with a 503. The asymmetry is deliberate: losing a link is worse than briefly failing to create one, and this is where that requirement is actually spent.
Two writers generate the same random codeThe unique constraint rejects the second insert and it retries with a fresh code. The collision is handled by the database refusing it, not by a check the application performs and hopes was still true a millisecond later.
Scaling it
Each step is triggered by a number, not a feeling — and carries what it costs.
10× reads — 12,000 a secondMove — Read replicas behind the cache, and a longer TTL now that the corpus is provably immutable.Replica lag makes a freshly created link 404 for a moment, and the one person guaranteed to click it immediately is the person who just made it. Read your own writes from the primary for a short window.
100× writes — 1,200 a secondMove — A pre-generated pool of unused codes, so insert stops being read-then-write.The pool is state that has to be refilled, and it introduces a failure nobody had before: running out of codes at peak, which looks like a total outage of creation.
Beyond one machine of storageMove — Shard by a prefix of the code, which is random and therefore spreads evenly by construction.Deletes and any future analytics become scatter-gather across shards. The read path is untouched, which is the reason to shard on the code rather than on the owner.
What gets probed
The design is the easy half. These are where the conversation goes, and each has a defensible answer above.
- What happens when two requests generate the same random code at the same moment?
- A link is deleted. How long can it keep redirecting, and who decided that?
- One link goes viral and is 90% of your traffic. What breaks first?
- How would you add per-link click counts without putting a write on the redirect path?