What is consistent hashing? | Interview Question

Q: What is consistent hashing?

**Target Audience:** Beginners to system design who know what a hash function and a cache are; no distributed-systems background assumed. **Difficulty:** Medium **Verified with:** Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output). History is cited from Karger et al., STOC 1997; system usage from the Dynamo paper (SOSP 2007) and the Apache Cassandra documentation. > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the words an interviewer expects. Numbers come from running the example; the **Verified** section quotes its full output. ## 1. Why This Even Matters — A Story First A school puts students into lockers by a simple rule: take the student number, divide by the number of locker rooms, and the remainder is your room. With 4 rooms, student 13 goes to room 1. It works perfectly until the school builds a fifth room. Now student 13 belongs in room 3, and so does nearly eve

The problem

Question presented to candidate: "We spread cache keys over servers with hash(key) % N. Every time we add or lose a server, the hit rate collapses. What is consistent hashing, how does it fix this, and what problem does it still have?"

What a strong answer should cover:

Why hash % N breaks: changing N changes the remainder for most keys, about N/(N+1) of them when one server is added
The hash ring: servers and keys are hashed onto the same circular space; a key belongs to the first server clockwise
Adding or removing a server moves only the keys on one arc, on average 1/N of them, and they move only to or from that server
Lookup is a binary search over sorted server positions, O(log n)
The remaining problem: with one position per server, arcs are very uneven; the standard fix is virtual nodes
Where it is used: distributed caches, Dynamo-style stores (Dynamo, Cassandra), and load balancers that need sticky placement

Code / implementation expected: Optional — a ring with a sorted array and binary search is a common whiteboard ask; the example measures movement against hash % N.

consistent-hashing

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners to system design who know what a hash function and a cache are; no distributed-systems background assumed. Difficulty: Medium Verified with: Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output). History is cited from Karger et al., STOC 1997; system usage from the Dynamo paper (SOSP 2007) and the Apache Cassandra documentation.

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the words an interviewer expects. Numbers come from running the example; the Verified section quotes its full output.

1. Why This Even Matters — A Story First

A school puts students into lockers by a simple rule: take the student number, divide by the number of locker rooms, and the remainder is your room. With 4 rooms, student 13 goes to room 1. It works perf

The solution is hidden so you can try first

11 min read · 12 sections

Read the code

A consistent hashing ring vs hash % N: keys moved when a node joins or leaves

Open in playground

// Consistent hashing ring vs hash(key) % N: how many keys move when a node joins or leaves.
// Hash: FNV-1a 32-bit plus the murmur3 finalizer, so every language gets the same numbers.
function h32(s) {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16;
  return h >>> 0;
}
const RING = 4294967296; // 2^32 positions
const pct = (num, den) => { const v = Math.floor((num * 10000) / den); return Math.floor(v / 100) + "." + String(v % 100).padStart(2, "0") + "%"; };

function buildRing(nodes) {
  return nodes.map((n) => [h32(n), n]).sort((a, b) => a[0] - b[0]);
}
function owner(ring, hk) { // first node clockwise at or after the key position
  let lo = 0, hi = ring.length;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (ring[mid][0] < hk) lo = mid + 1; else hi = mid; }
  return ring[lo === ring.length ? 0 : lo][1];
}
const keys = []; for (let i = 0; i < 10000; i++) keys.push("user:" + i);
const hashes = keys.map(h32);

const four = ["node-A", "node-B", "node-C", "node-D"];
const ring4 = buildRing(four);
console.log("Ring with one position per node:");
for (let i = 0; i < ring4.length; i++) {
  const [pos, name] = ring4[i];
  const prev = ring4[(i + ring4.length - 1) % ring4.length][0];
  const arc = (pos - prev + RING) % RING;
  const count = hashes.filter((hk) => owner(ring4, hk) === name).length;
  console.log(`  ${name} at ${pct(pos, RING).padStart(6)} of the ring, owns arc ${pct(arc, RING).padStart(6)}, keys ${count}`);
}

function compare(label, before, after, nodesBefore, nodesAfter) {
  const ringB = buildRing(before), ringA = buildRing(after);
  let ringMoved = 0, modMoved = 0; const dest = {};
  for (const hk of hashes) {
    const a = owner(ringB, hk), b = owner(ringA, hk);
    if (a !== b) { ringMoved++; dest[b] = (dest[b] || 0) + 1; }
    if (nodesBefore[hk % nodesBefore.length] !== nodesAfter[hk % nodesAfter.length]) modMoved++;
  }
  console.log(`\n${label}`);
  console.log(`  hash % N       moved ${String(modMoved).padStart(5)} of 10000 keys (${pct(modMoved, 10000)})`);
  console.log(`  hash ring      moved ${String(ringMoved).padStart(5)} of 10000 keys (${pct(ringMoved, 10000)})`);
  console.log("  ring keys moved to: " + Object.keys(dest).sort().map((k) => `${k}=${dest[k]}`).join(", "));
}
compare("Add node-E (4 -> 5 nodes):", four, [...four, "node-E"], four, [...four, "node-E"]);
compare("Remove node-B (4 -> 3 nodes):", four, ["node-A", "node-C", "node-D"], four, ["node-A", "node-C", "node-D"]);

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.