[System Design Interview] 5장 안정 해시 설계

안정 해시 사용 이유

수평적 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하고, 이를 위해 안정 해시가 사용 된다.

해시 함수란?

해시 함수는 임의의 길이의 입력값을 받아서 고정 크기의 출력값을 생성하는 수학 함수. e.g. SHA-256

해시 키 재배치 문제

N개의 캐시 서버가 존재할 때, 이 서버들에 부하를 균등하게 나누는 보편적 방법은 아래의 해시 함수를 사용하는 것이다.

4대의 서버를 사용할 때 위의 해시 함수의 결과값은 아래 표과 같이 나온다.

아래 그림은 키 값이 서버에 어떻게 분산되는지 보여준다.

이 방법은 서버 풀의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작한다.

하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다. 예를 들면 1번 서버가 장애를 일으켜 동작을 중단했다고 하자. 그러면 서버 풀의 크기는 3으로 변한다. 그 결과로, 키에 대한 해시 값은 변하지 않지만 나머지(%) 연산을 적용하여 계산한 서버 인덱스 값은 달라질 것이다.

figure 5-2를 보면 장애가 발생한 1번 서버에 보관되어 있는 키 뿐만 아닌 대부분의 키가 재분배되었다. 즉, 1번 서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 되고, 그 결과로 대규모 캐시 미스가 발생하게 된다.

안정 해시

안정 해시 : 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬록의 개수다.

 

해시 공간과 해시 링

해시 공간은 아래 그림과 같이 표현할 수 있다.

이 해시 공간의 양쪽을 구부려 접으면 아래와 같은 해시 링이 만들어진다.

해시 서버

해시 함수 f를 사용하면 서버 ip나 이름을 해시 링 위에 대응시킬 수 있다.

해시 키

여기 사용된 해시 함수는 "해시 키 재배치 문제"에 언급된 함수와는 다르며, 나머지 연산자는 사용하지 않고 있음에 유의한다. figure 5-6와 같이 캐시할 키 key0, key1, key3 또한 해시 링 위의 어느 지점에 배치할 수 있다.

서버 조회

어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.

서버 추가

서버를 추가하더라고 키 가운데 일부만 재배치하면 된다.

figure 5-8을 보면 새로운 서버 4가 추가된 뒤에 key0만 재배치됨을 알 수 있다.

서버 제거

하나의 서버가 제거되면 키 가운데 일부만 재배치된다.

기본 구현범의 두 가지 문제

• 서버가 추가되거나 삭제되는 상황에서는 파티션의 크기를 균등하게 유지하는 게 불가능하다.

• 키의 균등 분포를 달성하기가 어렵다는 것이다.

이 문제를 해결하기 위해 제안된 기법이 가상 노드 또는 복제라 불리는 기법이다.

가상 노드

• 가상 노드 : 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 사아 노드를 가질 수 있다.

figure 5-12를 보면 서버0과 서버1은 3개의 가상 노드를 갖는다. s0으로 표시된 파티션은 서버0이 관리하는 파티션이고, s1로 표시된 파티션은 서버1이 관리하는 파티션이다.

키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다. figure 5-13은 그에 해당하는 예제다.

 

• 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다.
  • 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다.
• 가상 노드의 개수를 더 늘리면 표준 편차의 값은 더 떨어진다. 그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다.
• 적절한 trade-off가 필요하다.

재배치할 키 결정

figure 5-14처럼 서버 4가 추가되었다고 해보자. s3부터 s4사이에 있는 키들을 s4로 재배치하여야 한다.

정리

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