Consistent Hashing

Metadata

1. Overview

What problem does it solve?

In a distributed system, you often need to distribute data (like cache keys or database rows) across multiple servers. The standard way to do this is using the modulo operator: server_index = hash(key) % N, where N is the number of servers.

This works perfectly until you need to add or remove a server. If N changes, almost every key hashes to a different server index. This causes a massive wave of cache misses (a "cache stampede") or requires migrating almost all data to new database shards.

Consistent Hashing is a technique that distributes data across servers in such a way that when a server is added or removed, only a small fraction of the data (specifically 1/N of the data) needs to be moved.

What breaks without it?

• Elastic Scalability: You cannot easily add or remove servers to handle traffic spikes.
• Fault Tolerance: If a node crashes, the N drops by 1, causing a massive reshuffling of all data, potentially crashing the entire system under the load.
• Data Locality: In distributed databases, rehashing everything means copying terabytes of data across the network just because one node was added.

2. Motivation

The Rehashing Problem

Imagine a simple distributed cache with 4 servers (N=4).

Keys: user:1 (hash=10), user:2 (hash=15), user:3 (hash=21).

Mapping:

• user:1 (10 % 4 = 2) -> Server 2
• user:2 (15 % 4 = 3) -> Server 3
• user:3 (21 % 4 = 1) -> Server 1

Now Server 3 crashes (N=3).

• user:1 (10 % 3 = 1) -> Server 1 (Moved!)
• user:2 (15 % 3 = 0) -> Server 0 (Moved!)
• user:3 (21 % 3 = 0) -> Server 0 (Moved!)

Every single key moved! To solve this, Karger et al. at MIT introduced Consistent Hashing in 1997. It was later popularized by Amazon's Dynamo paper and Memcached.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The Hash Ring

Instead of mapping a hash to a server array index, we map the hash space (e.g., 0 to $2^{32}-1$) onto a circle or Ring.

1. Hash the servers and place them on the ring.
2. Hash the keys and place them on the ring.
3. To find a key's server, walk clockwise from the key's position on the ring until you hit a server.

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff', 'tertiaryColor': '#f4f4f4'}}}%%
graph TD
    classDef ringNode fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef serverNode fill:#d4edda,stroke:#28a745,stroke-width:2px,color:#155724;
    classDef keyNode fill:#cce5ff,stroke:#007bff,stroke-width:2px,color:#004085;

    subgraph Hash Ring [0 to 359 degrees]
        direction LR
        S1((Server A<br/>Hash: 30)):::serverNode
        K1((Key 1<br/>Hash: 60)):::keyNode
        S2((Server B<br/>Hash: 120)):::serverNode
        K2((Key 2<br/>Hash: 150)):::keyNode
        K3((Key 3<br/>Hash: 200)):::keyNode
        S3((Server C<br/>Hash: 240)):::serverNode
        K4((Key 4<br/>Hash: 330)):::keyNode
        
        S1 -.-> K1
        K1 -.-> |Assigned to| S2
        S2 -.-> K2
        K2 -.-> K3
        K3 -.-> |Assigned to| S3
        S3 -.-> K4
        K4 -.-> |Assigned to| S1
    end

Adding a Node

If we add Server D at Hash 180, only keys between 120 and 180 (like Key 2) move to Server D. Key 3 stays on Server C. The rest of the ring is unaffected.

Virtual Nodes (VNodes)

Problem: Servers placed randomly on the ring can lead to uneven data distribution. One server might handle 50% of the ring, while another handles 5%. Solution: Instead of placing Server A on the ring once, place it K times (e.g., Server A_1, Server A_2, Server A_3). These are called Virtual Nodes. They balance the load and allow accounting for servers with different hardware capacities.

6. Internal Working

1. Hash Function Selection: Choose a hash function that uniformly distributes values (e.g., MD5, SHA-256, MurmurHash). Do not use cryptographic hashes if performance is a concern; MurmurHash is often preferred.
2. Ring Creation: The ring is typically represented as a sorted array of hashes.
3. Adding Servers: Hash ServerID + "#" + VirtualNodeIndex. Insert the resulting hash into the sorted array. Maintain a mapping from the hash to the actual Server IP/ID.
4. Locating a Key:
   • Hash the Key.
   • Perform a Binary Search (e.g., bisect_right) on the sorted array of server hashes to find the first server hash greater than the key's hash.
   • If the key's hash is greater than the largest server hash, wrap around to the first server in the array (index 0).
5. Removing Servers: Remove all virtual node hashes for that server from the sorted array.

7. Implementation

Why Python? Python provides the bisect module, which makes the binary search on the sorted ring trivial. This keeps the implementation focused entirely on the core algorithm without boilerplate search code.

"""
018 - Consistent Hashing
A complete implementation of a consistent hash ring with virtual nodes.
"""
import hashlib
import bisect
from collections import defaultdict


