"가상 면접 사례로 배우는 대규모 시스템 설계 기초"를 읽고 정리한 글입니다 :)
서버의 개수를 늘리는 수평적 규모 확장을 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시(Consistent Hash)가 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다. 안정 해시는 해시 키 재배치(Rehash) 문제를 해결할 수 있는 기술이다. 그러니 해시 키 재배치 문제에 대해 먼저 알아보자
해시 키 재배치(Rehash) 문제
N개의 캐시 서버가 있을 때, 이 서버들에 부하를 균등하게 나누는 보편적인 방법은 아래의 해시 함수를 사용하는 것이다.
serverIndex = hash(key) % N (N = 서버의 개수)이 방법은 서버 풀(Server Pool)의 크기가 고정되어 있을 때, 또 데이터 분포가 균등할 때는 잘 동작한다. 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 발생한다. 예를 들어 총 4개의 서버가 있는 시스템에서 한개의 서버가 동작을 중단한 경우, 서버 풀의 크기는 3이 된다. 그 결과 나머지 연산을 적용하여 계산된 serverIndex의 값이 달라질 것이다. 그 결과 대부분의 클라이언트가 자신이 원래 가야할 서버가 아닌 엉뚱한 서버에 접속하게 된다. 안정 해시는 이 문제를 효과적으로 해결할 수 있다.
안정 해시(Consistent Hash)
안정 해시(Consistent Hash)는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯(Slot)의 개수이다. 전통적인 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치한다.
안정 해시는 해시 링(Hash Ring)을 사용하여 데이터와 서버를 배치한다.
우선 서버 IP나 이름을 해시 함수를 사용하여 해시 링 위에 배치한다. 위 사진에서는 1, 2, 3, 4로 표시된 4개의 서버가 배치되었다고 가정하자.
서버 뿐만이 아니라 키들도 해시 링 위의 특정 지점에 배치를 할 수 있을 것이다. 이때 어떠한 키가 저장되는 서버는 해당 키의 위치에서부터 시계 방향으로 링을 탐색해 가장 먼저 만나는 서버이다. 즉, 위 사진에서 A 데이터는 2번 서버에 저장되고, B 데이터는 3번 서버에 저장된다.
이 방식을 사용한다면 새로운 서버를 추가하더라도 키 가운데 일부만 재배치하면 된다. 예를 들어 위 사진에서 B 데이터와 3번 서버 사이에 5번 서버가 추가되었다고 가정하자. 그렇다면, B 데이터만 5번 서버로 재배치하면 Rehash가 끝이 난다.
반대로 기존 서버를 제거할 때도, 일부 키만 재배치하면 된다. 위 사진에서 3번 서버가 제거되면, B 데이터만 4번 서버로 재배치하면 Rehash가 끝이 난다.
기본 접근법의 2가지 문제
안정 해시의 기본 접근법은 다음과 같다.
- 서버와 키를 균등 분포(Uniform Distribution) 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다.
이 접근법에는 2가지 문제가 있다.
먼저 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(Partition)의 크기를 균등하게 유지하는 게 불가능하다. 여기서 파티션은 인접한 서버 사이의 해시 공간을 의미한다. 기본 접근법에서는 서버가 추가되거나 삭제되는 경우 어떤 서버에 굉장히 작은 해시 공간 혹은 굉장히 큰 해시 공간을 할당받는 상황이 가능하다.
두번째 문제는 키의 균등 분포를 달성하기가 어렵다. 해시 공간이 균등하게 할당되는 것이 아닌 불균등하게 할당될 가능성이 크고, 키의 배치 역시 특정 공간에 몰릴 가능성이 크다.
이 문제를 해결하기 위해 제안된 기법이 가상 노드(Virtual Node) 또는 복제 노드(Replica)이다.
가상 노드
가상 노드(Virtual Node)는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다. 쉽게 얘기하면 위처럼 여러 개의 가상 노드를 두고, 각 서버는 하나가 아닌 여러개의 파티션을 관리하는 것이다.
이 가상 노드의 개수를 늘리면 키의 분포가 점점 더 균등해진다. 하지만 그만큼 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. 즉, TradeOff를 고려하여 적절한 개수를 고르는 것이 중요하다.
안정 해시의 이점
- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
- 핫스팟(HotSpot) 키 문제를 줄인다.
- 특정한 샤드(Shard)에 대한 접근이 지나치게 몰리는 것을 줄일 수 있다.
