CodeParkConsistent hashing places both cache nodes and keys on a ring, so adding or removing a node moves only a small share of keys. Distributed caches use it because plain modulo hashing moves almost every key.
The problem with modulo. With hash(key) % N, the node for a key depends on N, the number of nodes. When N changes, the result changes for most keys. So adding one cache node causes a flood of cache misses. All those misses go to the database and can overload it.
How the ring works.
- Each node and each key gets a position on a hash ring.
- A key belongs to the first node you meet going clockwise from the key's position.
- When a node joins, it takes only the keys on the arc between itself and the node before it.
- When a node leaves, only its own keys move, to the next node clockwise.
On average, only about 1/N of the keys move.
Virtual nodes. With only a few nodes, their positions on the ring are uneven. So some nodes own much bigger arcs and get much more load. Virtual nodes fix this by giving each physical node many points on the ring. This has three benefits:
- The load evens out across nodes.
- When a node fails, its keys spread across many surviving nodes, instead of all landing on one neighbour.
- A bigger machine can take more virtual nodes, so it gets a bigger share of keys.
- Modulo hashing moves most keys to a new node when N changes.
- Nodes and keys sit on a ring, and a key goes to the next node clockwise.
- Only about 1/N of the keys move when a node joins or leaves.
- Virtual nodes balance the load and spread a failed node's keys across many nodes.
- A stronger machine can get more virtual nodes, so it takes more keys.