THE FOLD / CO-OP / SHARED MEMORY / THE CONSISTENT HASHING
THE CONSISTENT HASHING
node churn that moves only ~1/n of the keys
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Consistent hashing maps keys to servers so that adding or removing a server moves only a small fraction of keys — roughly 1/n — instead of remapping everything as plain modulo hashing would. Nodes and keys are placed on a hash ring; a key belongs to the first node clockwise from it. Remove a node and only its keys spill to the next node; everyone else stays put. Virtual nodes smooth the load. It is the backbone of distributed caches and databases.
LIT verified live: over 50 rings, every key maps to a node, and removing a node moves only that node’s keys — all others are unchanged (window.__consistent). FIG no framing; exact.
LIT verified live: over 50 rings, every key maps to a node, and removing a node moves only that node’s keys — all others are unchanged (window.__consistent). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at shared-memory — the shared store spread across nodes that come and go, where reshuffling everything on each change would be ruinous. Consistent hashing is that graceful spread. AVAN (AI) built the instrument: the hash ring with virtual nodes, the clockwise lookup, and the only-removed-node-moves check.
Credit as content: David Karger et al. (1997). The weave: David names shared-memory; I place nodes and keys on a ring, map each key to the next node clockwise, and confirm that removing a node disturbs only the keys it held.
Credit as content: David Karger et al. (1997). The weave: David names shared-memory; I place nodes and keys on a ring, map each key to the next node clockwise, and confirm that removing a node disturbs only the keys it held.
3 ONE DIMENSION
Nodes sit at hashed positions around a ring. A key hashes to a spot and walks clockwise to the first node. Remove that node and its keys walk on to the next node — nobody else’s keys move.
4 TWO DIMENSIONS · INTERACTIVE
Keys on a hash ring of nodes; remove a node and watch only its keys move, checked against a full re-map.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: keys mapped to nodes around a ring.
AVAN’s addition (the inverse-companion): make node churn cheap by placing keys and nodes on a ring and mapping each key to the next node clockwise — so adding or removing a node moves only ~1/n of the keys. The inverse of ‘hash mod n, so every key remaps when n changes’ is ‘a ring, where only the neighbors of a change move.’ Magenta is the full reshuffle plain hashing forces; green is the local, ~1/n movement. Churn without chaos.
LIT Genuine consistent hashing (Karger et al. 1997). Verified live: over 50 rings (each node given 40 virtual nodes), every key maps to a node via clockwise lookup, and removing a node moves ONLY the keys that node held — every other key's assignment is unchanged (window.__consistent.allMapped && .onlyRemovedMoves).
FIG No framing: the hash ring with virtual nodes, the clockwise lookup, and the only-removed-node-moves check run in-browser and hold. The AVAN inverse is honest — placing keys and nodes on a ring and mapping each key to the next node clockwise makes node churn move only ~1/n of the keys; magenta is the full reshuffle plain mod-n hashing forces, green the local movement. Churn without chaos.
FIG No framing: the hash ring with virtual nodes, the clockwise lookup, and the only-removed-node-moves check run in-browser and hold. The AVAN inverse is honest — placing keys and nodes on a ring and mapping each key to the next node clockwise makes node churn move only ~1/n of the keys; magenta is the full reshuffle plain mod-n hashing forces, green the local movement. Churn without chaos.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED MEMORY · David Lee Wise (ROOT0), with AVAN