Consistent Hashing (일관된 해싱)

Consistent Hashing (일관된 해싱)

노드 추가/제거 시 최소한의 키만 재배치되도록 해시 값을 원형 공간(해시 링)에 매핑하는 분산 해싱 기법으로, 분산 캐시와 데이터베이스에서 핵심적으로 사용

목적: 노드 변경 시 최소 재배치, 부하 분산, 확장성, 분산 시스템

특징: 해시 링, 가상 노드(Virtual Node), 시계 방향 검색, 최소 재배치

해시 링(Hash Ring): 0~2^32-1(또는 2^64-1) 범위를 원형으로 표현

동작

• •노드 배치: 각 노드를 해시하여 링에 배치
• •키 배치: 키를 해시하여 시계 방향 첫 번째 노드에 할당
• •노드 추가: 새 노드와 이전 노드 사이의 키만 이동
• •노드 제거: 제거된 노드의 키만 다음 노드로 이동

가상 노드(Virtual Node)

• •각 물리 노드를 여러 가상 노드로 표현(예: 150개)
• •부하 균등화, 이질적 노드 처리, 핫스팟 방지

복제(Replication): 시계 방향 N개 노드에 복제, 가용성 향상

장점: 최소 재배치(1/N), 확장성, 부하 분산, 유연성

단점: 가상 노드 관리 복잡, 해시 함수 의존, 링 메타데이터

적용사례: Amazon Dynamo, Cassandra, Memcached, Redis Cluster, CDN

비교: Consistent Hashing(최소재배치) vs Modular Hashing(전체재배치) vs Rendezvous Hashing(대안)

연관: 분산 시스템, 해시 링, 가상 노드, Dynamo, 샤딩