Distributed Caching (+ Consistent-Hashing Intuition)

Your cache has been the hero of this whole chapter — soaking up reads, shielding the database, hiding every latency sin. And then, quietly, it starts running out of itself. The working set no longer fits in one machine's RAM, so eviction is throwing out keys that are still hot. One Redis process — single-threaded, one network card — is maxing a CPU core while the box's other fifteen sit idle. And after last lesson, one number should genuinely scare you: if this one box dies, one hundred percent of your cache goes cold at once — the full stampede, aimed at your database.

So you do the obvious thing, the same move this course keeps teaching: scale out. Not one cache box — a fleet of them, splitting one keyspace across many nodes. More RAM in total, more cores, more network — and if one node dies, only a slice of the cache goes cold instead of all of it. The blast radius shrinks from "everything" to "one-Nth of everything."

But the moment there's more than one node, every single read and write faces a question that simply didn't exist before: which node owns this key? When you GET product:8841, which of the four boxes do you ask? Get that answer wrong and the cache might as well be empty — the data's on node 2 and you're asking node 3.

That routing question sounds trivial. It is not. The obvious answer contains a booby trap that has taken down real systems at the exact moment their engineers tried to make things better — and the fix is one of the most elegant ideas in distributed systems, invented in 1997 for precisely this problem: a fleet of web caches.

Scope: how keys find their node, why the naive way explodes, and the intuition for the fix. The full machinery — virtual nodes, load balance, the production-grade ring — gets its own dedicated lesson later, when we shard databases. And keeping cache nodes replicated and failing over is a reliability-chapter story.

How should ten thousand clients, hitting four cache nodes, all agree on which node holds product:8841 — without asking anyone?

Your first instinct might be a lookup table — a little directory service mapping every key to its node. Squash it: now every cache read pays an extra network hop to consult the directory, the directory itself becomes a single point of failure, and it has to track millions of keys. The whole point of a cache is speed; a directory in the read path is a tollbooth.

The actual answer is prettier: compute it. Hash the key — the same trick hash tables have always used — and map the hash to a node:

node = hash("product:8841") % N (N = number of cache nodes)

Every client runs the same tiny formula and lands on the same node, deterministically, with zero coordination. No directory, no lookup, no chatter. A good hash scatters keys evenly, so each of your N nodes carries roughly 1/N of the keyspace and 1/N of the traffic. It's stateless, it's instant, and it's beautifully uniform.

And it has a flaw so deep that an entire field of research exists because of it. Did you spot it? The formula contains N — the number of nodes. Every key's home address is coupled to the size of your fleet. Keep that thought.

Black Friday is coming. Your three cache nodes are running warm, so you do the responsible thing and add a fourth. The deploy is clean. N changes from 3 to 4. And your hit rate falls off a cliff.

Here's why. A key that hashed to 173 lived on node 173 % 3 = 2. The instant N becomes 4, every client computes 173 % 4 = 1 and looks for it on node 1. The data still exists — sitting uselessly on node 2 — but nobody will ever look there again. That key is now a miss. And it's not one unlucky key: change the modulus and three out of every four keys change owners. In general, going from N to N+1 nodes remaps N/(N+1) of your entire keyspace — 75% at 3→4, 80% at 4→5, and a spectacular 92% at 12→13. The bigger your fleet, the worse it gets.

Now connect it to last lesson, because this is exactly the shape you already know: every remapped key is a miss, so adding that fourth node just turned three-quarters of your cache cold in one instant — a self-inflicted, fleet-wide version of the cold-start stampede. The miss storm slams the database — at the precise moment you added capacity because load was already high. You reached for the fire extinguisher and it sprayed gasoline.

And it cuts both ways: you don't have to add a node. When a node dies at 2 a.m., N drops by one, and mod-N gleefully remaps almost the entire keyspace — turning one node's failure into everyone's cold cache. That's the fatal property in one sentence: with mod-N, the size of the change doesn't matter; any change reshuffles everything. What we want instead is obvious to say and non-obvious to build: a scheme where adding or losing one node moves only the keys that have to move — about 1/N of them — and leaves everyone else's home alone.

