Phase 3 · Chapter 2

Consistent Hashing

How distributed systems partition data without destroying everything on rescale

What this chapter does to you: Every distributed system eventually asks: which node owns this data? Naive modulo hashing works until you add or remove a node — then everything remaps and your cache is useless. Consistent hashing solves this with one elegant idea: arrange nodes on a ring, and data moves only from the affected node, not everywhere. After this chapter, you will understand why Redis Cluster, Cassandra, and every CDN uses consistent hashing, and you will be able to derive it from first principles in an interview.

Part 1: The Problem — Distributing Data Across Nodes

You have a Redis cluster with 4 nodes. You need to decide which node stores each key. The simplest approach:

function getNode(key, numNodes) {
  const hash = murmurhash(key)      // hash key to integer
  return hash % numNodes            // modulo maps to node index
}

getNode('user:123', 4)  → node 2
getNode('user:456', 4)  → node 1
getNode('user:789', 4)  → node 0

Clean. Fast. Predictable. Every key maps to exactly one node.

Now you add a 5th node.

getNode('user:123', 5)  → node 3   // was node 2 — DIFFERENT
getNode('user:456', 5)  → node 1   // same
getNode('user:789', 5)  → node 4   // was node 0 — DIFFERENT

When numNodes changes from 4 to 5, the modulo result changes for approximately (N-1)/N = 80% of all keys.

80% of your cached data is now on the wrong node.

For a cache: 80% cache miss rate. Every miss hits your database. Your database gets 80% of your traffic suddenly. It melts.

For a database: 80% of your data must be physically moved to different nodes. During a resharding operation, the system is slow and vulnerable.

This is why naive modulo hashing fails for distributed systems. Adding or removing nodes is a routine operation. You cannot invalidate 80% of your data every time.

Part 2: The Insight — A Ring Instead of a Line

Consistent hashing replaces the modulo operation with a ring structure.

Building the Ring

Imagine the range of hash values as a circle (ring) from 0 to 2^32 - 1.

Place each node on the ring by hashing its identifier:

const ring = new Map()

function addNode(nodeId) {
  const position = murmurhash(nodeId)   // hash node ID → position on ring
  ring.set(position, nodeId)
}

addNode('node-1')  → position 892,341,024
addNode('node-2')  → position 2,147,483,648
addNode('node-3')  → position 3,221,225,472
addNode('node-4')  → position 429,496,730

The ring now looks like:

                    0
                    │
     node-4 ───────►│◄─────── node-1
    (pos 429M)      │         (pos 892M)
                    │
                    │
    node-3 ─────────┴─────── node-2
   (pos 3.2B)              (pos 2.1B)

Assigning Keys to Nodes

To find which node owns a key:

1. Hash the key → get a position on the ring
2. Walk clockwise from that position
3. The first node you hit — that's the owner

function getNode(key) {
  const keyPosition = murmurhash(key)

  // Find the first node clockwise from keyPosition
  const sortedPositions = [...ring.keys()].sort((a, b) => a - b)

  for (const nodePosition of sortedPositions) {
    if (nodePosition >= keyPosition) {
      return ring.get(nodePosition)
    }
  }

  // Wrap around: key is past the last node, goes to first node
  return ring.get(sortedPositions[0])
}

getNode('user:123')  // hash → position 1,500,000,000 → clockwise → node-2
getNode('user:456')  // hash → position 300,000,000  → clockwise → node-4

Before reading why adding a node is cheap, try it. Each tab asks you to predict first — adding a node, losing one, and virtual nodes.

Adding a Node — The Magic

Add node-5 at ring position 1,200,000,000 (between node-1 at 892M and node-2 at 2.1B):

Before: keys in range [892M, 2.1B] went to node-2
After:  keys in range [892M, 1.2B] go to node-5
        keys in range [1.2B, 2.1B] still go to node-2

Only the keys between node-1 and node-5's new position need to move. Everything else stays exactly where it is.

With 4 original nodes, adding a 5th means on average: 1/5 = 20% of keys move to the new node. The other 80% are completely unaffected.

Compare to modulo hashing: 80% moved. Consistent hashing: 20% moved.

Removing a node: Only that node's keys move — to its clockwise successor. All other nodes are unaffected.

Part 3: The Problem with Basic Consistent Hashing

With 4 nodes, each should own approximately 25% of the ring. But hash positions are random — some nodes might get 40% of the ring, others 10%. Unequal load distribution.

node-1: 15% of ring
node-2: 35% of ring   ← overloaded
node-3: 40% of ring   ← overloaded
node-4: 10% of ring   ← underloaded

The fix: virtual nodes (vnodes)

Instead of placing each physical node once on the ring, place it many times — each time with a different hash (e.g., hash the node ID combined with a counter: hash("node-1:0"), hash("node-1:1"), etc.).

