5장 안정 해시 설계
안정 해시 설계
수평적 규모 확장하려면 요청 이나 데이터를 서버에 균등하게 나누는 것이 중요합니다.
안정 해시를 보편적으로 사용 하는 기술입니다.
해시 키 재배치(rehash) 문제
N개의 캐시 서버가 있다고 가정
부하를 균등하게 나누기 위해 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 |
만약 hash(key0) % 4 = 1이면, 클라이언트는 캐시에 보관된 데이터를 가져오기 위해 서버 1에 접속해야 한다.
키 분포도
| 서버 인덱스 | 0 | 1 | 2 | 3 |
| 서버 | server 0 | server 1 | server 2 | server 3 |
| 키 | key1 key3 |
key0 key4 |
key2 key6 |
key5 key7 |
서버 풀의 크기가 고정이고 데이터 분포가 균등할 때는 잘 동작합니다.
만약 서버 1개가 추가되거나 삭제되면 문제가 생깁니다.
서버 1이 내려갔다면? 서버의 풀 크기는 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 |
변화된 키 분포도
| 서버 인덱스 | 0 | 1 | 2 | |
| 서버 | server 0 | server 2 | server 3 | |
| 키 | key0 key1 key5 key7 |
key2 key4 key6 |
key3 |
1번이 죽으면서 키가 재분배가 되면서 캐시 클아이언트가 데이터가 없는 엉뚱한 서버에 접속하게 됩니다.
그 결과로 대규모 캐시미스가 발생하게 됩니다.
안정 해시는 이 문제를 효과적으로 해결하는 기술입니다.
안정 해시
위키피디아 왈
- 안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치 하는 해시 기술
- k는 키의 개수, n은 슬롯(slot)의 개수
- 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치
해시 공간과 해시 링
해시 함수 f로 SHA-1을 사용, 함수의 출력 값 범위는 x0, x1, x2 ... xn과 같다고 하자.
SHA-1의 해시 공간 범위는 0 부터 2^160-1까지 이다.
x0 = 0, xn은 2^160-1
해시 서버
해시 함수를 사용하면 서버 IP나 이름을 링 위의 어떤 위치를 대응시킬 수 있다.
4개의 서버를 해시 링에 배치한 결과
해시 링
여기 사용된 해시 함수는 해시 키 재배치 문제에 업근된 함수와 다름
나머지 연산 사용하고 있지 않음
캐시할 키 key0, key1, key2, key3를 해시 링 위의 배치한 결과
서버 조회
어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버
key0 -> 서버 0에 저장, key 1 -> 서버 1에 저장, key 2 -> 서버 2에 저장, key 3 -> 서버 3에 저장
서버 추가
서버를 추가하더라도 키 가운데 일부만 재배치하면 됩니다.
서버 4를 추가하더라도 key0만 재배치됨을 보여집니다.
k1, k2, k3는 같은 서버에 그대로 남습니다.
왜냐하면 key0으 위치에서 시계 방향으로 순회했을 때 처음 만나는 서버가 서버4 이기 때문에 다른키들은 재배치를 안해도 된다.
서버 삭제
서버를 삭제 하더라도 키 일부분만 재배치 됩니다.
기본 구현법의 두 가지 문제
안정 해시 알고리즘은 MIT에서 처음 제안이 된 알고리즘입니다.
- 서버와 키를 균등 분포 해시함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버의 키가 저장될 서버.
이 접근법에는 2가지의 문제가 있습니다.
2. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는게 불가능하다.
- 파티션은 인접한 서버 사이의 해시 공간을 의미
- 어떤 서버는 굉장한 해시 공간을 할당 받고, 어떤 서버는 굉장한 큰 해시 공간을 할당 받는 상황이 가능
- s1 서버 삭제로 인한 s2의 파티션이 다른 파티션 대비 거의 2배로 커지는 상황
2. 키의 균등 분포를 달성하기가 어려움
- 서버 1과 서버3은 아무 데이터도 갖지 않는 반면, 대부분의 키는 서버2에 보관될 것
가상 노드
- 가상 노드(virtual node)는 실제 노드 또는 서버를 가리키는 노드
- 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
- 위 사진은 서버 0과 서버 1은 3개의 가상 노드를 가진다.
- 서버는 여러개 파티션을 관리해아한다.
- s0으로 표시된 파티션은 서버 0이 관리하는 파티션이고, s1은 서버1이 관리하는 파티션
- 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.
- k0이 저장되는 서버는 노드 s1_1, 서버 1이다.
가상 노드의 개수를 늘리면 키의 분포는 점점 균등해집니다.
표준 편차가 작아져서 데이터가 고르게 분포되기 때문입니다.
표준 편차는 데이터가 어떻게 퍼져 나갔는지를 보이는 척도
재배치할 키 결정
- 서버가 추가되거나 제거되면 데이터 일부는 재배치 해야합니다.
- 서버 4가 추가되었을 경우 s4로부터 반시계 방향에 있는 첫 번째 서버 s3 까지입니다.
- 즉 s3 ~ s4까지 재배치
- 만약 s1 삭제가 될 경우 s1기준 반시계 반향에 있는 s0 ~ s2 까지는 재배치 해야한다.
마치며
- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확정성을 달성하기 쉬움
- 핫스팟 키 문제를 줄인다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있음
- 안정 해시 사용하는 곳
- 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
- 아파치 카산드라 클러스터에서의 데이터 파티셔닝
- 디스코드 채팅 어플리케이션
- 아카마이 CDN
- 매그레프 네트워크 부하 분산기