Rebalance on Add/Remove

The ring tells you where keys should live. Rebalancing is what happens to the data already stored when that answer changes.

Add a node: it claims the arcs immediately counter-clockwise of each of its vnodes. Keys in those arcs move FROM each arc's previous owner (the old clockwise successor) TO the new node. Nothing else moves — that is the K/N guarantee — and because vnodes scatter the new node across the ring, the moved keys are donated a little by everyone, not dumped by one unlucky neighbor.

Remove a node: each of its arcs merges into the next vnode clockwise, so its keys are inherited by many survivors, not one.

What "move" means depends on the system:

• Cache (memcached): nothing is copied. Remapped keys simply MISS on their new node and refill lazily from the source of truth. Adding a node costs a temporary hit-rate dip proportional to the moved fraction — which is exactly why minimizing that fraction matters.
• Database (Dynamo family): the data must be COPIED to the new owner before reads redirect, or you answer "not found" for data you still have. Cassandra calls this streaming; Riak and Voldemort call ownership transfer handoff. A joining node serves reads only after its arcs finish streaming.

The measurement idiom — snapshot, change, re-look-up, diff:

Update owner as you print: a later ADD_NODE_AND_DIFF must diff against the ring as it stands after this one — a hidden test chains two in a row.

Why every test here prints moved=0 — and why that is the point

With the byte-sum hash, all vnodes huddle in one small cluster (A and B occupy 148..153) while the tracked keys hash far outside it (hsum("apple") = 530, hsum("k1") = 156, the u-keys 166..171). A key outside the cluster wraps to the ring's first vnode — and adding C (vnodes 150..154) or D (151..155) never changes who holds that lowest position. So no tracked key moves, and the grader expects literally moved=0/3, moved=0/4, moved=0/6. A key moves only when a new vnode lands between the key's position and its old owner: a vnode at 300, say, would capture the u-keys (166..171) from beta@495. The zeros are the K/N property at its extreme — an add disturbs only the arcs it claims, and here those arcs happen to contain no tracked keys. Contrast lesson one, where one resize under hash % N moved 80% of everything.

Your exercise

Implement ADD_NODE, KEYS (snapshot each key's current owner), and ADD_NODE_AND_DIFF. Formats are exact: unchanged keys print <key>: <owner>, moved keys <key>: <old> -> <new> (spaces around the arrow), then moved=<n>/<total>, keys in the order KEYS gave them. The grader-caught mistakes: bad lookup geometry — the alpha/beta hidden test expects every u-key at beta (alpha's vnodes sit at 601..605, beta's at 495..499; keys 166..171 take the first vnode at-or-above, beta@495); printing alpha means your bisect picked the wrong side or wrapped when it shouldn't. And the denominator — moved=0/6 counts the tracked set, not the moves; printing moved=0/0 or omitting the line fails every test.