System designMedium31 min readruns in the simulator
Design a URL shortener that survives losing its cache
How a URL shortener is designed: pre-generated keys, a Redis read path, Cassandra storage and Kafka analytics, with a simulator that shows where each version breaks.
- hashing
- caching
- key-generation
- nosql
- streaming
- throughput
- 4,020 rps
- redirect p99 latency
- 44.8 ms
- cost
- $2,847/mo
Requirements
Functional
- Create a short link for any valid long URL, with an optional custom alias.
- Count every click on a link without slowing the redirect down.
- No single client can take more than its share: a scraper or a spammer is refused before the API does any work.scrape refused over quota > 50%
Non-functional
- Handle 100M new URLs/month (~40 writes/s) at a 100:1 read/write ratio.create successful requests ≥ 38 rps
- Redirect (read) path p99 under 50 ms.redirect p99 latency < 50 ms
The requirements with a measurable target are checked live in the simulator: break something and watch them fail.
Back-of-the-envelope estimates
DAU -> requests/s
| Quantity | Value |
|---|---|
| New URLs / month input | 100,000,000 |
| Reads per write input | 100 |
| Writes/s | 39 rps |
| Reads/s | 3,858 rps |
Every value is computed from the inputs. Change them in the simulator and the model re-sizes itself.
High-level architecture
Scraperclient
One client trying random short keys to discover links, 50 requests a second.
Short keys can be guessed by brute force, so someone is always trying random ones to find private links. Those keys are not in the cache, so every attempt that gets through lands on Cassandra. The gateway holds the scraper to the same quota as anyone else.
Mobile Appclient · mobile
Opens short links from apps and messages; creates a few.
Mobile is a third of the traffic and the least forgiving of latency: a redirect on a cellular radio pays for every round trip, so the read path is built to answer from memory.
Web Browserclient · web
Opens short links in a browser; the dashboard creates them.
The server chooses the redirect code. A cached 301 would save a request on repeat clicks but hide them from analytics, so this design answers 302 and counts every click.
Load Balancerlb · nginx
Spreads requests over the API pods and drops unhealthy ones.
The API pods are stateless, so a load balancer is all it takes to scale them out and to keep serving when one pod dies. It terminates TLS so the pods spend their CPU on requests, not handshakes.
API GatewayapiGateway
Checks every request against its client’s quota, and new links against a cap for everyone, before the API does any work.
A shortener is an open door: anyone can create links and anyone can try keys. Limits per client stop one scraper or spammer from taking capacity everyone else shares, and they run in front of the API, so a refused request costs a counter check instead of a database read. How the gateway keeps its counts across its copies is its own business, designed in the rate limiter system.
API Serviceserver · api
Validates URLs, looks keys up, writes new links and emits click events.
One stateless service handles both paths: it keeps nothing but connection pools, so any pod can serve any request and scaling is a replica count. Reads and writes share the same code because they share the same validation and the same storage model.
Redis Cachecache · redis
Answers most redirects from memory; misses fall through to Cassandra.
Reads outnumber writes by two orders of magnitude and a small share of links takes most of the clicks, so an in-memory cache in front of the store turns the read path into a memory lookup for the hot set. Cache-aside keeps the cache optional: if it dies, the API still works, only slower.
Key Generation ServicesubSystem
Hands out unique short keys from batches generated ahead of time.
Generating a key on the request path means either hashing (and checking for collisions) or a counter (a single point of contention). Keys minted in advance and handed out in batches make key allocation a memory operation with no database round-trip and no collision check.
KGS Workerworker
Serves keys from an in-memory batch and refills it from the key pool.
Each worker claims its own batch of keys from the pool, so workers never coordinate on a request. A crashed worker loses the rest of its batch, which is a gap in the key space, not a duplicate.
Key Pool (SQL)db · sql
Stores the pre-generated random keys, with a flag for the ones already claimed.
A small relational table with a primary key is enough here: the pool is written in bulk offline and claimed in batches of 10,000 rows, and it is never on the redirect path.
URL Storage (Cassandra)db · nosql
Keeps every short key with its long URL, replicated three ways.
The data is a key-value lookup with no joins, written once and read many times, and it has to keep growing for years: a partitioned, replicated store with a native row TTL fits better than a single relational database that would need sharding by hand.
Analytics Stream (Kafka)messageBus · kafka
Buffers click events for analytics without blocking the redirect.
A click is recorded after the redirect has been sent, as a fire-and-forget event. The bus absorbs bursts and lets analytics fall behind during an incident without a single redirect waiting on it.
Analytics Workerworker
Aggregates click events into per-link counts and windows.
Counting in a stream processor keeps every write off the hot path and keeps the counts in a store built for aggregation, instead of incrementing a counter in Cassandra on every redirect.
Request paths
Open a short link
Load BalancerAPI GatewayAPI ServiceRedis Cacheon a missURL Storage (Cassandra)asyncAnalytics Stream (Kafka)Analytics Worker
Read path: a cache hit
- Someone opens a short link.
99% of the 4,000 requests a second are redirects: someone opened a short link. The load balancer passes them to the API gateway, which checks each address’s quota, and on to the 6 stateless API pods.
- Redis first.
The API looks the key up in Redis. 9 in 10 lookups are hits, answered straight from memory.
- Redirect.
The API answers with a redirect to the long URL. Because most lookups end in Redis, only about 400 of the 3,960 redirects a second ever reach Cassandra, which keeps the redirect p99 under its 50 ms target.
Read path: a cache miss
- A miss.
About 1 lookup in 10 isn't in Redis: a link nobody has opened lately.
- Read Cassandra.
The API falls back to Cassandra, about 4 ms a read. Misses add up to roughly 400 reads a second, well inside its 3,000 reads/s capacity.
- Fill the cache.
The API writes the URL back into Redis, so the next click on this link is a hit.
- Redirect.
The redirect goes out. A miss costs one extra database read, not a slow page.
Create a short link
Load BalancerAPI GatewayAPI ServiceKGS WorkerURL Storage (Cassandra)
Write path: creating a short link
- Validate the request.
About 1% of traffic creates links: roughly 40 writes a second out of 4,000 requests. The load balancer hands each one to the API gateway, which checks the caller’s quota, then to one of the 6 API pods, which checks the long URL and any custom alias.
- Grab a pre-generated key.
The API asks the Key Generation Service for a short key. Its workers hand out keys from batches already held in memory, so there is no collision check and no database round-trip on the request path.
- Persist to Cassandra.
The key and the long URL are written to Cassandra, and a replica has the row before the write is confirmed. Around 40 writes a second is far below the cluster's 2,000 writes/s capacity.
- Analytics on the side.
Events go onto Kafka and the analytics workers process them in the background. The client gets its short link back without waiting on any of it.
Try random keys
Load BalancerAPI GatewayAPI ServiceURL Storage (Cassandra)
How the design evolved
A link shortener for 150,000 users
4,050 requests a second at peak, 99 in 100 of them redirects. A redirect must answer within 50 ms at p99, and one scraper tries random keys to find links it was never given.
Stage 1
One server, one database
The first version is an API process and a database. Every redirect is a read from the store and every create is a write to it; the process generates keys itself. It works, and it stops working as soon as one process cannot keep up, because there is nothing to add.
breaks at 1,050 rpswhen redirect p99 latency < 50 ms stops holding$781/mo
Stage 2
Scale out the API behind a load balancer
The API keeps no state, so the fix for a saturated process is more processes behind a load balancer. That moves the bottleneck one hop back: every redirect is still a database read, and the store's read capacity is now the ceiling.
breaks at 1,700 rpswhen redirect p99 latency < 50 ms stops holding$1,445/mo
Stage 3
Put Redis in front of Cassandra
Because a small share of links takes most of the clicks, a cache-aside Redis in front of the store answers most redirects from memory and leaves the store serving misses. The read path now scales with the API tier, and the store is sized for a tenth of the reads.
breaks at 7,250 rpswhen redirect p99 latency < 50 ms stops holding$1,497/mo
Final design
Pre-generated keys, an analytics stream and a gateway
Three things were still wrong. Minting a key and counting a click were on the request path, where they did not belong: the Key Generation Service hands out keys from memory, and clicks go to Kafka after the redirect has been sent. And nothing stopped one client from taking everyone’s capacity: an API gateway in front of the API now limits opening links per address and creating links per key and in total. This is the design on the board.
Key decisions
How do we generate short keys?
Chosen
From a pool of keys generated ahead of time and handed out by the Key Generation Service. A key is unique by construction, unguessable, and costs the request one call into a worker's memory.
Why not
- Hash the long URL and truncate. Truncated hashes collide, so every insert needs a database check. The same URL always gets the same key, so users share links.
- An auto-incrementing counter. A single counter is a point of contention and a single point of failure. Its output is predictable, so every link can be enumerated.
- A random UUID. Unique and unguessable, but far too long to be a short link.
Source: Base62
Where does a redirect get answered?
Chosen
From a cache-aside Redis in front of Cassandra, filled on misses. Skewed click traffic makes the hot set small, so most redirects never reach the store, and the store is sized for misses.
Why not
- Read Cassandra on every redirect. The store would have to be sized for every read, and it would take every click storm on every viral link directly.
- Let the CDN cache permanent redirects. Cached redirects never reach the service, so clicks cannot be counted and a link cannot be repointed.
Which consistency level for writes and reads?
Chosen
LOCAL_QUORUM: a write is acknowledged by a majority of the replicas in the local data center, and a read waits for the same majority, so a freshly created link never reads as missing in the region that created it.
Why not
- ONE. Fastest, but a read can land on a replica that has not received the write yet and answer that the link does not exist.
- ALL. Every write waits for every replica, so one slow or dead replica stalls or fails writes.
Try the alternative in the simulator →
Source: Cassandra: dynamo-style replication and tunable consistency
How are clicks counted?
Chosen
As events published to Kafka after the redirect is sent, aggregated by a stream processor. The redirect never waits on analytics, and bursts are absorbed by the broker.
Why not
- Increment a counter in Cassandra on every redirect. Puts a write on the read path and doubles the load on the store during spikes. Hot links become write hot spots.
- Count on the client with a tracking beacon. Blocked by ad blockers and lost on cached redirects, so counts undercount unpredictably.
How do we stop one client from taking everyone’s capacity?
Chosen
An API gateway in front of the API, limiting opening links per address (redirects carry no key), creating links per API key, and creating links in total.
Why not
- No limits; size Cassandra for any load. Random keys miss the cache, so one scraper costs as much as thousands of people. Capacity for every abuser has no end.
- Limit inside each API pod. Each pod counts alone, so a client gets one quota per pod. A refused request has already cost a pod its work.
- Limit per address for everything. Creating links carries an API key, which identifies a customer far better than an address shared by a whole carrier.
Why pre-generate keys?
The key space
A short key is a string over the 62 characters a–z, A–Z and 0–9. Seven of them give 62⁷ keys, about 3.5 trillion, which is far more than any shortener will ever mint. The question is not whether keys exist but how to hand one out without two requests ever getting the same one.
Three ways to mint a key
| Approach | What it gives | What it costs |
|---|---|---|
| Hash the long URL | No state: the same URL always maps to the same key. | A truncated hash collides, so every insert needs a read to check, and two users shortening the same URL get one link they now share. |
| A counter | Unique by construction, trivially short. | One counter is a single point of contention and its output is guessable, so anyone can enumerate every link ever made. |
| Pre-generated keys | Unique by construction, unguessable, handed out from memory with no database round-trip on the request path. | A service to run, a pool to keep filled, and a used-key flag to keep honest. |
How the pool works
The Key Generation Service fills a relational table with random keys ahead of time. A worker claims a batch of 10,000 unused rows in one transaction, marks them used, and keeps them in memory, so two workers never fight over a row and the API only ever talks to a worker's memory. If a worker crashes, its remaining batch is lost: a gap in the key space, which nobody notices, rather than a duplicate, which everybody would.
Sizing the cache for skew
Includes stated assumptions
Most clicks land on few links
Click traffic is skewed: a small share of links takes most of the clicks, because links go viral and then fade. That skew is what makes a cache worth having. The cache does not need to hold every link ever made, only the ones being opened right now, and that hot set fits in the memory of a small Redis cluster.
What the hit ratio buys
Every hit is a redirect that never touched Cassandra. The store is sized for the misses, not for the reads, which is why the read path holds at a load the store alone could not serve. The Memory sizing calculator on the Redis node turns a key count and an average value size into the RAM the hot set needs; the estimates above turn the monthly volume into the reads per second the cache has to absorb.
When the skew turns against you
- A single viral link is a hot key: every shard but one sits idle while that one shard takes the click storm. Replicating hot keys or keeping them in the API's own memory spreads the load.
- When the cache restarts empty, every read is a miss until it warms up. A store sized for misses cannot take every read, which is the outage the scenario below plays out.
- Coalescing concurrent misses for the same key means one store read per key, not one per waiting request, which keeps a cold start from turning into a stampede.
Keeping analytics off the hot path
Record after redirecting
A redirect has to be fast; a click count has to be correct eventually. The API sends the redirect first and then publishes a click event to Kafka without waiting for an acknowledgement on the user's request. The stream processor consumes the events and keeps per-link counts in time windows, so a burst of clicks is smoothed by the broker instead of by the database.
Why not count in the database?
Incrementing a counter on every redirect would put a write on the read path and double the load on the store during exactly the traffic spikes analytics is supposed to measure. It would also make counts a source of contention on the hottest links.
The redirect code decides what you can count
A permanent redirect (301) is cached by the browser, so the second click on the same link never reaches the service and is never counted. A temporary redirect (302 or 307) costs a request every time but counts every click. A shortener that sells analytics uses the temporary form.
Who abuses a shortener, and what stops them
Two kinds of abuse
- **Guessing keys.** Short keys are short on purpose, so someone will try random ones to find private links. Random keys are never hot, so they all miss the cache and land on Cassandra.
- **Link spam.** Phishing campaigns create links by the thousand, filling Cassandra’s write capacity and the key pool, often from many accounts at once.
The gateway in front
Every request passes an API gateway before the API. Opening a link carries no API key, so the gateway counts it per address, generously enough for an office or a mobile carrier sharing one. Creating a link carries a key, so it is counted per key, and a cap over everyone catches a campaign spread across many accounts. A refused request costs the gateway a counter check, not a database read. How a gateway keeps those counts across its copies is the subject of the rate limiter design.
When everyone is honest
Limits do nothing when the load is real: a link that goes viral, or the cache dying. Then the question is what gives first. Shedding at the gateway, one of the fixes in Break It, drops scraping first and opening links last, so Cassandra keeps working for most people while capacity catches up.
What happens when it breaks
The cache dies at peak
Redis goes down; watch the retry storm take out Cassandra.
| Reading | Healthy | During the failure |
|---|---|---|
| p99 latency | 56.7 ms | 396 ms |
| error rate | 0% | 38.3% |
| throughput | 4,020 rps | 2,469 rps |
| cost | $2,847/mo | $2,847/mo |
- Handle 100M new URLs/month (~40 writes/s) at a 100:1 read/write ratio. (fails)
- Redirect (read) path p99 under 50 ms. (fails)
- No single client can take more than its share: a scraper or a spammer is refused before the API does any work. (still holds)
Cassandra is drowning in retries. What do you do first?
- Add backoff to API to DB retries.
Retries fall from ~7,700 to ~4,400 req/s, but Cassandra is still at ~280% of capacity and a third of requests keep failing. p99 climbs to ~1.2 s because retries now wait.
- Scale the API tier.
Twice the API pods, about +$745/mo, and nothing changes: Cassandra still takes ~11,700 req/s and 39% of requests fail.
- Add Cassandra read capacity.
Read capacity goes from 3,000 to 4,500 reads/s. Within 10 s the retries drain and errors drop below 1%, for about +$329/mo.
Losing Redis sent ~4,000 reads/s to a database sized for 3,000, and retries without backoff tripled that to ~11,700 req/s. Only more read capacity got above the real demand in time. Backoff trims the retries but can't replace the cache, and the API tier was never the bottleneck. The lasting fix is to stop one cache from being a single point of failure: an in-process L1 cache, coalesced misses, and backoff on every retry.
Trade-offs
Write consistency
| Option | Gain | Cost |
|---|---|---|
| LOCAL_QUORUMdefault | No stale reads in-region: every read and write waits for 2 of 3 replicas. | Slower reads and writes, since the coordinator waits for a second replica. |
| ONE | Fastest reads and writes: the first replica to answer wins. | Possible stale reads while replicas catch up. |
Fixes and what they cost
| Fix | What it does | Trade-off |
|---|---|---|
| Exponential backoff on API to DB | Spacing retries out stops them from multiplying load during an overload. | Failing requests take longer to give up, so users wait longer before seeing an error. |
| Double API pods | More API capacity. It only helps if the API is the bottleneck. | Costs more per month, and does nothing unless the API is the bottleneck. |
| Coalesce cache misses | Concurrent misses for the same key share one DB read, which prevents a thundering herd. | Requests for the same key wait for the first database read to come back. |
| Add a Cassandra node | More read capacity, at a real cost per month. | Costs a full database node per month, and one more node to operate. |
| In-process L1 cache in the API | Each API pod keeps its hottest redirects in memory. About 70% of lookups never leave the pod, so losing Redis no longer sends every read to Cassandra. | Each API pod can serve a slightly stale redirect, and uses more memory. |
| Pre-warm Redis before it takes traffic | A restarted or flushed Redis loads 90% of the hot set from a snapshot before it serves. It takes effect on the next flush or restart, so the cold-cache stampede never starts. | A Redis restart takes longer while the snapshot loads. |
| Autoscale API pods for the spike | Six times the API pods absorb a viral spike, at a real cost per month. Cassandra and the key service now take the extra load, so watch them next. | A very large monthly bill, and the other tiers still have to keep up. |
| Shed load at the gateway to protect Cassandra | While Cassandra is past 85%, the gateway drops requests itself: random-key scraping first, new links next, opening links last. | Shed requests are real people getting an error. With the cache down it holds Cassandra at 85% and ends the retry storm, but about a third of redirects and every new link get a fast error instead of a slow one. It keeps Cassandra working; it cannot replace the capacity it is missing. |
| Remove the per-address limit on opening links | Every address can open as many links as it likes. | One scraper trying random keys sends every attempt to Cassandra. |
Interview questions
Why not just hash the long URL to get the short key?
Because a hash long enough to be unique is not short, and a hash short enough to be a link collides. A truncated hash needs a database check on every insert to catch collisions, which puts a read on the write path, and it maps the same URL to the same key for everyone, so two users end up sharing a link and its analytics. Pre-generated keys are unique by construction and cost nothing on the request path.
What happens if two users shorten the same long URL?
They get two different short links. Each create request takes its own key from the Key Generation Service; nothing about the long URL feeds into the key. That keeps per-link analytics and per-user ownership separate, at the cost of storing the long URL twice.
Should the redirect be a 301 or a 302?
Use a temporary redirect (302 or 307) if you need to count clicks: the browser asks the service every time. A permanent redirect (301) is cached by the browser, which saves a request on repeat clicks but makes them invisible to analytics and browsers that cached it keep going to the old target even after the link changes.
Source: Redirections in HTTP
How long should a short link live?
Links expire by a row TTL in Cassandra, so expired rows disappear without a cleanup job. A default lifetime with an optional expiry on creation covers most products; links that must live forever are a policy choice, and their storage growth is what the disk calculator on the Cassandra node estimates.
Why Cassandra rather than a relational database?
The data is a single-key lookup with no joins that grows without bound and must stay available when a node dies. A partitioned, replicated store gives that without hand-built sharding, and a native row TTL handles expiry. A relational database works at small scale and is a fine first version; it is the point where sharding becomes your job that argues for Cassandra.
Source: Cassandra: dynamo-style replication and tunable consistency
What happens when Redis dies?
Every redirect becomes a cache miss and goes to Cassandra, which is sized for the misses, not for all reads. Reads queue up, time out, and the API retries them, so the load on the store grows exactly when it can least take it. The scenario on this page plays that out with the numbers, and the fixes that hold up are the ones that stop one cache from being a single point of failure: an in-process cache in the API, coalesced misses and backoff on retries.
Source: Cache stampede
How does a URL shortener stop abuse?
With limits at an API gateway in front of the API: opening links is limited per address, because redirects carry no API key, and creating links per key and in total. Random-key scraping matters most, because random keys miss the cache and every one that gets through is a database read.
Sources
- Redis benchmarks
- Base62, Wikipedia
- Cache stampede, Wikipedia
- Cassandra: dynamo-style replication and tunable consistency, Apache Cassandra
- Redirections in HTTP, MDN Web Docs