Introduction

Imagine you run a big web cache. You have n servers, and for each key you decide where it lives with the obvious trick: server = hash(key) mod n. Cheap, fast, evenly spread. Then one server dies, or you add a new one — and n changes.

Now almost every key maps somewhere new. A cache that was warm goes cold all at once; databases stampede; users wait. Changing a single machine should not reshuffle the whole world, yet plain modulo hashing does exactly that.

Consistent hashing fixes this with one beautifully simple move: instead of dividing by n, place both servers and keys on a circle. Add or remove a server and only the keys in its immediate neighborhood — about 1/n of them — ever have to move.

Try It: The Ring

Below is a hash ring. The colored wedges are servers; the small dots are keys. Each key belongs to the first server you meet going clockwise. Add or remove a server and watch the counter: only the keys that change owner light up, and there are surprisingly few of them.

<p class="hint">The big ring is the hash space (0–360). Colored wedges are <b>servers</b>; dots are <b>keys</b>. A key belongs to the first server found going <b>clockwise</b>. Add or remove a server — only the dots that change owner flash, and there are very few.</p>
<div class="wrap">
  <svg id="ring" viewBox="0 0 320 320" width="300" height="300" aria-label="hash ring"></svg>
</div>
<div class="status" id="status">3 servers, 30 keys.</div>
<div class="btns">
  <button id="add" type="button">Add a server</button>
  <button id="remove" type="button">Remove a server</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.wrap { display: flex; justify-content: center; }
