대규모 시스템 설계 기초 - 5장

5장. 안정 해시 설계

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요

이를 위해 사용되는 안정 해시의 필요성과 동작 방식을 살펴보자.

 

해시 키 재배치 문제

아래의 해시 함수를 사용해 N개의 캐시 서버에 부하들 균등하게 나누는 방법을 생각해보자.

serverIndex = hash(key) % N

총 4대의 서버를 사용하는 경우, 아래와 같이 키가 분산 됨

 

 

서버 풀의 크기가 고정되어 있을 때나 데이터 분포가 균등할 때는 잘 동작

서버가 추가되거나 기존 서버가 삭제되면 문제가 생김

 

e.g. 1번 서버가 동작을 중단한 경우, 대부분의 키가 재분배되어 대규모 캐시 미스 발생

 

 

안정 해시

해시 테이블 크기가 조정될 때 평균적으로 오직 k(키의 개수)/n(slot 개수) 개의 키만 재배치하는 해시 기술

 

 

해시 공간과 해시 링

SHA-1와 같은 해시 함수를 사용할 때, 해시 공간을 그림으로 나타내면 아래와 같다.

 

해시 공간의 양쪽을 구부려 접으면 다음과 같이 해시 링이 만들어진다.

 

 

해시 서버

서버를 링 위에 배치하면 다음과 같다

 

해시 키

해시 키도 다음과 같이 해시 링 위에 배치할 수 있다.

 

서버 조회

키는 해당 키의 위치로부터 시계 방향으로 링을 탐색하나가면서 만나는 첫 번째 서버에 저장된다

 

서버 추가

서버를 추가해도 일부 키만 재배치하면 된다

 

 

서버 제거

서버가 제거되면 일부 키만 재배치하면 된다

 

기본 구현법의 두 가지 문제

1) 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 게 불가

 

2) 키의 균등 분포를 달성하기 어려움

 

가상 노드

가상 노드를 통해 위 두 가지 문제를 해결할 수 있음

 

하나의 서버가 링 위에서 여러 개의 가상 노드를 갖도록 함

각 서버가 하나가 아닌 여러 개 파티션을 관리

 

가상 노드의 개수를 늘릴수록 키의 분포는 균등해짐

(100개의 가상 노드 사용시 표준 편차가 평균 10%, 200개의 가상 노드 사용시 표준 편차가 평균 5%)

 

그러나 가상 노드의 개수를 늘리면 저장할 공간이 더 많이 필요하기 때문에 타협적 결정이 필요함

 

 

마치며

안정 해시의 이점을 정리하면 아래와 같다

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화됨
• 데이터가 보다 균등하게 분포되므로 수평적 규모 확장성을 달성하기 쉽다
• 핫스팟 키 문제를 줄인다 (특정한 샤드에 대한 접근이 지나치게 빈번하지 않게 해줌)