Consistent Hashing일관 해싱

# 일반 해싱: node_count 변경 시 대부분의 키가 재배치됨
def get_node(key, node_count):
    return hash(key) % node_count

# 3개 노드: hash("user123") % 3 = 1 → Node 1
# 4개 노드: hash("user123") % 4 = 2 → Node 2 (이동!)
# 노드 1개 추가 시 약 75%의 키가 재배치됨

해시 링 (0 ~ 2^32):

           0
        ┌──────┐
   N3 ──┤      ├── N1
        │  링  │
   N2 ──┤      ├── (빈 구간)
        └──────┘

1. 노드(N1, N2, N3)를 해시 링에 배치
2. 각 키는 시계 방향으로 가장 가까운 노드에 할당

노드 추가 (N4):
- N4 이전 구간의 키만 N4로 이동
- 다른 노드는 영향 없음
- 평균 K/N 개의 키만 재배치 (K=전체 키, N=노드 수)

import hashlib
from sortedcontainers import SortedDict

class ConsistentHash:
    def __init__(self, replicas=150):
        self.replicas = replicas  # 가상 노드 수
        self.ring = SortedDict()
        self.nodes = set()

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

    def add_node(self, node: str):
        self.nodes.add(node)
        for i in range(self.replicas):
            virtual_key = self._hash(f"{node}:{i}")
            self.ring[virtual_key] = node

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

    def get_node(self, key: str) -> str:
        if not self.ring:
            return None
        h = self._hash(key)
        # 시계 방향으로 가장 가까운 노드
        idx = self.ring.bisect_left(h) % len(self.ring)
        return self.ring.values()[idx]

# 사용 예시
ch = ConsistentHash()
for node in ['redis-1', 'redis-2', 'redis-3']:
    ch.add_node(node)

print(ch.get_node('user:1001'))  # redis-2
print(ch.get_node('user:2002'))  # redis-1

가상 노드 없이:    N1 (33%), N2 (47%), N3 (20%) → 불균등
가상 노드 150개씩: N1 (33%), N2 (34%), N3 (33%) → 균등