System Design Interview Question: What Is Consistent Hashing?

Short answer: consistent hashing distributes keys across servers so that adding or removing a server moves only a small fraction of keys, instead of almost all of them.

The problem with modulo

server = hash(key) % N

N = 4 -> 5 servers: about 80% of keys now map to a different server

For a cache cluster, that means a near-total cache miss storm every time you scale.

The hash ring

1. Map the hash space onto a circle (for example 0 to 2^32 - 1).
2. Place each server on the ring by hashing its name.
3. Hash each key onto the ring and walk clockwise to the first server: that server owns the key.

Adding a server only takes keys from its clockwise neighbour; removing one gives its keys to the next server. Only about 1/N of keys move.

Virtual nodes

With few servers, positions on the ring are uneven, so some servers get much more data. Each physical server is placed at many points (virtual nodes, say 100-200), which evens out the load and lets bigger machines take more virtual nodes.

class HashRing {
  constructor(nodes, vnodes = 150) {
    this.ring = [];
    for (const node of nodes) {
      for (let i = 0; i < vnodes; i++) this.ring.push({ pos: hash(`${node}#${i}`), node });
    }
    this.ring.sort((a, b) => a.pos - b.pos);
  }
  nodeFor(key) {
    const h = hash(key);
    // first virtual node clockwise from the key (binary search in a real implementation)
    const entry = this.ring.find((e) => e.pos >= h) ?? this.ring[0];
    return entry.node;
  }
}

Where it's used

• Distributed caches (client-side sharding for Memcached).
• Distributed databases like Cassandra and DynamoDB-style systems for partitioning.
• Load balancers that need request affinity (the same user to the same server).

Bonus: mention rendezvous (highest random weight) hashing as a simpler alternative with similar properties, and replication by storing each key on the next K distinct servers on the ring.