Consistent hashing: stable key placement when nodes come and go

What it is

The Cassandra documentation (cited) contrasts naive hashing, key hash modulo the number of buckets, with consistent hashing: each node owns one or more tokens on a continuous hash ring, a key is hashed onto the ring, and ownership goes to the next node walking the ring in one direction. When the number of nodes changes, only a small fraction of keys move. With one token per node and few nodes there is no token position for a new node that leaves the ring balanced, and uneven ranges mean uneven load; Cassandra therefore follows the Dynamo paper and assigns several tokens per physical node, the virtual nodes, so that even a single added node takes many small pieces from many neighbours.

The nginx upstream module (cited) exposes the same choice: plain hash $key may remap most keys when a server is removed, while hash $key consistent uses the ketama method so that only a few keys move. Envoy (cited) offers a ring hash balancer and Maglev, a table-based variant with faster lookups; its documentation notes that Maglev moves more keys than the ring when hosts are removed.

Why it matters

Caches lose their hit ratio on every membership change if keys scatter; partitioned stores would have to move most data; session-affine services would lose affinity on every deploy. Consistent hashing bounds the disruption to what actually changed.

How to apply

• Choose a hash key with enough cardinality (user id, tenant id, cache key), not something like client IP behind a NAT.
• Use a library or proxy implementation; configure virtual nodes or table size so that per-node load is even, and monitor per-host share (Envoy exposes gauges for minimum and maximum entries per host).
• For replication, take the next k distinct physical nodes on the ring, skipping virtual nodes of the same machine and, if possible, the same rack or zone.
• Plan how data moves when a node joins: the new owner must receive its range before serving, or serve misses from the old owner during a transition.
• Fix the hash function for the lifetime of the deployment; changing it remaps everything.

Pitfalls

Consistent hashing does not fix hot keys: one popular key still lands on one node. Weighted nodes need proportionally more virtual nodes. Consistent hashing has nothing to do with data consistency; it only decides placement.