Partial Order Precedence
Concept of the day · distributed systems
Consistent Hashing
Adding a node should move 1/n of the keys, not all of them.
The mechanism. hash(key) % n is catastrophic under resizing: change n and almost every key maps somewhere new, so every cache misses and every shard rebalances at once. Consistent hashing maps both keys and nodes onto a ring. A key belongs to the first node clockwise from it. Add or remove a node and only the keys between it and its predecessor move — about 1/n of them.
Virtual nodes. With one point per node, the ring is lumpy: some nodes own far more of the keyspace than others, and removing a node dumps all its load onto a single neighbour. Give each physical node 100–200 virtual points and the distribution smooths out and the load of a departing node spreads across all the others. Every real implementation does this.
Bounded loads. Even with virtual nodes, a hot key or a skewed workload can overload one node. Consistent hashing with bounded loads caps any node at (1+ε) times the average, spilling to the next node on the ring when it is full. Useful for request routing, not for storage placement.
The alternatives. Rendezvous (highest random weight) hashing is simpler — hash (key, node) for every node and take the max — and gives perfect distribution with no virtual nodes, at O(n) per lookup. Jump consistent hash is faster and smaller still, but cannot handle arbitrary node removal, only shrinking the tail.
Where you will meet it. Memcached clients, Cassandra and DynamoDB partitioning, Envoy's ring-hash load balancer, and any sharded cache you are about to resize.