Chapter 30: Consistent Hashing & Data Placement

Introduction

Consistent hashing is the foundational technique for horizontal data partitioning in distributed systems. It solves a fundamental problem: how to distribute data across N servers such that adding or removing servers doesn't force a complete reshuffle.

This chapter covers:

• Why naive hashing (hash(key) % N) fails catastrophically when N changes
• Consistent hashing's hash ring concept and virtual nodes
• Modern variants: bounded-load, jump hash, rendezvous, Maglev
• Real implementations in DynamoDB, Cassandra, Memcached, Nginx
• Performance trade-offs and implementation details

1. The Problem: Naive Hashing

1.1 Naive Approach: Modulo Hashing

The obvious approach to distribute keys across N servers:

This works perfectly until N changes. When you add or remove a server, nearly every key remaps to a different server.

1.2 Catastrophic Redistribution

Result: Adding 1 server (N=3 → N=4) remapped 3 out of 5 keys (60%). In reality, with millions of keys, ~75% of all data must move.

1.3 Why This Matters

• Cache systems: All cache entries invalidate → thundering herd on backend
• Data stores: Massive data movement, network saturation, hours of downtime
• Elastic scaling: Can't add capacity without destroying performance

2. Consistent Hashing Concept

2.1 The Hash Ring

Consistent hashing (Karger et al., 1997) maps both keys and nodes to the same hash space, forming a conceptual ring.

Key idea: Each key is assigned to the first node encountered when traveling clockwise from the key's position on the ring.

2.2 Key Mapping Algorithm

function get_node(key, nodes):
    key_hash = hash(key)

    # Find first node clockwise from key_hash
    for node in sorted(nodes, key=lambda n: hash(n)):
        if hash(node) >= key_hash:
            return node

    # Wrap around: return first node
    return sorted(nodes, key=lambda n: hash(n))[0]

2.3 Why This Works

3. Virtual Nodes

3.1 Why Virtual Nodes

Basic consistent hashing has a fatal flaw: with few physical nodes, the ring positions are uneven, causing severe load imbalance.

Solution: Each physical node is represented by V virtual nodes at different positions on the ring.

3.2 Tuning V

Cassandra default: V=256 (historically), V=16 in modern versions

DynamoDB: Uses virtual nodes internally, not exposed to users

4. Adding/Removing Nodes

4.1 Redistribution Mechanics

When a new node joins, it claims responsibility for a fraction of the key space. Only keys in its clockwise arc must move.

4.2 Mathematical Proof

4.3 Minimal Disruption Guarantee

Consistent hashing provides a monotonicity property:

• Adding a node only causes keys to move to the new node
• Removing a node only causes its keys to move to its successor
• Keys never shuffle between existing nodes

5. Bounded-Load Consistent Hashing

Standard consistent hashing has no protection against hot spots—if keys skew to one arc, a single node becomes overloaded.

5.1 The Problem

5.2 Bounded-Load Solution (Mirrokni et al., Google 2018)

Set a load cap for each node:

Algorithm:

1. Start with standard consistent hash lookup
2. If target node is at max capacity, skip to next clockwise node
3. Repeat until finding a node under capacity
4. Track load in a separate data structure (not the ring)

function get_node_bounded(key, nodes, load_map, epsilon):
    key_hash = hash(key)
    avg_load = total_keys / len(nodes)
    max_load = (1 + epsilon) * avg_load

    candidates = sorted(nodes, key=lambda n: hash(n) if hash(n) >= key_hash
                                              else hash(n) + 2^32)

    for node in candidates:
        if load_map[node] < max_load:
            return node

    # Fallback: return least loaded
    return min(nodes, key=lambda n: load_map[n])

5.3 Performance Impact

6. Jump Consistent Hash

Jump Consistent Hash (Google, 2014) is a radically simpler algorithm that eliminates the hash ring entirely.

6.1 Algorithm Deep Dive

// C++ reference implementation (Lamping & Veach, Google 2014)
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}

How it works:

1. Starts with bucket -1, then "jumps" forward based on pseudorandom values derived from the key
2. Each iteration computes: "if we had j+1 buckets, would this key still be in bucket b?"
3. Loop terminates when j reaches num_buckets
4. Returns the last valid bucket index

6.2 Properties

6.3 Limitations

6.4 Use Cases

• Good: Client-side sharding where you control bucket count (e.g., 16 shards)
• Good: Static partitioning (e.g., partition log files across 100 buckets)
• Bad: Distributed caches where servers come and go
• Bad: Systems needing heterogeneous node weights

