Rendezvous Hashing

Also called highest random weight hashing. For each key, every node gets a score from hashing the key together with the node's name, and the node with the highest score holds the key. Adding a node only takes the keys it now scores highest for, and removing one only moves its own keys, each to its second-best node. There is no ring to keep and no virtual nodes, at the cost of computing one score per node on every lookup.

score = hash(user, node), out of 999N1N2N3N4user #1012296505759769user #10298997470672user #1443172208338730user #188384723318520user #2153730224161599user #240468437118038the filled cell is the highest score: that node holds the useradd a node and watch its new columnAppNode 1Node 2Node 3Node 4

The table in the panel shows each node's score for six sample users. Each dot in a node is one user record, coloured by country. Add or remove a node and the records that change node glide to their new place, ringed so you can count them. A node turns red when it serves well above its share of requests.

What a resize moves, and what a lookup costs
KB

  1. 1. Total data

    users x data per user = 500M x 10 KB = 4.66 TB

  2. 2. Adding one node

    the new node wins about 1 in (N + 1) keys, and only those move: 318 GB

  3. 3. Removing one node

    only its 1 / N of the keys move, each to its second-best node: 341 GB

  4. 4. Lookup work

    one hash per node per lookup: 14 x 100K/s = 1.4M hashes/s. A ring with 16 tokens per node needs about 8 steps of binary search per lookup instead.
  5. With tens or hundreds of nodes, scoring every node is cheap. With thousands, systems hash keys into a fixed set of partitions, run rendezvous once per partition, and keep the resulting table.
Where these formulas come from

Step 1 is the storage estimate from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1. Steps 2 and 3 follow from every node being equally likely to hold a key's top score. Step 4 counts the hashes rendezvous computes; the ring figure is log2 of its token count, for comparison.

Limits of rendezvous hashing

Every lookup scores every node

The work per lookup grows with the number of nodes. Fine for tens of nodes; for thousands, score partitions once and cache the table, or arrange nodes in a hierarchy.

One hot key is still one node

Scores spread different keys. Every request for the same key still goes to the same node, so a celebrity needs caching or deliberate splitting.

Range queries scatter

Like any hash placement, neighbouring keys land on unrelated nodes, so a range query must ask all of them.

Everyone needs the same node list

Two clients with different lists of nodes compute different winners. The list must be shared and updated together, as with a ring.

How GitHub and Apache Ignite use rendezvous hashing

Both score a fixed set of rows or partitions rather than every key, and keep the result as a table.

GitHub GLB: a primary and a secondary per row

GitHub's load balancer builds a table of 65k rows, "each row containing a primary and secondary server IP address." For each row, "Each server ... is hashed along with the row number, the servers are sorted by that hash", and the first two become primary and secondary. "When a new proxy server is added, for 1/N connections it becomes the new primary, and the old primary becomes the secondary."

Apache Ignite: partitions to nodes

Ignite splits keys into a fixed set of partitions ("0 to 1023 by default"), and "The default affinity function implements the rendezvous hashing algorithm" to place partitions on nodes. When the cluster changes, "partitions are migrated only to the new node that joined or from the node that left. No data exchange happens between the remaining nodes."
Sources and credibility

GitHub's engineering blog, written by the engineers who built GLB, and the Apache Ignite project's official documentation. Quoted phrases are short attributed quotations; everything else is described in our words.