Consistent hashing.
also: hash ring · consistent hash ringKeys and nodes are hashed onto a ring; each key belongs to the next node clockwise, so adding a node moves only one arc.
the two-minute refresher
- Hash the key onto a ring (0 to 2^32-1) and walk clockwise to the first node.
- Adding a node takes over one arc: about 1/(N+1) of keys move, all from one neighbour.
- Virtual nodes (many points per server) fix uneven arcs.
- Worth it when nodes come and go (caches, Dynamo-style stores); overkill for a fixed shard count.