The Problem with Plain Hashing
A simple way to spread keys across nodes is to take a hash and apply modulo by the node count. The trouble is that adding or removing a node changes the count, so almost every key remaps to a different node, forcing a massive reshuffle.
The Ring Idea
Consistent hashing maps both keys and nodes onto a circular space, often imagined as a ring from zero to a large maximum. To place a key, you hash it to a point on the ring and walk clockwise to the first node you meet. That node owns the key.
Why It Is Stable
- When a node joins, it takes over only the keys between it and the previous node on the ring.
- When a node leaves, only its keys move, to the next node clockwise.
- The rest of the keys stay exactly where they were, so churn touches a small slice.
Virtual Nodes
To avoid uneven load, each physical node is mapped to many points on the ring, called virtual nodes. This smooths out the distribution so no single node owns a huge arc by chance.
Key idea
Consistent hashing places keys and nodes on a ring so each key belongs to the next node clockwise, letting node changes move only a small neighboring slice of data.