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

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 오늘의 포스팅 주제는 안정 해시와 관련된 내용이니 천천히 살펴보도록 하자. 

 

해시 키 재배치 문제 

레디스와 같은 N개의 캐시 서버가 있다고 가정하자. 이 서버들에 부하를 균등하게 나누는 보편적 방법은 아래의 해시 함수를 사용하는 것이다. 현재 N은 4라고 가정을 한다. 

 

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

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

 

위의 표를 보면 특정 key가 보관되어 있는 서버를 알아내기 위해 해시에 모듈러 연산 n을 진행하면 어느 서버의 인덱스인지 확인할 수 있다. 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다. 예를 들면, 서버 하나가 장애를 일으켜 동작이 중단된다면 서버 풀의 크기(서버 개수 N)가 3으로 변하게 된다. 키에 대한 해시값은 변하진 않지만 모듈러 연산을 적용한 서버 인덱스 값은 완전히 틀려지는 것이다.

 

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

 

위의 표를 보면 key 값이 있는 기존의 캐시 서버가 한순간에 다 틀어져버린다. 

즉, 서버 하나가 죽어도 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다. 결국 대규모 캐시 미스(cache miss)가 발생하게 될 것이다.

 

안정해시 

안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. 

k는 키의 개수이고, n은 슬롯(slot)의 개수이다. 

 

 

해시 공간과 해시 링 

 

 

해시 함수 f로는 SHA-1을 사용한다고 가정하자. SHA-1의 해시 공간 범위는 0부터 2^160-1까지라고 알려져있다. 지금부터 0을 x0, 2^160-1을 xn이라고 지칭하겠다. 

 

*SHA-1은 Secure Hash Algorithm 1의 줄임말로, 해시 함수 중 하나이다. 데이터를 고정된 크기의 고유한 해시 값으로 변환하는 데 사용되며, 일방향 암호화 함수의 일종이다.

 

 

위의 해시공간을 양쪽을 잡고 끝점을 맞닿게 하면 다음과 같은 모양이 된다. 

 

 

 

---

 

해시서버 

 

 

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

 

---

 

해시 키

 

 

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

 

---

 

서버조회 

 

 

 

시계 방향으로 링을 탐색하면서 만나는 첫 번째 서버가 key가 저장된 곳이다. 

그림을 보면 k0은 s0, k2은 s2처럼 말이다. 

 

---

 

서버추가

 

 

서버를 추가하게 된다면 해시 링 위에 서버 4가 추가될 것이다.

그러면 key0은 위의 그림처럼 시계 방향으로 가장 가까운 서버 4에 저장된다. 

 

---

 

서버제거

 

 

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

위의 그림에서는 서버1이 죽고 key1만 서버 2로 재배치된다. 

 

 

기본 구현법의 두 가지 문제 

[문제 1]

인접한 서버 사이의 해시 공간을 파티션이라고 불리는데 서버가 추가되거나 삭제되는 상황을 생각해보면 파티션의 크기를 균등하게 유지하는 게 사실상 불가능하다. 그래서 어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 된다. 예를 들면, s1이 삭제된다면 s2의 파티션이 다른 파티션 대비 2배가 된다. 

 

 

[문제 2]

키의 균등 분포를 달성하기 어렵다. 예를 들면, 아래 그림을 보면 서버 3과 서버 1은 아무 데이터를 가지고 있지않다. 

*key들은 시계방향으로 가장 가까운 서버를 찾는다. 흰 공간의 원이 key라고 생각하고 s2는 4개, s0은 1개 s3과 s1은 0개다.

 

 

이 문제를 해결하기 위해 제안된 기법이 가상노드이다. 

 

 

 

가상노드 

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

필자는 서버당 가상 노드의 개수를 3으로 간주하겠다. 실제 시스템에서는 이보다 훨씬 큰 값이라는 것만 참고하자. 

 

서버 0과 서버 1이 있다고 치면 s0_0, s0_1, s0_2 / s1_0, s1_1, s1_2 으로 각 서버 당 3개의 가상 노드를 사용한다고 가정하고 설명하겠다. 

 

 

위의 그림에서 6개의 가상노드가 존재한다. 키의 위치로부터 시계방향으로 링을 탐색하다가 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다. 즉, k0이 s1_1을 만났으니 서버 1로 저장된다는 것이다.  가상 노드의 개수를 늘리면 당연 키의 분포는 점점 균등해질 것이며 표준편차가 작아져서 데이터가 고르게 분포된다. 그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 된다.

 

이때는 타협적 결정을 통해 가상 노드 개수를 적절히 조정해야한다. 

 

재배치할 키 결정

 

 

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

서버 4가 추가된다면 s3 ~ s4(시계방향) 사이의 해시공간에 위치한 키들을 s4로 재배치한다. 

서버 1이 삭제된다면 s1 ~ s0(반시계방향) 사이의 키들이 s2로 재배치되어야 한다. 

 

 

 

끝!