Say you run a cache on four machines, which we'll call nodes, and every piece of data is looked up by a name such as user:42, its key. Each key needs exactly one owner, and every client must be able to work out that owner by itself, without asking anyone. The obvious rule is to turn the key into a large number with a hash function (the same key always gives the same number, and different keys give numbers that look random) and take the remainder: hash(key) mod N, where N is the number of nodes. With four nodes the remainder is 0, 1, 2 or 3, and that picks the node.
The rule spreads keys evenly, and it breaks the day N changes. Add a fifth machine and the remainder changes for most keys, so most of the cache now sits on the wrong node, and every one of those lookups misses and goes to the database at once. A hash ring is the fix that the partitioning chapter builds up to. Keys and nodes are hashed onto the same circle, and a key belongs to the first node you meet walking clockwise from it. A node's spot on the circle is its token, and the stretch of circle between one token and the token before it is an arc. Every key in an arc has the same owner.
The question for this lab is how many keys really move when a node joins or leaves, and which ones. Below are 48 keys, user:1 to user:48, and four nodes, A to D. Every position comes from a real 32-bit hash, so the layout is the same every time you load the page, and every number in the experiments below can be checked against the widget.
Coloured band: the arc each node owns. Ticks: tokens. Circled dots: keys that just moved.
Things to try
1. Add a fifth node
Start from the beginning, with Reset if you've been clicking. The ring has four tokens: C at 76°, B at 178°, D at 287° and A at 347°, measuring clockwise from the top. Node E is about to join, and its name hashes to 51°.
With the ring selected, how many of the 48 keys change owner when E joins at 51°?
Click Add node E. The seven circled dots sit together just before E's tick, and each one has turned E's colour. The narration line names them. A fair share for E would be 48 ÷ 5, about ten keys, and it got seven because its arc happens to be short. That is the ring's one promise: when a node joins, the only keys that move are the ones the new node takes, and no key moves between two nodes that were already there.
2. Same change, hash mod N
Leave E in place and switch the toggle at the top to hash mod N. The keys stay where they are on the circle, but now their colour comes from the remainder rule, and the ring plays no part.
Going from four nodes to five under hash mod N, roughly what fraction of keys should change owner?
The comparison panel shows 44 of the 48 keys moved, and the narration adds that 36 of them moved between two nodes that were there before E arrived. Those 36 are pure waste: E wasn't involved, yet node A sent keys to node B and B sent keys to C. Click Repeat with 100,000 keys to check the 48 aren't a fluke. On 100,000 keys hash mod N moves 80.0%, rendezvous hashing (experiment 5) moves 20.1%, and the ring moves 17.6%, a little under the fair fifth for the same reason E got seven keys instead of ten.
3. Grow to eight nodes and look at the bars
Switch back to Ring and add F, G and H. Watch the count in the middle of the ring after each one. F moves 2 keys and G moves 2, and when H joins at 203°, the count is zero. H's token landed 4° after F's at 199°, its arc is about a hundredth of the circle, and not one of the 48 keys sits inside it.
A join that moves nothing sounds ideal, but it means H does nothing. Look at Ring share per node. With one token each, B owns 28.2% of the circle and H owns 1.1%, against a fair share of 12.5%. The figure beside the heading, busiest ÷ mean, divides the biggest share by the average share, and here it reads 2.26. B is the machine whose memory fills first, and it fills more than twice as fast as it should. One random point per node leaves gaps of very uneven length, and a node's load is the length of its gap.
The fix is to give each node many tokens, called virtual nodes. A node's share is then the sum of many small arcs scattered around the circle, and a sum of many random lengths lands close to its average.
With eight nodes, you move the virtual-nodes slider from 1 to 2 tokens per node. What happens to busiest ÷ mean?
Changing the token count re-places every token, so the lab treats it as a new layout and resets the move counts. Real systems pick the number once. Cassandra, a database built on a ring, used 256 tokens per node for years and lowered its default to 16 in version 4.0, pairing it with an algorithm that places tokens where they even out ownership instead of at random. The partitioning chapter covers that change in section 3.4.
4. Remove a node, with one token and with many
Click Reset, add E, F, G and H again, and set the slider back to 1. Now remove D with its × button.
With one token, D held 20 of the 48 keys, and all 20 go to A, the next token clockwise. A was already holding 6 keys, and now it holds 26, so the failure of one node has more than quadrupled the load on its single neighbour. In a cache that neighbour now takes every miss for D's keys while also serving its own.
Click Reset, add the four nodes again, slide to 200 tokens and remove D once more. This time D held 5 keys, because its share was close to fair, and they go to four different nodes: 2 to C and 1 each to A, E and G. Each of D's 200 arcs merges into whichever token comes next, and those tokens belong to everyone. So virtual nodes do two jobs: they even out the shares while every node is healthy, and they spread a dead node's work across the survivors instead of dumping it on one neighbour. Hash mod N, on the same removal, moved 42 of 48.
5. Rendezvous hashing, which needs no ring
Reset, then switch to Rendezvous. Rendezvous hashing, also called highest random weight, gives every key a score for every node, computed by hashing the key and the node name together, and the key goes to the node with the highest score. There are no tokens, so the band and ticks disappear.
Remove B. Its 12 keys each fall to their second-highest scorer, and they spread on their own: 7 to D, 3 to A and 2 to C. The other 36 keys still have the same winner, because taking B away doesn't change anyone else's score. Add a node and the same logic runs in reverse: the newcomer takes only the keys where its score beats the old winner. Back in experiment 2, on 100,000 keys, that came to 20.1% against a fair 20%, with no virtual nodes at all. The price is the lookup. The ring finds an owner with a binary search over sorted tokens, while rendezvous hashing computes one hash per node for every key, which is fine for a few dozen nodes and slow for thousands.
What this shows
The ring works because ownership is local. A key's owner depends only on the stretch of circle between the key and the next token, so a node joining or leaving changes the answer only for keys in the arcs it touches, and every key that moves goes to or from that node. Hash mod N makes every key depend on N, so changing N reshuffles nearly all of them, mostly between nodes that had nothing to do with the change.
Locality doesn't buy balance. With one token per node the arcs are wildly uneven, which shows up as a busiest node at more than twice its share and a removal that dumps everything on one neighbour. Many tokens per node fix both, at the cost of a bigger token table. Rendezvous hashing gets the same minimal movement and good balance without tokens, and pays for it with work on every lookup.
Where to read more
- Partitioning: Hash, then modulo shows twelve keys moving under
hash mod N, the problem this lab starts from. - Partitioning: The hash ring covers tokens, arcs and virtual nodes, with a script that counts moves on 100,000 keys.
- Partitioning: Jump hash, rendezvous hashing and the rest compares every scheme on one table, along with fixed slots as Redis Cluster uses them.
- Caching: Coherence across a fleet, in its subsection "Hot keys and failed cache servers", shows a cache fleet spreading keys with consistent hashing, and what still goes wrong when one key is hot or a server dies.