The Problem: Why Modulo Hashing Breaks

Imagine a cache cluster with 4 nodes. The naive way to assign a key to a node:

---------- Naive modulo hashing ----------
  node_index = hash(key) % 4
  -> key 'user:42'  -> hash 17 -> 17 % 4 = 1 -> node[1]
  -> key 'photo:9'  -> hash 23 -> 23 % 4 = 3 -> node[3]

Works fine until you add a fifth node. Now hash(key) % 5 assigns almost every key to a different node. With 5 nodes, only ~20% of keys keep their old assignment; 80% remap.

Consequences:

• The cache hit rate drops to near zero immediately after the resize.
• Every new request misses the cache, falls through to the database, and the database melts.
• For a partitioned database, you have to physically move 80% of the data to its new home. Hours of downtime, weeks of operational pain.

This is the core reason consistent hashing exists. The goal: only ~K/N keys move when a node is added or removed, where K is total keys and N is cluster size.

The Hash Ring

Consistent hashing arranges all hash values on a circular space (typically 0 to 2^32 - 1 or 2^160 - 1 depending on the hash function).

---------- The hash ring (4 nodes) ----------
                    0 / 2^32
                       |
              N1 ---+--+--+--- N2
               (hash=1.07B)  (hash=2.14B)
                /              \
           keys                 keys
                \              /
              N4 ---+--+--+--- N3
               (hash=4.29B)  (hash=3.22B)

Placement:

1. Hash each node's identifier (e.g., hash('cache-1.example.com')) onto the ring. Nodes are now points on the ring.
2. To assign a key, hash it onto the same ring. The key belongs to the first node found by walking clockwise from the key's position.

Adding a node: place the new node on the ring. Only the keys between the new node and its predecessor migrate to the new node. Roughly K/N keys move.

Removing a node: its keys go to the next clockwise node. Same K/N migration.

---------- Adding a node (N5 between N1 and N2) ----------
  before:  ... N1 [keys 1.07B - 2.14B all on N2] N2 ...
  after:   ... N1 [keys 1.07B - 1.6B on N5] N5 [keys 1.6B - 2.14B on N2] N2 ...
  movement: only the keys between 1.07B and 1.6B move from N2 to N5.

Lookup Algorithm

class ConsistentHashRing {
    constructor(nodes = []) {
        this.ring = []; // sorted array of {hash, node}
        for (const n of nodes) this.addNode(n);
    }

    addNode(node) {
        const h = hash(node);
        this.ring.push({ hash: h, node });
        this.ring.sort((a, b) => a.hash - b.hash);
    }

    removeNode(node) {
        const h = hash(node);
        this.ring = this.ring.filter((e) => e.hash !== h);
    }

    getNode(key) {
        if (this.ring.length === 0) return null;
        const h = hash(key);
        // first ring entry with hash >= h (binary search in production)
        for (const entry of this.ring) {
            if (entry.hash >= h) return entry.node;
        }
        return this.ring[0].node; // wrap around
    }
}

Lookup is O(log N) with binary search. Add/remove is O(log N).

The Load-Balance Problem (and Virtual Nodes)

Vanilla consistent hashing has a serious flaw: with random node placement, some nodes get a much larger arc of the ring than others. With 4 nodes, the largest could easily own 40% of the keys instead of the ideal 25%. With 100 nodes, the imbalance is even more pronounced.

Solution: virtual nodes (vnodes). Each physical node is placed on the ring at many positions (typically 100 to 200). Now the ring has 100 * N points, the average arc per vnode is much smaller, and the law of large numbers smooths out the imbalance.

---------- With virtual nodes ----------
  4 physical nodes x 100 vnodes = 400 ring points
  Each physical node owns ~25% of total ring (close to ideal)
  Variance: ~ +/- 2% in production

A second benefit: when a physical node fails, its 100 vnode arcs go to 100 different successors. Load is spread across the surviving cluster instead of dumping onto one neighbor.

Cassandra default: 256 vnodes per physical node (num_tokens: 256). DynamoDB and Riak use similar numbers under the hood.

