Consistent hashing and its alternatives

The problem with modulo hashing

node = hash(key) % N

Adding or removing one node changes N, so almost every key moves. Going from 10 nodes to 11 relocates about 91% of keys: a near-total miss storm for a cache, a full data migration for a database.

Requirement: when N changes by one, only about 1/N of keys should move.

Ring (consistent hashing)

Hash both nodes and keys onto a circular space. A key belongs to the first node clockwise from its position. Adding a node captures only the keys between it and its predecessor.

Virtual nodes are mandatory. With one point per node, randomly placed points produce very unequal arc lengths and badly uneven load. Place each physical node at 100 to 200 ring positions: