[대규모 시스템 설계] 안정 해시

수평적 규모 확장을 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.
안정 해시는 이 목표를 달성하기 위해 보편적으로 사용되는 기술이다.

 

일반적인 해시 함수의 문제점

N개의 캐시 서버가 있다고 해보자.
이 서버들에 부하를 균등하게 나누는 보편적인 방법은 hash_key % 서버 개수와 같은 해시 함수를 사용하는 것이다.
하지만 이러한 해시 함수는 서버가 추가되거나 삭제되는 경우에 문제가 생긴다.
서버가 추가되거나 삭제되는 경우 해시 키의 재배치가 일어나는데, 이때 데이터의 불균형이 발생할 수 있기 때문이다.

다음 예시는 4대의 서버 구성에서 서버 1대가 장애를 일으킨 경우의 해시 키 재배치의 문제점을 나타낸다.

해시 키가 서버 0에는 4개, 서버 3에는 1개 재배치되었다.
만약 서비스 규모가 크고 server0에 유명인사가 몰려 재배치되었다면, 핫스팟 키 문제가 발생해 연쇄적으로 서버 장애가 발생할 수 있다. 또한, 재분배된 키로 인해 캐시 클라이언트가 엉뚱한 서버로 접속하게 되어 결과적으로 대규모 캐시 미스(cache miss)가 발생할 수 있다.

이러한 문제를 효과적으로 해결할 수 있는 기술이 안정 해시다.

 

안정 해시

전통적인 해시 테이블은 슬롯의 수가 변경되면 거의 대부분 키를 재배치하는데,
이와는 달리 안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 k(키의 개수)/n(슬롯의 개수) 개의 키만 재배치하는 해시 기술이다.

 

안정 해시의 기본 개념

안정 해시의 기본 전략은 다음과 같다.

1. 해시 공간의 시작과 끝을 이어 붙여 해시 링을 만든다.
2. 서버 IP나 이름을 해시 링의 임의의 위치에 대응시켜 배치한다. (균등 분포 해시 함수 사용)
3. 해시 키를 해시 링 위의 어느 지점에 배치한다. (균등 분포 해시 함수 사용)
4. 해시 키는 시계 방향으로 링을 탐색하며 만나는 첫 번째 서버에 저장된다.

이 과정을 그림으로 표현하면 다음과 같다.

이렇게 만들어진 안정 해시는 서버가 추가되거나 제거돼도 해시 키를 전부 재배치하는 것이 아니라 해당 파티션의 해시 키만 재배치하므로 k/n의 키만 재배치되는 효율적인 구현을 할 수 있다.

하지만 이러한 구현법에도 문제점은 존재한다.

기본 구현법의 문제점

기본 구현의 첫 번째 문제점은
서버의 추가와 삭제를 감안했을 때, 파티션의 크기를 균등하게 유지하는 것이 불가능하다는 것이다.

처음에는 균등하게 분포되었던 서버 파티션 사이에 서버가 추가되거나 삭제되면 다른 서버와의 파티션 공간에 불균등이 일어난다.

이렇게 되면 어떤 서버는 큰 해시 공간을 할당받고, 어떤 서버는 작은 해시 공간을 할당받는 상황이 생긴다.
이렇게 늘어난 파티션의 크기 사이에 많은 해시 키가 존재한다면 불균등한 해시 키 분포가 일어나게 된다.
즉, 특정 서버에 해시 키가 몰리는 상황이 발생할 수 있다는 것이다.

그리고 기본 구현의 두 번째 문제점은
해시 키의 균등 분포를 달성하기 어렵다는 점이다.

해시 키가 다음과 같이 배치되었다고 생각해보자.

서버 3은 아무런 키를 갖지 않는 반면, 대부분의 키는 서버 2에 몰리게 된다.

이러한 문제점을 해결하기 위해 제안된 기법이 가상 노드 또는 복제(replica)라 불리는 기법이다.

 

가상 노드 기법

가상 노드는 실제 서버를 가리키는 노드로, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
실제 서버를 가리키는 가상의 노드를 링위에 촘촘히 배치하면 표준편차가 작아져 키의 분포를 균등하게 유지할 수 있게 된다.

또한 가상 노드 사이 파티션의 크기가 작아지므로 앞서 살펴본 문제점을 해결할 수 있게 된다.

서버는 물리적으로 한정되어 있지만, 가상 노드는 하나의 서버를 가리키므로 개수를 자유롭게 조정할 수 있다는 장점이 있다. 하지만 그만큼 가상 노드 데이터를 저장할 공간이 늘어남으로 적절한 트레이드오프가 필요하다.