Rendezvous Hashing

The ring is not the only way to get consistent placement. Rendezvous hashing — also called Highest Random Weight (HRW), published by Thaler and Ravishankar while the ring was being invented — needs no ring, no vnodes, no sorted structure. For a key, give every node a score that mixes the key and the node; the owner is the node with the highest score:

(min over (-score, name) is the tidy Python idiom for "max score, ties to the alphabetically smaller name".)

Why this is consistent: remove a node and only the keys whose winner it was change owners — every other key's ranking of the surviving nodes is untouched. Add a node and the only keys that move are those the newcomer now wins. That is the same minimal-disruption guarantee as the ring, from one max().

The trade against the ring:

• State: zero. No structure to maintain; membership is just a list.
• Lookup: O(N) score evaluations per key, vs the ring's O(log NK). Under ~100 nodes this is nanoseconds and irrelevant; at thousands of nodes the ring wins.
• Balance: with a well-mixing score function, naturally uniform — no vnode tuning at all.

Real deployments live exactly in that small-N sweet spot: Microsoft's CARP (the Cache Array Routing Protocol, 1998) selects proxy caches by HRW score; Apache Ignite's default data-placement function is literally named RendezvousAffinityFunction; Ceph's CRUSH straw2 buckets pick storage daemons by an HRW-style highest-draw.

The trap this exercise is built around

Everything above said "with a well-mixing score function". Our hand-checkable score is a byte sum:

Byte sums are additive: score(key, n) = hsum(key) + 124 + hsum(n). The key's contribution is identical for every node, so the argmax ignores the key entirely — the node with the largest name-byte-sum wins every single key. The tests show it: with nodes A, B, C, D, the hidden STATS over eight keys prints D: 8; with a, b, c it prints c: 4. One node owns everything. This is the same lesson the vnodes chapter taught the ring: consistency comes from the algorithm, but balance comes from the hash. Real HRW uses a non-linear mix — murmur(key + "|" + node), md5, xxHash — where the node genuinely changes how the key's bytes propagate.

Your exercise

Implement the toy score exactly as specified — resist the urge to "fix" it with md5, because the grader's outputs are computed from the byte sum: with A, B, C in the pool, LOOKUP foo must print C (scores 513, 514, 515). Empty pool prints NONE. STATS prints <name>: <count> sorted by name, omitting zeros — and yes, the correct hidden-test outputs are the degenerate D: 8 and c: 4. Also implement the specified tie-break (smaller name wins) even though no visible test exercises a tie: max() alone returns the first maximum in list order, which is insertion order, not alphabetical — the (-score, name) key above gets both rules right in one expression.