Consistent Hashing

You run a cache in front of a database, and one machine isn't enough, so you spread keys over N cache servers. The obvious way to pick a server is servers[hash(key) % N]: fast, stateless, and perfectly even. Every client computes the same answer with no coordination.

Then a server dies, and N goes from 5 to 4. The remainder of hash % 4 has almost nothing to do with hash % 5, so it isn't just the dead server's keys that move. Across 10,000 keys, killing one of five servers sends 79.9% of them to a different server. The dead server only held about 20%; the other ~60% were sitting on healthy machines, and now every client looks for them somewhere else.

For a cache, “somewhere else” means a miss. Most of the cache goes cold in one step, and every miss falls through to the database at the same moment. The database was sized for the trickle of misses a warm cache lets through, not for that: this is a cache stampede, and it turns one lost cache node into a database outage. Adding a server to relieve load does the same thing, which is worse: scaling up under pressure knocks over the database.

The Hashing & Collisions topic shows the in-memory version of this: resizing a hash table rehashes every key. That's fine when the buckets are array slots. It isn't fine when they're machines.

Consistent hashing (Karger et al., 1997) stops the server count from appearing in the formula at all. Take the whole hash space, 0 to 2³²−1, and bend it into a circle so the top wraps back to 0. Then:

1. Place each server on the ring by hashing its name.
2. Place each key on the same ring with the same hash.
3. A key belongs to the first server clockwise from it.

// ring: every virtual node's position, sorted ascending
function ownerOf(key: string): Node {
  const h = hash(key);                       // 0 … 2³² − 1
  let i = lowerBound(ring, h);               // first v-node with pos >= h
  if (i === ring.length) i = 0;              // walked off the end: wrap to the start
  return ring[i].node;
}

Each server owns the arc between its predecessor and itself. When a server dies, its arc merges into the next server clockwise: its keys slide to that one neighbour, and every other key's “first server clockwise” is unchanged. When a server joins, it lands inside one existing arc and takes only the part before it. Nothing else anywhere on the ring moves.

Measured over 10,000 keys with the simulation's own hash, and 100 virtual nodes per server on the ring:

The ring doesn't hit the ideal exactly, because a real server's share is only about 1/N. How close it gets depends on the next section.

With one position per server, arc lengths are luck. Five random points on a circle almost never split it into fifths: one server usually lands after a long empty stretch and owns far more than its share, and when a server dies, its entire load lands on one neighbour, which may already be the busiest node.

The fix is virtual nodes: hash each server onto the ring many times ("N2#vn0", "N2#vn1", …). Each server now owns many small arcs scattered around the circle, and the sum of many random arcs is far more predictable than one. A dead server's keys also scatter across many successors instead of dumping onto one. For 5 servers:

Going from 1 to 100 v-nodes takes the spread from 70.0% to 9.7%, and the busiest node from 2.24× to 1.07× its fair share. Spread shrinks roughly with 1/√v, so the curve flattens: most of the win is in the first 50–100, which is why memcached's ketama clients use 160 points per server and Cassandra historically used 256 tokens per node (16 by default since 4.0, paired with a smarter token allocator).

Virtual nodes also make weighting trivial: a server with twice the memory gets twice the v-nodes. The cost is memory and lookup time for the ring itself (a sorted array of N × v positions, binary searched), which is small.

Rendezvous hashing (Thaler & Ravishankar, 1996) reaches the same minimal disruption without a ring: every client scores every server for a key and picks the winner. A dead server only loses the keys it was winning, and each of those goes to whichever server scored second for it, so they spread evenly with no virtual nodes. The catch is O(N) work per lookup, which is nothing for 10 servers and a lot for 10,000.

Range partitioning gives up on computing the owner and writes it down instead. That costs a metadata service, but it's the only option here that keeps sorted scans on one machine, and it lets the system split one hot range without touching any other.

• Replication fixes the cold handover. Even a perfect ring moves K/N keys on a failure, and for a plain cache those are still misses. Storing each key on the next R nodes clockwise means the node that inherits a dead node's arc already has the data.
• Bounded loads. Virtual nodes even out the hash space, not the traffic: one viral key is still one key. Consistent hashing with bounded loads (Mirrokni et al., Google, 2016) caps every server at, say, 1.25× the average and sends overflow to the next server clockwise. Vimeo added it to HAProxy for exactly this reason.
• Jump consistent hash. Lamping and Veach's 2014 algorithm needs no ring and no memory, just a few lines of arithmetic, and balances perfectly. It only works when servers are numbered 0…N−1 and can only be added or removed at the end, so it suits storage shards better than a cache fleet where any node can die.
• Changing the v-node count moves keys too. Raising it adds positions that each take a slice of a neighbour's arc, so going from 10 to 20 per node moves about half the keys, even though no server came or went. Pick the count once.