수평적 규모 확장을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.
안정 해시가 고안된 이유 중 하나는 해시 키 재배치 문제이다.
해시 키 재배치(refresh) 문제
일반 해시 함수
N개의 캐시 서버가 있을 때 이 서버들에 요청을 균등하게 나누기 위해 일반 해시함수를 사용해 서버 인덱스를 부여할 수 있겠다.
서버 인덱스 = hash(key) % N그런데 이 방법은 서버 풀의 크기가 고정되어있고 키의 분포가 균등해야만 요청을 균등하게 잘 나눌 수 있다.
- 서버가 추가되거나 기존 서버가 삭제된다면?
- 서버 풀의 크기가 4였다가 3으로 줄면 키에 대한 해시값은 변하지 않아도 나머지 연산을 적용한서버 인덱스값이 달라질거고, 그러면 캐시 칼라이언트는 데이터가 없는 엉뚱한 서버에 접속하게 된다.
- 이것은 대규모 캐시 미스(cache miss)를 야기.
이 문제를 안정 해시가 해결해준다
안정 해시 (Consistent Hashing)
안정해시는 k는 키의 개수, n은 슬롯의 개수라고 할 때
해시 테이블의 크기가 조정되어도
평균적으로 오직 k/n 개의 키만 재배치 하는 해시 기술이다.
안정 해시의 동작원리
해시 공간과 해시 링
해시 공간의 양쪽을 구부려 붙여 만든 링이어서 해시 링이라고 한다
해시 서버
이 해시 함수 f를 사용해 우리가 정의한 키(서버 IP /이름 등)의 위치를 대응시키는 것이다.
서버 조회
어떤 키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫번째 서버다. (그림의 노드를 서버라고 생각하자)
서버 추가
서버가 새로 추가 된 경우 재배치해줘야 하는 키가 생긴다. 이번엔 반대로, 서버 기준 시계 반대방향으로 다른 서버가 나오기 전까지의 키들을 새로운 서버로 재배치하면 된다.
그림을 예시로 보자. 처음엔 노드 A, B만 있다가 노드 C가 추가 되었다.
새로 추가된 노드 C로부터 시계방향으로 가장 가까운 노드 A가
관리하던 키들 중, 노드 C 보다 시계 반대 방향에 있는 키들을 (주황 구간)
모두 C로 재배치한다.
서버 제거
하나의 서버가 제거될 때도 키 가운데 일부만 재배치 된다. 삭제되는 서버가 저장하고 있던 키들을 재배치한다. failure 도 이 상황에 포함된다.
기본 구현법의 문제들
안정 해시의 기본적인 절차는 다음과 같다.
- 서버와 키를 균등 분포 (uniform distribution) 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.
이 접근법에는 두가지 문제가 있다.
파티션의 크기를 균등하게 유지할 수 없다
파티션은 인접한 서버 사이의 해시 공간인데,
기본적인 구현법을 사용할 경우 서버 마다 할당 받는 파티션의 크기가 크게 차이날 수가 있다.
아까 그림처럼 처음에 노드 A, B, C가 있다가
C가 삭제되면 A의 파티션과 B의 파티션 크기가 균등하지 않게 된다.
키의 균등 분포를 달성하기 어렵다
두 번째 문제다. 안정해시의 기본 구현은 각 서버에 균등하게 키를 분포시키기가 어렵다.
이 두 문제를 해결하기 위해 제안된 기법이 가상노드/복제 라 불리는 기법이다.
가상 노드
가상 노드는 실제 노드 또는 서버를 가리키는 노드이다. 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다. 가상 노드의 개수가 늘어날 수록 표준 편차가 작아져 데이터가 고르게 분포된다.
가상노드 개수는 100~200개를 사용할 경우 표준 편차 값이 평균의 5%~10% 사이다.
타협적 결정 (tradeoff)
- 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다.
- 그러나 가상 노드 데이터를 저장할 공간이 더 많이 필요해질 것이다.
정리
이번 장에서는 안정 해시가 왜 필요하며 어떻게 동작하는지를 살펴 봤다.
안정해시의 이점
- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
- 핫스팟 키 문제를 줄인다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버에 과부하 문제가 생길 수 있다.
안정 해시의 유명한 사례
- 아마존 DynamoDB의 파티셔닝 관련 컴포넌트
- 아파치 카산드라 클러스터에서의 데이터 파티셔닝
- 디스코드 채팅 어플리케이션
- 아카마이 CDN
- 매그레프 네트워크 로드 밸런서
