Consistent Hashing

In plain words

You have millions of keys — user sessions, cache entries — and a handful of servers. You need a rule that says which server owns which key, and the rule has to keep working when you add a server or one dies. Consistent hashing is that rule: it puts servers and keys on a circle, and when a server appears or disappears only its neighbours' keys move.

Why modulo breaks

hash(key) % N is a fine rule as long as N never changes. Change it and almost every key's answer changes, because the remainder of a division has nothing to do with the remainder of a slightly different division.

The ring

Hash both the servers and the keys onto the same circle of numbers (say 0 to 2³²). A key belongs to the first server you meet walking clockwise from the key's position.

1. Place the servers

   Hash each server's name to a point on the ring: hash("cache-a") → 1,200,000, and so on.

2. Look up a key

   Hash the key, then find the next server clockwise. That is its owner. A sorted list plus a binary search: microseconds.

3. Add a server

   It lands at one point and takes over the arc between it and the previous server — only that arc. About 1/N of keys move, all from one neighbour.

4. Remove a server

   Its arc falls to the next server clockwise. Nothing else is disturbed.

import { createHash } from "node:crypto";

const h = (s: string) => parseInt(createHash("md5").update(s).digest("hex").slice(0, 8), 16);

class Ring {
  private points: { pos: number; server: string }[] = [];

  constructor(servers: string[], private vnodes = 150) {
    for (const s of servers) this.add(s);
  }

  add(server: string) {
    // Many points per server (virtual nodes) — see below for why.
    for (let i = 0; i < this.vnodes; i++) this.points.push({ pos: h(`${server}#${i}`), server });
    this.points.sort((a, b) => a.pos - b.pos);
  }

  remove(server: string) {
    this.points = this.points.filter((p) => p.server !== server);
  }

  owner(key: string): string {
    const pos = h(key);
    // First point clockwise from the key; wrap to the start if none.
    let lo = 0, hi = this.points.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.points[mid].pos < pos) lo = mid + 1; else hi = mid;
    }
    return this.points[lo % this.points.length].server;
  }
}

Virtual nodes are not optional

With one point per server, random placement gives some servers a huge arc and others a sliver — the widget shows one server owning 63% of the keys with four servers. Worse, when a server leaves, its whole arc lands on a single neighbour, which is how one failure becomes two.

That is what the vnodes = 150 in the code does. Turn the slider up in the widget and watch the shares converge.

What it does not solve

It also gives up ordering. Keys next to each other on the ring are unrelated in value, so "all keys between A and B" means asking every server. If range queries matter, that is the same trade-off as hash partitioning in sharding.

Where you meet it

• Cache clients. Memcached and Redis client libraries use it to pick a node — usually without you noticing, which is why the modulo disaster above happens mostly to people who wrote their own.
• Databases. Cassandra and DynamoDB place data with it; each node owns ranges of the ring.
• Load balancers and CDNs. "Same user → same server" without a shared session store, and it degrades gracefully when a server drops.

Take this with you

• The one idea: put nodes and keys on the same ring, so adding or losing a node moves about 1/N of the keys instead of nearly all of them.
• In an interview, explain hash % N first, then the ring, then virtual nodes — and say plainly that it balances keys, not traffic.
• At work, check whether your cache client already does this (most do). If it uses modulo, a scale-out is a cache wipe.