Rendezvous Hashing: Picking a Server Without a Ring

The core idea: argmax of a mixing hash

You have a key k and a set of nodes S = {s₁, …, sₙ}. Rendezvous hashing defines a scoring function w(k, sᵢ) = h(k, sᵢ), where h is a hash that mixes both arguments (not h(k) ⊕ h(sᵢ) — because XOR is linear, the relative ranking of any two nodes then depends only on h(sᵢ) ⊕ h(sⱼ), which is independent of the key, so every key would pick the same winner). The chosen node is simply:

owner(k) = argmax over sᵢ ∈ S of  h(k, sᵢ)

That's it. Every client independently computes the same n scores and picks the same maximum, so no client-to-client communication is needed to agree on placement. The magic is in two invariants that fall out of using a good hash:

• Determinism: for a fixed S, owner(k) is a pure function of k — same key, same answer, forever.
• Independence of ordering: the winner depends only on the set S, not the order you list nodes in. Adding or removing a node cannot change the relative order of the surviving nodes' scores.

This second invariant is the entire reason HRW is minimally disruptive. If node sⱼ was the argmax for key k and sⱼ stays alive, no addition or removal of other nodes can dethrone it — its score was already the highest. Only keys that were owned by a departed node get remapped.

Why this beats hash(key) mod n

The naïve alternative is owner(k) = h(k) mod n. It's O(1) and dead simple — and catastrophic under membership change. Change n from 100 to 101 and the modulus shifts almost every key: roughly (n−1)/n ≈ 99% of keys get a new owner. For a cache, that's a near-total cache miss storm; for a sharded store, it's a full data reshuffle.

Rendezvous hashing fixes exactly this. When you go from n to n+1 nodes, a key changes owner only if the new node's score beats its current winner. For a uniformly random hash, the probability the newcomer is the argmax over n+1 nodes is exactly 1/(n+1). So:

• Adding one node: steals a fraction 1/(n+1) of all keys, evenly drawn from all existing nodes. Everything else is untouched.
• Removing one node: its keys — its ≈1/n share — are redistributed among the survivors by taking the next-highest score. No other key moves.

This is the theoretical minimum churn: you cannot remap fewer keys than the ones that lived on the failed node. HRW hits that lower bound, and it does so without the ring, the sorted array, and the fleet of virtual nodes that consistent hashing needs to smooth its load.

The algorithm, step by step

The basic lookup is a linear scan tracking the running maximum — the same pattern as finding the max of an array:

function owner(k, S):
    best_node = null
    best_score = -∞
    for s in S:              # n iterations
        score = h(k, s)      # mix key and node id
        if score > best_score:
            best_score = score
            best_node  = s
    return best_node

Selecting k replicas (for redundancy) is equally natural and is where HRW shines relative to a ring: instead of walking clockwise to find distinct nodes, you just take the nodes with the top-k scores. Partial-sort or a bounded min-heap of size k does this in O(n log k):

function top_k(k, K_key, S):
    heap = min-heap of size k          # keyed by score
    for s in S:
        push (h(K_key, s), s)
        if heap.size > k: pop_min()
    return heap sorted descending      # the k owners, in priority order

Because scores impose a total order per key, the replica set for a key is a stable prefix: if node #1 dies, the old #2 becomes primary, #3 becomes secondary, and a single new node slides in at the bottom — exactly the well-behaved failover you want, with no reshuffle of the surviving replicas' roles.

Complexity analysis and the O(log n) skeleton

The basic scheme costs one hash per node per lookup:

• Time: Θ(n) hash evaluations per key lookup — best, average, and worst case are all Θ(n), since you must score every candidate to find the true argmax.
• Space: O(n) to store the node list; no per-key state, no ring structure.
• Add/remove a node: O(1) to update the set; membership change requires no precomputation.

The Θ(n) per-lookup cost is fine for n in the tens or low hundreds — a handful of nanoseconds each with a fast hash like xxHash or a truncated SHA. But at n in the thousands (large clusters), the linear scan hurts. Thaler and Ravishankar's fix is skeleton-based (hierarchical) rendezvous hashing: arrange the nodes as the leaves of a virtual tree of fixed fan-out, and run HRW recursively level by level — pick the winning subtree, descend, repeat.

• With a tree of depth O(log n), each level does O(1) HRW among a constant number of children, giving O(log n) hashes per lookup.
• The trade-off: hierarchical HRW slightly relaxes the exact minimal-disruption guarantee (churn stays O(1/n) in expectation but the structure adds a small constant), and rebalancing is confined to the subtree of the changed node.

