Stage 2: Virtual Nodes

stage 2 of 3 · ~25 min · runs in your browser

Objective:Extend the ring so each physical node owns K positions, producing statistically even load distribution across all nodes regardless of insertion order.

Virtual nodes (vnodes)K positions per physical nodeEven load distributionPosition namespace: hash(nodeId + '#' + i)Physical node deduplication

Extend createRing(vnodes = 100) so that addNode(nodeId) inserts K positions for each physical node, one per virtual node index:

for i in 0..vnodes-1:
  position = hash(nodeId + "#" + i)
  ring.insert({ position, nodeId })

removeNode(nodeId) must remove all K positions for the physical node.

getNode(key) uses the same binary search as Stage 1. The key's position lands on a vnode entry; the vnode entry's nodeId is the physical node.

With K=1, the ring behaves identically to Stage 1. With K=100 and 3 nodes, distributing 1000 keys should give each node between 25% and 42% of keys.

The nodes getter returns the full sorted ring array, including all vnode entries. Each physical node will appear K times.

Why this matters in production

With one position per physical node, the ring's load distribution depends entirely on where the hash function places those positions. With 3 nodes and unlucky hash values, one node might own 80% of the ring arc while another owns 5%. This hot-spot problem is structural -- no amount of configuration fixes it without changing the algorithm. Virtual nodes solve this by giving each physical node K non-contiguous positions spread across the ring. As K grows, the per-node fraction concentrates around 1/N by the law of large numbers. Cassandra uses K=256 (num_tokens per node). Memcached ketama uses K=160. In practice K=100 produces load within ±15% of 1/N for any ring with three or more nodes. This is why real consistent hash implementations always use vnodes -- the single- position variant is only useful as a pedagogical first step.

tests (6)

○ vnodes=1 behaves the same as the basic ring

○ nodes getter returns K entries per physical node

○ vnodes=100 produces even load across 3 nodes (25%-42% each)

○ adding a node does not cause more than 40% of existing keys to migrate

○ removeNode removes all K positions for that node

○ after removeNode, its keys reassign to remaining nodes (not null)

createRing.js

function createRing(vnodes = 100) {
  const ring = []; // sorted array of { position, nodeId }

function hash(str) {
    let h = 0;
    for (let i = 0; i < str.length; i++) {
      h = (h * 31 + str.charCodeAt(i)) >>> 0;
    }
    return h;
  }

return {
    get nodes() { return [...ring]; },

addNode(nodeId) {
      // TODO: insert vnodes positions for this physical node
    },

removeNode(nodeId) {
      // TODO: remove all positions belonging to this nodeId
    },

getNode(key) {
      if (ring.length === 0) return null;
      const keyPos = hash(key);
      const idx = binarySearch(keyPos);
      return idx === -1 ? ring[0].nodeId : ring[idx].nodeId;
    },
  };
}