Consistent and rendezvous hashing

How do you keep most keys in place when the set of nodes changes, and when is rendezvous better than the ring?

Consistent hashing

The problem it solves

With hash(key) % N, changing N by one reassigns about (N−1)/N of all keys.

For a cache, that is a near-total miss storm, at the exact moment when you are already weakened (a node just died). For a stateful consumer it is a complete redistribution of state. The naive scheme is unstable under the one event you must handle gracefully.

The mechanism

Map both the keys and the nodes onto a ring: a hash space that wraps around at its maximum value. A key belongs to the first node found going clockwise from the key's position.

        node A
      /        \
   key1          key2 ---> belongs to node B (next clockwise)
     |            |
   node D       node B
      \        /
        node C

Add or remove a node and only the keys between that node and its predecessor move. The expected reassignment is K/N, not K·(N−1)/N, where K is the number of keys. Going from 10 nodes to 11 moves about 1/11 ≈ 9% of the keys instead of ~91%. That is the entire point, and it is a large constant-factor difference.

Virtual nodes: required, not optional

With one ring position per node, the arc lengths are random and vary a lot: some nodes own 3 times more than others. Worse, removing a node dumps its whole load on exactly one successor, and that is often enough to knock that node over too. That is cascading failure by design.

The fix: give each physical node V ring positions (V is typically 100–256). Then:

• Load evens out. The variance falls roughly as 1/√V. (With V = 100 the typical spread is about 10%; with V = 256, about 6%.)
• A departure spreads over many successors instead of one. This is the more important benefit, and the one people forget.

• Different capacities are easy to express. A node with 2× capacity gets 2V positions. Weighting is free.

The cost: V times more ring memory, and a slightly slower lookup (a binary search over N·V positions, still trivial).

import bisect, hashlib

def h(s: str) -> int:
    return int(hashlib.md5(s.encode()).hexdigest(), 16)

class Ring:
    def __init__(self, nodes, vnodes=128):
        self.ring = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
        self.points = [p for p, _ in self.ring]

    def node_for(self, key: str) -> str:
        i = bisect.bisect(self.points, h(key)) % len(self.ring)   # first point clockwise
        return self.ring[i][1]

Bounded loads

Plain consistent hashing balances keys, not load. Real keys have very different request rates. Consistent hashing with bounded loads caps each node at (1 + ε) × average load. If the target node is at its cap, the lookup walks clockwise to the next node that has room. This keeps most of the stability and also enforces a real load bound. It is used by HAProxy and Vimeo, and it comes from work at Google. Know it, because the failure of plain consistent hashing under skewed request rates surprises people.

Rendezvous (HRW) hashing

For each key, compute hash(key, node_i) for every node, then pick the node with the highest value. That is the whole algorithm. (HRW means highest random weight.)

def rendezvous(key: str, nodes: list[str]) -> str:
    return max(nodes, key=lambda n: h(f"{key}|{n}"))

Why it is often better than the ring

• No ring, no virtual nodes, no state. Any client can compute the mapping from the node list alone.
• Optimal disruption. Remove a node and only its keys move, and they spread across all remaining nodes according to their next-highest score. Add a node and only the keys for which it now scores highest move. This is provably the minimum, and it is better than plain consistent hashing without needing virtual nodes to repair it.
• Better distribution than a ring with a modest V, with no tuning parameter.
• An ordered fallback for free. The top-k scores give a natural replica list and a natural failover order, and every client computes the same list without coordination.
• Weights through score = -w / ln(h), where h is the hash scaled to a number between 0 and 1 (weighted rendezvous). This is clean and exact.

The one real cost

A lookup is O(N) (it touches every node), against O(log N) for the ring. At N = 10 nodes this is irrelevant: ten hash computations. At N = 10,000 it matters, and you need hierarchical rendezvous (a tree of clusters with a branching factor, giving O(log N)).

When to use which

An honest assessment: for most application-level cases (client-side load balancing, choosing a cache node, shard assignment with tens of nodes) rendezvous is the better default and is underused. Consistent hashing dominates in practice largely for historical reasons (the influence of Amazon's Dynamo paper) and because it is genuinely better at very large N.