필요성
수평적인 확장을 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해싱은 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.
해시 키 재비치(Refresh) 문제
N개의 캐시 서버가 있다고 할때, 이 서버들에 부하를 균등하게 나누는 보편적인 방법은 흔히 사용하는 제산함수 를 사용한 방법이 있다.
serverIndex = Hash(key) % #(서버의갯수)
위의 제산함수를 사용한 해싱기법은 구현이 편하다는 장점이 있다.
하지만 이는 어떤 우연에 의한 Key값에 대한 Hash가 편중되어(Skewed) 특정 서버로만 해싱이 편중될 수 있다는 단점이 있다. 또한 예기치 못한 상황으로 임의의 서버가 dead 되었을 때, 다른 서버로 트래픽을 밸런싱하는 경우에 문제가 발생한다.
예를들어, 총 4대의 서버가 있는 상황에서 3번 서버에 이상이 있는 상황을 가정하자.(서버의 인덱스는 1~4이다) 3번 서버가 dead 상태로 돌입하면서 3번서버로 Hashing 되었던 클라이언트들은 인근의 1,2,4번 서버로 키가 재분배 될 것이다. 하지만 이들은 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다.
그결과로 대규모 캐시미스(Cache Miss) 가 발생하게 될 것이다.
이런 상황에서 안정해시설계 는 이런 문제들을 효과적으로 해결하는 기술이다.
안정해시
위키피디아에 따르면 "안정 해시"는 해시테이블 크기가 조정될 때 오직 K/N 개의 키만 재배치하는 해시 기술이다. (K : 키의 갯수, N : 슬롯의 갯수) 링크 : Consistent Hashing (Wikipedia)
해시공간과 해시링
이제 본격적인 안정해시 기법을 맛볼(?) 차례이다. 우선 해시함수로 SHA-1을 사용한다고 가정하자. More. SHA-1
SHA-1의 해싱으로 총 160bit 의 해시값을 갖게 되므로 SHA-1의 해시공간의 범위는 0 ~ 까지이다.따라서 이 되고 이 된다.
이 해시 공간의 양쪽을 구부려 접으면 다음과 같은 해시링(Hash Ring)이 만들어진다.
해시 서버
이 해시 함수f를 사용하면 서버 IP나 이름을 이 링위의 어떤 위치에 대응시킬 수 있다.
해시 키
나머지 연산을 사용하지 않고 있는 해시키는 다음과 같이 캐시할 Key0 ~ KeyN 을 해시 링 위의 어느 지점에 배치할 수 있다.
서버 조회
어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버이다. 이 그림에서는 Key0는 서버0에 저장되고, Key1은 서버1에 저장된다.
서버 추가
서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.
서버 4가 추가되면 반시계방향에 있는 키들만 재배치하면 된다.
서버 제거
하나의 서버가 제거되는 과정도 살펴보면 다음과 같다.
서버1이 제거되면, 서버1에 저장되어 있는 Key1은 시계방향으로 순회하여 서버2로 재배치된다.
이와같은 설계를 통해서 서버가 제거되어도 나머지 키에는 영향이 없다는 장점이 있다.
기본 구현법의 두가지 문제
안정 해시 알고리즘의 기본 절차는 다음과 같다.
- 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다.
하지만 이 접근법에는 두 가지 문제가 있다.
- 서버가 추가/삭제 되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 것이 불가능하다
- 어떤 서버는 굉장히 작은 해시공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 발생한다.
- 키의 균등 분포를 달성하기가 어렵다
- 서버간의 좁은 해시공간과 키값의 배치에 따라서 어떤 서버는 아무 데이터도 갖지 않게 된다.
이 문제를 해결하기 위해 제안된 기법이 가상 노드(Virtual Node) 또는 복제(Replica) 라는 기법이다.
가상 노드
가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
위의 그림을 보면 서버1은 여러개의 가상노드(서버1_0, 서버1_1, 서버1_2) 를 갖게 된다.
따라서 각 서버는 하나가 아닌 여러 개 파티션을 관리하게 된다. 가상 노드의 개수를 늘리면 표준편차가 작아지기 때문에 키의 분포는 점점 더 균등해진다. (100~200개의 가상 노드를 사용한 경우, 표준 편차 값은 평균의 5%~10% 사이로 된다.)
가상노드의 갯수를 늘리게 되면, 표준편차의 값은 더 떨어지지만 가상 노드 데이터를 저장할 공간이 더 필요하게 된다.
즉, 가상노드의 갯수와 균등정도 사이의 Trade Off 가 필요 하다는 뜻이다. 이는 시스템 요구사항에 맞도록 가상 노드 갯수를 적절히 조정해햐 할 것이다.
재배치할 키 결정
서버가 추가되거나 제거되면 데이터 일부는 재배치해야 한다.
이때는 추가된 서버를 시작으로, 반시계방향으로 순회하면서 만나게 되는 처음 서버까지가 범위가 된다.
즉, 추가된 서버 ~ 반시계방향으로 만나는 첫 서버 까지의 Key들은 새롭게 추가된 서버에 재배치 될 것이다.
정리
안정해시의 이점
- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성에 도움이 된다.
- 핫스팟(Hotspot) 키 문제를 줄인다.
- 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부화 문제가 생길 수 있는데, 안정해시는 이런 문제(Hotspot Key Problem) 를 줄여준다.
