How to Implement Consistent Hashing in Python

import hashlib
from bisect import bisect_right


class ConsistentHashRing:
    def __init__(self, nodes, replicas=3):
        self.replicas = replicas
        self.ring = {}
        self.sorted_keys = []
        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):
            vnode_key = self._hash(f"{node}:{i}")
            self.ring[vnode_key] = node
            self.sorted_keys.append(vnode_key)
        self.sorted_keys.sort()

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

    def get_node(self, key):
        if not self.sorted_keys:
            return None
        h = self._hash(key)
        idx = bisect_right(self.sorted_keys, h)
        if idx == len(self.sorted_keys):
            idx = 0
        return self.ring[self.sorted_keys[idx]]


if __name__ == "__main__":
    nodes = ["node-a", "node-b", "node-c"]
    ring = ConsistentHashRing(nodes, replicas=3)

    keys = [f"user-{i}" for i in range(10)]
    mapping = {k: ring.get_node(k) for k in keys}

    print("Initial mapping:")
    for k, v in mapping.items():
        print(f"  {k} -> {v}")

    ring.remove_node("node-b")
    print("\nAfter removing node-b:")
    for k in keys:
        new_node = ring.get_node(k)
        moved = " (moved)" if new_node != mapping[k] else ""
        print(f"  {k} -> {new_node}{moved}")