Consistent Hashing

The Rehashing Problem

Imagine you have 4 cache servers. You map keys using hash(key) % 4.

• key1 -> Server 1
• key2 -> Server 2

What if Server 1 dies? Now you have 3 servers. The formula becomes hash(key) % 3.

• key1 moves to Server X?
• key2 moves to Server Y?

With uniformly distributed hashes and unchanged index labels, changing modulo 4 to modulo 3 remaps about 75% of keys. Requests for remapped keys can miss until the new owners fill their caches. This can sharply increase database load; the effect depends on access skew, capacity and warm-up controls.

The Solution: The Ring

Instead of mapping to a server index (0, 1, 2), we map both keys and servers to a position on a Circle (0° to 360°), also known as the hash ring.

How it works

1. Map Servers: Hash the IP of Server A -> 45°. Server B -> 200°. Server C -> 310°.
2. Map Keys: Hash UserID -> 100°.
3. Assign: Walk clockwise from UserID (100°) until you hit a Server (Server B at 200°). That server owns the key.

Adding/Removing Nodes

• If we add Server D (150°):

  • Only keys between Server A (45°) and Server D (150°) move to D.
  • Keys after 150° stay on Server B.
  • Minimal Movement: Only $K/(N+1)$ keys move on average when adding one equal-capacity node to N nodes, assuming a sufficiently balanced ring.

• If Server B dies (200°):

  • Only keys that were on Server B (between 150° and 200°) move to the next server clockwise (Server C at 310°).
  • All other servers are unaffected.

Virtual Nodes (VNodes)

The Hotspot Problem

With only a few physical nodes on the ring, the distribution is often uneven. If Server A handles 10° to 200° (190° range), and Server B handles 200° to 10° (170° range), the load is skewed.

The Solution: Multiple Points Per Server

Don't put Server A on the ring once. Put it 100-200 times at different positions:

• Server A_1 → 23°, Server A_2 → 87°, Server A_3 → 156° ... Server A_100 → 342°

This improves the expected distribution of keys even with few physical servers.

VNode Advantages

1. Load Balancing: More virtual nodes reduce partition-size variance; they cannot split one extremely hot key.
2. Heterogeneous Hardware: A powerful server can have 300 virtual nodes while a smaller one has 100, proportional to their capacity.
3. Faster Recovery: When a node fails, its load is spread across many other nodes instead of just one successor.

import hashlib
from bisect import bisect_left

class ConsistentHash:
    def __init__(self, num_vnodes=150):
        if not isinstance(num_vnodes, int) or num_vnodes < 1:
            raise ValueError("num_vnodes must be a positive integer")
        self.num_vnodes = num_vnodes
        self.servers = set()
        self.ring = {}  # position -> server_name
        self.sorted_keys = []

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, server: str):
        """Add a server with N virtual nodes to the ring."""
        if server in self.servers:
            return
        self.servers.add(server)
        for i in range(self.num_vnodes):
            vnode_key = f"{server}:vnode{i}"
            position = self._hash(vnode_key)
            self.ring[position] = server
            self.sorted_keys.append(position)
        self.sorted_keys.sort()

    def remove_node(self, server: str):
        """Remove server and all its virtual nodes."""
        if server not in self.servers:
            return
        self.servers.remove(server)
        for i in range(self.num_vnodes):
            vnode_key = f"{server}:vnode{i}"
            position = self._hash(vnode_key)
            del self.ring[position]
            self.sorted_keys.remove(position)

    def get_node(self, key: str) -> str | None:
        """Walk clockwise to find the responsible server."""
        if not self.ring:
            return None
        h = self._hash(key)
        # Binary search for the first position >= h
        index = bisect_left(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[index]]

# Usage
ch = ConsistentHash(num_vnodes=150)
ch.add_node("Server-A")
ch.add_node("Server-B")
ch.add_node("Server-C")

print(ch.get_node("user:1001"))  # Deterministic owner for this ring
print(ch.get_node("user:2345"))  # Deterministic owner for this ring

Scope and failure decisions

The original Dynamo paper describes consistent hashing and virtual nodes. Do not infer the exact internal layout of the DynamoDB managed service from this historical system. Cassandra’s architecture documentation describes its own partitioning model.

The sample above demonstrates placement only. It is single-threaded, assumes no hash collisions and does not transfer data, assign replicas or coordinate membership changes. A real migration needs ownership versions, a transfer plan, checksums and a strategy for writes arriving during transfer.

For a hypothetical cache with four equal nodes and one million uniformly accessed keys, adding a fifth moves about 200,000 keys in expectation. Those moved keys can still create a large burst of cache misses. Add traffic gradually and compare cold-cache origin load in the capacity lab. Virtual nodes spread ranges; they do not make a viral single key cheap.

Comparison

Interview Tips 💡

1. Start with the problem: "Modulo hashing breaks when servers change because many keys get remapped."
2. Explain the ring: "Both servers and keys are hashed onto a circle. Walk clockwise to find the owner."
3. Always mention VNodes: "Virtual nodes reduce expected range-size imbalance and enable weighted placement."
4. Quantify the benefit: "Adding 1 node to N nodes moves about 1/(N+1) of keys in expectation."
5. Name real systems: Cassandra and the original Dynamo paper, explaining their documented scope.

Related Concepts

• Database Sharding — Compare placement strategies with range and directory sharding
• Load Balancing — Balancing requests across servers
• CAP Theorem — Trade-offs in distributed data stores
• Unique ID Generation — Hash-based approaches for distributed IDs