Understanding Consistent Hashing in Distributed Caches

Introduction

When you add or remove a node from a distributed cache using modulo hashing (node = hash(key) % N), changing N causes nearly every key to map to a different node — invalidating the entire cache. For a cache with millions of entries, this causes a cache stampede: all traffic suddenly hits the origin database, potentially overwhelming it. Consistent hashing solves this by arranging nodes on a virtual ring, so adding/removing a node only remaps ~1/N of the keys (where N is the number of nodes).

Step-by-Step: How Consistent Hashing Works

flowchart TD
    A["1. The Hash Ring"]
    B["2. Key Lookup (Clockwise Traversal)"]
    C["3. Node Addition (Only ~1/N Keys Remapped)"]
    D["4. Virtual Nodes for Even Distribution"]
    E["5. Redis Cluster Implementation"]
    A --> B
    B --> C
    C --> D
    D --> E

Step 1: The Hash Ring

Imagine a circular ring of integers from 0 to 2³² - 1. Each cache node is placed on the ring at a position determined by hashing its identifier:

import hashlib

def hash_key(key: str) -> int:
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % (2**32)

# Place nodes on ring
nodes = {
    hash_key("cache-node-1"): "cache-node-1",  # Position: 892340123
    hash_key("cache-node-2"): "cache-node-2",  # Position: 1234567890
    hash_key("cache-node-3"): "cache-node-3",  # Position: 3456789012
}
# Ring: 0 ... [node1:892M] ... [node2:1.23B] ... [node3:3.45B] ... 2^32

Step 2: Key Lookup (Clockwise Traversal)

To find which node holds a key, hash the key and walk clockwise to the next node:

import bisect

class ConsistentHashRing:
    def __init__(self, nodes: list[str], vnodes: int = 100):
        self.ring = {}
        self.sorted_keys = []
        self.vnodes = vnodes
        for node in nodes:
            self.add_node(node)
    
    def add_node(self, node: str):
        # Each physical node has 'vnodes' virtual nodes for even distribution
        for i in range(self.vnodes):
            virtual_key = hash_key(f"{node}#{i}")
            self.ring[virtual_key] = node
            bisect.insort(self.sorted_keys, virtual_key)
    
    def get_node(self, key: str) -> str:
        if not self.ring:
            raise Exception("Ring is empty")
        hash_val = hash_key(key)
        # Binary search: find first node position >= hash_val
        idx = bisect.bisect(self.sorted_keys, hash_val)
        if idx == len(self.sorted_keys):
            idx = 0  # Wrap around ring
        return self.ring[self.sorted_keys[idx]]

ring = ConsistentHashRing(["cache-1", "cache-2", "cache-3"])
print(ring.get_node("user:12345"))  # → "cache-2"
print(ring.get_node("session:abc")) # → "cache-3"

Step 3: Node Addition (Only ~1/N Keys Remapped)

Before adding cache-4:
  Keys 1B–2B → cache-2

After adding cache-4 at position 1.5B:
  Keys 1B–1.5B → cache-2    (unchanged)
  Keys 1.5B–2B → cache-4    (remapped — only these keys are cache misses)

With N=3 nodes, adding cache-4: only ~25% of keys remapped (vs ~75% with modulo hashing)
With N=10 nodes, adding 1 node: only ~9% of keys remapped

Step 4: Virtual Nodes for Even Distribution

Without virtual nodes, physical node placement may be uneven — one node handles 60% of keys. Virtual nodes (vnodes) place each physical node at multiple positions on the ring:

cache-1 at positions: 45M, 312M, 891M, 1.2B, 2.1B, 3.7B (100 vnodes)
cache-2 at positions: 89M, 456M, 934M, 1.5B, 2.8B, 4.1B (100 vnodes)
cache-3 at positions: 12M, 234M, 678M, 1.8B, 3.2B, 4.3B (100 vnodes)

Result: Each physical node handles ~33% of keys (evenly distributed)

Step 5: Redis Cluster Implementation

Redis Cluster uses a simplified consistent hashing variant with hash slots:

# Redis Cluster uses 16,384 hash slots
# hash_slot = CRC16(key) mod 16384

# Each node owns a range of slots:
# Node 1: slots 0-5460
# Node 2: slots 5461-10922
# Node 3: slots 10923-16383

# Check which slot a key maps to
redis-cli cluster keyslot "user:12345"
# → 2915 (maps to Node 1)

# Add a node - Redis migrates only the relevant slots
redis-cli --cluster add-node new-node:6379 existing-node:6379
redis-cli --cluster reshard existing-node:6379

Key Takeaways

• Modulo hashing remaps ~(N-1)/N keys when adding/removing a node — causing cache stampedes. Consistent hashing remaps only ~1/N keys.
• Keys are assigned to the first node clockwise on the hash ring — a simple binary search using a sorted array of node positions.
• Virtual nodes (100–200 per physical node) ensure even key distribution across nodes with varying capacities.
• When a node fails, only its keys remap to the next clockwise node — other nodes are unaffected.
• Redis Cluster uses 16,384 hash slots (a fixed consistent hashing variant) — nodes own slot ranges that are migrated during rebalancing.