Rendezvous Hashing

The ring is not the only way to get consistent placement. Rendezvous hashing, also called Highest Random Weight (HRW) and published by Thaler and Ravishankar in the late 1990s, needs no ring, no virtual nodes and no sorted structure. Your program will pick a key's owner by scoring every node and taking the best one.

The rule

For a key, give every node a score that mixes the key and the node. The owner is the node with the highest score. In this course the score is the h32 hash of the text key|node, and a tie goes to the smaller node name.

key     red         green       blue        owner
page1   1893209739  601664996   1992519423  blue
page2   3841187204  4237365167  1187875748  green
page3   3704692274  4213873642  436657056   green

Why this is consistent: remove green and only the keys it won change owner, because every other key's ranking of the surviving nodes is untouched.

page1   red 1893209739   blue 1992519423                 -> blue   (unchanged)
page2   red 3841187204   blue 1187875748                 -> red    (moved)
page3   red 3704692274   blue 436657056                  -> red    (moved)

Add a node and the only keys that move are the ones the newcomer now wins. That is the same minimal-disruption guarantee as the ring, from one max.

The ranking is useful on its own. Sort all nodes by score and the first N are the key's replica list, with no walk and no deduplication. Your TOP command returns exactly that.

How it compares with the ring

• State. None. Membership is just a list of names, so there is nothing to rebuild when it changes.
• Lookup. O(N) score computations per key, against the ring's O(log NK) binary search. For a few dozen nodes that is microseconds; with thousands of nodes the ring wins.
• Balance. With a mixing score function each node wins about the same number of keys without any virtual nodes. On four nodes and 8,000 keys the tests show counts within a percent or two of 2,000 each.

Real deployments live in the small-N sweet spot: Microsoft's CARP (Cache Array Routing Protocol) selects proxy caches by HRW score, Apache Ignite's default placement is a class named RendezvousAffinityFunction, and Ceph's CRUSH straw2 buckets pick storage daemons by a highest-draw rule in the same family.

The trap: the score must mix

Everything above assumed a score that mixes the key and the node. Replace it with the byte sum and the algorithm still runs but stops working:

sum("page1|red") = 901   sum("page1|green") = 1115   sum("page1|blue") = 1010
sum("page2|red") = 902   sum("page2|green") = 1116   sum("page2|blue") = 1011

A byte sum is additive: sum(key|node) = sum(key) + sum("|") + sum(node). The key's part is identical for every node, so the comparison ignores the key and the node with the largest name sum wins every single key. One node owns everything. Consistency comes from the algorithm, but balance comes from the hash.

Common mistakes

• No separator. Scoring key + node instead of key|node makes ("ab", "c") and ("a", "bc") collide.
• Forgetting the tie-break. Two nodes can score identically (rarely, but the tests contain one). The smaller name wins, whatever order the nodes were added in. "First maximum seen" depends on insertion order.
• Taking the lowest score. The owner is the highest.
• Treating scores as signed. Scores are unsigned 32-bit values, so compare them as such.

Your exercise

The starter reads the commands, keeps the list of nodes, and has the tracking and diff code from the rebalance lesson. You write the score, the ranking and the lookup.