Rendezvous Hashing

Imagine you run a cluster of cache servers and a million requests per second need to find the right one. The naive answer — key mod N — crumbles the moment a server joins or leaves: suddenly almost every key maps to a different node, the cache goes cold, and the origin gets hammered.

The smarter answer is consistent hashing, and its most elegant variant is rendezvous hashing (also called Highest Random Weight, or HRW). First described by David Thaler and Chinya Ravishankar at the University of Michigan in 1996, the idea is almost absurdly simple: for a given key, compute one hash score per server, and send the key to the server with the highest score. No ring structure, no virtual nodes, no coordinator process, no shared state.

When a server is added, only the keys whose scores it now wins move to it — all other assignments are undisturbed. When a server is removed, its keys are redistributed by re-running the same competition among the survivors. In both cases exactly the minimum number of keys moves, which is precisely 1/N of the total (where N is the new server count).

Related reading: load balancing and consistent hashing show the broader landscape of distributed routing tricks.

The demo below shows 30 keys distributed across a cluster of servers. Each colored column represents one server; each dot is a key assigned to it. Add a new server and watch only a fraction of keys migrate. Remove a server and its keys scatter to the survivors — everyone else keeps their owner.

<p class="hint">{{hint}}</p>
<div class="controls">
  <button id="btn-add" type="button">{{btn_add}}</button>
  <button id="btn-remove" type="button">{{btn_remove}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="cluster"></div>
<div class="legend" id="legend"></div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
#cluster { display: flex; gap: 10px; flex-wrap: wrap; align-items: flex-end; margin-bottom: .2rem; }
.server-col { display: flex; flex-direction: column; align-items: center; gap: 3px; min-width: 40px; }
.server-label { font: 700 12px system-ui; margin-bottom: 3px; }
.key-dot { width: 13px; height: 13px; border-radius: 50%; }
.key-dot.moved { outline: 2.5px solid #e63946; outline-offset: 1px; }
.legend { display: flex; gap: 10px; flex-wrap: wrap; font-size: .8rem; margin-top: .4rem; }
.legend-item { display: flex; align-items: center; gap: 4px; }
.legend-dot { width: 11px; height: 11px; border-radius: 50%; flex-shrink: 0; }
.status { font-size: .92rem; font-weight: 600; margin-top: .6rem; min-height: 1.3em; color: #1d3557; }

// Code not found

Notice that when you add server E, roughly 1/5 of keys move to it — but no key that was on server A moves to server B or C. That isolation is the whole point: the only disruption is the disruption you absolutely cannot avoid.

Rendezvous hashing is a solved, efficient algorithm — not a hard open problem. Its properties are precisely understood:

• Lookup cost is $O(N)$: to route a key you compute hash(key, $server_{i}$) for every server i. With N servers that is N hash evaluations. For small clusters (dozens to low hundreds of servers) this is negligible; for very large clusters it becomes a bottleneck compared to ring-based approaches.
• Disruption is provably minimal: when the server count changes from N to N±1, exactly 1/(N+1) or 1/(N−1) of all keys move on average — the theoretical minimum. No other scheme can do better without additional shared state.
• No shared state: every client independently computes the same answer given the same server list. There is no coordinator, no ring metadata to synchronize, no version vector to agree on.
• Balance depends on the hash function: a good hash (e.g. SHA-256 or MurmurHash keyed on the concatenation of key and server name) distributes keys uniformly. A poor hash produces hot spots.
• Weighted variants: assign each server a weight $w_{i}$ and replace the raw score with −$w_{i}$ / ln(uniform random based on hash). Keys migrate to heavier servers proportionally — still no shared state, still $O(N)$.

The algorithm sits in the family of consistent hashing schemes, introduced by Karger et al. (1997) for web caches. Rendezvous hashing predates that paper by a year and trades the ring's $O(\log N)$ lookup for its own $O(N)$ in exchange for simpler code, perfect balance, and easier reasoning about what moves when.

Any system that needs to route a key to one of N servers — and survive server churn — benefits from rendezvous hashing:

• Content Delivery Networks (CDNs): edge nodes use HRW to decide which cache server handles a given URL. When an edge node goes offline, only its URLs re-fetch from origin; all other URLs stay warm.
• Distributed databases: systems like Apache Cassandra and Couchbase use variants of consistent hashing to partition data. Rendezvous hashing is a clean alternative for clusters small enough that $O(N)$ lookup is acceptable.
• Peer-to-peer overlays: the Kademlia DHT and its relatives assign responsibility for keys to the node with the numerically closest ID — a distance-based variant of the same winner-takes-all idea.
• Microservice routing: an API gateway can use HRW to pin a user session to one backend pod without sticky sessions or session affinity configuration in the load balancer.
• Feature flag targeting: assign users to experiment buckets deterministically — same user always lands in the same bucket, even if the bucket count changes, with minimal reassignment.

The common thread is stateless determinism: any node in the system can independently compute the correct routing decision using only the key and the server list. No gossip protocol, no Paxos round, no single point of failure.

Rendezvous hashing distills a genuinely hard distributed systems problem — "route every key consistently across a changing cluster" — into a single elegant rule: compute one score per server, pick the max. No ring, no coordinator, no shared metadata.

The trade-off is honest: $O(N)$ lookup cost means it scales best when N is in the dozens or low hundreds. For massive clusters ring-based consistent hashing or jump consistent hashing may be preferable. But for the common case, rendezvous hashing is correct by construction, easy to implement, and provably optimal in the disruption it causes.

The next time a cache server goes down and your users barely notice, there is a good chance a variant of this 1996 algorithm is quietly doing the math.