7. Rendezvous Hashing (Highest Random Weight)

Rendezvous hashing (Thaler & Ravishankar, 1998) takes a completely different approach: for each key, compute a score for every node and pick the highest.

7.1 Algorithm

function rendezvous_hash(key, nodes):
    max_score = -1
    selected_node = None

    for node in nodes:
        score = hash(key + node.id)  # Combine key and node
        if score > max_score:
            max_score = score
            selected_node = node

    return selected_node

Key insight: Since the score depends on both key and node, adding/removing a node only affects keys where that node had the highest score.

7.2 Comparison

7.3 Optimization: Top-K Candidates

For replication, rendezvous naturally extends to "pick top K nodes by score":

function rendezvous_top_k(key, nodes, k):
    scores = [(node, hash(key + node.id)) for node in nodes]
    scores.sort(key=lambda x: x[1], reverse=True)
    return [node for node, score in scores[:k]]

7.4 Use Cases

• Small N: When you have 10-100 nodes, O(N) lookup is acceptable
• Weighted nodes: Easy to give powerful nodes more replicas
• Simple implementation: No complex ring data structure

8. Maglev Hashing

Maglev (Google, 2016) is designed for high-performance load balancers. It pre-computes a lookup table for O(1) lookups with minimal disruption.

8.1 Concept

Instead of a hash ring, Maglev builds a fixed-size table where each entry points to a backend. Keys hash to table indices.

8.2 Table Population Algorithm

function populate_maglev_table(backends, M):
    table = [None] * M

    # Generate permutation for each backend
    permutations = {}
    for backend in backends:
        offset = hash1(backend) % M
        skip = hash2(backend) % (M - 1) + 1
        perm = [(offset + i * skip) % M for i in range(M)]
        permutations[backend] = perm

    # Fill table round-robin
    indices = {b: 0 for b in backends}
    filled = 0

    while filled < M:
        for backend in backends:
            idx = indices[backend]
            while idx < M:
                pos = permutations[backend][idx]
                indices[backend] += 1
                idx += 1

                if table[pos] is None:
                    table[pos] = backend
                    filled += 1
                    break

    return table

Properties:

• Each backend gets ~M/N entries in the table
• Backends are evenly distributed (no virtual nodes needed)
• When a backend is added/removed, only ~1/N entries change

8.3 Performance

8.4 Connection Disruption

9. Real Systems

9.1 DynamoDB

Architecture:

• Partition key → MD5 hash → 128-bit value → maps to partition
• Consistent hashing with virtual nodes (internal, not exposed)
• Each partition ~10GB, splits automatically when exceeded

// DynamoDB partition assignment (conceptual)
partition_key = "user:12345"
hash_value = MD5(partition_key)  // 128-bit
partition = ring.find_node(hash_value)

// Replication: N=3 replicas across AZs
replicas = [partition, partition.successor, partition.successor.successor]

9.2 Cassandra

Architecture:

• Token ring: each node claims a range of tokens (virtual nodes)
• Default: V=256 (older) or V=16 (3.0+, tunable)
• Partition key → Murmur3 hash → token → node
• Replication factor (RF) determines how many nodes store each key

// Cassandra token ring (simplified)
CREATE KEYSPACE my_keyspace WITH replication = {
  'class': 'NetworkTopologyStrategy',
  'datacenter1': 3
};

// Key lookup
key = "user:12345"
token = murmur3(key) % 2^63  // Signed 64-bit range
coordinator = token_ring.find_node(token)
replicas = coordinator.successors(RF=3)

9.3 Memcached

Client-side consistent hashing: Memcached server has no knowledge of the ring—clients implement it.

// libmemcached consistent hashing (C)
memcached_st *memc = memcached_create(NULL);
memcached_behavior_set(memc, MEMCACHED_BEHAVIOR_DISTRIBUTION,
                       MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA);

// Ketama algorithm (default): MD5 hash with 160 virtual nodes per server
// Client computes: hash(key) → binary search on ring → server

Ketama algorithm:

• Each server gets 160 virtual nodes (40 hashes × 4 positions each)
• MD5 hash: hash(server_address + ":" + i) for i in [0, 40)
• Take 4 × 32-bit slices from each 128-bit MD5 output

9.4 Nginx

Upstream consistent hash directive:

upstream backend {
    hash $request_uri consistent;
    server backend1.example.com;
    server backend2.example.com;
    server backend3.example.com;
}

