consistent-hash-lab

Add one cache node, lose 90% of your cache

With hash(key) % n, growing a cluster from 10 to 11 nodes gives almost every key a new owner, and every one of those is a cold miss. Consistent hashing moves only the 1/(n+1) share the new node should take. Below, one seeded key set runs through five schemes: modulo, a vnode ring, jump hash, rendezvous hashing and bounded loads. Everything runs in this tab.

1. One node joins

Each card places every key on , then again on one more, and counts the keys whose owner changed. The tag says whether every moved key went to the new node, or how many moved between nodes that were already there. The bars are keys per node before the join, with the fair share marked.

2. The ring

Each node hashes node#0, node#1 and so on onto a 32-bit circle. A key goes to the first point clockwise from its own hash, so each coloured arc is the share of keys that node owns. With one point per node the arcs are wildly uneven; with a hundred they average out, which is why the ring card above flattens as the vnode slider goes up.

Jump hash and rendezvous need no ring. Jump hash runs a 64-bit LCG seeded by the key and jumps through bucket numbers in O(log n) with no memory, but only the last bucket can leave. Rendezvous scores every node against the key and takes the top score, which costs O(n) per lookup and lets any node leave.

Bounded loads keep the ring and add a cap: no node may hold more than ceil((1 + epsilon) * m / n) of the m keys placed so far, and a key whose node is full walks on to the next one with room.

3. In code

Each scheme is one small module with no dependencies, tested with node --test for the property that makes it consistent: when a node joins, keys only move to that node.

import { createRing } from "./src/ring.js";
import { jumpHash } from "./src/jump.js";
import { rendezvous } from "./src/rendezvous.js";

const ring = createRing({ vnodes: 100 });
["cache-a", "cache-b", "cache-c"].forEach((n) => ring.add(n));
ring.lookup("user:42");          // one of the three

jumpHash("user:42", 3);          // bucket 0..2
rendezvous("user:42", ["a", "b", "c"],
  { weights: { a: 1, b: 2, c: 1 } });