When 87% of Your Cache Vanishes

You run a cache cluster with 4 Redis nodes. Every key hashes to hash(key) mod 4, spreading evenly. At midnight on a Tuesday, traffic spikes. You spin up a fifth node, update the client, and switch to mod 5. Within seconds, your database goes on fire—thousands of queries per second that should have cached now miss. You add a sixth node hoping to spread load. It gets worse. By 2 AM you’ve rolled back, killed the new nodes, and reverted to mod 4. This is the cache-wipe catastrophe, and it has brought down real services.

Left: hash(key) mod N breaks catastrophically when N changes. Right: consistent hashing distributes keys to the next node clockwise on a ring.

The Modulo Hashing Trap

Modulo hashing is so obvious it’s taught first. nodeId = hash(key) mod N. It’s uniform—keys spread evenly across N nodes. It works until you need to scale.

When N changes from 4 to 5, almost every key gets a different nodeId. Here’s why: if hash(key) = 1,000,000, then 1,000,000 mod 4 = 0 but 1,000,000 mod 5 = 0. That’s a collision. But 1,000,001 mod 4 = 1 and 1,000,001 mod 5 = 1. Also a collision. But statistically, for a uniformly distributed hash, the probability that hash(key) mod 4 == hash(key) mod 5 is 1/4 × 1/5 = 1/20, or 5%. That means 95% of keys remapped. Your cache on all 4 nodes is now stale. Every miss goes to the database. The database, which was fine for reads at the cache layer, now sees a 20× spike.

Companies have hit this. A DC operator scaling Memcached from 10 nodes to 11 watched throughput collapse. Queries climbed from 100K/sec to 2M/sec on the database. The fix was to rehash all data offline, a 12-hour outage.

The Consistent Hashing Insight

Instead of mapping keys to numbers and taking modulo, map them to points on a circle. Do the same for nodes. A key belongs to the first node reached walking clockwise.

Imagine a circle with positions 0 to 2^32 − 1. Place 4 nodes on it: N0 at 0, N1 at 2^32/4, N2 at 2^32/2, N3 at 3×2^32/4. Now hash each key to a position on the same circle. If a key hashes to position 1.2×2^32/4 (between N1 and N2), it belongs to N2. If another key hashes to 0.9×2^32/4 (between N0 and N1), it belongs to N1.

Add a fifth node N4 at 1.5×2^32/4 (between N2 and N3). Now keys in the arc between N3 and N4 that used to belong to N3 now belong to N4. Keys in every other arc still point to the same node. On average, 1/N of keys move, not 95% of them.

When N4 fails, its keys slide to N3 (the next node clockwise). A rehash wipe touches only that one arc, not the entire cluster.

Mechanism: The Ring in Practice

Here’s how Discord and DynamoDB actually build this:

1. Hash nodes. Compute hash("N0"), hash("N1"), … and map each to a position on [0, 2^32). These positions are fixed unless you add/remove nodes.

2. Hash keys. Compute hash(userID) and map it to the same circle.

3. Locate. Walk clockwise from the key’s position until you reach a node position. That’s your home node. Use binary search (the ring is sorted) for O(log N) lookup.

4. Scale up. Introduce node N4. It occupies one position on the circle between two existing nodes. Write a rebalance daemon that walks keys in that arc and migrates them. In production, this happens in the background while traffic continues.

5. Scale down. When N2 fails, its keys are already owned by N3 (the next clockwise node). If N2 was explicit about its “successor,” the transition is instantaneous. If not, you have one arc of temporary 404s until the ring converges.

Virtual Nodes: Fixing the Uneven Load Problem

Consistent hashing has a secret flaw. If a node hashes unluckily—if its position ends up next to two other nodes very close together—it owns a small arc. Meanwhile, another node might hash to a sparse region and own a huge arc, receiving 60% of the traffic. This is called a “hot spot.”

Imagine you have 10 nodes and one happens to sit alone on a large stretch of the ring. In the worst case, 1 node owns 90% of keys while 9 share 10%. Load rebalances, but unevenly.

Virtual nodes fix this. Each physical node doesn’t hash to one position—it hashes to many. Typically 100 to 500. So you don’t have 10 positions on the ring; you have 1,000 to 5,000. A key still walks clockwise, but now it might hit a vnode belonging to any of the 10 physical nodes with near-equal probability.

If a physical node fails, its 100–500 vnodes’ keys spread across many survivors, not one. Load rebalances evenly.

Cassandra uses vnodes by default. Redis Cluster assigns 16,384 hash slots (conceptually vnodes) across all nodes. Discord’s chat shard key uses ~150 vnodes per physical node.

When Consistent Hashing Is Overkill

This solves real problems. But it’s not free.

• Complexity. You must implement a ring, handle wraparound, and manage rebalance migrations.
• Lookup overhead. A binary search on the ring is O(log N) versus O(1) modulo.
• Rebalance cost. Moving 1/N of your data isn’t trivial when N is 100 and you have terabytes.

If your cluster size is truly fixed—three Postgres replicas that never change—use modulo hashing or just shard manually. If you scale monthly and can handle a cache flush, modulo is simpler. Consistent hashing shines only when you:

• Scale frequently (Kubernetes deployments, auto-scaling groups).
• Can’t afford cache invalidation (Discord’s 10-year chat history, every lookup must be fast).
• Run a large cluster where 1/N is small (100+ nodes, 1% moves is acceptable).

Virtual nodes fix hot spots: a single physical node owns many small scattered arcs instead of one large one.

The Trade-offs Honestly

Consistent hashing assumes your data is idempotent to move or re-request. This is true for caches (miss it, fetch from source) and distributed databases (Cassandra, HBase). It breaks for databases with strong consistency and transaction logs—moving data changes commit ordering. Traditional databases stick with modulo and accept occasional rehashing pain.

The ring also assumes hash collisions are rare. If two nodes or keys hash to the same position, you need a tiebreaker. Production systems use libraries that generate position lists (hash(node-id-1), hash(node-id-2), …) to avoid collisions.

Takeaway

Modulo hashing is a trap disguised as simplicity. It works until it doesn’t, and then it breaks catastrophically. Consistent hashing adds a thin layer of topology—a circle—and rewires the question from “which N?” to “which node am I pointing at?” It’s the default for systems that scale: Discord’s shard key, Amazon DynamoDB’s partition key selection, Redis Cluster’s hash slot assignment, Cassandra’s token ranges. The cost is real but paid by infrastructure engineers once. The payoff is a cache that doesn’t evaporate when you add a node at 2 AM.