수평적 규모 확장성을 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.
이를 위해 안정 해시를 보편적으로 사용한다.
해시 키 재배치(rehash) 문제
N개의 캐시 서버가 있다고 가정하고, 이 서버들에 부하를 균등하게 나누는 보편적인 방법은 아래의 해시 함수를 사용하는 것이다.
serverlndex = hash(key) % N (N은 서버의 개수)총 4대의 서버를 사용한다고 하자.
| 키 | 해시 | 해시 % 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 |
특정한 키가 보관된 서버를 알아내기 위해, 나머지 연산을 %4로 적용하였다.
이 문제는 서버풀의 크기가 고정되어 있을때, 그리고 데이터 분포가 균등할 때는 잘 동작한다.
하지만 서버가 추가되거나 삭제되면 문제가 생긴다.
예를 들어 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 |
이렇게 되면 대부분의 키가 재분배 되게 된다.
대부분의 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다. 그 결과 대규모 캐시미스가 발생하게 될 것이다.
이를 해결하기 위해 안정해시를 사용한다.
안정 해시
안정해시란 무엇일까?
안정 해시란 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치 하는 해시 기술이다.
이때 k는 키의 개수이고, n은 슬롯의 개수이다.
해시 공간과 해시 링
안정 해시의 동작 원리를 보려면 먼저 해시 공간을 이해해야 한다.
해시 함수로 SHA-1을 쓴다고 하면 출력값의 범위는 0부터 2¹⁶⁰ − 1까지다. 이 범위를 x0(= 0)부터 xn(= 2¹⁶⁰ − 1)까지 일렬로 늘어놓은 것이 해시 공간이다.
이 해시 공간의 양쪽 끝을 구부려 이으면 해시 링(hash ring)이 된다. x0와 xn이 같은 지점에서 만나면서, 시작도 끝도 없는 원형 구조가 만들어진다.
$
해시 서버
이 해시함수 f를 사용하면 서버 IP나 이름을 이 링 위의 어떤 위치에 대응시킬 수 있다.
해시 키
여기 사용된 해시 함수는 해시 키 재배치 문제에 언급된 함수와는 다르다. 나머지 연산을 사용하지 않는다.
그리고 캐시할 키 또한 해시 링 위의 어느 지점에 배치할 수 있다.
서버 조회
어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.(key0은 서버 0에 저장, key1은 서버 1에 저장...)
서버 추가
앞서 설명에 따르면, 서버를 추가하더라도 키 중 일부만 재배치 하면 된다.
그림을 보면 서버4가 추가된 뒤에 key0만 재배치 됨을 알 수 있다.
서버가 추가되고 key0의 위치에서 시계방향으로 순회했을 때 처음으로 만나는 서버가 서버4이기 때문이다.
서버 제거
하나의 서버가 제거되면 마찬가지로 키 중 일부만 재배치된다.
그림을 보면 서버1이 삭제되었을 때 key1만 서버2로 재배치 됨을 알 수 있다.
기본 구현법의 두가지 문제
안정 해시 알고리즘의 절차는 다음과 같다.
- 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.
이 접근법에는 두가지 문제가 있다.
1. 서버가 추가되거나 삭제되는 상황을 감안하면, 파티션(인접한 서버 사이의 해시 공간)의 크기를 균등하게 유지하는 것이 불가능하다.
s1이 삭제되면서 s2의 파티션이 다른 파티션 대비 거의 두배 커지게 되었다.
2. 키의 균등 분포를 달성하기 어렵다.
서버 1과 서버3은 아무 데이터를 갖지 않지만, 대부분의 키는 서버 2에 보관된다.
이를 해결하기 위해 가상 노드 또는 복제를 사용한다.
가상노드
가상노드란 실제 노드 또는 서버를 가리키는 노드이다. 하나의 서버는 링 위에 여러개의 가상 노드를 가질 수 있다.
s0으로 표시된 파티션은 서버 0이 관리하는 파티션이고, s1로 표시된 파티션은 서버 1이 관리하는 파티션이다.
그리고 s0_x, s1_x는 같은 서버의 몇번째 가상 노드인지 구별하는 일련번호이다.
키의 위치로부터 시계 방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.
위 그림에서 k0가 저장되는 서버는 k0부터 시계방향으로 탐색하다 만나는 최초의 가상노드 s1_1가 나타내는 서버, 즉 서버1이다.
key0의 위치에서 링을 시계 방향으로 탐색한다.- 최초로 만난 가상 노드는
s1_1— 이건 링 위의 좌표일 뿐이다. - 매핑 테이블에서
s1_1 → 서버 1을 조회한다. - 따라서
key0은 서버 1에 저장된다.
링 위에서 찾는 건 노드고, 저장하는 곳은 그 노드가 가리키는 서버이다
가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 하지만 가상노드의 개수를 늘리면 저장공간이 더 많이 필요하게 되므로 시스템 요구사항에 맞는 개수를 적절히 선택해야한다.
재배치할 키 결정
서버가 추가되거나 제거되면 데이터 일부는 재배치해야 한다. 어느 범위의 키들이 재배치되어야 할까?
서버 4가 추가되었다면 s4(새로 추가된 노드)부터 그 반시계 방향에 있는 첫번째 서버 s3까지이다.
즉 s3 ~ s4 사이에 있는 키들은 s4로 재배치해야 한다.
서버 s1이 위 처럼 삭제되면 s1 ~ s0 사이에 있는 키들이 s2로 재배치되어야 한다.
마치며
안정 해시의 이점은 다음과 같다.
- 서버가 추가, 삭제될 때 재배치되는 키의 수가 최소화된다.
- 데이터가 균등하게 분포되므로 수평적 규모 확정성을 하기 쉽다.
- 핫스팟 키 문제를 줄인다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하가 생긴다. 하지만 안정해시는 데이터를 좀 더 균등하게 분배해 이 문제를 완화한다.
안정해시가 쓰이는 몇가지를 예로 들자면
- 아마존 DynamoDB의 파티셔닝 관련 컴포넌트
- 아파치 카산드라 클러스터에서의 데이터 파티셔닝
- 디스코드 채팅
- 아카마이 CDN
- 매그레프 네트워크 부하 분산기
