요약
- 분산 시스템에서 노드 추가/제거 시 최소한의 키만 재배치하는 해싱 알고리즘.
- 일반적인
hash(key) % N분배가 가진 rehash 문제를 해결 → 서버 스케일링 시 대규모 캐시 미스 방지. - 구체 자료구조 구현은 HashRing은 분산 시스템에서 데이터를 균등 분배하는 자료구조다 참고.
본문
동기: 분산 캐시의 rehash 문제
분산 캐시 환경에서 매핑의 일반적 요구사항:
- 리소스와 노드 사이의 매핑이 빠르고 쉬워야 함
- 노드들 사이의 부하가 비교적 균등해야 함
- 매핑은 노드의 빈번한 추가/제거에 유연해야 함
가장 단순한 분배 방식은 serverIndex = hash(key) % N (N은 서버 수). 데이터가 균등 분포일 때는 잘 동작하지만, N이 바뀌는 순간 거의 모든 키의 매핑이 깨진다.
- 클라이언트가 캐시 없는 서버로 몰림 → 대규모 캐시 미스.
- 전통적인 해시 테이블 리사이징도 같은 문제(rehash) — 새 해시 함수로 전체 재배치 필요. 분산 환경에서는 이 비용이 운영적으로 치명적.
핵심 아이디어: 해시링
- 키와 서버를 같은 해시 공간
R = [0, 2^k - 1]위에 균등 분포 해시 함수로 배치 → 원형 링. - 각 키는 자신의 위치에서 시계 방향으로 가장 가까운 서버에 저장.
- 서버가 추가되면 새 서버 직전 구간의 키만 재배치 → 평균 재배치 비용이
O(K/N)수준. - 서버가 제거되면 그 서버가 담당하던 구간의 키만 다음 서버로 이동.
이 방식은 두 가지 본질적 문제를 남긴다:
- 파티션 균등성: 서버 추가/제거 환경에서 서버 사이 해시 공간(파티션) 크기를 균등하게 유지하기 어려움.
- 키 균등 분포: 서버 위치가 무작위 해시로 결정되므로, 키도 결과적으로 균등하게 분포하지 않을 수 있음.
가상 노드(virtual node)
위 두 문제를 완화하는 표준 기법:
- 하나의 실제 서버를 링 위의 여러 가상 노드로 표현.
- 키는 시계 방향으로 가장 가까운 가상 노드를 찾고, 그 가상 노드가 가리키는 실제 서버로 저장.
- 가상 노드 개수가 늘어날수록 파티션과 키 분포가 대수의 법칙에 따라 균등해진다 — 보통 한 서버당 100~200개 가상 노드를 둠.
관련 노트
참고
- http://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-hashing.pdf
- Karger et al., "Consistent Hashing and Random Trees" (1997)