The Hash Ring

Consistent hashing's core move: stop tying placement to N. Hash both nodes and keys into one fixed space — here 0..999 via hsum(s) = sum(s.encode()) % 1000, in production usually 0..2^32-1 — and treat that space as a circle. A key belongs to the first node at or after its position, walking clockwise; if no node lies above it, wrap around to the lowest one.

ring positions:  beta=412   gamma=515   alpha=518

hsum("foo") = 324       -> first node >= 324  -> beta@412
hsum("whatever") = 870  -> no node >= 870     -> wrap -> beta@412

Why this fixes resizing: each node owns exactly the arc between its predecessor and itself. Add a node D at position 700 and D takes precisely the keys in (518, 700] — keys that used to wrap past alpha@518 to their old owner. Every other arc is untouched. Node count never appears in the placement rule, so changing it disturbs only the arcs adjacent to the change: the K/N guarantee from lesson one.

The idiom — a sorted list plus binary search:

bisect_left finds the first position >= the key's hash — the clockwise successor — in O(log N). Note bisect_left, not bisect_right: a key that hashes exactly onto a node's position belongs to that node. Memcached's libketama is this structure with MD5 and 160 points per server (next lesson explains why 160).

Two classic footguns

The builtin-hash trap. Many tutorials (including an older version of this page) write h = hash(key). Python salts string hashes per process, so that ring assigns keys to different nodes every run — as a router it's broken, and against a grader with fixed expected outputs it can never pass. Always use the specified deterministic hash.

Re-sorting per lookup. Calling sorted(...) inside lookup turns each O(log N) query into O(N log N). Keep the list sorted once, at insert time, with bisect.insort.

And removal must be complete: delete the position from the sorted list AND every map. A leftover entry is a ghost node that still "owns" an arc and eats lookups.

Your exercise

ADD_NODE prints OK <hash> (OK 518 for alpha), RING prints <name>:<hash> lines in ascending hash order — for alpha/beta/gamma exactly beta:412, gamma:515, alpha:518 — and LOOKUP walks clockwise, printing NONE on an empty ring. The grader-caught mistakes: forgetting the wrap — with only alpha@518 in the ring, LOOKUP whatever (hsum 870) must print alpha; an unwrapped bisect index is an IndexError or the wrong node. And incomplete removal — a hidden test runs ADD_NODE node1, REMOVE_NODE node1, LOOKUP foo and expects OK 471 / OK / NONE; if position 471 survives in any structure, you print node1 where NONE belongs.