5장 : 안정 해시 설계
수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.
해시 키 재배치(rehash) 문제
N개의 캐시 서버가 있따고 할 때 이 서버들에 부하를 균등하게 나누는 보편적 방법은 아래의 해시 함수를 사용하는 것이다.
이 방법은 서버 풀(server pool)의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작하지만, 서버가 추가되거나 기존 서버가 삭제되었을 경우 대규모 캐시미스가 발생하게 된다.
안정 해시
안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯(slot)의 개수이다.
안정 해시 동작 원리
해시 공간과 해시 링
해시 서버와 해시 키
서버 조회
서버 추가
서버 제거
기본 절차
서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.
기본 절차의 문제점
서버 추가 및 삭제시 파티션 크기를 균등하게 유지하는 것은 불가능
키 균등 분포를 달성하기가 어려움
이 문제를 해결하기 위해 제안된 기법이 가상 노드(virtual node) 또는 복제(replica)라 불리는 기법이다.
가상 노드
가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다.
마치며
안정 해시의 이점
서버가 추가 및 삭제될 때 재배치 키의 수가 최소화
데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
핫스팟 키 문제를 줄인다.
example
아마존 DynamoDB의 파티셔닝 관련 컴포넌트
Apach Cassandra 클러스터에서의 데이터 파티셔닝
Discord 채팅 어플리케이션
Akamai CDN
Meflev 네트워크 부하 분산기
Last updated
