[가상면접 사례로 배우는 대규모 시스템 설계 기초] 5장. 안정 해시 설계

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

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 있을 때, 이 서버들에 부하를 균등하게 나누는 보편적인 방법은 아래의 해시 함수를 사용하는 것이다.

• `serverIndex = hash(key8) % N (N은 서버의 개수)`

표 5-1, 그림 5-1

이 방법은 서버 풀(server pool)의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작한다.

 

하지만, 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.

예를 들어, 1번 서버가 장애를 일으켜 동작을 중단했다고 하자. 서버 풀의 크기는 3으로 변하고, 그 결과 키에 대한 해시 값은 변하지 않지만 나머지(%) 연산을 적용하여 계산한 서버 인덱스 값은 표 5-2와 같이 달라질 것이다.

표 5-2, 그림 5-2

이 결과 장애가 발생한 1번 서버에 보관되어 있는 키 뿐만 아니라 대부분의 키가 재분배되었다. 1번 서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다는 뜻이다. 안정 해시는 이 문제를 효과적으로 해결하는 기술이다.

안정 해시(consistent hash)

"안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯(slot)의 개수다. 이와는 달리 전통적인 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다"

해시 공간(hash space)과 해시 링(hash ring)

해시 함수로 f는 SHA-1을 사용하고, 그 함수의 출력 값 범위는 x0, x1, ..., xn과 같다고 하자. 해시 공간(hash space)의 그림을 표현하면 그림 5-3과 같고, 이 해시 공간의 양쪽을 구부려 접으면 그림 5-4와 같은 해시 링(hash ring)이 만들어진다.

그림 5-3

그림 5-4

해시 서버

그림 5-5

그림 5-5는 4개의 서버를 해시 링 위에 배치한 결과이다.

해시 키

그림 5-6

캐시할 키 key0, key1, key2, key3를 해시 링 위의 어느 지점에 배치할 수 있다.

서버 조회

그림 5-7

어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다. 그림 5-7이 이 과정을 보여준다. 따라서 key0은 서버 0에 저장되고, key1은 서버 1, ... 에 저장된다.

서버 추가

그림 5-8

서버를 추가하더라도 키 가운데 일부만 재배치하면 된다. 그림 5-8을 보면 새로운 서버 4가 추가된 뒤에 key0만 재배치됨을 알 수 있다.

서버 제거

그림 5-9

하나의 서버가 제거되면 키 가운데 일부만 재배치된다. 그림 5-9를 보면 서버 1이 삭제되었을 때, key1만이 서버 2로 재배치됨을 알 수 있다.

기본 구현법의 두 가지 문제

이 접근법에는 두 가지 문제가 있다.

 

첫 번째, 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(partition)의 크기를 균등하게 유지하는 게 불가능하다.

 

두 번째, 키의 균등 분포(uniform distribution)를 달성하기 어렵다.

그림 5-10, 그림 5-11

 

이 문제를 해결하기 위해 제안된 기법이 가상 노드(virtual node) 또는 복제(replica)라 불리는 기법이다.

가상 노드(virtual node)

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

그림 5-12, 그림 5-13

그림 5-12를 보면 서버 0과 서버 1은 3개의 가상 노드를 갖는다.(숫자 3은 임의로 정한 것, 실제 시스템에서는 그보다 훨씬 큰 값이 사용됨)

 

서버 0을 링에 배치하기 위해 s0 하나만 쓰는 대신, `s0_0, s0_1, s0_2`의 세 개 가상 노드를 사용했다.

 

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 표준 편차(standard deviation)가 작아져서 데이터가 고르게 분포되기 때문이다.

재배치할 키 결정

그림 5-14

그리 5-14처럼 서버 4가 추가되었다고 하면, 이에 영향을 받는 범위는 s4(새로 추가된 노드)부터 그 반시계에 있는 첫 번째 서버 s3까지이다. 즉 s3부터 s4 사이에 있는 키들을 s4로 재배치해야 한다.

그림 5-15

그림 5-15와 같이 서버 s1이 삭제되면 s1부터(삭제된 노드) 그 반시계 방향에 있는 최초 서버 s0 사이에 있는 키들이 s2로 재배치되어야 한다.

정리

안정 해시가 왜 필요하며, 어떻게 동작하는지를 살펴보았다. 안정 해시의 이점은 다음과 같다.

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
• 핫스팟(hotspot) 키 문제를 줄인다. 특정한 샤드(shard)에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다.