Consistent Hashing

Consistent hashing is a technique for assigning keys to nodes (servers, cache instances, shards) in a way that survives adding or removing nodes without reshuffling almost everything. It shows up constantly in system design interviews because it solves a very concrete, very common problem: how do you distribute data or requests across a changing set of machines, without a full rebalance every time the set changes?

The problem with the naive approach

The obvious way to assign a key to one of N servers is hash(key) % N. It's simple and spreads keys evenly — right up until N changes. If you add or remove even one server, N changes, and hash(key) % N returns a completely different answer for almost every key. In a cache, that means almost every cache entry suddenly maps to the "wrong" server and is effectively lost (a cache miss storm). In a sharded database, it means moving almost all your data around just because you added one more shard — clearly not something you want happening every time you scale.

The consistent hashing idea

Instead of hashing keys onto a number line of size N, consistent hashing hashes both keys and nodes onto the same fixed, large circular space (usually visualized as a ring, e.g. hash values from 0 to 2³²−1 wrapping back to 0). To find which node owns a key:

Hash the key to get a position on the ring.
Walk clockwise from that position until you hit the first node.
That node owns the key.

Because nodes are placed on the same ring as keys, adding a new node only affects the keys that fall between the new node and the next node counter-clockwise from it — everything else on the ring is untouched. Removing a node only affects the keys that were assigned to it (they move to the next node clockwise). Roughly speaking, adding or removing one of N nodes only remaps about 1/N of the keys, instead of nearly all of them.

Virtual nodes: fixing uneven distribution

A ring with just one point per physical node can be lumpy — by chance, one node might end up "owning" a much longer arc of the ring than another, especially with a small number of nodes. The standard fix is virtual nodes: each physical node is hashed onto the ring multiple times (e.g., 100–200 times, at different hash positions, often computed as hash(nodeName + "-" + replicaIndex)). More points on the ring per physical node means the law of large numbers smooths out the arc lengths, so load ends up much closer to evenly distributed — and a real machine can also be given proportionally more virtual nodes if it has more capacity than its peers.

Try it yourself

The demo below builds a small hash ring with 3 nodes (each with several virtual replicas), assigns 20 sample keys, then adds a 4th node and recomputes. Run it and compare how many keys moved under consistent hashing versus how many would have moved under plain hash(key) % N (essentially all of them). Try changing VIRTUAL_NODES_PER_NODE to 1 and re-running to see the distribution get lumpier.

// A minimal consistent hashing ring, for demonstration.

function hashString(str) {
// FNV-1a: fast, decent distribution, no dependencies.
let hash = 0x811c9dc5;
for (let i = 0; i < str.length; i++) {
  hash ^= str.charCodeAt(i);
  hash = Math.imul(hash, 0x01000193);
}
return hash >>> 0; // unsigned 32-bit
}

const VIRTUAL_NODES_PER_NODE = 3;

function buildRing(nodeNames) {
const ring = [];
for (const node of nodeNames) {
  for (let replica = 0; replica < VIRTUAL_NODES_PER_NODE; replica++) {
    ring.push({ hash: hashString(node + '-' + replica), node });
  }
}
ring.sort((a, b) => a.hash - b.hash);
return ring;
}

function assign(ring, key) {
const keyHash = hashString(key);
for (const point of ring) {
  if (point.hash >= keyHash) return point.node;
}
return ring[0].node; // wrap around the ring
}

function countByNode(assignments) {
const counts = {};
for (const node of Object.values(assignments)) {
  counts[node] = (counts[node] || 0) + 1;
}
return counts;
}

const keys = Array.from({ length: 20 }, (_, i) => 'user:' + i);

// --- Before: 3 nodes ---
const ringBefore = buildRing(['nodeA', 'nodeB', 'nodeC']);
const assignmentsBefore = {};
for (const key of keys) assignmentsBefore[key] = assign(ringBefore, key);

// --- After: add nodeD ---
const ringAfter = buildRing(['nodeA', 'nodeB', 'nodeC', 'nodeD']);
const assignmentsAfter = {};
for (const key of keys) assignmentsAfter[key] = assign(ringAfter, key);

const moved = keys.filter((k) => assignmentsBefore[k] !== assignmentsAfter[k]);

// --- For comparison: naive hash(key) % N ---
function naiveAssign(key, n) {
return 'node' + String.fromCharCode(65 + (hashString(key) % n));
}
const naiveBefore = {};
const naiveAfter = {};
for (const key of keys) {
naiveBefore[key] = naiveAssign(key, 3);
naiveAfter[key] = naiveAssign(key, 4);
}
const naiveMoved = keys.filter((k) => naiveBefore[k] !== naiveAfter[k]);

const lines = [];
lines.push('Distribution with 3 nodes: ' + JSON.stringify(countByNode(assignmentsBefore)));
lines.push('Distribution with 4 nodes: ' + JSON.stringify(countByNode(assignmentsAfter)));
lines.push('');
lines.push('Consistent hashing: ' + moved.length + ' / ' + keys.length + ' keys moved after adding nodeD');
lines.push('Naive hash % N:     ' + naiveMoved.length + ' / ' + keys.length + ' keys moved after adding nodeD');
lines.push('');
lines.push('Moved keys (consistent hashing): ' + JSON.stringify(moved));

document.getElementById('output').textContent = lines.join('\n');

Open Sandbox

Where it's actually used

Consistent hashing was popularized by Akamai's content distribution network and later by Amazon's Dynamo paper, and today shows up in:

Distributed caches (e.g., Memcached client libraries) — so adding a cache node doesn't invalidate almost the entire cache.
Database sharding — so adding a shard doesn't require moving nearly all existing data (see Database Sharding).
Load balancers that want to route the same client to the same backend for session affinity, even as backends scale up or down.
Distributed hash tables (DHTs) in peer-to-peer systems.