The whole design, in writing
Learn system design by building a distributed cache like Redis or Memcached step by step. An interactive guide covering cache-aside, consistent hashing across nodes, eviction and TTL, replication, invalidation, and surviving cache stampedes and hot keys.
Every step of the build above, written out: the problem each piece solves, the option that was taken and the ones that were not, the numbers, and how it fails in production.
The big idea
What is a distributed cache?
Your database is the slowest, most precious resource you own, and the same handful of rows get read thousands of times a second. Asking it the same question over and over is both slow for users and an expensive way to melt your database.
Keep the hot answers in RAM, in front of the database — and spread that RAM across many nodes so it’s bigger than any one machine and survives a node dying. The art is keeping it fast, fresh, and resilient when things fail.
What the new pieces do
- App Serverclient
- A service that reads the same data far more than it changes — a user profile, a product, a session. Hitting the database every time is wasteful and slow.
Step 1 · The pattern
Cache-aside
The app needs a value. Where does it look first, and what happens when the cache doesn’t have it yet? Get this dance wrong and you either serve stale data or never actually offload the database.
The app needs a value that’s usually cached. What’s the read/miss dance?
If you read the DB every time, you never offload it — the cache only absorbs writes, not reads. The point is to answer hot reads without touching the database.
Cache-aside: a hit returns in <1ms, a miss falls through to the DB and writes the value back for next time. Only requested data gets cached, so memory holds what’s genuinely hot.
Eagerly caching everything wastes memory on cold data that’s never read, and the whole dataset won’t fit in RAM anyway. Populate lazily, on demand.
Use cache-aside: the app asks the cache; on a hit it returns instantly, on a miss it reads the database, then writes the value back into the cache for next time. The app owns the logic; the cache stays a dumb, fast key-value box.
- <1mscache hit
- ~99%hit rate target
- lazypopulation
What the new pieces do
- Cache Clientbackend
- A thin client library (or proxy) that decides which cache node holds a key and talks to it. The app just calls get/set; the routing is invisible.
- Databasestore
- The slow, durable backing store. The cache exists to shield it: a cache miss falls through to here, then the value is written back to the cache.
- Cache Node Acache
- An in-memory shard. Sub-millisecond gets and sets because it never touches disk — the whole point is to keep hot data in RAM.
Back of the envelope
- 99% hit ⇒ 1% reaches DB
- a ~100× reduction in database read load
- hit ≈ <1ms RAM
- vs ms–10s of ms for a DB query
- first read misses, rest hit
- lazy population keeps only hot data
Step 2 · Bigger than one box
Shard with consistent hashing
One cache node is capped by its RAM and network card. Add nodes naively with hash(key) % n and changing n remaps nearly every key — a mass cache miss that stampedes the database the instant you scale.
One node’s RAM is full. You add nodes — how do you map keys so scaling doesn’t stampede the DB?
Changing n remaps nearly every key — a mass cache miss the instant you scale, stampeding the database. Modulo couples every key to the exact node count.
Adding or removing a node moves only the keys in one arc (~1/N), so scaling disturbs a small slice and the database stays shielded from a thundering herd.
A key→node directory for a huge keyspace is itself a hot, memory-heavy bottleneck and a new failure point. The ring computes ownership from the hash — no table needed.
Put nodes on a hash ring. Each key maps to the next node clockwise, so adding or removing a node only moves the keys in one arc — a small fraction. The Cache Client hashes the key and talks straight to the owning node.
- 1/Nkeys moved on change
- O(1)key → node
- linearcapacity growth
What the new pieces do
- Hash Ringservice
- Maps keys and cache nodes onto a circle so each key has a home node. Adding or losing a node reshuffles only a small slice of keys, not all of them.
- Cache Node Bcache
- Another shard holding a different slice of the keyspace. More nodes means more total memory and more aggregate throughput.
- Cache Node Ccache
- A third shard. Consistent hashing spreads keys evenly across A, B and C so no single node becomes the bottleneck.
Back of the envelope
- add/remove node ⇒ ~1/N keys move
- vs ~all keys with hash % n — a miss storm
- key → node = O(1) hash
- computed in the client, no directory
- N nodes ⇒ N× RAM + throughput
- capacity grows linearly
Step 3 · Finite memory
Eviction & TTL
RAM is small and the dataset is huge — the cache will fill up. Which entries do you drop to make room, and how do you stop values from lingering forever after they’ve gone stale?
RAM is finite and the dataset is huge — the cache will fill. What do you drop, and how do you bound staleness?
Refusing to cache new hot data means the cache stops adapting to what’s popular now. You must make room by evicting, not by freezing the contents.
A full flush turns every key into a miss at once — a self-inflicted stampede. Evict individual cold entries, never the entire cache.
TTL bounds staleness; LRU (drop least-recently-used) or LFU (favor enduring popularity) bounds size. The cache becomes a self-managing window onto the hottest data.
Give each entry a TTL so it self-expires, and when memory is full, evict by policy: LRU (drop least-recently-used) suits most workloads; LFU favors enduring popularity. The cache becomes a self-managing window onto the hottest data.
- LRUdefault policy
- TTLbounds staleness
- evicton memory pressure
Step 4 · Don’t lose a shard
Replication & failover
If a cache node dies, its entire slice of keys instantly becomes misses — and all that traffic slams the database at once. A cache that amplifies failure into a database outage is worse than no cache.
A cache node dies and its whole slice of keys becomes misses at once. How do you stop a DB meltdown?
A dropped shard’s worth of simultaneous misses can take the database down — the cache would be amplifying its own failure into an outage. You must keep the shard alive.
A primary serves while replicas stay in sync; on death a replica is promoted so the shard’s keys survive and the DB is shielded. Async replication is usually fine — losing a few recent sets beats a full-shard blackout.
Full mirroring throws away the capacity win of sharding — you’re back to one machine’s RAM. Replicate each shard a couple of times, not the whole dataset everywhere.
Replicate each shard: a primary serves traffic while one or more replicas stay in sync. On failure, a replica is promoted, so the shard’s keys survive and the database is shielded from a sudden miss storm.
What the new pieces do
- Replicationservice
- Each shard has a primary and one or more replicas. If a node dies, a replica takes over so a chunk of the cache doesn’t vanish and stampede the database.
Step 5 · Stay fresh
Invalidation
The moment the database changes, every cached copy of that value is wrong. Serving a stale price or a deleted post erodes trust — but eagerly clearing everything defeats the cache.
The DB changes and every cached copy is now wrong. How do you keep the cache fresh?
Perfectly updating every cached copy on every write is the famously hard problem — racy and complex. Prefer dropping keys over trying to keep them perfectly in sync.
TTL alone means you knowingly serve stale data for the whole window — bad for prices or deleted posts. TTL is the backstop, not the primary freshness mechanism for write-sensitive data.
A write emits an invalidation; the next read repopulates. For data that can’t be stale, write-through updates cache and DB together. TTL remains the safety net if a message is missed.
On a write, publish an invalidation message so the relevant cache nodes drop the key (and the next read repopulates it). For writes you can’t afford to be stale, use write-through (update cache and DB together); otherwise lean on TTL + invalidation.
What the new pieces do
- Invalidation Busbus
- When the database changes, a message tells cache nodes to drop the stale key. Keeps the cache from confidently serving yesterday’s value forever.
Step 6 · The stampede
Surviving a thundering herd
A popular key expires. In the same millisecond, a thousand requests all miss, all hit the database for the same value, and all try to recompute it — a cache stampede that can take the database down.
A hot key expires and 1,000 requests miss it simultaneously. What stops them all hitting the DB?
A bigger DB is expensive and still gets N identical recompute requests in the same millisecond. The fix is to not send N requests, not to survive them.
A per-key lock / request coalescing ensures N simultaneous misses produce one recompute, not N. Jittering TTLs stops keys expiring together, and hot keys can refresh before expiry.
Longer TTL just delays the stampede and increases staleness meanwhile — when it finally expires, the herd still hits at once. You need to coalesce the misses, not postpone them.
Let only one request rebuild a missing key while others wait or serve a slightly stale value: a per-key lock or request coalescing. Add jittered TTLs so keys don’t all expire together, and optionally refresh hot keys before they expire.
Back of the envelope
- 1,000 misses in 1ms
- without coalescing ⇒ 1,000 DB hits for one value
- single-flight ⇒ 1 recompute
- the other 999 wait or serve slightly stale
- TTL + jitter
- keys don’t all expire on the same tick
Step 7 · Hot keys & writes
The sharp edges
Consistent hashing assumes keys are roughly equal, but one celebrity key (a viral post) can overwhelm its single owning node. And write-heavy data forces a choice about how cache and database stay in step.
For hot keys, replicate the key across nodes or add a tiny local in-process cache so one shard isn’t crushed. For writes, pick a policy: write-through (consistent, slower) or write-back (fast, risk of loss). Match the policy to how much staleness the data tolerates.
You did it
You just designed a distributed cache.
Everything you assembled, in order
- Cache-aside: hit returns instantly, miss falls through to the DB and backfills.
- Consistent hashing shards across nodes, moving only ~1/N keys on change.
- TTL bounds staleness; LRU/LFU eviction bounds memory.
- Per-shard replication and failover so a dead node never stampedes the DB.
- Invalidation (and write-through) keep cached values fresh after writes.
- Single-flight rebuilds + jittered TTLs defeat cache stampedes.
- Hot-key replication and a chosen write policy handle the sharp edges.