Consistent Hashing: The Ring That Barely Reshuffles

The problem with server = hash(key) % n

The obvious way to spread keys across n cache servers is server = hash(key) % n. It's a single line of code and it distributes load perfectly evenly — as long as n never changes. The moment you add a sixth server to a five-node cluster, the modulus flips from %5 to %6 for essentially every key, and the server each key maps to jumps almost at random. In expectation, roughly (n-1)/n of all keys — about 83% for n=6 — land on a different server than before, even though only one server actually changed. Every one of those keys is now a cache miss, and they all arrive at the origin database at once, right when the cluster is already under the extra load of a scaling event.

Putting servers and keys on the same ring

Consistent hashing, published by Karger et al. at MIT in 1997, fixes this by hashing servers and keys into the same space and arranging that space as a circle — the hash ring — running from 0 to 2³²−1 and wrapping back to 0. Both the server names and the keys are passed through one hash function (fast, non-cryptographic hashes like MurmurHash3 or xxHash are the usual choice, since uniformity matters far more than security here) to get a position on that circle. A key is owned by whichever server sits at the first position clockwise from the key's own position — no modulus, no fixed table size, just "walk clockwise until you hit a server."

Only the neighbouring arc moves

This single change to how ownership is computed has a dramatic consequence. When a new server is inserted at position P between existing servers A and B, only the keys that used to fall in the arc between A and P need to move — they now belong to the new node instead of continuing on to B. Every key anywhere else on the ring still finds the exact same server clockwise from it, because nothing about its neighbourhood changed. Removing a server works the same way in reverse: its keys simply fall through to its clockwise successor.

// lookup: first ring position >= hash(key), binary search over sorted positions
function getServer(key, sortedPositions, ring) {
  const pos = hash32(key);
  let lo = 0, hi = sortedPositions.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (sortedPositions[mid] < pos) lo = mid + 1; else hi = mid;
  }
  const idx = lo >= sortedPositions.length ? 0 : lo;   // wrap to first node
  return ring.get(sortedPositions[idx]);
}
// expected keys remapped when 1 node joins or leaves an n-node ring ≈ 1/n

For a five-node ring, adding a sixth server remaps only about 1/6 of keys instead of 5/6 — a reduction of roughly (n-1)× compared with naive modulo hashing, and it's the theoretical minimum: you cannot add capacity without moving some keys onto the new server, but consistent hashing guarantees you never move more than necessary.

Virtual nodes: smoothing out a lumpy ring

With only a handful of physical servers, their random positions on the ring can clump together by chance, leaving one server responsible for a huge arc and another for almost nothing. The fix is virtual nodes: each physical server is hashed to many positions on the ring (Apache Cassandra defaults to 256 per node, historically often 100-200 in other systems), each a separate small arc. With enough virtual nodes per server, the law of large numbers takes over and every physical server ends up responsible for close to an equal total share of the ring — and a beefier server can simply be assigned more virtual nodes to absorb a proportionally larger fraction of the load, a clean mechanism for heterogeneous hardware.

Where the ring shows up

Consistent hashing is the routing layer underneath most elastic distributed storage. Memcached clients use it (via the libketama library) so that adding a cache node doesn't invalidate the whole cluster's cache. Amazon DynamoDB and Apache Cassandra use ring partitioning with virtual nodes (Cassandra's configurable num_tokens) combined with an N-way preference list of clockwise successors for replication. Distributed hash tables (DHTs) like Chord in peer-to-peer networks, and CDN request routing at companies like Akamai, are built on exactly the same ring idea — map resource identifiers and node identifiers into one space, and let proximity decide ownership.

Frequently asked questions

Try it live

Every ring position, arc and virtual node above runs live in Consistent Hashing — The Hash Ring. Add and remove nodes and watch exactly which keys migrate — and how virtual nodes flatten out the load.