Replication on the Ring

For durability, each key needs to live on N replicas (typical N = 3). The standard pattern: walk clockwise from the key's hash, assign to the first node, then keep walking and assign to the next N-1 distinct physical nodes.

---------- Replication factor 3 on the ring ----------
  key 'photo:42' hashes to position p
  -> primary:    next vnode (physical node A)
  -> replica 1:  next vnode owned by a different physical node (B)
  -> replica 2:  next vnode owned by a different physical node (C)

Dynamo and Cassandra do exactly this. Reads and writes can use a quorum (R + W > N) to give linearizability per key.

When the Hash Function Matters

The hash function choice has real impact:

• MD5 / SHA-1: cryptographically uniform, slow (~100 ns per call). Good for small key counts where collisions matter; total overkill for caches.
• MurmurHash3 (Cassandra default): non-cryptographic, very fast (~10 ns), excellent distribution.
• xxHash: even faster (~5 ns), used by Memcached clients and some CDNs.
• CRC32: 32-bit, weak distribution above ~10K keys, only good for tiny clusters.

For a high-QPS cache, the hash function is on the critical path. MurmurHash3 or xxHash is the production answer.

Where Consistent Hashing Shows Up

Alternatives and Their Trade-offs

Rendezvous Hashing (Highest Random Weight, HRW)

For each key, compute hash(key, node_id) for every node and pick the node with the highest hash. Same minimal-disruption property as consistent hashing, no ring data structure, no virtual nodes needed.

Pros: simpler code, naturally balanced (no vnodes required), good for small clusters. Cons: O(N) per lookup vs O(log N) for ring; hurts at very large cluster sizes (1000+ nodes).

Used in: Akamai's load balancers, some content-delivery scenarios.

Jump Consistent Hash (Google, 2014)

A single fast function: given a key and bucket count N, returns a bucket in O(log N) without any ring or precomputed state. Designed for systems where N changes rarely.

Pros: extremely fast, no memory state, perfect uniformity. Cons: only works for adding buckets at the end; cannot remove arbitrary buckets and stay balanced.

Used in: Google's internal systems, F1, Spanner partitioning.

Maglev Hashing (Google's load balancer, 2016)

Builds a fixed-size lookup table (~65K entries) using a permutation algorithm. Lookup is O(1) array access. When backends change, ~1% of entries reshuffle.

Pros: O(1) lookup, very even distribution, low disruption. Cons: requires precomputed table; rebuild is O(M log N) where M is table size.

Used in: Google's Maglev L4 load balancer, Cilium's eBPF-based load balancer.

Choosing the Right Scheme

How to Talk About This in an Interview

1. Lead with the problem. 'If we use hash(key) % N, adding a node remaps almost all keys and crashes the cache. We use consistent hashing to bound key movement to ~K/N.'
2. Mention virtual nodes immediately. 'Each physical node has ~150 virtual nodes on the ring to balance load and spread failure cost.'
3. Quote the migration property. 'Only the keys between the new node and its predecessor move; roughly K/N total.'
4. Name a real system. 'DynamoDB, Cassandra, and Memcached all use a variation of this.'
5. Discuss replication. 'For replication factor 3, we walk clockwise and pick the next 3 distinct physical nodes.'
6. Mention alternatives if asked. 'Rendezvous hashing is simpler; jump consistent hash is faster but only allows growing; Maglev is the L4 load-balancer choice.'

Quick Review

• Naive hash % N remaps almost all keys when N changes - unacceptable.
• Consistent hashing places nodes and keys on a ring; each key goes to the first clockwise node.
• Adding/removing a node moves only ~K/N keys.
• Virtual nodes (100-200 per physical node) are required for balanced load.
• Replication: walk clockwise, pick the next N-1 distinct physical nodes.
• Standard in DynamoDB, Cassandra, Memcached, Riak, Discord, CDNs.
• Alternatives: rendezvous (simpler), jump (faster, grow-only), Maglev (L4-LB).