A cache tier of N nodes sits behind a proxy that picks a node with hash(key) mod N. What happens to the hit rate when one node is removed, and how does consistent hashing change the outcome?

## Why modulo hashing is fragile `hash(key) mod N` is attractive because it is stateless: any proxy can compute the owner with no coordination. The flaw is that the divisor is the fleet size. Change N and you change the arithmetic for every key at once. Going from four nodes to three, only keys whose hash happens to give the same index under both moduli stay put — empirically about a quarter of them; roughly three quarters move. Every moved key is a guaranteed miss on the new owner, plus a stranded copy on the old one. The operational shape of that is worse than the number suggests. Node loss is usually not a calm event: you lose a node because it crashed or was drained, and the cache tier exists precisely because the origin cannot serve full traffic. Now the origin receives a near-total miss storm while it is already unhappy, every node begins filling with keys it does not have, and memory pressure evicts keys that were still valid. Adding a node is the same event with the same cost — which is why teams with modulo hashing quietly stop resizing their cache tier at all. ## The ring Consistent hashing puts nodes and keys into one circular keyspace, for example the range of a 32-bit hash. Each node is hashed to a position on the circle; each key is hashed to a position too, and belongs to the first node encountered walking clockwise. Lookup is a binary search over the sorted node positions. The crucial property: a node's ownership is defined by *its neighbours on the ring*, not by the total count. Remove a node and only the arc between it and its predecessor changes hands, passing to the next node clockwise. Every other key's answer is unchanged. Add a node and it takes a slice out of exactly one successor. The share that moves is about 1/N — the minimum possible, since those keys had to move somewhere. ```python import bisect, hashlib def h(s): return int(hashlib.md5(s.encode()).hexdigest()[:8], 16) # one node at one ring position gives very uneven arcs; # hashing each node under many labels evens them out positions = sorted(h(f"node{i}#{v}") for i in range(4) for v in range(100)) print(bisect.bisect(positions, h("cart:42")) % len(positions)) ``` ## Virtual nodes, and why a naive ring is not enough With one ring position per node, arc sizes are the gaps between random points: highly variable, so one node can own several times another's share. Worse, when a node leaves, its *entire* arc lands on a single successor — which may already be the largest owner — so removing one node can double another's load and take it down too. The fix is virtual nodes: hash each physical node under many labels (`node2#0`, `node2#1`, …), typically 100–200 positions per node. Arcs become numerous and small, so the law of large numbers evens out each physical node's total share, and a departing node's many small arcs are spread across all remaining nodes instead of one. Virtual nodes also give you weighting for free — a machine with twice the memory simply gets twice as many positions. ## What consistent hashing buys, and what it costs It buys **locality**: the same key reliably reaches the same node, so per-node caches stay warm, an in-memory index or shard stays on the node that owns it, and rate-limit or session counters can be kept locally without a shared store. It buys **graceful membership change**: scale-out, scale-in and node loss cost about 1/N of the cache instead of all of it. What it costs is load-awareness. Routing is now a function of the key, not of how busy the target is, so a genuinely hot key — one product on the front page, one large tenant — saturates its owner while the rest of the ring idles, and no amount of balancing helps because every request for that key is required to go to that node. Mitigations exist (replicate hot keys across a few successors, add a bounded-load rule that spills to the next node when the owner is over a threshold, or fall back to a load-based algorithm for keys detected as hot), and interviewers like to hear that you know hashing and load-awareness are in tension rather than a free upgrade. The other cost is state: every proxy must agree on the ring, so membership changes have to propagate. Two proxies with different views route the same key differently, which for a cache means a duplicated entry and for a stateful shard can mean a correctness problem — which is why sharded stateful systems put ring membership behind a consensus mechanism rather than letting each proxy guess.