Consistent Hashing

Mapping keys to nodes so that adding or removing one node moves roughly 1/N of the keys instead of nearly all of them.

Syntaxnode = ring.firstPointClockwiseFrom(hash(key)) // wrapping past the top of the space

Consistent hashing maps keys to nodes so that changing the node count moves as few keys as possible. With hash(key) % N the node count is part of the answer, so going from 8 nodes to 9 changes the destination of about 8 keys in 9. For a cache that is a near-total miss storm arriving at your database in one second; for a sharded store it is a full reshuffle of the data. Karger and colleagues published the alternative in 1997 for exactly this problem.

The ring

Hash nodes and keys into the same space — typically 32 or 128 bits, treated as a circle. A key belongs to the first node found walking clockwise from the key's own position. Removing a node hands only its arc to its clockwise neighbour; adding one takes an arc from a single node. On average 1/N of keys move rather than (N-1)/N, and no other key is disturbed.

Why virtual nodes

One point per node gives arcs of wildly unequal length, so load is uneven and gets worse the fewer nodes you have. The fix is to place each physical node at many points: libketama puts each server on the continuum roughly 160 times, and Envoy's ring_hash builds a ring of minimum_ring_size entries, 1024 by default. Virtual nodes also make weighting trivial — twice the capacity, twice the points — and spread a departing node's load over all survivors instead of dumping it on one neighbour.

What trips people up

Replica selection has to skip points belonging to a node already chosen. Dynamo builds a key's preference list by walking clockwise and skipping positions that map to a host already in the list, or three replicas can land on one machine.

Example

// A consistent hash ring with virtual nodes, next to the modulo mapping it
// replaces. Every client that routes keys must build this the same way.
import { createHash } from 'node:crypto';

const hash32 = (s) => createHash('md5').update(s).digest().readUInt32BE(0);

class HashRing {
  // points: virtual nodes per unit of weight. More points, flatter load.
  // libketama uses about 160 per server; 100-200 is the usual range.
  constructor(nodes = [], points = 160) {
    this.pointsPerNode = points;
    this.ring = []; // sorted ascending by h
    for (const n of nodes) this.add(n);
  }

  add(node, weight = 1) {
    for (let i = 0; i < this.pointsPerNode * weight; i++) {
      // This string is part of the contract. Change it and every key moves,
      // so hash the node's stable identity and never its array index.
      this.ring.push({ h: hash32(`${node}#${i}`), node });
    }
    this.ring.sort((a, b) => a.h - b.h);
  }

  remove(node) {
    this.ring = this.ring.filter((p) => p.node !== node);
  }

  // The first point clockwise from the key, wrapping past the top.
  indexFor(key) {
    const h = hash32(String(key));
    let lo = 0, hi = this.ring.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.ring[mid].h < h) lo = mid + 1; else hi = mid;
    }
    return lo % this.ring.length; // lo === length means we wrapped to the start
  }

  get(key) {
    return this.ring[this.indexFor(key)].node;
  }

  // n DISTINCT physical nodes: skip further points of a node already chosen.
  // Dynamo calls this the key's preference list. Without the skip, all three
  // replicas of a key can end up on one machine.
  getN(key, n) {
    const start = this.indexFor(key);
    const out = [];
    for (let i = 0; i < this.ring.length && out.length < n; i++) {
      const { node } = this.ring[(start + i) % this.ring.length];
      if (!out.includes(node)) out.push(node);
    }
    return out;
  }
}

// What it replaces. N is in the answer, so changing N changes the answer for
// roughly (N-1)/N of every key in the system.
const moduloShard = (key, nodes) => nodes[hash32(String(key)) % nodes.length];

When to use it

Adding a node to a Memcached or Redis cluster at peak without invalidating nearly every cached key.
Routing WebSocket connections so the same chat room always lands on the same application server.
Giving a mixed fleet of large and small cache nodes a share of traffic proportional to their memory.
Picking the three nodes that hold replicas of a key in a leaderless key-value store.

More examples

What modulo actually costs, measured

The number to quote when someone proposes adding a Memcached node at peak. It also shows the limit of the technique: 1/N of keys still move, so a cache still takes a measurable miss spike, and a sharded datastore still has to copy 1/N of its data somewhere. Consistent hashing makes that survivable, not free.

// How many keys change node when the cluster goes from 8 nodes to 9.
const keys = Array.from({ length: 100_000 }, (_, i) => `user:${i}`);
const eight = Array.from({ length: 8 }, (_, i) => `node-${i}`);
const nine = [...eight, 'node-8'];

let modMoved = 0;
for (const k of keys) {
  if (moduloShard(k, eight) !== moduloShard(k, nine)) modMoved++;
}

const ringA = new HashRing(eight);
const ringB = new HashRing(nine);
let ringMoved = 0;
for (const k of keys) {
  if (ringA.get(k) !== ringB.get(k)) ringMoved++;
}

console.log((modMoved / keys.length).toFixed(3));  // ~0.89, which is 8/9
console.log((ringMoved / keys.length).toFixed(3)); // ~0.11, which is 1/9

// For a cache, 0.89 is nearly every key missing at once and the whole miss
// load arriving at the database in the same second. 0.11 is a bad minute.

The ring size in a real load balancer

Useful because it names the thing the ring size really controls. Ring entries are virtual nodes, and the default is sized for a handful of hosts; a large fleet on the default ring gets lumpy load that looks like a capacity problem rather than a configuration one. Reach for a larger ring before you reach for more replicas.

# Envoy hashing a key onto a ring of upstream hosts, so the same session or
# cache key keeps reaching the same host.
clusters:
  - name: sessions
    lb_policy: RING_HASH
    # Shorthand: omit ring_hash_lb_config entirely and you get exactly the
    # block below -- minimum_ring_size 1024, maximum_ring_size 8388608.
    # Spell it out when the distribution needs to be flatter: the ring size
    # IS the total virtual-node count, divided among hosts by weight, so a
    # 1024-entry ring across 200 hosts gives each host about 5 arcs and
    # visibly uneven load.
    ring_hash_lb_config:
      minimum_ring_size: 1024      # the default
      maximum_ring_size: 8388608   # the default, and the hard ceiling

# Which value gets hashed is set on the route, not here -- a header, a cookie
# or the source IP. Hash something stable: hashing a header the client does
# not always send silently falls back to random host selection.