svg { max-width: 100%; height: auto; }
.key { fill: #9aa0a6; transition: fill .2s, r .2s; }
.key.moved { fill: #e63946; }
.srv-dot { stroke: #fff; stroke-width: 2; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; text-align: center; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: not-allowed; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Consistent hashing: servers and keys live on a circle [0,360). A key is owned
    // by the first server clockwise from it. Adding/removing one server only changes
    // ownership of the keys in one arc — about K/n of them (Karger et al., 1997).
const PALETTE = ['#1d3557','#2a9d8f','#e9c46a','#f4a261','#e76f51','#7d4f9e','#457b9d','#06a77d'];
const CX = 160, CY = 160, R = 120;
const NUM_KEYS = 30;

// Deterministic positions so the demo is stable and verifiable.
function hashTo360(n){ // simple integer hash -> [0,360)
  let x = (n * 2654435761) >>> 0;
  x ^= x >>> 13; x = (x * 1597334677) >>> 0; x ^= x >>> 16;
  return (x % 36000) / 100;
}
const KEYS = [];
for (let i = 0; i < NUM_KEYS; i++) KEYS.push({ id: i, ang: hashTo360(i + 1) });

let servers = [];     // array of angles (degrees)
let seed = 1000;

function freshServer(){ const a = hashTo360(seed++); return a; }
function reset(){ servers = [hashTo360(7), hashTo360(99), hashTo360(250)].sort((a,b)=>a-b); }

// Owner of a key = first server at angle >= key angle (clockwise), wrapping around.
function ownerOf(ang){
  const s = [...servers].sort((a,b)=>a-b);
  for (const v of s) if (v >= ang) return v;
  return s[0]; // wrap to the first server
}
function colorFor(ang){
  const s = [...servers].sort((a,b)=>a-b);
  return PALETTE[s.indexOf(ang) % PALETTE.length];
}

function polar(ang, rad){
  const t = (ang - 90) * Math.PI / 180; // 0deg at top, clockwise
  return [CX + rad * Math.cos(t), CY + rad * Math.sin(t)];
}

let moved = new Set();
function render(){
  const svg = document.getElementById('ring');
  const s = [...servers].sort((a,b)=>a-b);
  let html = `<circle cx="${CX}" cy="${CY}" r="${R}" fill="none" stroke="#d7dde3" stroke-width="10"/>`;
  // server markers
  s.forEach(a => {
    const [x,y] = polar(a, R);
    html += `<circle class="srv-dot" cx="${x}" cy="${y}" r="9" fill="${colorFor(a)}"/>`;
  });
  // keys, colored by owner
  KEYS.forEach(k => {
    const own = ownerOf(k.ang);
    const [x,y] = polar(k.ang, R);
    const cls = moved.has(k.id) ? 'key moved' : 'key';
    const r = moved.has(k.id) ? 6 : 4.5;
    html += `<circle class="${cls}" cx="${x}" cy="${y}" r="${r}" fill="${colorFor(own)}"/>`;
  });
  svg.innerHTML = html;
  document.getElementById('remove').disabled = servers.length <= 1;
}
function setStatus(t){ document.getElementById('status').textContent = t; }

function snapshot(){ const m = {}; KEYS.forEach(k => m[k.id] = ownerOf(k.ang)); return m; }
function diff(before){
  moved = new Set();
  KEYS.forEach(k => { if (before[k.id] !== ownerOf(k.ang)) moved.add(k.id); });
  return moved.size;
}

function add(){
  const before = snapshot();
  servers.push(freshServer());
  const n = diff(before);
  render();
  setStatus(fmt('Added server #%length%. %n% of %NUM_KEYS% keys moved (%round%%).', { length: servers.length, n: n, NUM_KEYS: NUM_KEYS, round: Math.round(100*n/NUM_KEYS) }));
}
function remove(){
  if (servers.length <= 1) return;
  const before = snapshot();
  servers.pop();
  const n = diff(before);
  render();
  setStatus(fmt('Removed a server (%length% left). %n% of %NUM_KEYS% keys moved (%round%%).', { length: servers.length, n: n, NUM_KEYS: NUM_KEYS, round: Math.round(100*n/NUM_KEYS) }));
}
function doReset(){ reset(); seed = 1000; moved = new Set(); render(); setStatus(fmt('%length% servers, %NUM_KEYS% keys.', { length: servers.length, NUM_KEYS: NUM_KEYS })); }

document.getElementById('add').addEventListener('click', add);
document.getElementById('remove').addEventListener('click', remove);
document.getElementById('reset').addEventListener('click', doReset);
doReset();
Result
Console

Try adding several servers in a row. With plain hash(key) mod nhash(key) \bmod n, every add would relocate nearly 100% of keys. On the ring, each new server steals only the slice between it and its clockwise neighbor — on average about 1/n of all keys. That gap between "move everything" and "move a sliver" is the whole reason large systems can grow without falling over.

The Real Complexity

Consistent hashing is not an open problem or an impossibility result — it is a solved engineering idea with proven guarantees, introduced by David Karger and colleagues at MIT in 1997. Here is what it buys you:

  • Minimal disruption. With K keys and n servers, adding or removing a server relocates only about K/n keys on average. Plain modulo hashing relocates almost all K.
  • Fast lookups. Servers sit at sorted positions on the ring, so finding the owner of a key is a binary search: O(log⁡n)O(\log n) per lookup.
  • Monotonicity. When you add a server, keys only ever move to the new server, never bouncing between existing ones. That is the property plain hashing lacks.
  • Balance via virtual nodes. A single point per server can leave the ring lumpy. The fix is to place each server at many random positions ("virtual nodes"), which evens the load to within a small factor with high probability.

None of this is NP-hard or undecidable. The depth is in the analysis: proving that random placement on a ring keeps loads balanced and key movement minimal is a clean probabilistic argument, the same flavor that powers load balancing and hashing-based pattern matching.

Where It Matters

Once you can add and remove machines without reshuffling everything, you can build systems that grow elastically. Consistent hashing is the quiet workhorse behind much of the cloud:

  • Distributed databases: Amazon Dynamo, Cassandra, Riak and ScyllaDB place data on a ring so nodes can join and leave with minimal data movement.
  • Caching layers: memcached client libraries and Redis Cluster-style setups use the ring so a dead cache node only invalidates its own slice.
  • Content delivery networks: CDNs route a URL to a cache server by hashing it onto a ring, keeping requests sticky as the fleet changes.
  • Load balancers: ring hashing keeps a given client mapped to the same backend, preserving sessions and warm connections.

The common thread is the same shape as in load balancing: spread work fairly, and let the system absorb change gracefully instead of all at once.

Conclusion

Consistent hashing is a rare thing in computer science: a problem that looks like it should be hard — keep data placement stable as machines come and go — that turns out to have an elegant, provably good answer. Wrap the address space into a circle, walk clockwise to find an owner, and a single failed or added server disturbs only its own neighborhood.

It will not solve anything from P vs NP. But it is one of those ideas that quietly makes the impossible-seeming routine, letting a handful of servers grow into a planet-scale system without ever moving more than it has to.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/consistent-hashing/Content licensed under CC BY-NC 4.0.