5장 안정 해시 설계

서론

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다. 하지만, 우선 이 해시 기술이 풀려고하는 문제부터 좀 더 자세하게 살펴보자.

 

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 있다고 하자. 이 서버들에 부하를 균등하게 나누는 보편적 방법은 아래처럼 해시 함수를 사용하는 것이다. 이전에 봤던 기본적인 샤딩 방식과 동일하다.

serverIndex = hash(key)%N (N은 서버의 수)

키	해시	서버 인덱스
key0	18358617	1
key1	26143584	0
key2	181311146	2
key3	35863496	0
key4	34085809	1
key5	27581703	3
key6	38164978	2
key7	22530351	3

위는 총 4대의 서버를 사용할 때의 예시다. 

그림 5-1

그림 5-1은 표의 key가 어떻게 분산되는지 보여준다. 해당 방법은 Server pool의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작한다. 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다. 예를들어, server1이 장애가 발생하여 동작할 수 없을 때, server pool의 크기는 3으로 변한다. 키에 대한 해시 값은 변하지 않지만 나머지 연산을 적용하여 계산한 서버 인덱스 값은 달라질 것이다. 따라서 그림 5-2와 같은 결과를 얻는다.

그림 5-2

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

 

안정 해시

테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. k는 키의 개수, n은 슬롯(slot)의 개수다. 

해시 공간과 해시 링

해시 함수 f로는 SHA-1을 사용한다고 하고, 그 함수의 출력 값 범위는 x0, ...., xn과 같다고 가정하자. SHA-1의 해시 공간(hash space) 범위는 0부터 2^160-1 까지라고 한다. 따라서 xn은 2^160-1이다. 

그림 5-3

그림 5-4

그림 5-3인 해시 공간을 양쪽으로 구부려 접으면 그림 5-4와 같은 해시 링이 만들어진다.

 

해시 서버

해시 함수 f를 사용하면 서버 IP나 이름을 링 위의 어떤 위치에 대응시킬 수 있다. 

그림 5-5

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

 

해시 키

여기 사용된 해시 함수는 "해시 키 재배치 문제"에 언급된 함수와는 다르며, 나머지 연산을 사용하지 않고 있음에 유의하자.

그림 5-6

그림 5-6 같이, key 또한 해시 링의 어느 지점에 배치할 수 있다.

 

서버 조회

어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.

그림 5-7

그림 5-7이 해당 과정을 보여준다. 

 

서버 추가

서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.

그림 5-8

그림 5-8을 보면 새로운 서버4가 추가된 뒤에 key0만 재배치됨을 알 수 있다. 

 

서버 제거

하나의 서버가 제거되면 키 가운데 일부만 재배치된다. 

그림 5-9

그림 5-9를 보면 서버1이 삭제되었을 때, key1만이 server2로 재배치됨을 알 수 있다.

 

기본 구현법의 두 가지 문제

안정 해시 알고리즘은 MIT에서 처음 제안되었다. 그 기본 절차는 아래와 같다.

• 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 재배치한다.
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.

하지만, 이 접근법에는 두 가지 문제가 있다. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(partition)의 크기를 균등하게 유지하는 게 불가능하다는 것이 첫 번째 문제다. 여기서 파티션은 인접한 서버 사이의 해시 공간이다. 어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 가능하다는 것이다.

그림 5-10

그림 5-10은 s1이 삭제되는 바람에 s2의 파티션이 다른 파티션 대비 거의 2배로 커지는 상황을 보여준다. 2번째 문제는 키의 균등 분포(uniform distribution)를 달성하기가 어렵다는 것이다. 

그림 5-11

예를 들어, 서버가 그림 5-11같이 배치되어 있다고 해보자. 서버1과 서버3은 아무 데이터도 갖지 않는 반면, 대부분의 키는 서버2에 보관될 것이다.

 

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

 

가상 노드 or 복제

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

그림 5-12

그림 5-12를 보면 서버0과 서버1은 3개의 가상 노드를 갖는다. 서버0을 링에 배치하기 위해 s0 하나만 쓰는 대신 s0_0,  s0_1, s0_2인 가상 노드 3개를 사용했다. 따라서 서버는 1개가 아닌 여러 개 파티션을 관리해야 한다. 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.

 

이렇게 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 이유는 표준 편차(standard deviation)가 작아져서 데이터가 고르게 분포되기 때문이다. 링크에 따르면 100~200개의 가상 노드를 사용했을 경우 표준 편차 값은 평균의 5%~10%사이다. 가상 노드의 개수를 더 늘리면 표춘 편차의 값을 더 떨어진다. 타협적 결정(trade off)이 필요하다는 뜻이다. 그러니 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야 할 것이다.

 

재배치할 키 결정

서버가 추가되거나 제거되면 데이터 일부는 재배치해야 한다. 

그림 5-13

그림 5-13처럼 서버4가 추가되었다고 해보자. 이에 영향받는 범위는 s4부터 s3까지이다. 즉, s3부터 s4 사이에 있는 키들을 s4로 재배치해야 한다.

그림 5-14

그림 5-14같이 s1이 삭제되면 s1부터 s0 사이에 있는 키들이 s2로 재배치되어야 한다.

 

마치며

이번에는 안정 해시가 왜 필요하며 어떻게 동작하는지를 살펴봤다. 안정 해시의 이점은 아래와 같다.

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

안정 해시는 실제로 널리 쓰이는 기술이다. 그 중 유명한 것 몇가지를 예롤 들어보면 아래와 같다.

• 아마존 다이나모 데이터베이스(AWS DynamoDB)의 파티셔닝 관련 컴포넌트
• 아파치 카산드라(Apache Cassandra) 클러스터에서의 데이터 파티셔닝
• 디스코드(Discord) 채팅 어플리케이션
• 아카마이(Akamai) CDN
• 매그레프(Meglev) 네트워크 부하 분산기

 

Reference

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초