Rebalance on Add and Remove

The ring tells you where a key lives right now. This lesson is about what happens to the data you already stored when that answer changes. Your program will measure it: which keys move, from where, to where.

What a membership change does

Add a node. Each of its points claims the arc that ends at that point. The keys in that arc used to belong to the arc's old owner, the next point clockwise, and now belong to the new node. No other key moves. So on an add, every key that moves moves to the new node, and none moves between two old nodes. Because the new node's points are scattered around the ring, it takes a little from everyone rather than a lot from one neighbour.

Remove a node. Each of its arcs merges into the next point clockwise. Every key that moves leaves the removed node, and the survivors inherit them, again from many nodes at once. No key moves between two survivors.

Measured on this lesson's ring (64 points per node) with 10,000 tracked keys, adding web9 to web1..web8:

web1 -> web9: 295     web5 -> web9: 173
web2 -> web9: 128     web6 -> web9: 182
web3 -> web9: 148     web7 -> web9: 102
web4 -> web9:  32     web8 -> web9:  20
moved=1080/10000

That is 10.8% of the keys, close to the ideal 1/9. Routing the same keys with hash % 8 and then hash % 9 moves 8,919 of them. Removing web3 from the nine nodes moves the 1,053 keys it owned, and every line starts with web3 ->.

What "move" costs

It depends on the system. In a cache (memcached) nothing is copied: moved keys simply miss on their new node and refill lazily, so a join is a temporary hit-rate dip proportional to the moved fraction. In a database (Dynamo family) the data must be copied to the new owner before reads are redirected, or you answer "not found" for data you still hold. Cassandra calls the copy streaming, Riak calls it handoff. Either way, moving less is cheaper, which is why this property matters.

Measuring it: snapshot, change, look up again, diff

1. Snapshot. For a tracked set of keys, remember each key's current owner.
2. Change the ring.
3. Look up again. Ask the ring who owns each tracked key now and compare it with the snapshot.
4. Group. Count the changed keys by (old owner, new owner) pair and print the pairs in sorted order, then print how many moved out of how many were tracked.
5. Replace the snapshot with the new owners.

Step 5 is the one people skip. The next diff must compare against the ring as it stands now. If you keep the original snapshot, a second diff re-reports every move from the first.

Common mistakes

• A stale snapshot. After ADD_NODE D, DIFF, ADD_NODE E, DIFF, the second report must contain only the moves caused by E.
• Reporting keys that stayed. Only pairs where the owner changed are printed. A line like A -> A is wrong.
• The wrong denominator. moved=1080/10000 divides by the number of tracked keys, not by the node count and not by the number of moves.
• Unsorted pairs. Print the pairs ordered by old name, then new name, in plain string order.
• Ignoring a second TRACK. A new TRACK replaces the tracked set and the snapshot.

Your exercise

The ring from the last lesson is already in the starter, with 64 points per node. You write the tracking and the diff.