What is consistent hashing with virtual nodes and when do you need it?

Q: What is consistent hashing with virtual nodes and when do you need it?

**Target Audience:** Readers who know the basic hash ring; if you do not, read [What is consistent hashing?](/interview-question/what-is-consistent-hashing) first, as this page builds on it. **Difficulty:** Medium **Verified with:** Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output). Cassandra facts are cited from The Last Pickle, Instaclustr and the Apache Cassandra 4.0 production docs. > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the words an interviewer expects. Numbers come from running the example; the **Verified** section quotes its full output. ## 1. Why This Even Matters — A Story First Ten friends share a large round pizza, and each one makes a single cut at a random spot; everyone gets the slice that ends at their cut. One friend ends up with a third of the pizza and another with a sliver. Now let each friend make a hundred random cuts and collect the hundred

The problem

Question presented to candidate: "You have a consistent hashing ring for a cache or a key-value store. Explain virtual nodes: what problem they solve, how many you would use, and in which situations you would or would not bother with them."

What a strong answer should cover:

The problem: with one token per server, the ring arcs are random and very unequal, so load is uneven and a failed server dumps all its keys on one neighbour
Virtual nodes: each physical server gets many tokens; its share is the sum of many small arcs, so imbalance shrinks roughly with the square root of the token count
Second benefit: a failed or joining server exchanges data with many peers in parallel, not one
Third benefit: weighting heterogeneous servers by giving bigger machines more tokens
Costs: a bigger routing table, more ranges to stream and repair, and in replicated stores more node pairs sharing data; a real data point such as Cassandra lowering num_tokens from 256 to 16 in 4.0 with a smarter token allocator
When you do not need them: fixed logical partitions, rendezvous hashing, or a static set of identical servers

Clarifying questions expected:

How many servers, and do they differ in size?
Is this a cache (movement costs misses) or a replicated store (movement costs streaming and repair)?

Code / implementation expected: Optional — a ring with N tokens per server and the measured imbalance; the example runs 1 to 1000 vnodes.

consistent-hashing
sharding
load-balancing

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Readers who know the basic hash ring; if you do not, read What is consistent hashing? first, as this page builds on it. Difficulty: Medium Verified with: Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output). Cassandra facts are cited from The Last Pickle, Instaclustr and the Apache Cassandra 4.0 production docs.

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the words an interviewer expects. Numbers come from running the example; the Verified section quotes its full output.

1. Why This Even Matters — A Story First

Ten friends share a large round pizza, and each one makes a single cut at a random spot; everyone gets the slice that ends at their cut. One friend ends up with a third of the piz

The solution is hidden so you can try first

10 min read · 12 sections

Read the code

Virtual nodes: load balance at 1, 10, 100 and 1000 vnodes, failure spread, weighted capacity

Open in playground

// Virtual nodes: how many ring positions per server you need before load evens out,
// where a dead server's keys go, and how weights give a big server a bigger share.
function h32(s) {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16;
  return h >>> 0;
}
const x2 = (num, den) => { const v = Math.floor((num * 100) / den); return Math.floor(v / 100) + "." + String(v % 100).padStart(2, "0") + "x"; };

function buildRing(tokensPerNode) { // tokensPerNode: array of [name, count]
  const r = [];
  for (const [name, count] of tokensPerNode) for (let t = 0; t < count; t++) r.push([h32(name + "#" + t), name]);
  return r.sort((a, b) => a[0] - b[0] || (a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0));
}
function owner(ring, hk) {
  let lo = 0, hi = ring.length;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (ring[mid][0] < hk) lo = mid + 1; else hi = mid; }
  return ring[lo === ring.length ? 0 : lo][1];
}
const KEYS = 100000;
const hashes = []; for (let i = 0; i < KEYS; i++) hashes.push(h32("user:" + i));
const nodes = []; for (let i = 0; i < 10; i++) nodes.push("node-" + i);
const counts = (ring) => { const c = {}; for (const n of nodes) c[n] = 0; for (const hk of hashes) c[owner(ring, hk)]++; return c; };

console.log("10 nodes, 100000 keys. Fair share = 10000 keys per node.");
console.log("vnodes  ring entries  busiest node     idlest node");
for (const v of [1, 10, 100, 1000]) {
  const c = counts(buildRing(nodes.map((n) => [n, v])));
  const vals = nodes.map((n) => c[n]);
  const max = Math.max(...vals), min = Math.min(...vals);
  console.log(`${String(v).padEnd(8)}${String(v * 10).padEnd(14)}${String(max).padStart(6)} (${x2(max * 10, KEYS)})  ${String(min).padStart(6)} (${x2(min * 10, KEYS)})`);
}

console.log("\nnode-3 fails. Where do its keys go?");
for (const v of [1, 100]) {
  const before = buildRing(nodes.map((n) => [n, v]));
  const after = buildRing(nodes.filter((n) => n !== "node-3").map((n) => [n, v]));
  const got = {}; let moved = 0;
  for (const hk of hashes) {
    const a = owner(before, hk);
    if (a === "node-3") { moved++; const b = owner(after, hk); got[b] = (got[b] || 0) + 1; }
    else if (owner(after, hk) !== a) throw new Error("a key not on node-3 moved");
  }
  const top = Math.max(...Object.values(got));
  console.log(`  vnodes=${String(v).padEnd(4)} ${moved} keys moved to ${Object.keys(got).length} node(s), largest receiver took ${top}`);
}

console.log("\nnode-9 is a server twice as big, so it gets 200 vnodes; the rest get 100:");
const c = counts(buildRing(nodes.map((n) => [n, n === "node-9" ? 200 : 100])));
const others = nodes.filter((n) => n !== "node-9").map((n) => c[n]);
const avg = Math.floor(others.reduce((a, b) => a + b, 0) / others.length);
console.log(`  node-9 keys ${c["node-9"]}, average other node ${avg}, ratio ${x2(c["node-9"], avg)}`);

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.