Consistent Hashing

Maps both nodes and keys onto the same circular hash space, so a key belongs to whichever node's marker comes next going clockwise. Adding or removing one node only remaps the keys in that node's arc, not the entire keyspace: the property plain hash(key) % numNodes partitioning doesn't have.

How it works

Picture a clock face with 232 positions instead of 12. Each physical node is hashed onto that circle multiple times, once per virtual node (e.g. node-a#0, node-a#1, ...): these are the colored dots on the ring below. A key is hashed onto the same circle, then walks clockwise to the first dot it meets; whichever node owns that dot owns the key.

Why virtual nodes? With only one point per physical node, a single unlucky hash can give one node a huge arc (and thus most of the keys) while another gets almost none. Spreading each node across many random points averages that out: the more virtual nodes per physical node, the more even the key distribution, at the cost of more positions to store and search.

Why "consistent"? When a node is added or removed, only the arc(s) immediately counter-clockwise of its vnode(s) change ownership. Every other arc, and therefore every other key, keeps mapping to the same node it always did: roughly a 1 / numNodes fraction of keys move, instead of nearly all of them as with hash(key) % numNodes, where changing numNodes reshuffles almost every key's target.

Interactive demo

Nodes
No nodes yet.
Keys
No keys placed yet.
Physical nodes0
Virtual nodes0
Keys placed0
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new ConsistentHashRing(virtualNodes?)Create an empty ring; each node added will be hashed to virtualNodes points.O(1)
addNode(name): positionsHash the node onto virtualNodes ring positions.O(V log V) for V total vnodes
removeNode(name): positionsRemove all of a node's ring positions.O(V) for V total vnodes
getNode(key): nodeHash the key, walk clockwise to the first vnode.O(log V) via binary search
getRingEntries(): entries[]All vnodes sorted by ring position, for visualization.O(V)

References

Original papers

Library implementations

Real-world use cases