How Consistent Hashing Works Under the Hood

A cache node dies at 3am. That part is fine — you provisioned for it, the runbook says "replace the instance." What is not fine is the ninety seconds after it leaves the pool, when your router recomputes hash(key) % node_count and decides almost every key in the system now lives somewhere else.

I measured it on a million synthetic session keys. Drop one node out of a hundred and 99.01% of lookups miss. Add two nodes to a cluster of ten and 83.36% miss. Every miss becomes a database read, all at once, from every app server you own.

Consistent hashing is the fix, and the whole ring fits in about sixty lines. But most explanations of it repeat numbers nobody checked, so this one ships with the harness. Every figure below came out of code you can paste and run.

The modulo problem, measured

Shard user sessions across Redis with hash(session_id) % N. Fast, no lookup table, and it assumes N never changes — which it does, roughly every time anything interesting happens.

Here is the churn function. Hash a million keys, bucket them at from nodes, bucket them again at to nodes, count the disagreements.

function moduloBucket(hash: number, buckets: number): number {
  return hash % buckets;
}
 
/** Fraction of keys whose bucket index changes when the cluster resizes. */
function moduloChurn(hashes: number[], from: number, to: number): number {
  let moved = 0;
  for (const h of hashes) {
    if (moduloBucket(h, from) !== moduloBucket(h, to)) moved++;
  }
  return moved / hashes.length;
}

Run it against 1,000,000 keys hashed with the ringHash defined further down:

The closed form is worth internalising, because the folk version of it is wrong. People say "you lose (N-1)/N of your keys." That is only true when you remove exactly one node. The general answer is:

fraction that survives = min(n, m) * gcd(n, m) / (n * m)

h % n and h % m agree only when h mod lcm(n, m) is smaller than min(n, m). So going 10 → 11 is nearly total loss (90.91%), but 10 → 12 is less destructive (83.33%) because 10 and 12 share a factor of 2. Scaling from 10 nodes to 12 hurts less than scaling from 10 to 11. That is not a property you want your capacity planning to depend on.

The ring

Consistent hashing decouples the arithmetic from the node count. Instead of mod N, everything is hashed into one fixed space — here 0 to 2^32 - 1 — arranged as a circle. Nodes get positions in that space. Keys get positions in that space. A key belongs to the first node you meet walking clockwise from the key's position, wrapping past the top back to zero.

Read the arcs as ownership: node-b owns (1000, 4000], node-c owns (4000, 8000], node-a owns the wrap-around segment (8000, 2^32) ∪ [0, 1000]. The node count appears nowhere in that definition, which is the whole point.

Now kill node-b. Its token vanishes and the arc it owned merges into the next token clockwise.

Keys on node-a do not move. Keys on node-c do not move. I verified that rather than asserting it: over 1,000,000 keys on a 10-node ring, removing one node moved 9.59% of keys and exactly zero keys off a healthy node. The assertion movedButNotOnDeadNode === 0 is in the test block below, and it holds at every cluster size I tried.

Compare the bottom row against the modulo table: 0.999% versus 99.01% for the same event.

Why a naive ring still melts a node

With one token per server, the ring is only as balanced as the hash function's luck with three or ten inputs. Hash functions do not space their outputs politely.

Take the arrangement people reach for when illustrating this — nodes at 1000, 1050, 2000, and 4,000,000,000 on a 2^32 ring. Summing the arcs:

D owns 93.13%, not "basically everything" and not the 99% figure that gets quoted — the wrap-around segment leaves A with a real, if useless, 6.87%. B and C own arcs of 50 and 950 positions respectively out of 4.29 billion, which rounds to nothing.

That is a hand-picked example, so I also ran 200 four-node clusters with one token each and names varied per cluster. The worst put 97.1% of the ring on a single node. Even the luckiest of the 200 gave its busiest node 29.2% against an ideal 25%. One token per node is a coin flip, not a distribution strategy.

