Partition keys across nodes by hashing. With plain key mod NAssign each key to node (key mod N). Fast and simple โ but if N changes, almost every key gets a new home. hashing, changing the node count remaps almost every key โ a stampede of data movement. Consistent hashingPlace nodes and keys on a virtual ring by hashing their identifiers. Each key belongs to the nearest clockwise node โ so adding or removing one node only disturbs its neighbours on the ring. places nodes on a ring so adding or removing one only disturbs its neighbour's share.
1 node added.
200k of 1M keys shift to a new home with consistent hashing โ the minimum possible. Plain mod-4 hashing would move 80% (800k).
The consistent line stays low: it moves exactly |ฮN| / max(N, M) โ the irreducible minimum. The mod-N line runs near the top because changing the divisor reassigns most keys, except in the occasional tidy case where M is a multiple of N and some keys happen to land on the same node by arithmetic luck.
| Move | Consistent | Mod-N |
|---|---|---|
| +1 (4โ5)now | 20% | 80% |
| โ1 (4โ3) | 25% | 75% |
| ร2 (4โ8) | 50% | 50% |
| รท2 (4โ2) | 50% | 50% |
Consistent hashing puts nodes and keys on a ring; a new node only steals the arc between it and its successor, so just ~1/M of keys move; a leaving node hands its arc to the next node. Mod-N ties every key's home to the count, so changing the count remaps almost everything โ except when the new count is a tidy multiple, when some keys happen to stay. Virtual nodesAssign each physical node multiple positions on the ring โ typically 100โ200 virtual nodes per physical node. This evens out the load distribution so no one node holds a much larger arc than the others, which is the main weakness of basic consistent hashing with few nodes. even out the per-node load without changing these moved-key fractions.