안정 해시 설계
해시 키 재배치 문제
나머지 연산으로 데이터를 분산할 때 서버 수가 변경되면 발생하는 문제를 살펴봅니다.
가장 단순한 방식은 키의 해시값을 서버 수로 나눈 나머지를 서버 인덱스로 사용하는 것입니다. 계산식은 serverIndex = hash(key) % N이며, 같은 키와 같은 서버 수를 사용하면 항상 동일한 서버가 선택됩니다.
text serverIndex = hash(key) % N
대부분의 키가 다른 서버를 가리키면 기존 데이터가 남아 있어도 캐시 미스가 발생합니다. 클라이언트가 새 서버에 접근했을 때 데이터가 없으므로 원본 데이터베이스나 백엔드에 요청이 집중될 수 있습니다.
안정 해시와 해시 링
서버 수와 직접 결합하지 않고 키와 서버를 동일한 해시 공간에 배치하는 원리를 설명합니다.
안정 해시는 서버 추가와 제거 시 데이터 이동을 최소화합니다. 키가 k개이고 서버가 n개라면 평균적으로 약 k/n개의 키만 영향을 받도록 설계할 수 있습니다.
서버의 IP 주소나 이름을 해싱해 링 위의 위치를 정하고, 키도 같은 해시 함수로 링 위에 배치합니다. 서버와 키가 동일한 좌표 체계를 사용하므로 키의 위치를 기준으로 담당 서버를 찾을 수 있습니다.
s0, s1, s2, s3 서버 노드가 놓이고, 그 사이에 k0, k1, k2, k3 키 노드가 배치되어 있습니다.서버 추가와 제거
안정 해시에서 서버 구성이 바뀔 때 영향을 받는 키의 범위를 설명합니다. 쉽게 말해 서버가 추가되면 일부 키만 새 서버로 이동하고, 서버가 제거되면 그 서버가 맡던 키만 다음 서버로 넘어갑니다.
새 서버의 위치와 반시계 방향의 이전 서버 사이에 있는 키만 새 서버로 이동합니다. 링의 다른 구간에 있는 키는 기존 서버에 그대로 남습니다.
k0과 기존 서버 s0 사이에 새 서버 s4가 추가되고, 이전에 s0으로 향하던 k0만 s4로 연결됩니다.제거된 서버가 담당하던 키는 시계 방향의 다음 서버로 이동합니다. 제거된 서버와 무관한 구간의 키는 기존 배치를 유지합니다.
s1 서버에 X 표시가 생기고, s1이 담당하던 k1이 다음 서버인 s2로 이동합니다.데이터를 한꺼번에 옮기지 않고 작은 단위로 나눠 점진적으로 재배치하며, 이동 속도를 제한해 네트워크와 디스크 부하를 조절합니다. 서버 추가 시에는 캐시 워밍이나 이중 읽기로 초기 캐시 미스를 줄이고, 서버 제거 시에는 복제본으로 요청을 분산합니다. 운영 중에는 여유 용량을 확보하고 지연 시간과 오류율을 관찰하며 재배치 속도를 조정해야 합니다.
기본 안정 해시의 한계
서버를 링에 한 번씩만 배치했을 때 발생하는 파티션 편향과 부하 불균형을 설명합니다.
기본 안정 해시는 재배치를 줄이지만 데이터가 항상 균등하게 분산되는 것은 아닙니다. 서버 사이의 간격이 제각각이면 파티션 크기와 서버별 키 수에 큰 차이가 생길 수 있습니다.
제거된 서버의 구간이 시계 방향의 다음 서버 구간에 합쳐집니다. 다음 서버의 담당 범위가 다른 서버보다 크게 늘어나 부하 불균형이 심해질 수 있습니다.
s1이 제거되고, 원래 s1이 담당하던 긴 원호가 s2의 영역으로 합쳐져 s2의 파티션이 다른 영역보다 크게 표시됩니다.가상 노드
하나의 물리 서버를 여러 논리 노드로 분산 배치해 데이터 균등성을 개선하는 방법을 설명합니다.
가상 노드는 한 서버가 링의 여러 구간을 담당하도록 만듭니다. 가상 노드는 복제 노드 또는 replica라고도 부릅니다.
가상 노드가 많으면 데이터 분포는 더 균등해지지만 메타데이터와 관리 비용도 증가합니다. 시스템 규모와 부하 편차를 고려해 적절한 수를 선택해야 합니다.
운영 효과와 활용 사례
안정 해시의 장점과 실제 분산 시스템에서의 활용 범위를 정리합니다.
서버 구성 변경 시 재배치되는 키의 수를 최소화할 수 있다는 점입니다. 가상 노드와 함께 사용하면 데이터 분포를 균등하게 만들고 수평적 확장을 단순화할 수 있습니다.
서버와 키를 동일한 해시 공간에 배치하고, 키에서 시계 방향으로 처음 만나는 서버를 선택합니다. 운영 환경에서는 가상 노드, 복제본, 장애 감지, 링 구성 동기화까지 함께 설계해야 합니다.
text 1. 서버 또는 가상 노드의 해시값을 계산한다. 2. 노드를 해시값 기준으로 정렬한다. 3. 키의 해시값 이상인 첫 노드를 찾는다. 4. 노드가 없으면 링의 첫 노드를 선택한다.