The Runtime Theory

Consistent Hashing Ring: Hash Placement, Clockwise Lookup, and Virtual Nodes

See how consistent hashing places nodes and keys on a 2^32 ring, walks clockwise to assign ownership, and rebalances only O(1/N) of keys on membership change.

The Runtime Theory Team08 stages

trace / request.md

THE RINGNODES PLACEDKEY HASHEDCLOCKWISE WALKVNODESSPREAD LOADNODE ADDEDNODE REMOVEDTHE RISK: SKEW

readyKeyspace is a circle from 0 to 2^32−1. Every position maps to a hash; the ring is the entire universe of possible keys, laid out in order.

Consistent hashing answers a question naive hashing gets wrong: what happens to cached keys when the node count changes? Modulo hashing remaps everything — a cache becomes a sieve. Consistent hashing remaps only the neighborhood of the change: adding a node moves the keys between it and its predecessor; removing one moves only its own keys onward.

Ownership is a walk, not a lookup: hash the key, step clockwise, take the first node. The ring's geometry does all the bookkeeping. Virtual nodes are the refinement that makes the geometry fair — with plain hashing, a few nodes means lumpy arcs and hot nodes; with 100–200 vnodes per physical node, ownership smooths out and per-node weights become expressible. That is why memcached layers, CDNs, and partitioning schemes all use the ring: membership changes cost O(1/N) of the keyspace in moves, and lookups stay a single hash and a walk.