So you get a genuine choice: flat HRW for small n (simplest, exactly minimal churn), skeleton HRW for large n (logarithmic lookups). Compare this with consistent hashing, which is O(log n) via binary search on a sorted ring but pays O(n·v) space for its v ≈ 100–200 virtual nodes per real node.

Load balancing and weighted nodes

With a good hash, HRW spreads keys uniformly: each node is the argmax for a fraction 1/n of the keyspace in expectation, with the relative deviation shrinking like 1/√(load per node). Critically, no virtual nodes are required — the uniformity comes for free from scoring every node independently, which is the single biggest operational simplification over ring-based consistent hashing (whose raw form is notoriously lumpy until you sprinkle in hundreds of vnodes).

Heterogeneous capacity is handled by weighted rendezvous hashing. The clean formulation (from Schindelhauer & Schomaker, and refined by Jason Resch's log-based trick) maps the hash into a uniform value u ∈ (0,1) and computes:

score(k, sᵢ) = -weightᵢ / ln( uniform(h(k, sᵢ)) )

Taking the argmax of this score selects node sᵢ with probability exactly proportional to weightᵢ. A node with twice the weight owns twice the keys — and it composes correctly under membership change, unlike ad-hoc vnode-count tuning. Set all weights equal and you recover plain HRW. This makes it trivial to give a beefy 64-core box 4× the shards of a small one, or to drain a node before maintenance by ramping its weight to zero.

Where it runs in production

Rendezvous hashing quietly powers a lot of infrastructure:

• Ceph's CRUSH algorithm uses rendezvous-style straw2 buckets: for each item, every candidate device draws a weighted straw and the longest straw wins — HRW by another name, giving stable, weighted, replica-aware placement across the storage cluster.
• Apache Ignite uses a rendezvous affinity function as its default partition-to-node mapper, precisely because it needs stable assignment with minimal movement when the topology changes.
• CDN and cache request routing: many edge tiers pick an origin/cache peer via HRW so that independent edge nodes agree on which peer owns a URL, maximizing cache-hit ratio without a shared coordination service.
• Kafka-style and gRPC client-side load balancers and sticky-session routers use HRW to pin a client or key to a backend deterministically while surviving backend churn gracefully.

The standard references are Thaler & Ravishankar, "Using Name-Based Mappings to Increase Hit Rates" (IEEE/ACM ToN, 1998, from their 1996 work) and, for the weighted log-trick, Jason Resch's "New Hashing Algorithms for Data Storage". Karger et al.'s 1997 consistent-hashing paper is the sibling worth reading alongside it.

Pitfalls, edge cases, and variants

HRW is simple but there are real ways to get it wrong:

• Don't XOR the hashes. h(k) ⊕ h(sᵢ) is not a valid scoring function: because XOR is linear the per-key node ordering collapses to a single key-independent ranking, so every key funnels to the same node and uniformity is destroyed. You must hash the concatenation or feed both into a single mixing function so key and node interact.
• Tie-breaking. With a good 64-bit hash, collisions among n scores are astronomically unlikely, but a correct implementation still needs a deterministic tie-break (e.g., higher node id wins) so all clients agree.
• The O(n) cost is per lookup, not per rebuild. On a hot path serving millions of keys/sec with thousands of nodes, flat HRW's Θ(n) hashing dominates — reach for the skeleton variant or cache the mapping. Consistent hashing's O(log n) lookup can win purely on constant factors here.
• Hash quality matters. A weak hash (e.g., a poor mix or truncating to too few bits) reintroduces both load imbalance and disruption. Use a well-mixed non-cryptographic hash (xxHash, wyhash, murmur3) unless you need adversary-resistance, in which case truncate a keyed cryptographic hash.
• Variants to know: skeleton/hierarchical HRW for O(log n) at large scale; weighted HRW for heterogeneous capacity; and controlled replication (top-k) for redundancy. Jump consistent hashing is a different O(log n) alternative but only maps to numbered buckets, not arbitrary node ids.

Rendezvous hashing vs. consistent hashing (ring) for placing one key across n nodes

Property	Rendezvous (HRW)	Consistent hashing (ring)
Lookup for one key	O(n) hashes (or O(log n) skeleton)	O(log n) binary search on sorted ring
State per client	O(n) — just the node list	O(n·v) — ring with v virtual nodes each
Load balance	Near-uniform, no vnodes needed	Uneven unless v ≈ 100–200 vnodes/node
Keys moved when a node leaves	Exactly its ≈1/n share	Its ≈1/n share (only its ring arcs)
Top-k / replica selection	Natural: take top-k scores	Walk ring clockwise past distinct nodes
Weighted nodes	Clean: scored HRW weighting	Adjust vnode count per node