class ConsistentHashRing:
    def __init__(self, virtual_nodes=100):
        """
        :param virtual_nodes: The number of virtual nodes per physical server 
                              to ensure an even distribution.
        """
        self.virtual_nodes = virtual_nodes
        # Sorted list of hashes representing positions on the ring
        self.ring = []
        # Mapping from ring hash back to the physical server name
        self.hash_to_server = {}

    def _hash(self, key):
        """
        Use MD5 to hash the key. In production, MurmurHash3 is faster.
        Returns an integer representation of the hash.
        """
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

    def add_server(self, server_name):
        """Add a server to the ring using virtual nodes."""
        for i in range(self.virtual_nodes):
            # Create a unique name for the virtual node (e.g., "server1#0")
            vnode_key = f"{server_name}#{i}"
            h = self._hash(vnode_key)
            
            # Maintain the sorted ring
            bisect.insort(self.ring, h)
            self.hash_to_server[h] = server_name

    def remove_server(self, server_name):
        """Remove a server and all its virtual nodes from the ring."""
        for i in range(self.virtual_nodes):
            vnode_key = f"{server_name}#{i}"
            h = self._hash(vnode_key)
            
            self.ring.remove(h)
            del self.hash_to_server[h]

    def get_server(self, key):
        """
        Find the server responsible for a given key.
        Returns None if the ring is empty.
        """
        if not self.ring:
            return None

        h = self._hash(key)
        # Find the index of the first server hash greater than the key hash
        idx = bisect.bisect_right(self.ring, h)
        
        # If we went past the end of the ring, wrap around to the first server
        if idx == len(self.ring):
            idx = 0
            
        server_hash = self.ring[idx]
        return self.hash_to_server[server_hash]


# ── Test Harness ──

if __name__ == "__main__":
    ring = ConsistentHashRing(virtual_nodes=3) # Low vnode count for demo visibility

    print("1. Adding servers A, B, and C")
    ring.add_server("Server A")
    ring.add_server("Server B")
    ring.add_server("Server C")

    keys = ["user:123", "user:456", "session:xyz", "cart:999", "img:profile.jpg"]
    
    print("\n2. Initial Key Distribution:")
    distribution = defaultdict(list)
    for key in keys:
        server = ring.get_server(key)
        distribution[server].append(key)
        print(f"  {key:<16} -> {server}")

    print("\n3. Server B crashes! Removing Server B...")
    ring.remove_server("Server B")

    print("\n4. New Key Distribution:")
    new_distribution = defaultdict(list)
    for key in keys:
        server = ring.get_server(key)
        new_distribution[server].append(key)
        print(f"  {key:<16} -> {server}")
        
    print("\nNote how keys that were on A and C mostly stayed on A and C.")

Sample Output

1. Adding servers A, B, and C

2. Initial Key Distribution:
  user:123         -> Server A
  user:456         -> Server A
  session:xyz      -> Server C
  cart:999         -> Server B
  img:profile.jpg  -> Server C

3. Server B crashes! Removing Server B...

4. New Key Distribution:
  user:123         -> Server A
  user:456         -> Server A
  session:xyz      -> Server C
  cart:999         -> Server A   <-- Only this key moved!
  img:profile.jpg  -> Server C

Note how keys that were on A and C mostly stayed on A and C.

8. Complexity

Scalability Characteristics

• Memory overhead is tiny: 1000 servers \times 200 virtual nodes = 200,000 integers. This easily fits in CPU cache.
• Lookups take microseconds.
• Can handle millions of lookups per second per node.

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. Why don't we just use hash(key) % N to distribute data? Hint: What happens when N becomes N+1? How much data has to move?

2. How does Consistent Hashing solve the uneven distribution of data (the "hotspot" problem)? Hint: Discuss Virtual Nodes (VNodes).

3. In a Consistent Hashing setup with S servers, what fraction of keys need to be remapped when a server is added? Hint: Only the keys that fall between the new server and the previous server on the ring move. Statistically, it's 1/S.

4. How would you implement replication in a Consistent Hashing ring? Hint: When walking the ring clockwise, don't stop at the first server. Stop after finding K unique physical servers.

13. Used By (Downstream Blocks)

• 020 Database Sharding — Relies heavily on consistent hashing to distribute data across shards.
• 037 Gossip Protocol — Often used in tandem to distribute the state of the consistent hash ring to all nodes without a master server.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Implement Replication

Modify the get_server(key) function to become get_replicas(key, N=3). Instead of returning just one server, it should return a list of N unique physical servers by continuing to walk the ring clockwise. Make sure you don't return the same physical server twice if you hit its virtual nodes sequentially!

Exercise 2: Capacity-Weighted Virtual Nodes

Modify add_server to accept a weight parameter. A server with weight=2 should get twice as many virtual nodes on the ring as a server with weight=1. Test how this changes the distribution of keys.

Website Metadata