Consistent Hashing: why mod-N fails, the ring, virtual nodes

When you scale from one cache (Redis) to many, how do you route keys to the right cache node? Naive hashing breaks when nodes are added/removed. Consistent hashing solves this.

The Problem: Naive Modulo

3 cache nodes: N0, N1, N2

hash(key) % 3:
  "user:123" % 3 = 0 → N0
  "user:456" % 3 = 1 → N1
  "post:789" % 3 = 2 → N2

Add node N3?

Now hash(key) % 4:
  "user:123" % 4 = 3 → N3 (moved!)
  "user:456" % 4 = 0 → N0 (moved!)
  "post:789" % 4 = 1 → N1 (moved!)

All keys rehash. Massive cache misses. Database thrashed.

Why it's bad: O(N) keys rehash when a node is added. Every cache miss hits the database.

---

Consistent Hashing: The Ring

Idea: Hash both keys AND nodes onto a ring (0 to 2^32 - 1). A key goes to the next node clockwise.

Ring (0 to 360 degrees):

     N0 (at 10°)
    /
   /
  P (post:789 at 340°)
            N2 (at 180°)
      |
      |
     N1 (at 90°)

To find node for "post:789":
  1. Hash("post:789") → 340°
  2. Walk clockwise: 340° → 10° (wrap) → found N0
  3. Store on N0

Add N3 at 260°:

     N0 (10°)
    /
   /
  P (340°)
          N3 (260°)
      /
      N2 (180°)
      |
      |
     N1 (90°)

"post:789" at 340°: walk clockwise → 10° (N0). Still on N0.
"user:555" at 250°: walk clockwise → 260° (N3). Now on N3 (moved from wherever).

Only keys between N2 (180°) and N3 (260°) rehash. Others stay put.

Benefit: Adding one node affects O(1/N) keys (1/4 of keys if adding 4th node), not all keys.

---

Virtual Nodes: Fixing Skew

Problem: With one position per node, distribution is uneven. If N0 is at 10° and N1 at 180°, N0 "owns" an arc of 350°. Unbalanced.

Solution: Each physical node maps to multiple positions on the ring ("virtual nodes").

3 physical nodes, 3 virtual nodes each:

N0: [10°, 50°, 70°]
N1: [90°, 110°, 200°]
N2: [180°, 250°, 300°]

Hash("user:123") → 145°:
  Walk clockwise: 145° → 180° (N2)

Hash("post:456") → 75°:
  Walk clockwise: 75° → 90° (N1)

Distribution is more even because N0 has 3 chances to catch a key.

Rule of thumb: 150-200 virtual nodes per physical node. More = better distribution, more memory.

---

Adding/Removing Nodes

Add node: New node gets virtual node positions on the ring. Only keys in the arcs it covers rehash (to it).

Remove node: Node's virtual nodes disappear. Keys in those arcs rehash (to the next node clockwise). Rebalancing is gradual.

---

Real-World Example: Memcached Cluster

10 Memcached servers.
Each key hashes to a server via consistent hashing.

Client code:
  hash(key) → position on ring
  find next server clockwise
  connect to that server

If server 5 dies:
  Only keys that hashed to server 5 rehash (to server 6).
  Other 9 servers unaffected.
  Cache hit rate drops minimally.

---

Comparison: Naive vs Consistent

| Scenario | Naive (mod N) | Consistent | |----------|---------------|-----------| | 1000 keys, add 1 node | 1000 rehash (~100% churn) | ~250 rehash (~25% churn) | | Remove 1 node | 1000 rehash | ~250 rehash | | Uneven distribution | Possible (hot spots) | Mitigated (virtual nodes) | | Implementation | Simple (one line) | Moderate (binary search on ring) |

---

In the interview

1. Problem first: "With N cache nodes and hash(key) % N, adding a node causes all keys to rehash. Database gets hammered."

2. Solution: "Consistent hashing: hash keys and nodes onto a ring. A key goes to the next node clockwise. Adding one node only rehashes O(1/N) keys."

3. Virtual nodes: "One position per node causes skew. Using 150+ virtual nodes per physical node evens the distribution."

4. Use cases: "Memcached clusters, DynamoDB, Cassandra—anywhere you need to scale a key-value store horizontally without massive rehashing."

5. Tradeoff: "Consistent hashing is slightly more complex but saves cache misses during scaling. Worth the effort."