Consistent Hashing: Minimal Key Redistribution

Key Insights

Traditional modulo-based hashing redistributes nearly all keys when servers change; consistent hashing moves only K/N keys on average, where K is total keys and N is node count.
Virtual nodes solve the uneven distribution problem inherent in basic consistent hashing, with 100-200 vnodes per physical node being a practical starting point.
Consistent hashing isn’t free—it trades memory overhead and implementation complexity for minimal redistribution, making it most valuable when key movement is expensive.

The Problem with Traditional Hashing

When you need to distribute data across multiple servers, the obvious approach is modulo hashing: hash the key, divide by server count, use the remainder as the server index. It’s simple, fast, and works perfectly—until you add or remove a server.

def modulo_hash(key: str, server_count: int) -> int:
    return hash(key) % server_count

# With 4 servers
servers = ["server-0", "server-1", "server-2", "server-3"]
keys = ["user:1001", "user:1002", "user:1003", "session:abc", "cache:xyz"]

print("Distribution with 4 servers:")
for key in keys:
    server_idx = modulo_hash(key, 4)
    print(f"  {key} -> {servers[server_idx]}")

print("\nDistribution with 5 servers:")
servers.append("server-4")
for key in keys:
    server_idx = modulo_hash(key, 5)
    print(f"  {key} -> {servers[server_idx]}")

Run this code and watch the chaos unfold. A key that hashed to server 2 with four servers might now hash to server 4 with five servers. The math is brutal: when you change from N to N+1 servers, approximately (N)/(N+1) of your keys need to move. Going from 10 to 11 servers? About 91% of your cache is now invalid.

For a caching layer, this means a thundering herd of cache misses hitting your database. For a sharded database, it means massive data migration. Neither is acceptable in production systems that need to scale dynamically.

How Consistent Hashing Works

Consistent hashing reimagines the problem by placing both nodes and keys on a circular hash space—typically represented as a ring from 0 to 2^32-1. Each node gets a position on the ring based on hashing its identifier. To find which node owns a key, you hash the key, find its position on the ring, and walk clockwise until you hit a node.

import hashlib
from bisect import bisect_right
from typing import Optional

class ConsistentHashRing:
    def __init__(self):
        self.ring: dict[int, str] = {}  # position -> node
        self.sorted_positions: list[int] = []
        self.nodes: set[str] = set()
    
    def _hash(self, key: str) -> int:
        """Generate a 32-bit hash position on the ring."""
        digest = hashlib.md5(key.encode()).hexdigest()
        return int(digest[:8], 16)
    
    def add_node(self, node: str) -> None:
        if node in self.nodes:
            return
        self.nodes.add(node)
        position = self._hash(node)
        self.ring[position] = node
        self.sorted_positions = sorted(self.ring.keys())
    
    def remove_node(self, node: str) -> None:
        if node not in self.nodes:
            return
        self.nodes.remove(node)
        position = self._hash(node)
        del self.ring[position]
        self.sorted_positions = sorted(self.ring.keys())
    
    def get_node(self, key: str) -> Optional[str]:
        if not self.ring:
            return None
        
        position = self._hash(key)
        # Find the first node position >= key position
        idx = bisect_right(self.sorted_positions, position)
        
        # Wrap around to the first node if we're past the last position
        if idx >= len(self.sorted_positions):
            idx = 0
        
        return self.ring[self.sorted_positions[idx]]

# Usage
ring = ConsistentHashRing()
for node in ["cache-1", "cache-2", "cache-3"]:
    ring.add_node(node)

print(f"user:1001 -> {ring.get_node('user:1001')}")
print(f"user:1002 -> {ring.get_node('user:1002')}")

When you add a new node, it takes a position on the ring and only claims keys that were previously assigned to its clockwise neighbor. When you remove a node, only its keys move—to its clockwise neighbor. The rest of the ring remains undisturbed.

Virtual Nodes for Better Distribution

The basic implementation has a critical flaw: with only a few physical nodes, the distribution is often wildly uneven. One node might own 60% of the ring while another owns 10%. Random hash positions don’t guarantee uniform spacing.

Virtual nodes solve this by giving each physical node multiple positions on the ring. Instead of “cache-1” appearing once, it might appear 150 times as “cache-1#0”, “cache-1#1”, and so on. More positions means better statistical distribution.

class ConsistentHashRingWithVnodes:
    def __init__(self, vnodes_per_node: int = 150):
        self.vnodes_per_node = vnodes_per_node
        self.ring: dict[int, str] = {}  # position -> physical node
        self.sorted_positions: list[int] = []
        self.nodes: set[str] = set()
    
    def _hash(self, key: str) -> int:
        digest = hashlib.md5(key.encode()).hexdigest()
        return int(digest[:8], 16)
    
    def add_node(self, node: str) -> None:
        if node in self.nodes:
            return
        self.nodes.add(node)
        
        for i in range(self.vnodes_per_node):
            vnode_key = f"{node}#vnode{i}"
            position = self._hash(vnode_key)
            self.ring[position] = node
        
        self.sorted_positions = sorted(self.ring.keys())
    
    def remove_node(self, node: str) -> None:
        if node not in self.nodes:
            return
        self.nodes.remove(node)
        
        for i in range(self.vnodes_per_node):
            vnode_key = f"{node}#vnode{i}"
            position = self._hash(vnode_key)
            if position in self.ring:
                del self.ring[position]
        
        self.sorted_positions = sorted(self.ring.keys())
    
    def get_node(self, key: str) -> Optional[str]:
        if not self.ring:
            return None
        
        position = self._hash(key)
        idx = bisect_right(self.sorted_positions, position)
        if idx >= len(self.sorted_positions):
            idx = 0
        
        return self.ring[self.sorted_positions[idx]]

