Introduction

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.

Try It

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">40 keys are assigned to servers using rendezvous (highest random weight) hashing.
    Each server gets roughly an equal share. Add or remove a server and watch <b>only</b> the
    affected keys move — everything else stays put.</p>
<div class="controls">
  <button id="btn-add" type="button">Add server</button>
  <button id="btn-remove" type="button">Remove server</button>
  <button id="btn-reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Rendezvous (Highest Random Weight) hashing demo.
// hash(key, server) -> deterministic score; each key goes to the server with
// the highest score. On server list change only keys whose winner changed move.

const KEYS = 40;
const PALETTE = ['#1d6fa4','#e07b39','#2a9d5c','#9b59b6','#e63946','#e6a817','#0097a7'];
const NAMES = ['A','B','C','D','E','F','G'];

function hashScore(key, server) {
  // Well-mixed unsigned 32-bit score from (key, server) pair.
  // All intermediate steps use >>> 0 to stay unsigned.
  let a = ((key + 1) * 2654435761 + server * 2246822519) >>> 0;
  a = (a ^ (a >>> 16)) >>> 0;
  a = Math.imul(a, 0x45d9f3b) >>> 0;
  a = (a ^ (a >>> 16)) >>> 0;
  return a;
}

function assignKey(key, serverList) {
  let best = -1, winner = -1;
  for (const s of serverList) {
    const score = hashScore(key, s);
    if (score > best) { best = score; winner = s; }
  }
  return winner;
}

function computeAssignments(serverList) {
  return Array.from({ length: KEYS }, (_, k) => assignKey(k, serverList));
}

let servers = [0, 1, 2, 3];
let assignments = [];

function render(prevAssignments) {
  const cluster = document.getElementById('cluster');
  const legend = document.getElementById('legend');
  cluster.innerHTML = '';
  legend.innerHTML = '';

  const groups = {};
  for (const s of servers) groups[s] = [];
  for (let k = 0; k < KEYS; k++) groups[assignments[k]].push(k);

  for (const s of servers) {
    const col = document.createElement('div');
    col.className = 'server-col';

    const lbl = document.createElement('div');
    lbl.className = 'server-label';
    lbl.textContent = NAMES[s];
    lbl.style.color = PALETTE[s];
    col.appendChild(lbl);

    for (const k of groups[s]) {
      const dot = document.createElement('div');
      dot.className = 'key-dot';
      dot.style.background = PALETTE[s];
      if (prevAssignments && prevAssignments[k] !== assignments[k]) {
        dot.classList.add('moved');
      }
      dot.title = fmt('key %k%', { k: k });
      col.appendChild(dot);
    }
    cluster.appendChild(col);

    // legend entry
    const item = document.createElement('div');
    item.className = 'legend-item';
    const ldot = document.createElement('div');
    ldot.className = 'legend-dot';
    ldot.style.background = PALETTE[s];
    item.appendChild(ldot);
    item.appendChild(document.createTextNode(fmt('Server %v%: %length%', { v: NAMES[s], length: groups[s].length })));
    legend.appendChild(item);
  }

  document.getElementById('btn-remove').disabled = servers.length <= 1;
  document.getElementById('btn-add').disabled = servers.length >= NAMES.length;
}

function setStatus(msg) {
  document.getElementById('status').textContent = msg;
}

function init() {
  servers = [0, 1, 2, 3];
  assignments = computeAssignments(servers);
  render(null);
  setStatus(fmt('%KEYS% keys distributed across %length% servers.', { KEYS: KEYS, length: servers.length }));
}

document.getElementById('btn-add').addEventListener('click', () => {
  if (servers.length >= NAMES.length) return;
  const prev = assignments.slice();
  const newServer = servers.length;
  servers.push(newServer);
  assignments = computeAssignments(servers);
  const moved = assignments.filter((s, k) => s !== prev[k]).length;
  render(prev);
  setStatus(fmt('Added server %v%. %moved% keys moved (red outline) — %v2% untouched.', { v: NAMES[newServer], moved: moved, v2: KEYS - moved }));
});

document.getElementById('btn-remove').addEventListener('click', () => {
  if (servers.length <= 1) return;
  const prev = assignments.slice();
  const removed = servers[servers.length - 1];
  servers.pop();
  assignments = computeAssignments(servers);
  const moved = assignments.filter((s, k) => s !== prev[k]).length;
  render(prev);
  setStatus(fmt('Removed server %v%. Its %moved% keys spread to survivors (red outline).', { v: NAMES[removed], moved: moved }));
});

document.getElementById('btn-reset').addEventListener('click', init);

init();
Result
Console

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.

The Real Complexity

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

  • Lookup cost is O(N)O(N): to route a key you compute hash(key, serveriserver_{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 wiw_{i} and replace the raw score with −wiw_{i} / ln(uniform random based on hash). Keys migrate to heavier servers proportionally — still no shared state, still O(N)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)O(\log N) lookup for its own O(N)O(N) in exchange for simpler code, perfect balance, and easier reasoning about what moves when.

Where It Matters

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)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.

Conclusion

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)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rendezvous-hashing/Content licensed under CC BY-NC 4.0.