Mod-N vs consistent vs rendezvous hashing

The idea: three ways to pick a node for a key

A cache or a sharded store spreads its keys over N nodes, and every client must agree on which node holds which key without asking anyone. So the node is computed from the key. Mod-N hashing takes hash(k) % N as an index into the node list. Consistent hashing puts nodes as tokens on a ring and gives each key to the next token clockwise. Rendezvous hashing, also called highest random weight (HRW) hashing, scores every node for the key with w(k, node) and picks the highest score.

The page runs all three side by side on the same 24 keys and the same nodes A, B, C (D can join later). Each key's position is a toy hash, h(k) = (37·k + 11) mod 100, and the rendezvous weight is a small 32-bit mix taken mod 100, so every number fits on screen. Each chip is one key, filled with its node's colour. Under each side, three lines compare the sides: keys per node, how loaded the busiest node is, and how many keys the last change moved.

One lookup, three computations

Demo: look up key 43. Mod-N computes 2 % 3 = 2 and reads entry 2 of the list, C. The ring marks position 2 and walks clockwise to the first token, A's at 15. Rendezvous computes three weights, A 16, B 19, C 89, and C wins. Mod-N and the ring cost one hash each (the ring adds a binary search over the sorted tokens). Rendezvous costs one hash per node, so a lookup is O(N). For tens of nodes that is cheap. For thousands, systems group the nodes into a tree or switch to a ring.

Adding and removing a node

A change first marks the keys that will move (yellow, still on their old node) and then moves them. Demo: add a node: D joins. Mod-N now divides by 4 instead of 3, so 17 of 24 keys get a new node, and most of them move between A, B and C, which did not change. On the ring, D's token at 86 takes the arc before it, so 6 keys move, all from A to D. Rendezvous computes one more weight per key, w(k, D). A key moves only if D beats its old winner, so 6 keys move (1 from A, 2 from B, 3 from C), all to D.

Demo: remove a node: B leaves. Mod-N's list closes up and 16 keys move, even keys that were never on B. On the ring, B's 7 keys walk on to the next token, which is C's: one neighbour takes them all. Rendezvous drops B from every ranking, and each of B's 8 keys goes to its second-highest weight: 4 to A, 4 to C. Only the keys that have to move do, and they spread out.

Load balance and virtual nodes

With one token per node, the ring's arcs have random lengths. Here A's arc is 58 positions long and C's only 15, so A holds 13 keys and C holds 4: the busiest node has 1.63× its even share. And when B leaves, its whole arc goes to one neighbour. The fix is virtual nodes: each node gets many tokens (Cassandra's num_tokens, 16 by default in recent versions), so it owns many short arcs. Demo: virtual nodes on the ring switches to 4 tokens per node: the keys are now 8 · 8 · 8, and removing B spreads its keys 4 and 4.

Rendezvous gets this spread without any tokens. Every key ranks all nodes independently, so each node is the winner for about 1/N of the keys, and each node's second choices are spread over all the others. Here it gives 8 · 8 · 8 with nothing to configure. A node with more capacity can get a larger share with weighted rendezvous hashing, which scales each node's score.

Which one to use

	Mod-N	Ring (consistent)	Rendezvous (HRW)
Lookup	1 hash	1 hash + binary search	N hashes
State to keep	the node list	the sorted token list	the node list
Keys moved when a node joins	most ✗	about 1/N ✓	about 1/N ✓
Where a leaving node's keys go	everything reshuffles ✗	the next token(s): one neighbour with 1 token	spread over all the others ✓
Balance	good	needs virtual nodes	good, no tuning
Used by	simple caches, hash % shards	Dynamo, Cassandra, Riak, many memcached clients	Ceph CRUSH (straw2), GitHub's load balancer, Apache Ignite, Twitter EventBus

Rendezvous also gives replicas for free: the top 3 weights are the key's 3 replicas, and when one of those nodes fails, the next weight takes over. Demo: add D, then remove B shows the minimum holding after two changes in a row. See also consistent hashing for the ring with replicas and hinted handoff, Redis Cluster for the fixed-slot alternative (16384 hash slots moved as a unit), and range vs hash partitioning.

What the page leaves out

Real hash functions (64-bit MurmurHash or xxHash, not a mod-100 toy), many more keys (the page's 24 keys make the shares lumpy), hundreds of virtual nodes per node, weighted rendezvous for nodes of different sizes, skeleton-based (hierarchical) rendezvous that keeps lookups O(log N), jump consistent hash and Maglev hashing, replication and moving the data itself while keys change owners.

References

Thaler and Ravishankar, A Name-Based Mapping Scheme for Rendezvous (1996)

Karger et al., Consistent Hashing and Random Trees (STOC 1997)

DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007)

Rendezvous hashing (Wikipedia)