Hashing & Collision Resolution

Consistent Hashing is one of the foundational building blocks of distributed systems (used in Apache Cassandra, Amazon DynamoDB, Akamai CDN, and Envoy Proxy).

1. The Problem with Naive Modulo Hashing

If you have 4 servers and use hash(key) % 4, when server 4 crashes, you now compute hash(key) % 3. Because almost every number changes its remainder modulo 3, nearly 100% of cached keys instantly miss, hammering your backend database in a catastrophic thundering herd.

In Consistent Hashing, when a server is added or removed, only $1/N$ of keys need to be remapped on average. All other keys stay on their existing servers!

2. The Hash Ring & Why Virtual Nodes are Mandatory

Imagine a circular ring of numbers from $0$ to $2^{32} – 1$ (the output space of a 32-bit hash function like Murmur3 or MD5).

• Each physical server is hashed onto a point on this ring.
• To find where a key belongs, you hash the key, find its coordinate on the ring, and walk clockwise until you hit the first server!

The Hot Spot Problem: If you only place 3 physical servers on the ring, their hash positions might be clustered close together (e.g. at 10 degrees, 25 degrees, and 280 degrees). Server 3 will end up handling 70% of all traffic, causing a massive hot spot!

The Solution (Virtual Nodes): Instead of hashing Server A once, we hash it 100 or 200 times under different labels ("server-A#1", "server-A#2", …, "server-A#200"). By distributing hundreds of virtual replicas uniformly across the 360-degree ring, standard deviations drop to near zero, and load is balanced evenly across all physical hardware.

Production Python 3.12 Implementation with bisect

import bisect
import hashlib

class ConsistentHashRing:
    def __init__(self, replicas: int = 150):
        self.replicas = replicas  # Virtual nodes per physical server
        self.ring: list[int] = [] # Sorted list of virtual node hash keys
        self.node_map: dict[int, str] = {} # hash_key -> physical_node_id

    def _hash(self, key: str) -> int:
        """Returns 32-bit integer hash using MD5."""
        return int(hashlib.md5(key.encode('utf-8')).hexdigest()[:8], 16)

    def add_node(self, node: str) -> None:
        """Adds a physical node by creating virtual replicas across the ring."""
        for i in range(self.replicas):
            v_key = f"{node}#vn_{i}"
            h = self._hash(v_key)
            idx = bisect.bisect_left(self.ring, h)
            self.ring.insert(idx, h)
            self.node_map[h] = node

    def remove_node(self, node: str) -> None:
        """Removes all virtual replicas belonging to the physical node."""
        for i in range(self.replicas):
            v_key = f"{node}#vn_{i}"
            h = self._hash(v_key)
            idx = bisect.bisect_left(self.ring, h)
            if idx < len(self.ring) and self.ring[idx] == h:
                self.ring.pop(idx)
                del self.node_map[h]

    def get_node(self, key: str) -> str | None:
        """Finds the physical server responsible for the given key in O(log(V * N))."""
        if not self.ring:
            return None

        h = self._hash(key)
        # Binary search clockwise to the nearest virtual node
        idx = bisect.bisect_right(self.ring, h)
        
        # If we walked past the end of the ring, wrap around to index 0
        if idx == len(self.ring):
            idx = 0

        return self.node_map[self.ring[idx]]

Complexity Breakdown

• Key Lookup: O(log(R * N)) using binary search, where R is replicas (e.g. 150) and N is physical servers (e.g. 10). Searching an array of 1,500 numbers takes 11 comparisons (< 1 microsecond).
• Node Add/Remove: O(R * log(R * N)). Adding a server only migrates keys from its immediate clockwise neighbor!