Consistent Hashing

Traditional: hash(key) % n

Server assignment: hash("user123") % 4 = 2 → Server 2

When server added (n=5):
hash("user123") % 5 = 3 → Server 3  ← Key moved!

Result: Most keys remapped, cache invalidation storm

1. Hash server IDs to positions on ring
2. Hash keys to positions on ring
3. Walk clockwise to find first server

Example:
- Key K1 at position 45° → Assigned to S2 (at 90°)
- Key K2 at position 200° → Assigned to S4 (at 270°)

import hashlib
from bisect import bisect_right

class ConsistentHash:
    def __init__(self, nodes=None, replicas=100):
        self.replicas = replicas  # Virtual nodes per server
        self.ring = {}            # hash -> node mapping
        self.sorted_keys = []     # Sorted hash positions

        if nodes:
            for node in nodes:
                self.add_node(node)

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

    def add_node(self, node):
        for i in range(self.replicas):
            virtual_key = f"{node}:{i}"
            hash_val = self._hash(virtual_key)
            self.ring[hash_val] = node
            self.sorted_keys.append(hash_val)
        self.sorted_keys.sort()

    def remove_node(self, node):
        for i in range(self.replicas):
            virtual_key = f"{node}:{i}"
            hash_val = self._hash(virtual_key)
            del self.ring[hash_val]
            self.sorted_keys.remove(hash_val)

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

        hash_val = self._hash(key)
        # Find first node clockwise
        idx = bisect_right(self.sorted_keys, hash_val)
        if idx == len(self.sorted_keys):
            idx = 0  # Wrap around

        return self.ring[self.sorted_keys[idx]]