コンシステントハッシュ法

consistent_hashing.py

import bisect
import hashlib


def h(key: str) -> int:
    return int.from_bytes(hashlib.md5(key.encode()).digest()[:8], "big")


class HashRing:
    def __init__(self, nodes=(), vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted hash positions on the ring
        self.owner = {}    # position -> physical node
        for node in nodes:
            self.add(node)

    def add(self, node):
        for i in range(self.vnodes):
            p = h(f"{node}#{i}")
            bisect.insort(self.points, p)
            self.owner[p] = node

    def remove(self, node):
        for i in range(self.vnodes):
            p = h(f"{node}#{i}")
            self.points.pop(bisect.bisect_left(self.points, p))
            del self.owner[p]

    def get(self, key):
        if not self.points:
            raise LookupError("ring is empty")
        i = bisect.bisect_left(self.points, h(key)) % len(self.points)
        return self.owner[self.points[i]]


ring = HashRing(["A", "B", "C"])
keys = [f"user:{n}" for n in range(10_000)]
before = {k: ring.get(k) for k in keys}
ring.add("D")
moved = sum(before[k] != ring.get(k) for k in keys)
print(f"moved {moved / len(keys):.1%} of keys")  # about 25%
ring.remove("D")
print(all(ring.get(k) == before[k] for k in keys))  # True

python consistent_hashing.py