안정 해시 설계

해시 키 재배치 문제

N개의 캐시 서버가 있다고 가정했을 때, 각각의 캐시 서버는 균등한 요청을 받을 수 있어야 합니다. 그래야 어떤 한 서버에 과도한 부하가 생기지 않기 때문입니다. 각 서버들에 부하를 균등하게 나누는 가장 보편적인 방법은 아래와 같은 해시 함수를 사용하는 것입니다.

Hash Server Index = Hash(key) % N (해시 서버의 수)

하지만 이 방법에는 엄청나게 치명적인 단점이 숨겨 있습니다. 이 방법은 서버 풀의 크기가 고정적이고 데이터 분포가 균등할 때만 잘 동작한다는 것입니다. 서버가 추가되거나 기존 서버가 삭제되면 문제가 발생합니다. 서버가 추가되거나 삭제되면, 모든 해시값들에 대해 다시 분배를 해 줘야 하는 어마어마한 수정이 일어나게 되는 것입니다.

안정 해시

💬 안정 해시

안정 해시는 해시 테이블이 추가되거나 삭제될 때 평균적으로 k / n 개의 키만 재배치가 일어나도록 하는 해시 기술입니다. 여기서 k란 키의 개수이고, n은 슬롯의 개수입니다. 이해를 편하게 하기 위해서 일직선으로 된 해시 테이블의 메모리를 둥그렇게 말아 해시링으로 살펴보도록 하겠습니다.

해시링에서 캐시할 키는 해시링 위의 어느 지점에든 배치할 수 있습니다. 이때 실제로 해시키는 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버에 할당됩니다. 따라서 해시링 위에 해시키가 추가되거나 삭제되더라도 영향을 받는 범위에 있는 해시키만 재배치하면 되기 때문에, 전통적인 해시 서버 구축 방법처럼 대규모 수정이 발생하지 않습니다.

💬 기본 구현법의 두 가지 문제점

❕파티션 크기 불균형

• 캐시 서버가 추가되거나 삭제되는 상황을 고려해 본다면 파티션의 크기를 일정하게 유지하기 어렵습니다.

❕키의 분포 불균형

• 예를 들어 해시키가 해시링의 한 부분에 집중적으로 배치된다면, 특정 해시 서버에만 부하가 몰리는 불균형 현상이 발생할 것입니다.

💬 가상 노드

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버가 해시링 위에 여러 개의 가상 노드를 가지게 해서 파티션의 크기와 해시키 분포의 균등함을 챙기는 기법입니다. 여러 개의 가상 노드를 둠으로 인해 각 서버는 하나가 아닌 여러 개의 파티션을 관리해야 합니다.

가상 노드 기법에서도 기존과 비슷하게 시계 방향으로 링을 탐색하다가 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 됩니다. 가상 노드의 개수를 늘리면 늘릴수록 표준 편차가 작아져서 키의 분포가 점점 균등해진다는 장점이 있습니다.