System designMedium17 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,000 rps
- redirect p99 latency
- 43 ms
- cost
- $2,774/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.
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
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.
Browsers cache a permanent redirect, which saves a request on the next click but hides it from analytics. The redirect code is therefore a trade-off the web client carries, not the server.
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 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 owns a range of 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 keys and which ranges are taken.
A small relational table with a primary key is enough here: the pool is written in bulk offline and read in ranges, 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 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 spreads them over 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 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 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.
How the design evolved
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 and an analytics stream
Two things were still on the request path that did not belong there: minting a key and counting a click. The Key Generation Service hands out keys from memory, and clicks go to Kafka after the redirect has been sent. 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 datacenter, 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.
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 and marks each one used when a worker takes it. Workers take keys in batches and own a numeric range each, 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.
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 | 55.2 ms | 395 ms |
| error rate | 0% | 38.3% |
| throughput | 4,000 rps | 2,469 rps |
| cost | $2,774/mo | $2,774/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)
Cassandra is drowning in retries. What do you do first?
- Add backoff to API to DB retries.
Retries fall from ~7,600 to ~4,300 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,600 req/s and 38% 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 ~3,960 reads/s to a database sized for 3,000, and retries without backoff tripled that to ~11,600 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. |
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 makes it impossible to change where a link points later.
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
Sources
- Redis benchmarks
- Base62, Wikipedia
- Cache stampede, Wikipedia
- Cassandra: dynamo-style replication and tunable consistency, Apache Cassandra
- Redirections in HTTP, MDN Web Docs