Virtual Nodes — Consistent Hashing

Overview

What this concept solves

The vanilla ring has one nagging flaw: server positions are random, so the arcs between them are uneven. With a handful of servers, one might own a third of the ring and another a sliver — lopsided load. And when a server dies, all of its keys fall onto the single next server, which can tip it over. Virtual nodes fix both problems with one idea.

Instead of placing each server at one point, place it at many. A single physical server beta is hashed to V different positions — call them b1, b2, …, bV — each landing somewhere different on the ring. Those points are called virtual nodes (vnodes). The lookup rule is unchanged: a key still walks clockwise to the nearest point. But now that point belongs to one of a server's many vnodes, and the server's total share is the sum of all its little arcs scattered around the circle.

Spreading each server across many points averages out the randomness. Instead of one big lucky-or-unlucky arc, a server owns dozens of small ones all over the ring, so its share converges toward its fair fraction. And when it leaves, its many arcs each hand off to whatever different server is next — so its keys scatter across all survivors rather than crushing one.

Mechanics

How it works

Each server becomes V points

Choose V, the number of virtual nodes per server (often 100–256 in real systems).
For each server, hash V distinct labels — hash("beta#0"), hash("beta#1"), … — and drop all V points onto the ring.
Keep a map from every vnode point back to its physical server.
Look a key up exactly as before: walk clockwise to the nearest point, then follow the map to find which physical server owns that vnode.

More points means smaller, more numerous arcs, which means the law of large numbers works in your favour. The statistical wobble in each server's share shrinks roughly like 1/√V — so going from V=1 to V=100 cuts the imbalance by about 10×. The prototype's imbalance readout (the spread between the busiest and idlest server) is exactly this number; slide V up and watch it fall.

Capacity for free: weight by vnode count

Because a server's load is proportional to how many points it has, you get heterogeneous capacity almost for nothing: give a machine that's twice as powerful twice as many virtual nodes and it takes on twice the keys. No special weighting logic — just hand the bigger boxes more points. This is exactly how Dynamo tunes for mixed hardware.

This is what real systems ship

Amazon Dynamo introduced vnodes to solve the vanilla ring's uneven load; Cassandra exposes the count directly as num_tokens (commonly 16–256), and Riak and ScyllaDB use the same idea. When someone says 'consistent hashing' in production, they almost always mean the ring with virtual nodes.

More vnodes isn't free

Each vnode is another entry in the sorted ring, so memory and lookup cost grow with N·V, and in a real cluster more tokens mean more ranges to gossip about and stream during repair. There's a sweet spot — enough points to balance load, not so many that bookkeeping dominates. That's why Cassandra moved its default down from 256 to 16.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Virtual Nodes

About this simulation

Same ring — but now each server owns V points instead of one. With V=3, server alpha appears as a1, a2, a3, scattered around the circle; same colour means same server. Drag the V slider and watch the imbalance number drop as each server's positions interleave. Remove a server and its keys spread across the survivors instead of dumping on one.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Slide V and watch imbalance fall

Drag the Vnodes per server (V) slider from 1 up to 15. Watch the imbalance σ/μ readout: at V=1 it's the lumpy vanilla ring, and as V grows the per-server key counts tighten toward the ideal per server line. That shrinking spread is the entire point of virtual nodes.

try 02

Remove a server, watch keys scatter

With a few servers placed, click a server (a vnode dot or its stat card) to remove it. Its keys don't all pile onto one neighbour the way they did on the vanilla ring — they spread across the remaining servers, because its many vnodes each handed off to a different survivor.

try 03

See the labels interleave

At a low V, hover the dots: each server's points (a1, a2, a3 …) sit at scattered positions, interleaved with every other server's. Add a server and +6 keys, then nudge V — notice how mixing the colours around the ring is what produces the even split.

In practice

When to use it — and what you give up

When to reach for it

Any production ring — if you're using a hash ring at all, you almost certainly want virtual nodes on top. The vanilla ring's imbalance is real.
Mixed-capacity fleets — give bigger machines more vnodes and they take proportionally more load, with no separate weighting code.
Smoother failure handling — when a node dies, its load fans out across all survivors instead of doubling one neighbour's burden.
Faster rebalancing — a joining node pulls a little data from many existing nodes in parallel, rather than a lot from one.

Pros

Evens out load — imbalance shrinks roughly like 1/√V as you add points.
A failing server's keys scatter across all survivors instead of dumping on one neighbour.
Heterogeneous capacity comes for free: more vnodes = proportionally more load.
Rebalancing is smoother — joins and leaves touch many nodes a little, not one node a lot.

Cons

Ring size grows to N·V, so memory and lookup cost rise with the vnode count.
More tokens mean more ranges to track, gossip, and stream during repair in real clusters.
Picking V is a tuning decision — too few and load stays lumpy, too many and overhead dominates.
Still hash-based placement: it balances on average, not perfectly, for any single layout.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

vnode-ring.ts

// Consistent-hashing ring with virtual nodes.
// Each physical server is placed at V points; a map leads each point home.
class VNodeRing {
  private ring: { hash: number; server: string }[] = [];

  constructor(private vnodes = 100) {}

  private hash(s: string): number {
    let h = 2166136261 >>> 0;
    for (let i = 0; i < s.length; i++) {
      h ^= s.charCodeAt(i);
      h = Math.imul(h, 16777619) >>> 0;
    }
    return h >>> 0;
  }

  addServer(name: string, weight = 1): void {
    // weight just scales how many points this server gets
    const points = this.vnodes * weight;
    for (let i = 0; i < points; i++) {
      this.ring.push({ hash: this.hash(`${name}#${i}`), server: name });
    }
    this.ring.sort((a, b) => a.hash - b.hash);
  }

  removeServer(name: string): void {
    this.ring = this.ring.filter((e) => e.server !== name);
  }

  getServer(key: string): string | null {
    if (this.ring.length === 0) return null;
    const h = this.hash(key);
    // first vnode clockwise; wrap to 0 if past the end
    const hit = this.ring.find((e) => e.hash >= h) ?? this.ring[0];
    return hit.server; // the map from point -> physical server
  }
}

const ring = new VNodeRing(150);
ring.addServer("alpha");
ring.addServer("beta", 2); // twice the capacity -> twice the points
ring.getServer("user:42");

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What does a virtual node actually add to the ring?

question 02 / 03

Why does increasing V make the load more even?

question 03 / 03

How do virtual nodes give you heterogeneous (mixed-capacity) servers almost for free?

0/3 answered