THE FOLD / CO-OP / THE PUSH / THE JUMP CONSISTENT HASH
THE JUMP CONSISTENT HASH
buckets that barely move when you add one
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Jump consistent hashing maps a key to one of N buckets so that when N grows, almost no keys move — and it does so with no lookup table, in a few lines and O(1) memory. It replays a tiny pseudo-random sequence seeded by the key, and each “jump” decides whether the key hops to a higher bucket; the last bucket it lands on is the answer. Two guarantees fall out: the keys spread uniformly across buckets, and going from N to N+1 buckets relocates only about 1/(N+1) of the keys — and every one that moves goes straight to the new bucket, never shuffling among the old ones.
LIT verified live: 100,000 keys spread within a few percent of uniform across the buckets, and growing N→N+1 moves a fraction ~1/(N+1) of keys, each landing exactly on the new bucket (window.__jump). FIG no framing; the hash, the distribution, and the remap count all run in-browser.
LIT verified live: 100,000 keys spread within a few percent of uniform across the buckets, and growing N→N+1 moves a fraction ~1/(N+1) of keys, each landing exactly on the new bucket (window.__jump). FIG no framing; the hash, the distribution, and the remap count all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-push — adding a node pushes only its fair share of keys onto the newcomer, leaving everyone else untouched. AVAN (AI) built the instrument: the jump hash with a 64-bit LCG, a uniformity check, and a remap sweep from N to N+1.
Credit as content: John Lamping & Eric Veach (Google, 2014). The weave: David names the push; I confirm the spread is uniform and that only ~1/(N+1) of keys move, all to the new bucket.
Credit as content: John Lamping & Eric Veach (Google, 2014). The weave: David names the push; I confirm the spread is uniform and that only ~1/(N+1) of keys move, all to the new bucket.
3 ONE DIMENSION
Keys spread across the buckets — a near-flat histogram, no lookup table behind it, just a replayed pseudo-random sequence per key.
4 TWO DIMENSIONS · INTERACTIVE
Add a bucket; only about 1/(N+1) of the keys move, and every one of them jumps straight to the new bucket — the rest stay put.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: keys resting in their buckets, spread evenly.
AVAN’s addition (the inverse-companion): don’t rehash everything when a node joins — move only the newcomer’s share. The inverse of ‘N changed, recompute all’ is ‘only ~1/(N+1) of keys jump, and only ever onto the new bucket.’ Magenta are the keys that move; green are the many that stay. Add a node, barely disturb the rest.
LIT Genuine jump consistent hash (John Lamping & Eric Veach, Google, 2014): table-free, O(1)-memory consistent hashing. Verified live: 100k keys uniform within ~6% across buckets (window.__jump.uniform), N→N+1 moves a fraction ≈ 1/(N+1) (.minimalRemap), and every moved key goes only to the new bucket (.movesToNew).
FIG No framing: the jump hash (a 64-bit LCG via BigInt), the distribution, and the N→N+1 remap sweep all run in-browser. The AVAN inverse is honest — moving only the newcomer's ~1/(N+1) share (all onto the new bucket) rather than rehashing everything is the whole point of consistent hashing; magenta are the keys that move, green the many that stay. Add a node, barely disturb the rest.
FIG No framing: the jump hash (a 64-bit LCG via BigInt), the distribution, and the N→N+1 remap sweep all run in-browser. The AVAN inverse is honest — moving only the newcomer's ~1/(N+1) share (all onto the new bucket) rather than rehashing everything is the whole point of consistent hashing; magenta are the keys that move, green the many that stay. Add a node, barely disturb the rest.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PUSH · David Lee Wise (ROOT0), with AVAN