Consistent hashing
A way to place keys on machines so that adding or removing one moves only a small share of the data. Builds on Range and hash partitioning.
5 minute lesson
Put the machines on the same circle
Hash modulo N ties every key to the number of machines, so changing that number moves almost everything. Consistent hashing removes N from the formula. Picture the hash values as a circle. Each machine is hashed to a point on it, and so is each key. A key belongs to the first machine found going clockwise.
- Keya point on the ring
- Go clockwiseto the next machine
- Ownerthat machine
Adding a fourth machine
- Three machines
Machines A, B and C sit on the ring. Each owns the stretch of the circle that ends at its own point.
- Aowns a stretch
- Bowns a stretch
- Cowns a stretch
- D joins
Machine D is hashed to a point between A and B. The keys between A and D used to go on to B. Now they stop at D.
- Aunchanged
- Dtakes part of B's keys
- Bkeeps the rest
- What moved
Only keys from one stretch moved, from B to D. Every key that belongs to A or C stayed where it was. With hash modulo N, four fifths of all keys would have moved.
- Consistent hashingabout 1 key in 4
- Hash modulo Nmost of the keys
A cache cluster of 10 machines uses consistent hashing and holds 100 million keys, spread evenly. An eleventh machine is added.
Roughly how many keys move?
- About 9 million
- About 50 million
- About 91 million
- All 100 million
Show the answer
- About 9 million
The new machine should end up with a fair share of the keys, one eleventh, and that share is what it takes over: about 9 million. The other 91 million stay where they are. With hash modulo N the numbers would be the other way round: about 91 million would move.
With consistent hashing a new machine takes about 1/n of the keys, and nothing else moves.
One point per machine is not enough
With one point each, the machines land at random places, and the stretches between them differ a lot. One machine may own half the circle. And when a machine leaves, its whole stretch falls on a single neighbour.
- 1 point eachUneven sharesand one neighbour inherits everything
- 100 points eachEven sharesand a leaver's keys spread over all
So each machine is placed on the ring many times, under many names. Each of these points is a virtual node. A bigger machine can be given more of them, and with them a bigger share.
Five machines sit on a hash ring with one point each. All of them run at 70% of their capacity. One machine fails.
What happens to its keys?
- All of them fall on one neighbour, which overloads
- They are shared out evenly among the other four
- They are lost, as no machine owns that stretch
- They stay in place until the machine comes back
Show the answer
- All of them fall on one neighbour, which overloads
With one point per machine, the failed machine's whole stretch now ends at the next machine clockwise. That neighbour gets a double share: 140% of its capacity. It may fail too, and pass an even larger load to the next one. With many virtual nodes the failed machine's points are scattered round the ring, and each of the others inherits a little.
Without virtual nodes a failed machine's whole load lands on one neighbour.
How does consistent hashing place a key, and why does adding a machine move so little data?
Show the answer
Machines and keys are both hashed onto a circle, and a key belongs to the first machine clockwise from it. A new machine takes over one stretch of the circle, the part just before its own point, from one neighbour. All other keys keep their machine. With n machines about one key in n moves, where hash modulo n moves almost all of them.
Recap
- Machines and keys are hashed onto a ring. A key belongs to the next machine clockwise.
- Adding or removing a machine moves only the keys of one stretch: about one in n.
- Virtual nodes place each machine many times, which evens out the shares.