Numbers like "75% remapped" are easy to nod at and easy to underestimate. Watch it happen to your keys instead.

Below are sixty keys, colored by which node owns them, routed two ways at once with the same fleet: naive hash % N in the top lane, and a consistent-hashing ring in the bottom lane. You control the fleet.

Do this:

1. Click ＋ add node. In the mod-N lane, watch nearly every key flash — each flash is a key whose owner just changed, which means a cache miss on its next read. The DB miss-storm bar spikes past capacity: that's the stampede from last lesson, and you caused it by scaling up. Meanwhile the ring lane, given the exact same event, flashes only a small fraction — the new node claiming its fair arc — and the database barely stirs.
2. Now click − remove node (pretend it crashed at 2 a.m.). Same asymmetry: mod-N reshuffles almost everything again; the ring only re-homes the dead node's own keys, handing them to its clockwise neighbor.
3. Do it at different fleet sizes and watch the counters — mod-N moves N/(N+1) of everything while the ring moves about 1/(N+1), so the gap widens as your fleet grows: 3× fewer moves at three nodes, 12× fewer at twelve.

One honest caveat while you play: with each node as a single point, the ring's arcs come out lumpy — some nodes own more than their share. Hold that thought; it's the cliffhanger this lesson ends on.

What you just watched in the bottom lane is consistent hashing, and the intuition fits in three sentences.

Take the whole range of possible hash values and bend it into a circle. Hash each node onto that circle — each gets a position, like houses on a circular street. Hash each key onto the same circle, and give it one rule: walk clockwise; the first node you meet is your home.

That's the entire trick — but look at what it buys. When you add a node, it lands somewhere on the circle and claims exactly the keys between itself and the previous node counter-clockwise — its "arc." Those keys — roughly a fair 1/N share — move to the newcomer. Every other key's clockwise walk is completely unchanged. When a node dies, only its keys move — they just keep walking clockwise to the next survivor. Nobody else even notices.

Compare the two schemes at their cores: mod-N couples every key's home to the total count N, so any change anywhere reshuffles everyone. The ring couples each key only to its local neighborhood on the circle, so a change moves exactly the keys in the affected arc and nothing else. The remap cost stops being proportional to your fleet and becomes proportional to the change.

This idea — published by David Karger and colleagues at MIT in 1997, invented for exactly our problem, a fleet of web caches — is one of those rare algorithms that quietly runs the internet: cache clients, CDNs, load balancers, and half the distributed databases you'll meet in this course.

Now, that lumpy-arcs caveat from the sim: one point per node makes uneven slices — bad luck can hand one node a triple share, and a hot slice makes a hot node. The classic fix is to give each node many points on the ring ("virtual nodes"), which evens everything out — and the mechanics of that, plus the production-grade ring, is precisely the Consistent Hashing deep-dive waiting for you in the data-systems chapter. Here, the intuition is what matters: move only what must move.

Someone has to run that hash-and-route step on every request. In practice it lives in one of three places — and you've almost certainly used all three without noticing.

