Consistent Hashing (일관성 해싱) 정리

0. 분산 캐시 환경에서의 노드 변경

• 분산 캐시는 여러 서버(노드)에 데이터를 나누어 저장하여 성능과 가용성을 높이는 구조이다.
• 현실 환경에서는 다음 이유로 노드가 자주 추가되거나 삭제됨:
  1. 수평 확장(Scale-out): 트래픽 증가 → 서버 추가
  2. 장애 처리(Failover): 서버 다운 → 노드 제거
  3. 업그레이드 / 유지보수: 서버 교체 필요
• 이때 기존 Mod 기반 샤딩을 쓰면, 서버 수 N이 바뀔 때 거의 모든 키가 재배치되어 데이터 이동량이 많음 → 성능 저하

따라서 분산 캐시에서는 데이터 이동량 최소화가 핵심 요구사항

1. 해시 링(Hash Ring) 개념

• Consistent Hashing은 전체 해시 공간을 원형 링(Circular Hash Space)으로 생각함
• 예: 32비트 해시 → 0 ~ 2³²−1
• 링 구조 → 마지막 점 다음이 첫 점과 연결된 원으로 취급

2. 서버(Node)와 데이터(Key) 배치

• 서버와 데이터 키 모두 해시 함수로 변환 → 링 상의 한 점에 배치
• 시계 방향 탐색 → 가장 가까운 서버가 키를 담당

예시

서버	해시 위치
A	100
B	300
C	700

키	해시 위치	담당 서버
k1	50	A
k2	350	C
k3	720	A

3. 기존 Mod 기반 샤딩 문제

• 기존 방식: key % N
• N(서버 수)이 바뀌면 거의 모든 키 재배치 필요 → 데이터 이동량 많음
• 분산 캐시에서 노드 추가/삭제가 잦으면 매우 비효율적

4. Consistent Hashing의 장점

• 새로운 서버 추가/제거 시 인접 범위의 키만 이동
• 전체 데이터 이동량 약 1/N 수준 → 안정적

예시: 키 이동

원래 상태:

Ring (0 ~ 1024)
[0]---A(100)---B(300)---C(700)---[1024]---(0)

Keys:
k1(50)   -> A
k2(350)  -> C
k3(720)  -> A

-------------------------

D(400) 노드 추가 후:

Ring (0 ~ 1024)
[0]---A(100)---B(300)---D(400)---C(700)---[1024]---(0)

Keys 배치 변경:
k1(50)   -> A   (변경 없음)
k2(350)  -> D   (이전에는 C 담당)
k3(720)  -> A   (변경 없음)

• D가 들어오면서 B~C 구간 일부만 D가 담당
• 나머지 키는 그대로 → 데이터 이동량 최소화

5. 왜 데이터 이동량이 1/N 수준인가?

• N = 기존 서버 수
• 해시 링에서 서버가 균등 분포한다고 가정
• 새로운 서버는 인접 서버 구간 일부만 담당 → 이동 키 약 1/N
• 기존 데이터 대부분은 이동하지 않음 → 안정적

6. 데이터 배치 방식 요약

1. 모든 서버를 해시 → 링 상 위치 배치
2. 각 데이터 키를 해시 → 링 상 위치 배치
3. 데이터 키 위치 이후(시계 방향) 가장 가까운 서버가 담당

7. 추가 개선: 가상 노드(Virtual Node)

• 실제 서버 하나에 여러 가상 노드를 링 위에 배치
• 장점:
  1. 서버 간 데이터 불균형 해소
  2. 서버 추가/제거 시 영향 최소화
• 실무 분산 캐시(예: Redis Cluster)에서 자주 사용됨