Virtual nodes, and how many you actually need

Give each physical server many positions instead of one. Hash 10.0.1.4#0, 10.0.1.4#1, ... 10.0.1.4#255, drop all 256 onto the ring pointing back at the same box. More samples, smoother coverage.

The Dynamo paper introduced this vocabulary — a virtual node "looks like a single node in the system, but each node can be responsible for more than one virtual node," and each of those ring positions is a token (DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, §4.2). Dynamo's own stated reason is the one measured above: "the random position assignment of each node on the ring leads to non-uniform data and load distribution."

How many tokens is enough? I ran 10-node rings over 200,000 keys, 30 independently-named clusters per row, and averaged.

Ideal share is 10.00% per node. The pattern is stdev ≈ 10 / sqrt(V) percentage points — the square-root law — and it tells you the payoff curve flattens hard. Going 1 → 100 removes an order of magnitude of imbalance. Going 256 → 1000 buys 0.29pp instead of 0.58pp, for four times the ring array and four times the gossip payload.

The implementation

Two things matter. The lookup: with thousands of tokens you cannot linear-scan per request, so keep positions in a sorted array and binary-search for the first token at or above the key's hash. The second is less obvious, and it is where the textbook version breaks — see the callout after the code.

import { createHash } from "node:crypto";
 
/**
 * 32 bits of MD5. Not a security choice — MD5 is broken for that. We need a
 * fast, well-spread integer, and this one measures uniform: chi-square 237.8
 * on 255 degrees of freedom over 1,000,000 keys binned into 256 buckets.
 * Swap in MurmurHash3 or xxHash if the hashing shows up in your profile.
 */
export function ringHash(key: string): number {
  return parseInt(createHash("md5").update(key).digest("hex").slice(0, 8), 16);
}
 
interface RingPoint {
  hash: number;
  node: string;
}
 
export class HashRing {
  private points: RingPoint[] = [];
  private readonly vnodesPerNode: number;
 
  constructor(vnodesPerNode: number = 256) {
    this.vnodesPerNode = vnodesPerNode;
  }
 
  addNode(node: string): void {
    for (let i = 0; i < this.vnodesPerNode; i++) {
      this.points.push({ hash: ringHash(`${node}#${i}`), node });
    }
    // Ties broken by name so two colliding tokens keep a stable, total order.
    this.points.sort((a, b) => a.hash - b.hash || (a.node < b.node ? -1 : 1));
  }
 
  removeNode(node: string): void {
    this.points = this.points.filter((p) => p.node !== node);
  }
 
