Database Architecture and Partitioning Questions

import bisect
import hashlib

def h(s):
    return int(hashlib.md5(s.encode()).hexdigest(), 16)

class ConsistentHashRing:
    def __init__(self, replicas=100):
        self.replicas = replicas
        self.ring = []              # sorted list of hashes
        self.hash_to_node = {}      # map hash -> node_id

    def add_node(self, node_id):
        for i in range(self.replicas):
            hv = h(f"{node_id}:{i}")
            if hv in self.hash_to_node: 
                continue
            bisect.insort(self.ring, hv)
            self.hash_to_node[hv] = node_id

    def remove_node(self, node_id):
        to_remove = [hv for hv, n in self.hash_to_node.items() if n == node_id]
        for hv in to_remove:
            idx = bisect.bisect_left(self.ring, hv)
            if idx < len(self.ring) and self.ring[idx] == hv:
                self.ring.pop(idx)
            del self.hash_to_node[hv]

    def get_node(self, key):
        if not self.ring:
            return None
        hv = h(str(key))
        idx = bisect.bisect_right(self.ring, hv)
        if idx == len(self.ring):
            idx = 0
        return self.hash_to_node[self.ring[idx]]