# Hash the request URI, use consistent hashing to pick server
# Minimizes cache misses when backend servers change

Virtual nodes: Nginx uses 160 virtual nodes per server by default (same as Ketama).

10. Algorithm Comparison

Decision Matrix

11. Implementation Considerations

11.1 Hash Function Choice

Recommendation: Use xxHash for new implementations (fast, good distribution). Use MurmurHash3 for compatibility with Cassandra/Redis ecosystems.

11.2 Replication with Consistent Hashing

Store data on the primary node and its N-1 clockwise successors:

function get_replica_nodes(key, ring, replication_factor):
    primary = ring.find_node(hash(key))
    replicas = [primary]

    current = primary
    while len(replicas) < replication_factor:
        current = ring.successor(current)
        # Skip if same physical node (virtual nodes)
        if current.physical_id not in [r.physical_id for r in replicas]:
            replicas.append(current)

    return replicas

Rack/Zone Awareness:

• Cassandra: NetworkTopologyStrategy ensures replicas in different racks/DCs
• DynamoDB: Replicas always in different Availability Zones

11.3 Preference Lists

DynamoDB-style preference list: pre-compute N replicas for fast quorum operations.

// Preference list: ordered list of nodes for a key
class PreferenceList {
    primary: Node
    replicas: Node[]  // Length = N

    function quorum_write(key, value, W):
        responses = []
        for node in replicas:
            responses.append(node.write_async(key, value))

        # Wait for W successes
        return wait_for_n(responses, W)

    function quorum_read(key, R):
        responses = []
        for node in replicas:
            responses.append(node.read_async(key))

        # Wait for R responses, resolve conflicts
        results = wait_for_n(responses, R)
        return resolve_conflicts(results)
}

11.4 Handling Node Failures

11.5 Code Example: Consistent Hash Ring

class ConsistentHashRing:
    def __init__(self, nodes, virtual_nodes=100):
        self.virtual_nodes = virtual_nodes
        self.ring = {}  # position -> node_id
        self.sorted_positions = []

        for node in nodes:
            self.add_node(node)

    def add_node(self, node):
        for i in range(self.virtual_nodes):
            vnode_key = f"{node}:{i}"
            position = xxhash.xxh64(vnode_key).intdigest()
            self.ring[position] = node

        self.sorted_positions = sorted(self.ring.keys())

    def remove_node(self, node):
        for i in range(self.virtual_nodes):
            vnode_key = f"{node}:{i}"
            position = xxhash.xxh64(vnode_key).intdigest()
            del self.ring[position]

        self.sorted_positions = sorted(self.ring.keys())

    def get_node(self, key):
        if not self.ring:
            return None

        position = xxhash.xxh64(key).intdigest()

        # Binary search for first node clockwise
        idx = bisect.bisect_right(self.sorted_positions, position)
        if idx == len(self.sorted_positions):
            idx = 0  # Wrap around

        return self.ring[self.sorted_positions[idx]]

    def get_nodes(self, key, n):
        """Get n distinct physical nodes for replication"""
        if not self.ring:
            return []

        position = xxhash.xxh64(key).intdigest()
        idx = bisect.bisect_right(self.sorted_positions, position)

        nodes = []
        seen = set()
        count = 0

        while len(nodes) < n and count < len(self.sorted_positions):
            if idx >= len(self.sorted_positions):
                idx = 0

            node = self.ring[self.sorted_positions[idx]]
            if node not in seen:
                nodes.append(node)
                seen.add(node)

            idx += 1
            count += 1

        return nodes

12. Interview Signals

Strong Signals

• Explains why naive hashing fails: "Modulo creates a global dependency on N—changing N remaps almost all keys"
• Quantifies data movement: "Consistent hashing moves only K/N keys vs K×(N-1)/N for naive"
• Mentions virtual nodes unprompted: "With few nodes, you need virtual nodes to balance the ring"
• Knows alternative algorithms: "Jump hash is O(1) memory but can't remove arbitrary nodes"
• Discusses real systems: "Cassandra uses Murmur3 with 16 vnodes by default, down from 256"
• Addresses hot keys: "Standard consistent hashing doesn't prevent hot spots—you need bounded-load or sharding"

Weak Signals

• Only memorizes "hash ring" without understanding redistribution math
• Can't explain why virtual nodes are needed
• Doesn't know any real system implementations
• Confuses consistent hashing with quorum consensus
• Can't compare consistent hash vs jump hash vs rendezvous

Common Mistakes

Sample Interview Questions