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.
Why this piece earns its place
Cache-aside quietly assumes every key has a value. A lookup that misses falls through to the database, and if the database has nothing either, there is nothing to write back — so the next identical request misses too, and so does the one after it. For a normal key that costs one slow read. For an id that does not exist it costs every read forever, and a client looping over ids it invented, or a crawler walking a deleted range, goes straight through the cache into the database as if the cache were not there. Nothing looks broken, either: each one is just a miss falling through, indistinguishable on a dashboard from the ordinary first read of a cold key — the only tell is that these keys never populate, so the same ids miss again tomorrow. The fix is to cache the absence — a short-lived negative marker that is distinguishable from “no entry”, so a miss on a missing row still shields the database. Give it a far shorter TTL than a real value, since a key that starts existing should become visible in seconds, not hours. Where the keyspace is enumerable, a membership filter in the client rejects impossible keys before a round trip happens at all.
- <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.
Why this piece earns its place
Putting each node on the ring once sounds right and distributes badly: three random points cut a circle into three very unequal arcs, so one node can own a multiple of another’s keys while the dashboard reports a cluster of identical machines. The knob this step really introduces is virtual nodes. Hash each physical node onto the ring many times, so its ownership is the sum of many small arcs and averages out, and when a node leaves its share is absorbed by every survivor rather than dumped on the one neighbour clockwise of it. Set it in the hundreds per node: too few and the imbalance is back, too many and the ring itself grows — every client holds a copy, every membership change rebuilds it, and lookups walk a longer structure for nothing. The ring also assumes every client agrees on membership, and during a change they do not. A client with a stale view reads the old owner, misses, and writes its value there; that is survivable only because the database is the source of truth and the orphaned copy expires on its own.
- 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.
Why this piece earns its place
The policy is the part everyone debates and the ceiling is the part that pages you. Eviction only begins when the node believes it is full, which is a limit you configure, and the right value is not the box’s RAM. The process also holds per-key metadata, replication and client buffers, and fragmentation, so the memory it occupies is bigger than the sum of the values you stored — and expiry is usually lazy, sampled rather than swept, so entries already past their TTL keep holding memory until something looks at them. Set the ceiling too close to physical RAM and the kernel kills the process instead of the cache evicting a key, which turns a memory problem into a lost shard and the miss storm of the next step. Set it far too low and you evict warm data the workload was about to ask for, and the hit rate sags with no obvious cause. Leave real headroom, alarm on the eviction rate rather than on used bytes, and remember the LRU you get is approximated from a handful of sampled candidates, not a true global ordering.
- 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.
Why this piece earns its place
Replication is the easy half; deciding a node is dead is the hard one, and the failover this step adds is itself something that can fire wrongly. A node that is alive but stalled — a long pause, a saturated network card, a partition only some observers can see — looks exactly like a dead one from outside. Promote on a single observer’s opinion and you can end up with two nodes each believing they are primary for the same shard, serving different values for the same key to whichever clients can reach them. Because the database stays the source of truth that is a staleness bug rather than data loss, which is the one mercy here. Still, the promotion decision belongs to a quorum of separate observers, and the old primary should be fenced — demoted and made to refuse writes — before the new one takes traffic. The detection window is the knob: too short and a brief pause flaps the shard, moving keys and throwing away a warm node’s contents for nothing; too long and you are sitting in the exact miss storm replication was bought to prevent.
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.
Why this piece earns its place
Order the write and the invalidation the wrong way round and this makes staleness permanent instead of preventing it. Publish the drop message before the database commits, and a reader that misses in that gap loads the pre-commit value and writes it back after the message has already been applied. The cache is now confidently wrong and no further message is coming, because the write that would have triggered one has already happened. So the invalidation goes out after the commit, never before. A narrow window still remains, since a reader can be holding a value it read microseconds before the commit and backfill it just after the drop; where the data is worth the effort a second, delayed delete closes it, and where it is not, the TTL from step 3 is what bounds how long the wrong value survives. Prefer dropping the key to updating it in place for the same reason: two concurrent writers updating a cached value can land in either order, while two deletes cannot disagree about anything.
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.
Why this piece earns its place
Coalescing only counts the misses it can see. A single-flight lock inside one process stops that process from sending a thousand requests, but the thousand requests arrived across a fleet of app servers, so a per-process lock still yields one database read per server — quieter, and still a herd. Making it genuinely one recompute means the lock lives in the cache itself, taken on a key nobody else owns, which means it is a lock held over the network by a process that might die holding it. So it gets a lease that expires rather than being held until released, and the waiters need an answer for the moment that lease runs out. Falling through re-creates the stampede on a delay, so the better default is to keep serving the expired value for a grace period while one holder rebuilds. That needs an entry to outlive its own TTL — a soft expiry marking a value as due for refresh and a hard one that removes it — which is also exactly what lets a hot key be refreshed before anybody misses it.
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.
Why this piece earns its place
Both hot-key fixes work by making more copies of a value, and every copy is something the invalidation of step 5 now has to reach. Replicating a key across nodes is the manageable version: the client has to know this key is special and pick a copy at random, and the drop message has to go to all of them rather than to the single owner the ring would have named. The in-process local cache is the dangerous one, because it is invisible — no message reaches it, no operator can inspect it, and every app server holds its own slightly different idea of the value. The only thing bounding it is time, so its TTL is measured in seconds, deliberately far shorter than the cluster’s, and it is reserved for data where a few seconds of disagreement between two servers is genuinely fine. That is the real decision under the write policy too: write-through and write-back are not a performance preference, they are an answer to how much staleness or loss this data tolerates — and a viral post and an account balance do not get the same answer.
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.