Consistent Hashing Ring
Node membership changes with minimal key movement
N servers are placed on a hash ring; M keys scatter to their clockwise successors. Remove a server — only the keys it owned move, not all of them. Increase virtual-nodes-per-server and watch the load variance collapse.
Servers5
Virtual nodes / server1
Keys400
Load per server
S0
43
S1
0
S2
275
S3
76
S4
6
coefficient of variation
1.040
keys remapped
0 (0.0%)
Removing a server reassigns only the keys between it and its predecessor — not the whole ring. Raise virtual nodes to shrink the load variance: more placements per server average out the gaps.
Under consistent hashing, adding or losing a node moves ~1/N of the keys. Under modulo hashing, it moves nearly all of them. That is the whole point.