python
class ConsistentHashRing:
def __init__(self, replicas=100):
self.replicas = replicas
self.positions = []
self.owners = {}
def add_node(self, node: str):
for i in range(self.replicas):
key = f"node:{node}:replica:{i}"
position = hash_position(key)
if position in self.owners:
raise ValueError("Hash position collision")
self.owners[position] = node
bisect.insort(self.positions, position)
def remove_node(self, node: str):
remaining = [
p for p in self.positions
if self.owners[p] != node
]
self.positions = remaining
self.owners = {
p: owner
for p, owner in self.owners.items()
if owner != node
}
def get_node(self, key: str) -> str:
if not self.positions:
raise ValueError("Hash ring is empty")
position = hash_position(f"key:{key}")
index = bisect.bisect_left(
self.positions,
position
)
if index == len(self.positions):
index = 0
return self.owners[self.positions[index]]
python
ring = ConsistentHashRing(replicas=100)
ring.add_node("server-A")
ring.add_node("server-B")
ring.add_node("server-C")
keys = [f"user:{i}" for i in range(10000)]
before = {
key: ring.get_node(key)
for key in keys
}
ring.add_node("server-D")
after = {
key: ring.get_node(key)
for key in keys
}
moved = sum(
before[key] != after[key]
for key in keys
)
print("moved:", moved)
print("ratio:", moved / len(keys))