The trade-off is memory: with 10 physical nodes and 150 vnodes each, you’re storing 1,500 ring positions. For most applications, this is negligible, but it’s worth considering at scale.

Measuring Redistribution: The Math

Let’s quantify the improvement. With consistent hashing, adding a node to a cluster of N nodes should move approximately 1/(N+1) of the keys—only those that fall between the new node’s position and its predecessor.

import random

def measure_redistribution():
    # Compare modulo vs consistent hashing
    num_keys = 100_000
    keys = [f"key:{i}" for i in range(num_keys)]
    
    # Modulo hashing: 10 -> 11 servers
    modulo_moved = 0
    for key in keys:
        old_server = hash(key) % 10
        new_server = hash(key) % 11
        if old_server != new_server:
            modulo_moved += 1
    
    # Consistent hashing: 10 -> 11 servers
    ring = ConsistentHashRingWithVnodes(vnodes_per_node=150)
    for i in range(10):
        ring.add_node(f"server-{i}")
    
    old_assignments = {key: ring.get_node(key) for key in keys}
    
    ring.add_node("server-10")
    
    consistent_moved = 0
    for key in keys:
        if ring.get_node(key) != old_assignments[key]:
            consistent_moved += 1
    
    print(f"Keys: {num_keys}")
    print(f"Modulo hashing (10->11 servers): {modulo_moved} moved ({100*modulo_moved/num_keys:.1f}%)")
    print(f"Consistent hashing (10->11 servers): {consistent_moved} moved ({100*consistent_moved/num_keys:.1f}%)")
    print(f"Theoretical optimal: {num_keys/11:.0f} ({100/11:.1f}%)")

measure_redistribution()

You’ll see modulo hashing moving around 90% of keys while consistent hashing moves close to the theoretical minimum of 9%. That’s a 10x reduction in data movement.

Real-World Implementations

Consistent hashing powers some of the most demanding distributed systems:

Amazon DynamoDB uses consistent hashing with virtual nodes for partition assignment. Their implementation includes preference lists—each key maps to multiple nodes for replication, walking clockwise to find N distinct physical nodes.

Apache Cassandra implements a similar approach with configurable vnode counts. Recent versions default to 16 vnodes per node (down from 256) after finding that fewer vnodes with token-aware rebalancing provides better operational characteristics.

Memcached clients like libketama implement consistent hashing client-side, allowing cache servers to be added or removed without coordinated deployment. The algorithm runs identically on every client, ensuring consistent key routing.

Load balancers like HAProxy and Nginx use consistent hashing for session affinity. The same client IP or session ID always routes to the same backend, enabling stateful applications without shared session stores.

Trade-offs and Considerations

Consistent hashing isn’t universally superior. Consider these factors:

Memory overhead grows with vnode count. At 200 vnodes across 1,000 nodes, you’re storing 200,000 ring positions. The sorted position list and binary search remain efficient, but memory-constrained environments may need to tune down.

Hash function selection matters. MD5 is fine for distribution purposes (cryptographic weakness is irrelevant here), but you need consistent behavior across all clients. MurmurHash3 and xxHash are faster alternatives.

Weighted nodes require attention. If one server has twice the capacity, give it twice the vnodes. But changing weights means redistributing keys, partially defeating the purpose.

Replication adds complexity. Finding N replicas means walking the ring and skipping virtual nodes that map to already-selected physical nodes. Get this wrong and you’ll have replicas on the same machine.

When to skip it: If your server count rarely changes, or if key redistribution is cheap (cache warm-up takes seconds), modulo hashing’s simplicity wins. Consistent hashing shines when redistribution is expensive—large data migrations, cold cache penalties, or systems that scale frequently.

Practical Implementation Tips

Start with 100-200 virtual nodes per physical node. Fewer vnodes mean worse distribution; more means diminishing returns and higher memory usage. Measure your actual distribution before tuning.

def analyze_distribution(ring: ConsistentHashRingWithVnodes, num_samples: int = 100_000):
    """Analyze how evenly keys distribute across nodes."""
    distribution: dict[str, int] = {node: 0 for node in ring.nodes}
    
    for i in range(num_samples):
        key = f"sample:{i}:{random.random()}"
        node = ring.get_node(key)
        if node:
            distribution[node] += 1
    
    expected = num_samples / len(ring.nodes)
    
    print(f"Expected keys per node: {expected:.0f}")
    print(f"Actual distribution:")
    
    max_deviation = 0
    for node, count in sorted(distribution.items()):
        deviation = abs(count - expected) / expected * 100
        max_deviation = max(max_deviation, deviation)
        print(f"  {node}: {count} ({deviation:+.1f}% from expected)")
    
    print(f"\nMax deviation: {max_deviation:.1f}%")
    return max_deviation

# Test with different vnode counts
for vnodes in [10, 50, 150, 300]:
    print(f"\n{'='*50}")
    print(f"Testing with {vnodes} vnodes per node")
    ring = ConsistentHashRingWithVnodes(vnodes_per_node=vnodes)
    for i in range(5):
        ring.add_node(f"server-{i}")
    analyze_distribution(ring)

Integrate with health checks by removing failed nodes from the ring automatically. But add hysteresis—a node flapping between healthy and unhealthy will cause repeated key migrations. Wait for stable state before modifying the ring.

Test redistribution before deploying. Simulate adding and removing nodes, measure actual key movement, and verify it matches theoretical expectations. Bugs in consistent hashing implementations often manifest as excessive redistribution—exactly what you’re trying to avoid.