안정 해시(Consistent Hash), 노드 증감 시 재샤딩 비용을 줄이는 방법

왜 안정 해시가 필요한가

데이터를 여러 노드에 나누어 둘 때, 보통 `nodeIndex = hash(key) % N`처럼 키를 해시한 뒤 노드 수 N으로 나눈 나머지로 배치합니다. N이 고정돼 있으면 문제가 없지만, 노드가 추가되거나 제거되면 N이 바뀌면서 대부분의 키에 대해 나머지가 달라집니다. 그 결과 대량의 데이터가 다른 노드로 옮겨가고, 캐시라면 캐시 미스가 크게 늘어납니다. 안정 해시는 노드가 늘거나 줄어들 때 평균적으로 k/n개 정도의 키만 재배치되게 해서, 재샤딩 비용과 캐시 붕괴를 줄이는 기법입니다.

해시 링과 키·서버 배치

해시 함수의 출력 범위(예: SHA-1이면 0 ~ 2^160−1)를 한 바퀴 둥글게 이어 붙인 것을 해시 링이라고 합니다. 서버는 `hash(nodeId)`, 키는 `hash(key)`로 링 위 한 점에 매핑합니다. 각 키는 링 위에서 시계 방향으로 돌아가며 처음 만나는 서버에 배치합니다. 이렇게 하면 노드가 하나 추가되거나 제거될 때, 그 노드가 담당하던 구간의 키만 인접 서버로 옮기면 됩니다. 나머지 키는 그대로 두면 됩니다.

한계: 파티션과 키 분포 불균등

해시 링에 서버를 그대로 두면 두 가지 문제가 생깁니다. 첫째, 인접 서버 사이 구간인 파티션 크기가 들쭉날쭉해져서 어떤 서버는 키를 많이, 어떤 서버는 적게 받을 수 있습니다. 둘째, 키 위치도 해시값에 따라 정해지다 보니, 키가 한쪽 구간에 몰리면 특정 서버만 과부하를 겪을 수 있습니다.

보완: 가상 노드(Virtual Node)

이를 완화하기 위해 가상 노드를 둡니다. 하나의 실제 노드를 여러 개의 가상 노드로 링 위에 흩어서 배치하고, 키는 여전히 시계 방향으로 만난 첫 (가상) 노드에 매핑하며, 그 가상 노드가 가리키는 실제 서버에 저장합니다. 가상 노드 수를 늘리면 한 실제 노드가 여러 작은 파티션을 나눠 갖게 되어, 파티션 크기와 키 개수의 편차가 줄어듭니다. 대신 가상 노드 정보를 저장할 메모리가 늘어나는 트레이드오프가 있습니다.

정리

안정 해시는 분산 시스템에서 노드 증감 시 재배치되는 키 수를 k/n 수준으로 줄여, 데이터 이동과 캐시 미스를 줄이는 데 쓰입니다. 해시 링 위에 서버와 키를 배치하고, 가상 노드로 부하 분산을 고르게 하는 방식으로 실제 설계에 널리 활용됩니다.