const VNODES_PER_NODE = 150   // each physical node appears 150 times

function addNode(nodeId) {
  for (let i = 0; i < VNODES_PER_NODE; i++) {
    const vnodeId = `${nodeId}:${i}`
    const position = murmurhash(vnodeId)
    ring.set(position, nodeId)   // position → physical node
  }
}

With 150 virtual nodes per physical node:

• 4 physical nodes × 150 vnodes = 600 positions on the ring
• Distribution converges to ~25% per node (law of large numbers)
• When a node is added: its 150 vnodes are spread across the ring, taking small amounts of load from every existing node

Cassandra uses 256 virtual tokens (vnodes) per node by default. Redis Cluster uses 16,384 hash slots (a different implementation of the same idea).

Part 4: Redis Cluster — Consistent Hashing in Production

Redis Cluster doesn't use a pure consistent hash ring. It uses hash slots — a fixed set of 16,384 slots, statically divided among nodes.

Slots 0–5460:      Node A (primary + replica)
Slots 5461–10922:  Node B (primary + replica)
Slots 10923–16383: Node C (primary + replica)

To find which node owns a key:

function getSlot(key) {
  return crc16(key) % 16384   // CRC16 hash, modulo 16384
}

getSlot('user:123')  → slot 7891  → Node B
getSlot('session:x') → slot 1234  → Node A

When you add a node:

• Assign it some slots from existing nodes
• Move data for only those slots to the new node
• Other slots unaffected

This is the consistent hashing principle implemented as discrete slots rather than a continuous ring. The math is the same — only affected data moves.

The hash tag trick:

You want user:123:profile and user:123:settings to live on the same node (so you can do multi-key operations on them).

Redis uses the content inside {} as the hash key:

user:{123}:profile   → hash of "123" → slot 7891 → Node B
user:{123}:settings  → hash of "123" → slot 7891 → Node B

Both keys have the same hash tag {123} → same slot → same node. Multi-key operations (MGET, MULTI/EXEC) work because both keys are local.

Part 5: Consistent Hashing in CDNs

Your CDN (Cloudflare, Akamai, Fastly) has edge nodes in hundreds of cities. When a request arrives, which edge node caches and serves the response?

Consistent hashing determines this:

Request for: cdn.example.com/video/abc.mp4
Hash of URL: → position on ring → nearest edge node in that region

Every request for video/abc.mp4 hits the same edge node (the one that "owns" that hash position). That node caches the video. Subsequent requests from anywhere in the region served by that node hit the cache.

Adding a new edge node: Only URLs that hash between the new node's position and its predecessor start routing to the new node. All other URLs continue hitting their existing edge nodes — cache still warm.

Without consistent hashing: adding an edge node invalidates the entire cache for that region (all URLs remap). Every request becomes a cache miss. Your origin servers get hammered. Globally. This is a real CDN failure mode.

Part 6: Where Consistent Hashing Appears in Your Stack

Every time you see "shard data across nodes," consistent hashing is likely underneath.

Part 7: The Vocabulary Map

Part 8: Practice Problems

Problem 1 (The Math): You have a consistent hash ring with 3 nodes at positions:

• Node A: 100
• Node B: 200
• Node C: 300

Keys hash to the following positions:

• key1: 50
• key2: 150
• key3: 250
• key4: 350

Which node owns each key? (Remember: wrap around at 300 → back to 100.)

Now you add Node D at position 175. Which keys move? Which node do they move to? Which keys stay? What percentage of keys moved vs modulo hashing (which would move 75%)?

Problem 2 (Virtual Nodes): Without virtual nodes, 3 nodes on a ring produce this distribution:

• Node A owns 40% of the key space
• Node B owns 35% of the key space
• Node C owns 25% of the key space

You add 150 virtual nodes per physical node. Explain qualitatively why this makes the distribution converge to ~33% each. What is the statistical principle at work?

What are the downsides of using 1,000 virtual nodes instead of 150? (Think about memory and lookup time.)

Problem 3 (Redis Cluster Design): AttemptIQ's Redis Cluster has 3 primary nodes. You need to store:

• session:{userId} — user session data
• user:{userId}:profile — cached user profile
• user:{userId}:scores — test score history

You need to run a Lua script that reads all three keys for a given user atomically.

How do you ensure all three keys land on the same Redis slot? Write the exact key format using hash tags. What is the limitation of this approach at scale?

Problem 4 (Failure Scenario): Redis Cluster has 3 primaries (A, B, C) each with one replica (A', B', C'). Node B crashes. Node B' is promoted to primary.

In consistent hashing terms:

• Which hash slots were owned by B?
• Where do writes to those slots go during the failover window (between B crash and B' promotion)?
• After B' is promoted, does the slot ownership change?
• What happens if you later add a new node to replace the lost replica?

End of Phase 3, Chapter 2.