Consistent Hashing

Ten cache servers. Which one holds a given key?

const server = servers[hash(key) % servers.length];

Correct, fast, and it fails catastrophically the moment servers.length changes.

The modulo problem

Go from 10 servers to 11 and the divisor changes for every key at once. Around 90% of keys map somewhere new.

That is not a rebalance, it is a cache flush. Every miss goes to the database, simultaneously, at the exact moment you were adding capacity because you were already under load. Adding a server takes the system down.

The ring

Map both keys and servers onto the same circular space — say 0 to $2^{32}$.

A key belongs to the first server clockwise from it.

Now add a server. It lands somewhere on the ring and takes over only the arc between itself and the previous server. Every other arc is untouched, because no other key’s answer to “who is next clockwise?” changed.

class HashRing {
  private ring = new Map<number, string>();   // position → server
  private sorted: number[] = [];

  addServer(server: string) {
    for (let i = 0; i < this.replicas; i += 1) {
      const position = hash(`${server}#${i}`);   // ← several positions each
      this.ring.set(position, server);
    }
    this.sorted = [...this.ring.keys()].sort((a, b) => a - b);
  }

  serverFor(key: string): string {
    const h = hash(key);
    // First position clockwise — a binary search, not a scan.
    const index = lowerBound(this.sorted, h) % this.sorted.length;
    return this.ring.get(this.sorted[index]!)!;
  }
}

That is binary search on a sorted array of positions: $O(\log n)$ per lookup.

Virtual nodes are not optional

The alternatives, which are often better

Consistent hashing is the famous answer, not always the best one.

Rendezvous hashing (HRW). For each key, compute hash(key + server) for every server and pick the highest. No ring, no virtual nodes, perfectly even distribution, and trivially weighted. It is $O(n)$ per lookup rather than $O(\log n)$, which for a few hundred servers is irrelevant. If you are choosing today, start here.

Jump consistent hash. Google’s algorithm: seven lines, no memory, perfectly balanced. The constraint is that servers must be numbered 0…n−1 and you can only remove the last one — fine for shard counts, useless for a fleet with arbitrary failures.

Explicit shard maps. Many production systems just keep a table saying which range lives where, and move ranges deliberately. Less elegant, far easier to reason about and to rebalance on purpose.

Where it is used

Memcached clients, Cassandra and DynamoDB’s partitioning, Riak, Envoy’s ring-hash load balancing, and CDN request routing.

The common thread is worth naming: it is not really about hashing. It is about making the mapping depend on which servers exist rather than on how many, so that a change is proportional to its size.