Consistent Hashing

노드 추가/제거 시 재분배되는 키 수를 최소화하는 분산 해싱 기법. 기존 모듈러 해싱(key % N)은 N 변경 시 대부분의 키 재분배가 필요하다.

링 구조

0 ─────────────────── 2³²-1
       ↑ 노드 A, B, C가 링 위에 배치
       키는 시계 방향으로 가장 가까운 노드에 배정

노드 추가: 새 노드가 담당하는 구간의 키만 이동. 평균 K/N개 (K=전체 키, N=노드 수).

노드 제거: 해당 노드의 키만 다음 노드로 이전.

Virtual Nodes (vnodes)

단일 노드를 링 위 여러 지점에 배치 → 부하 균등 분배 + 핫스팟 방지:

노드A → [A1, A2, A3] 각기 다른 링 위치

실제 구현: Cassandra, Amazon DynamoDB, Redis Cluster.

모듈러 해싱과 비교

연결 노트

• ZK-cap-theorem — AP 시스템에서 노드 분할 시 영향 범위 최소화
• ZK-hash-table — 기반 해싱 원리 공유
• ZK-microservices-principles-decomposition — 샤딩 전략으로 서비스 데이터 분산
• ZK-big-o-complexity — 노드 조회 O(log N), 재분배 O(K/N)