  /** First ring position at or above `hash`, wrapping to index 0. */
  private indexFor(hash: number): number {
    let lo = 0;
    let hi = this.points.length - 1;
    let target = -1;
    while (lo <= hi) {
      const mid = (lo + hi) >>> 1;
      if (this.points[mid].hash >= hash) {
        target = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    return target === -1 ? 0 : target;
  }
 
  getNode(key: string): string | null {
    if (this.points.length === 0) return null;
    return this.points[this.indexFor(ringHash(key))].node;
  }
 
  /** Coordinator plus successors, skipping tokens of nodes already chosen. */
  getReplicas(key: string, count: number): string[] {
    if (this.points.length === 0) return [];
    const start = this.indexFor(ringHash(key));
    const replicas: string[] = [];
    for (let step = 0; step < this.points.length && replicas.length < count; step++) {
      const node = this.points[(start + step) % this.points.length].node;
      if (!replicas.includes(node)) replicas.push(node);
    }
    return replicas;
  }
}

And the harness. A throwing assert, not console.assert — that one logs and keeps going, so a broken ring still prints a clean run.

const assert = (cond: boolean, msg: string): void => {
  if (!cond) throw new Error(msg);
};
 
const KEY_COUNT = 1_000_000;
const keys: string[] = [];
for (let i = 0; i < KEY_COUNT; i++) keys.push(`session:user_${i}`);
const keyHashes = keys.map(ringHash);
 
// 1. Modulo churn
const mod4to3 = moduloChurn(keyHashes, 4, 3);
const mod10to12 = moduloChurn(keyHashes, 10, 12);
console.log(`modulo 4 -> 3 : ${(mod4to3 * 100).toFixed(2)}% of keys move`);
console.log(`modulo 10 -> 12: ${(mod10to12 * 100).toFixed(2)}% of keys move`);
assert(mod4to3 > 0.74 && mod4to3 < 0.76, "modulo 4->3 should move ~75%");
assert(mod10to12 > 0.83 && mod10to12 < 0.84, "modulo 10->12 should move ~83%");
 
// 2. Ring churn — only the dead node's keys are allowed to move
const nodes = Array.from({ length: 10 }, (_, i) => `10.0.1.${i}`);
const ring = new HashRing(256);
nodes.forEach((n) => ring.addNode(n));
 
const before = keys.map((k) => ring.getNode(k));
ring.removeNode(nodes[3]);
const after = keys.map((k) => ring.getNode(k));
 
let movedTotal = 0;
let movedButNotOnDeadNode = 0;
for (let i = 0; i < KEY_COUNT; i++) {
  if (before[i] !== after[i]) {
    movedTotal++;
    if (before[i] !== nodes[3]) movedButNotOnDeadNode++;
  }
}
console.log(`ring 10 -> 9  : ${((movedTotal / KEY_COUNT) * 100).toFixed(2)}% of keys move`);
console.log(`collateral damage: ${movedButNotOnDeadNode} keys`);
assert(movedTotal / KEY_COUNT < 0.13, "ring should move roughly 1/N of the keys");
assert(movedButNotOnDeadNode === 0, "no key off a healthy node may move");
 
// 3. Replicas must land on distinct physical nodes
const rf3 = ring.getReplicas("session:user_42", 3);
assert(rf3.length === 3, "expected 3 replicas");
assert(new Set(rf3).size === 3, "replicas must be distinct physical nodes");
assert(rf3[0] === ring.getNode("session:user_42"), "first replica is the coordinator");
for (const k of keys.slice(0, 20000)) {
  assert(new Set(ring.getReplicas(k, 3)).size === 3, `duplicate replica for ${k}`);
}
 
console.log("all assertions passed");

Actual output on Node 22, node --experimental-strip-types:

modulo 4 -> 3 : 74.93% of keys move
modulo 10 -> 12: 83.36% of keys move
ring 10 -> 9  : 9.59% of keys move
collateral damage: 0 keys
all assertions passed

The getReplicas skip is not decoration. Dynamo spells out why: "with the use of virtual nodes, it is possible that the first N successor positions for a particular key may be owned by less than N distinct physical nodes... the preference list for a key is constructed by skipping positions in the ring to ensure that the list contains only distinct physical nodes." Skip it and you write three replicas to one disk and call it RF=3.

What Cassandra actually does in 2026

Cassandra is the usual reference implementation, and the usual description of it is a decade out of date.

The architecture is Dynamo's: peer-to-peer, gossip for membership, keys hashed onto a token ring, walk clockwise to collect distinct replicas. The Cassandra docs describe the walk as "similar to the Chord algorithm," and confirm the distinct-node rule — "replicas are always chosen such that they are distinct physical nodes which is achieved by skipping virtual nodes if needed." Two details most write-ups get wrong:

It is not 256 tokens per node any more. conf/cassandra.yaml on the 5.0 branch ships num_tokens: 16, alongside allocate_tokens_for_local_replication_factor: 3. The docs are blunt about where 256 came from: "in Cassandra 2.x, the only token allocation algorithm available was picking random tokens, which meant that to keep balance the default number of tokens per node had to be quite high, at 256... That is why in 3.x+ a new deterministic token allocator was added which intelligently picks tokens such that the ring is optimally balanced while requiring a much lower number of tokens per physical node." The production guide recommends 1, 4, 8, or 16 depending on how elastic the cluster is, and warns that more tokens means more ring neighbours and therefore lower availability under multi-node failure. My vnode table above describes a randomly-placed ring; a deterministic allocator reaches the same balance at a fraction of the token count, which is why the default dropped.

Streaming a new node in does not free the old node's disk. A bootstrapping node takes ownership of ranges and the previous owners stream the matching rows to it — then keep their copies. From the operations docs: "As a safety measure, Cassandra does not automatically remove data from nodes that 'lose' part of their token range due to a range movement operation (bootstrap, move, replace). Run nodetool cleanup on the nodes that lost ranges to the joining node... If you do not do this the old data will still be counted against the load on that node." If you have ever added capacity and watched disk usage refuse to drop, that is why.

Three things consistent hashing does not fix

It balances keys, not load. At a perfect 10.00% of keys per node, one key can still be 40% of your traffic. Discord hit the storage version of this: messages in Cassandra were partitioned by channel, and a single busy channel's partition blew past 100MB, so the primary key became ((channel_id, bucket), message_id) with roughly ten days of messages per bucket. Ring placement was never the problem — the key was too coarse. Hot keys need a different tool: replicate the key, shard it, or put a small local cache in front.

It is the wrong tool for stateless HTTP. If your backend pods hold no per-request state, round-robin or least-connections beats a hash ring on every axis. Consistent hashing buys data locality — caches, sharded stores, sticky sessions. On stateless services it adds a hash and a binary search per request and balances worse than a counter.

Failure still cascades — vnodes just make it slower. If a node dies from overload, its traffic lands on its successors, which are now carrying their own load plus a share of the dead node's. Whether that kills them depends entirely on how many successors there are. Measured on a 10-node ring, 500,000 keys, one node removed:

With one token per node, the successor eats the entire failed node's traffic and is next in line to fall over. With 256, the load fragments across nine survivors and the worst-hit takes 15.2%. Same failure, completely different blast radius.

Check yourself

The answer is 83%, measured at 83.36% over a million keys. The tempting answer is 91%, from the folk rule "you lose (N-1)/N" — but that rule only describes removing a single node. h % 10 and h % 12 agree whenever h mod lcm(10, 12) is below min(10, 12), so 10/60 of keys survive, and 83.33% move. The shared factor of 2 between 10 and 12 is doing the work.

A hash map answers "is this exact value present," and a key's hash is essentially never equal to a token. This is a successor query over an ordered set: sorted array with binary search, or a balanced tree, or a skip list. The array wins in practice because it is contiguous and the ring is read far more often than it changes.

Where to look next

If the ring's memory footprint or gossip traffic is your bottleneck, two alternatives are worth reading:

• Rendezvous hashing (Thaler and Ravishankar, 1996). Score every node with hash(key, node_id) and take the highest. No ring array, minimal movement on membership change, but O(N) per lookup unless you build a tree over it.
• Jump consistent hash (Lamping and Veach, arXiv:1406.2294, 2014). Five lines, zero storage, and per the abstract it "does a better job of evenly dividing the key space among the buckets" than the Karger ring. The catch is in the same abstract: "the buckets must be numbered sequentially, which makes it more suitable for data storage applications than for distributed web caching." You cannot remove bucket 7 from the middle.

The original is still the best entry point: Karger, Lehman, Leighton, Panigrahy, Levine and Lewin, Consistent Hashing and Random Trees, STOC '97 — reference [10] in the Dynamo paper, ten years before Dynamo made it famous.

One habit to take away: whatever ring you build, write the assertion that no key off a healthy node may move, and run it against your real key distribution before you ship. Mine caught a collision bug that only appears above 25,000 tokens, and it would otherwise have shipped as "works on my three-node laptop cluster."