Consistent hashing vs rendezvous (HRW) hashing — which for what scale?

// Ring (with and without vnodes) vs rendezvous / highest-random-weight hashing:
// balance, keys moved on join and leave, work per lookup, and replica sets.
function h32(s) {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16;
  return h >>> 0;
}
const x2 = (num, den) => { const v = Math.floor((num * 100) / den); return Math.floor(v / 100) + "." + String(v % 100).padStart(2, "0"); };
const KEYS = 20000;
const keys = []; for (let i = 0; i < KEYS; i++) keys.push("user:" + i);
const names = (n) => { const r = []; for (let i = 0; i < n; i++) r.push("node-" + i); return r; };
let steps = 0, hashCalls = 0;

function ring(nodes, v) {
  const r = [];
  for (const n of nodes) for (let t = 0; t < v; t++) r.push([h32(n + "#" + t), n]);
  r.sort((a, b) => a[0] - b[0] || (a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0));
  return (key) => {
    hashCalls++; const hk = h32(key);
    let lo = 0, hi = r.length;
    while (lo < hi) { steps++; const mid = (lo + hi) >> 1; if (r[mid][0] < hk) lo = mid + 1; else hi = mid; }
    return r[lo === r.length ? 0 : lo][1];
  };
}
function rank(nodes, key) { // every node gets a score for this key; highest wins
  hashCalls += nodes.length;
  return nodes.map((n) => [h32(n + "/" + key), n]).sort((a, b) => b[0] - a[0] || (a[1] < b[1] ? -1 : 1)).map((p) => p[1]);
}
const hrw = (nodes) => (key) => rank(nodes, key)[0];

const schemes = [["ring, 1 vnode", (ns) => ring(ns, 1), true], ["ring, 100 vnodes", (ns) => ring(ns, 100), true], ["rendezvous (HRW)", hrw, false]];
const ten = names(10), eleven = names(11), nine = ten.filter((n) => n !== "node-4");
console.log("10 nodes, 20000 keys (fair share 2000). Then add node-10, or remove node-4.");
console.log("scheme             busiest/fair  add: moved  to new node  remove: moved  receivers  hashes/lookup  search steps");
for (const [label, make, isRing] of schemes) {
  steps = 0; hashCalls = 0;
  const f10 = make(ten);
  const own = keys.map(f10);
  const perLookupHash = hashCalls / KEYS, perLookupSteps = isRing ? x2(steps, KEYS) : "-";
  const c = {}; for (const o of own) c[o] = (c[o] || 0) + 1;
  const busiest = Math.max(...Object.values(c));
  const f11 = make(eleven), f9 = make(nine);
  let addMoved = 0, toNew = 0, remMoved = 0; const recv = new Set();
  keys.forEach((k, i) => {
    const a = f11(k); if (a !== own[i]) { addMoved++; if (a === "node-10") toNew++; }
    const b = f9(k); if (b !== own[i]) { remMoved++; recv.add(b); }
  });
  console.log(`${label.padEnd(19)}${(x2(busiest * 10, KEYS) + "x").padStart(12)}  ${String(addMoved).padStart(10)}  ${String(toNew).padStart(11)}  ${String(remMoved).padStart(13)}  ${String(recv.size).padStart(9)}  ${String(perLookupHash).padStart(13)}  ${perLookupSteps.padStart(12)}`);
}

console.log("\nReplica sets with HRW: the top 3 scores are the 3 replicas.");
let sample = 0; while (!rank(ten, "user:" + sample).slice(0, 3).includes("node-4")) sample++;
console.log(`  user:${sample} on 10 nodes:     ` + rank(ten, "user:" + sample).slice(0, 3).join(", "));
console.log(`  user:${sample} without node-4: ` + rank(nine, "user:" + sample).slice(0, 3).join(", "));
let changed = 0, oneSwap = 0;
for (const k of keys) {
  const a = rank(ten, k).slice(0, 3), b = rank(nine, k).slice(0, 3);
  if (a.join() !== b.join()) { changed++; if (a.filter((n) => !b.includes(n)).length === 1) oneSwap++; }
}
console.log(`  removing node-4 changed ${changed} of ${KEYS} replica sets; ${oneSwap} of them swapped exactly one member`);

console.log("\nWork per lookup as the cluster grows (ring with 100 vnodes per node):");
console.log("nodes   HRW hashes  ring entries  ring search steps");
for (const n of [10, 100, 1000, 10000]) {
  let s = 0; while ((1 << s) < n * 100) s++;
  console.log(`${String(n).padEnd(8)}${String(n).padStart(10)}  ${String(n * 100).padStart(12)}  ${String(s).padStart(17)}`);
}