5장. 안정 해시 설계
수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.
해시 키 재배치 문제
N개의 개키 서버가 있으면 부하를 균등하게 나누는 보편적 방법은 아래 함수이다.
- serverIndex = has(key) % N (N은 서버의 개수이다)
장점: 해당 방법은 서버 풀의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때 잘 동작한다.
단점: 서버 하나가 오류가 발생하면, 다른 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다.
안정 해시
안정해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술이다.
전통적인 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다.
- k는 키의 개수
- n은 슬롯의 개수
> 해시 공간과 해시 링
해시함수 f는 SHA-1을 사용한다고 하면,
- 함수의 출력 값 범위는 x0, x1, x2, x3, ... , xn과 같다.
- SHA-1의 해시 공간 범위는 0부터 2^160 - 1 까지이다.
- x0은 0, xn은 2^160 -1 이다.
> 해시 서버
해시 함수 f를 사용하면 서버 IP나 이름을 링 위의 어떤 위치에 대응시킬 수 있다.
f(서버 n) → 위치가 나온다.
> 해시 키
여기서 사용된 해시 함수는 "해시 키 재배치 문제"에 언급된 함수와 다르다.
나머지 연산(%)을 사용하지 않고 있다.
> 서버 조회
키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째
key0은 서버 0에 저장되고, key 1은 서버 1에 저장되고, key2는 서버 2에 저장 된다
> 서버 추가
서버를 추가하면 키 아누데 일부 재배치하면 된다.
S4가 중간에 재배치 된 것을 아래 그림에서 확인할 수 있다.
> 서버 제거
하나의 서버가 제거 되면 키 가운데 일부만 재배치된다.
서버 1(S1)이 삭제 되면서 key 1만 서버 2로 재배치된 것을 확인할 수 있다.
> 기본 구현법의 두 가지 문제
안전 해시 알고리즘이 처음 제시되었을 때 절차는 아래와 같다.
- 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.
첫 번째 문제, 서버가 추가 되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는게 불가능하다.
→ 어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 가능하다.
→ 파티션은 인접한 서버 사이의 해시 공간이다.
두 번째 문제, 키의 균등 분포를 달성하기가 어렵다
→ 중간에 서버가 배치되면 다른 서버들은 아무 데이터도 가지 않게 된다.
> 가상 노드
가상 노드(virtual node)는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
예)
S0 하나만 사용하는 대신, S0_0, S0_1, S0_2, S0_3과 같이 사용한다.
각 서버는 하나가 아닌 여러 개 파티션을 관리해야한다.
- 가상 노드의 개수를 늘리면 키의 분포는 점점 균등해진다.
- 표준 편차가 작아져서 데이터가 고르게 분포하게 된다.
- 표준 편차는 데이터가 어떻게 퍼져 나갔는지를 보여주는 척도이다.
> 재배치할 키 결정
서버가 추가되거나 제거되면 데이터 일부는 재배치해야 한다. 어느 범위의 키들이 재배치 되어야 할까?
서버가 재배치(추가 및 삭제) 된다면 반시계 방향에 있는 서버 사이에 있는 키들을 재배치해야한다.