How does consistent hashing work, and why do distributed caches like Memcached/Redis Cluster need it instead of simple modulo hashing?

#Why Modulo Hashing Falls Apart When the Cluster Changes

The naive way to shard keys across N cache servers is server = hash(key) % N. It's fast, it's uniform (assuming a decent hash function), and it works fine as long as N never changes. The moment you add or remove a single server — scaling out, a node crashing, a rolling deploy replacing an instance — N changes, and hash(key) % N recomputes to a different server for almost every key in the system, not just the keys that "belong" to the node you added or removed.

Concretely: with 4 servers, key_hash % 4 and key_hash % 5 agree on almost nothing. A key that mapped to server 2 out of 4 has no particular reason to still map to server 2 out of 5. The practical effect is a cache stampede — the instant you resize the cluster, the overwhelming majority of your working set is now "on the wrong server," every cache read becomes a miss, and all of that traffic pours onto the database at once, at the worst possible moment: right when you were trying to add capacity.

#Consistent Hashing: Only the Affected Slice Moves

Consistent hashing fixes this by hashing both the servers and the keys into the same circular space — typically the output range of a 32-bit or 64-bit hash function, imagined as a ring from 0 to 2^32 - 1 that wraps back to 0. Each server occupies one or more points on that ring. To find the owner of a key, hash the key into the same space and walk clockwise until you hit the first server position — that server owns the key.

When a server is added, it claims a single arc of the ring, and only the keys that fall in that arc move to it — everything else keeps its existing owner. When a server is removed, only the keys it owned move, to its clockwise neighbor. In both cases, the number of keys that move is proportional to 1/N of the total, not "almost all of them." That's the entire value proposition: bounded, predictable disruption instead of a near-total reshuffle.

Following the ring clockwise (increasing hash, wrapping past 2^32-1 back to 0): session:99 (hash 5) has Node A (15) as the first node clockwise from it, so Node A owns it. user:42 (20) is owned by the next node clockwise, Node B (25). user:17 (40) is owned by Node C (50). order:8 (60) wraps all the way around the ring without meeting any node until it reaches Node A (15) again, so Node A owns it too.

#Virtual Nodes: Fixing Uneven Load

A ring with only 3-5 physical servers, each hashed to a single point, distributes load very unevenly — the arc lengths between consecutive nodes are essentially random, so one server might own 50% of the keyspace and another 5%. The fix is virtual nodes: instead of hashing each physical server once, hash it many times under different labels (cache-a#0, cache-a#1, … cache-a#149) and place all of those points on the ring. Every physical node now owns many small, scattered arcs instead of one large arc, and the law of large numbers takes over — with 100-200 virtual nodes per physical node, the standard deviation of load between servers drops to a few percent instead of being dominated by chance.

Virtual nodes have a second benefit: when a physical node is added or removed, its virtual nodes are scattered all around the ring, so the keys that move are drawn evenly from every surviving node rather than dumping the entire burden of a rebalance onto one unlucky neighbor.

#Implementing a Ring with Virtual Nodes

import { createHash } from "crypto";

function hash32(input: string): number {
  const digest = createHash("md5").update(input).digest();
  return digest.readUInt32BE(0); // first 4 bytes as an unsigned 32-bit int
}

class ConsistentHashRing {
  private ring = new Map<number, string>();   // ring position -> physical node id
  private sortedPositions: number[] = [];
  private readonly virtualNodesPerNode: number;

  constructor(virtualNodesPerNode = 150) {
    this.virtualNodesPerNode = virtualNodesPerNode;
  }

  addNode(nodeId: string): void {
    for (let i = 0; i < this.virtualNodesPerNode; i++) {
      const position = hash32(`${nodeId}#${i}`);
      this.ring.set(position, nodeId);
    }
    this.rebuildIndex();
  }

  removeNode(nodeId: string): void {
    for (let i = 0; i < this.virtualNodesPerNode; i++) {
      const position = hash32(`${nodeId}#${i}`);
      this.ring.delete(position);
    }
    this.rebuildIndex();
  }

  // Returns the physical node that owns `key`.
  getNode(key: string): string | undefined {
    if (this.sortedPositions.length === 0) return undefined;
    const target = hash32(key);

    // Binary search for the first ring position >= target (the clockwise successor).
    let lo = 0;
    let hi = this.sortedPositions.length - 1;
    if (target > this.sortedPositions[hi]) {
      return this.ring.get(this.sortedPositions[0]); // wrap around to the top of the ring
    }
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.sortedPositions[mid] < target) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }
    return this.ring.get(this.sortedPositions[lo]);
  }

  private rebuildIndex(): void {
    this.sortedPositions = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }
}

// --- usage ---
const ring = new ConsistentHashRing(150);
ring.addNode("cache-a");
ring.addNode("cache-b");
ring.addNode("cache-c");

console.log(ring.getNode("user:42")); // e.g. "cache-b"
console.log(ring.getNode("user:17")); // e.g. "cache-a"

// Adding a fourth node only remaps roughly 1/4 of keys — the other 3/4
// keep resolving to the same node they always did.
ring.addNode("cache-d");

Each lookup costs O(log(N * V)), where N is the number of physical nodes and V is virtual nodes per node — a binary search over a sorted array of ring positions. In production you'd typically maintain this structure client-side, as Memcached client libraries like libketama do (since Memcached servers have zero awareness of each other), or use a battle-tested library rather than hand-rolling MD5 math — but the mechanics above are exactly what those libraries do internally.

#Redis Cluster: A Related but Different Mechanism

It's worth being precise here, because this is a common point of confusion in interviews. Memcached has no clustering protocol at all — the servers don't know about each other, so consistent hashing is implemented entirely in the client library, which is free to use a ring with virtual nodes exactly as above. Redis Cluster, by contrast, does not use a continuous hash ring. It divides the keyspace into a fixed 16,384 hash slots, computes CRC16(key) % 16384 to find a key's slot, and assigns contiguous ranges of slots to each master node. Resharding in Redis Cluster means explicitly migrating a range of slots from one node to another (CLUSTER SETSLOT), not walking a ring.

Both designs solve the same underlying problem — bounding how many keys move when the cluster's membership changes — but they solve it differently: Redis Cluster's fixed slot count means slots (and the keys in them) are moved in controlled, explicit batches, while a virtual-node ring redistributes ownership implicitly and continuously as the node set changes. Conflating the two in an interview answer is a common tell that a candidate has memorized "consistent hashing" as a keyword rather than understanding what problem it solves.