hash % n breaks when n changes
To split data over 4 cache servers you might pick hash(key) % 4. Add a fifth server and % 5 sends almost 80% of keys somewhere new — a flood of cache misses. Consistent hashing places servers on a ring; each key goes to the next server clockwise. Add a server and only the keys it takes over move — about one in five.
The ring
function fnv1a(text) {
let h = 0x811c9dc5;
for (let i = 0; i < text.length; i++) {
h ^= text.charCodeAt(i);
h = Math.imul(h, 0x01000193) >>> 0;
}
return h;
}function createRing(nodes = [], vnodes = 100) {
let points = [];
function add(node) {
for (let v = 0; v < vnodes; v++) points.push({ hash: fnv1a(`${node}#${v}`), node }); // many points per node
points.sort((a, b) => a.hash - b.hash);
}
const ring = {
add,
remove(node) {
points = points.filter((p) => p.node !== node);
},
nodeFor(key) {
if (points.length === 0) throw new Error("Empty ring");
const h = fnv1a(key);
let lo = 0;
let hi = points.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (points[mid].hash < h) lo = mid + 1;
else hi = mid;
}
return points[lo % points.length].node; // first point clockwise, wrapping around
},
};
nodes.forEach(add);
return ring;
}