Consistent Hashing: Why Virtual Nodes Are Not Optional

The first time you partition a cache by hash(key) % N, it feels clean. The first time you add a node and watch the hit rate collapse from 92 percent to 4 percent, you understand the trap. Changing N from 8 to 9 reshuffles roughly 8 out of every 9 keys. Every shard simultaneously misses, every backing database simultaneously gets hammered, and the team that was supposed to be scaling up spends the next hour rolling the change back.

Consistent hashing replaces the modulo with a ring. Each node is placed on a circle of hash values, and each key is mapped to the next node clockwise from its own hash. When you add a node, only the keys that fall between the new node and its predecessor move. The expected fraction of keys that relocate is K divided by N, not K times (N minus 1) over N. Adding a ninth node touches one ninth of the keyspace, not all of it.

That math is what Dynamo, Cassandra, the memcached client libraries, and most service meshes rely on. It is also what makes scaling a cache fleet a normal Tuesday operation instead of a maintenance window.

The catch is that a ring with one point per physical node is not actually balanced. Hash positions are random. With eight nodes on the ring, some arcs between neighbors will be three or four times longer than others, and the node sitting clockwise of the longest arc owns three or four times the keys. Add the fact that real key distributions have hot spots, and the variance gets worse.

A team I worked with ran a memcached fleet without virtual nodes. One physical node was taking six times the median request rate because two hot key prefixes hashed to positions that landed back to back on the ring, and the unlucky node owned both arcs. The instinct was to add capacity to "balance" the load. They added four nodes. The rebalance moved cold ranges, the hot prefixes stayed exactly where they were, and the imbalance got worse.

The fix was 200 virtual nodes per physical node, which is the Cassandra default for a reason. Each physical node owns 200 small arcs scattered around the ring instead of one large arc. The variance in load between physical nodes drops from "one node carries six times the median" to "the busiest node carries about 1.2 times the median." Adding capacity now moves a proportional slice of every range.

A hash ring is not a load balancer. A hash ring with enough vnodes is.