Consistent Hashing for Distributed Caches

The article begins by highlighting the common pitfalls of naive modulo-based sharding for distributed caches. When the number of nodes changes (due to scaling up or down), a simple `hash(key) % N` approach leads to a massive key remapping, effectively invalidating the entire cache and putting immense pressure on the backend database. This demonstrates a critical challenge in distributed system design: maintaining data locality and availability during topology changes.

The Solution: Consistent Hashing

Consistent hashing addresses this problem by mapping both keys and cache nodes onto a circular hash ring. A key is assigned to the first node encountered when moving clockwise from the key's position on the ring. The key benefit is minimal data movement: when a node is added or removed, only the keys residing in the affected segment of the ring need to be remapped to a new node, leaving the majority of the cache untouched.

Enhancements: Virtual Nodes and Gossip Protocol

While consistent hashing solves the remapping problem, a basic implementation can suffer from uneven data distribution if physical nodes are not perfectly spread on the ring, leading to hotspots. Virtual nodes (vnodes) mitigate this by assigning multiple points on the hash ring to each physical node. This strategy improves load balancing and reduces the impact of a single node's failure or addition. Furthermore, a gossip protocol allows nodes to discover each other and maintain a consistent view of the cluster state without a central coordinator, enhancing fault tolerance and decentralization.

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, nodes=None, replicas=100):
        self.replicas = replicas
        self.ring = dict()  # hash -> node
        self._sorted_keys = []  # list of hashes in ascending order
        self.nodes = set(nodes or [])
        for node in self.nodes:
            self._add_node(node)

    def _hash(self, key):
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

    def _add_node(self, node):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            self.ring[h] = node
            bisect.insort(self._sorted_keys, h)

    def _remove_node(self, node):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            del self.ring[h]
            idx = bisect.bisect_left(self._sorted_keys, h)
            del self._sorted_keys[idx]

    def get_node(self, key):
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect_left(self._sorted_keys, h)
        if idx == len(self._sorted_keys):
            idx = 0  # wrap around the ring
        return self.ring[self._sorted_keys[idx]]