In the client. Every application server holds the node list and hashes keys itself. This is Memcached's classic model — there is no "Memcached cluster," just independent nodes and smart clients — and it's why libketama (built at Last.fm in 2007, still the name you'll see in configs) put consistent hashing into the client library; Etsy famously runs its whole memcached fleet this way. Zero extra hops, maximum speed — but every client must agree on the node list, or two servers will route the same key differently.

In a proxy. Put a small router in front — clients speak to one endpoint, and the proxy (Twitter's twemproxy is the classic) does the hashing and fan-out. Clients stay dumb and config lives in one place, at the cost of one extra network hop and a component you must keep alive.

In the cluster itself. Redis Cluster bakes routing into the servers — and does something worth pausing on: it deliberately does not use consistent hashing. Instead, the keyspace is pre-chopped into exactly 16,384 slots (slot = CRC16(key) mod 16384), and each node owns a range of slots. Scaling means migrating whole slots — thousands of keys as one movable unit — from node to node; keys never re-hash, because a key's slot never changes. Clients learn the slot→node map once and go direct (a node answers MOVED if you ask the wrong one). It's a different route to the same destination: decouple key placement from node count, so change moves only what must move. And it hands you a myth-buster for interviews: "Redis Cluster uses consistent hashing" is false — it uses fixed hash slots, and knowing the difference is exactly the kind of precision that reads as real experience.

One catch survives every routing scheme in this lesson, and it's worth naming before the chapter moves on: hashing balances key placement, not load.

Remember why caching works at all — Zipf. A few keys get monstrous traffic. Hashing will dutifully place your viral sneaker listing on exactly one node… and now that node takes the viral traffic alone. Perfectly even key counts, wildly uneven work: one box pegged at 100% CPU (worse in Redis, where a single thread does everything) while its neighbors nap. That's a hot shard — and no amount of clever hashing fixes it, because the imbalance is in the traffic, not the placement.

The escape hatches all share one shape — spread the hot thing itself: replicate the hot key to several nodes and pick one at random per read; serve it from local in-process cache in front of the fleet; or "smear" it — Etsy's trick — by writing the same value under several suffixed keys (sneaker:1, sneaker:2, …) so the hash scatters the copies. Each buys throughput with a little staleness or memory.

File the principle, because it returns with force when we shard databases: uniform placement is not uniform load — and hot partitions are one of the defining fights of data systems.

• "hash % N spreads keys evenly — done." Evenly today. The layout is coupled to N itself: add or lose one node and N/(N+1) of all keys change homes. Uniform placement, catastrophic re-placement.
• "Adding cache capacity can only help." Naively routed, adding a node cold-starts most of your cache at the moment of highest load — the self-inflicted stampede. Capacity changes are exactly when routing schemes earn their pay.
• "Redis Cluster is consistent hashing." It isn't — it's 16,384 fixed slots with slot migration. Same goal (move only what must move), different mechanism, and the distinction is a genuine signal of depth.
• "Consistent hashing balances the load." It minimizes movement. Single points make lumpy arcs (virtual nodes fix that — next chapter), and no hashing scheme fixes a hot key: placement ≠ load.
• "We need a directory service to find keys." You almost never do: the hash is the directory — or the slot map is, learned once. Adding a lookup hop to every cache read defeats the cache.
• "One cache node dying is a small event." Under mod-N it isn't — N changed, so everything reshuffles. A routing scheme decides whether a failure costs you 1/N of your cache or all of it.

• One cache box has three ceilings — RAM, throughput, and blast radius — and a fleet fixes all three, at the price of one new question on every request: which node owns this key? The answer is computed, not looked up: the hash is the directory.
• hash % N is a booby trap. It couples every key's home to the fleet size, so any change — scale-up or 2 a.m. failure — remaps N/(N+1) of the keyspace and self-inflicts a cold-cache stampede (the exact disaster from last lesson, triggered by adding capacity).
• Consistent hashing moves only what must move: nodes and keys share a circle, keys walk clockwise, and a change touches only the affected arc — about 1/(N+1) instead of N/(N+1), a gap that grows with fleet size. Born in 1997 for web caches; runs half the internet.
• The hash lives in one of three places — smart clients (memcached + ketama), a proxy (twemproxy), or the cluster itself (Redis Cluster: 16,384 fixed slots, migrating slots not keys — deliberately not consistent hashing).
• Placement ≠ load: a hot key makes a hot shard under any scheme — replicate, front-cache, or smear it.

Two threads now dangle on purpose: lumpy arcs (virtual nodes) get their full treatment in the Consistent Hashing deep-dive next chapter, and hot partitions return when we shard databases.

Next — CDNs: Caching at the Edge. We've been shrinking the distance between your data and your servers. Time to shrink the distance between your data and the planet: the world's largest distributed cache, with nodes in hundreds of cities — and the same questions of routing, freshness, and stampedes at global scale.