Consistent Hashing's own Pitfalls section
measured a real problem and named its fix without building it: with three nodes hashed onto one
ring position each, cache-south, cache-remote, and
cache-central land at positions 306, 473, and 690 out of 1000 — and the gap from
cache-central back around to cache-south is 616 of those 1000 positions,
so cache-south alone owns 61.6% of the ring. Nothing is wrong; three random numbers
just happened to fall that way. Virtual nodes fix it by hashing each physical
server onto many ring positions instead of one — commonly 100 or more — so no single unlucky gap
can dominate. This page builds that, and finds a real, checkable trap in the obvious way to
generate those extra positions.
Same three default nodes as the parent page, now each hashed onto K ring positions instead of 1. Pick K, add or remove a node, and watch the per-node share table and the ring itself — every small dot is one virtual point, colored by which physical node it belongs to. Check "naive replica hashing" to switch the point-generation formula to the broken one this page's Pitfalls section measures — watch the dots for one color clump into one or two tight arcs instead of spreading around the ring.
K distinct ring positions for this
one physical node and insert all of them into the sorted position array, each tagged with the
same owner name. O(K log(nK)) for a ring already holding nK points.
Generating the K positions is the one genuinely new step over plain consistent
hashing — see Pitfalls for why the obvious way to do it barely works.O(nK) to filter the array. Skipping this — removing only the first
matching entry — is a real, checked bug; see Pitfalls.O(log(nK)) — one binary search over a ring that's now
K times longer than plain consistent hashing's, the direct cost of this technique.Same sorted-array-plus-binary-search shape as the parent page's ConsistentHashRing,
with two changes: addNode takes a replica count and generates that many positions per
node, and each ring position now stores an owner separately from a node identity. The position
generator is an iterative rehash: hash the node's name once to get a seed, then
repeatedly hash the seed's own decimal string to get each next replica's position. Feeding the
entire previous hash back in — not just appending a small counter — is what makes each replica's
position differ from the last by an unpredictable amount instead of a predictable one:
class ConsistentHashRingVN {
static RING_SIZE = 1000;
#points = []; // [{ pos, owner }], kept sorted by pos
#hash(s) {
let h = 0;
for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0;
return h;
}
addNode(name, K) {
let seed = this.#hash(name);
const taken = new Set(this.#points.map(p => p.pos));
for (let i = 0; i < K; i++) {
let pos = seed % ConsistentHashRingVN.RING_SIZE; // replica 0 is the plain hash itself
while (taken.has(pos)) pos = (pos + 1) % ConsistentHashRingVN.RING_SIZE;
taken.add(pos);
this.#insertSorted(pos, name);
seed = this.#hash(String(seed)); // rehash the whole seed for the next replica
}
}
removeNode(name) {
this.#points = this.#points.filter(p => p.owner !== name); // every replica, not just one
}
#insertSorted(pos, owner) {
let i = 0;
while (i < this.#points.length && this.#points[i].pos < pos) i++;
this.#points.splice(i, 0, { pos, owner });
}
assign(key) {
const pos = this.#hash(key) % ConsistentHashRingVN.RING_SIZE;
let lo = 0, hi = this.#points.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.#points[mid].pos >= pos) hi = mid; else lo = mid + 1;
}
return this.#points[lo === this.#points.length ? 0 : lo].owner;
}
}assign itself was verified once already, on the parent page, against a brute-force
linear scan — nothing about it changes here beyond the array being K times longer.
The position generator is built so that a single node at K=1 reduces to exactly the parent page's
own single-hash scheme (replica 0 is the plain hash, not a rehash of it) — checked directly: this
page's three default nodes at K=1 reproduce the parent page's own 61.6% / 16.7% / 21.7% split
exactly. Exact position collisions do happen as K grows and get resolved by the same nudge-forward
loop the parent page uses — measured across 100 trials per K (3–8 random nodes each): a negligible
0.03 nudges per trial at K=1, rising to 8.2 at K=20 and a full 502 at K=100, where up to 800 points
are competing for slots in a ring that only has 1000 — see Complexity for why that specific number
matters.
The obvious way to generate K positions per node — hash name + "#" + i for
i = 0..K-1 — barely improves on not using virtual nodes at all, with this page's own hash
function. The fold hash h = h * 31 + c accumulates left to right, so two
strings that differ only in their last character or two produce outputs that differ only by a
small, predictable amount — exactly the mechanism Consistent Hashing's own second pitfall already
demonstrated for node names that share a prefix. Here it's worse, because the whole point of
generating K positions is that they land far apart. Checked directly: hashing
cache-south#0 through cache-south#19 at K=20 doesn't produce 20 spread-out
positions — it produces exactly two runs of 10 consecutive positions each, 967–976 and
688–697, because i from 0–9 changes one character and i from
10–19 changes two, and each family folds through the hash almost linearly. On this page's own
three-node default at K=20, that leaves one node owning half the ring — cache-central
at 52.1% (23.1% / 24.8% / 52.1% across the three nodes) — barely better than the
no-virtual-nodes baseline's worst case of 61.6%, and worse than what correct virtual nodes achieve
on the identical three nodes at the identical K: 23.6% / 40.9% / 35.5%, every node within ten
points of the ideal 33.3% instead of one node taking half the ring. A broader sweep confirms it's
not this one example: across 300 random node sets (3–8 nodes) at K=20, the naive scheme's mean
largest share is 37.6% versus the correctly-mixed scheme's 25.7%.
The iterative-rehash fix in this page's
reference implementation works because it feeds the entire previous hash back in as a new
string on every replica — changing many characters at once, not one trailing digit — which is
exactly the property the fold hash needs to mix well.
Removing a node has to delete every one of its K positions — deleting just one is a
real bug, not a smaller version of correct removal. Checked against this page's own
three-node, K=20 default with 200 sample keys: cache-south starts out owning 53 of
them. A buggy removeNode that deletes only the first matching ring position (a
one-character typo away from the correct version — splice one match instead of
filter everything) leaves 19 of cache-south's 20 positions still on the
ring. Result: 48 of its 53 former keys — 90.6% — still resolve to
cache-south, a node that's supposed to be gone; only the handful whose nearest
remaining ring point used to be that one deleted position move away. The failure is silent: no
error, no crash, every lookup returns an answer, and the vast majority of those answers are wrong.
This is the same shape of bug as forgetting to update every table a value lives in — the node
looks removed from whatever list a UI reads, but the ring itself, which is what assign
actually consults, mostly still has it.
Time: addNode is O(K log(nK)) for a ring already
holding nK points (K inserts, each a sorted-array insertion); removeNode
is O(nK) to filter the array; assign is O(log(nK)), one
binary search over a ring K times longer than plain consistent hashing's — the direct,
quantifiable cost of the balance this technique buys. Space: O(nK)
for the position array, versus plain consistent hashing's O(n).
The balance improvement itself has diminishing returns, and this demo's small 1000-position ring makes that visible in a way a real deployment's ring usually isn't: the 300-trial sweep above found mean largest share dropping from 45.8% (K=1) to 30.8% (K=5) to 26.0% (K=20), but K=50 and K=100 measured 24.1% and 23.4% — barely any further improvement, because at K=100 with as few as 3 nodes this ring is placing up to 800 points into only 1000 slots, the same resolution limit the reference implementation's own nudge counts above already showed climbing steeply at that K (502 nudges per trial, versus 8.2 at K=20). Production rings use a much larger position space (commonly 232 or more, the same point Consistent Hashing's own Pitfalls section makes about single-node placement), which is exactly what lets K keep paying off well past 100 instead of plateauing this early.