Consistent hashing.

also: hash ring · consistent hash ring

Keys 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.

also: hash ring · consistent hash ring

Keys and nodes are hashed onto a ring; each key belongs to the next node clockwise, so adding a node moves only one arc.

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.