[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 5장. 안정 해시 설계

해시 키 재배치(rehash)문제

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

serverIndex = hash(key) % N (N은 서버의 개수)

• 이 방법은 서버 풀의 크기가 고정되어 있을 때 그리고 데이터 분포가 균등할 때는 잘 동작함.
  • 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.
• 1번 서버의 동작 중단 시 서버 풀은 크기가 3으로 변함.
• 그 결과 키에 대한 해시 값은 변하지 않지만 나머지 연산을 적용하여 계산한 서버 인덱스 값은 달라질 것으로 예측 가능하다.
• 따라서 1번 서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다. 그 결과 대규모 캐시 미스가 발생 가능.
• 안정해시는 이용하여 이러한 문제를 해결 가능.

안정해시

안정해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯의 개수이다. 이와는 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다.

해시 공간과 해시 링

• 해시함수는 f로는 SHA-1을 사용한다고 하고, 그 함수의 추력 값 범위는 x0, x1 … xn과 같다고 하자.
• SHA-1의 해시공간 범위는 0부터 $2^{160}$-1까지라고 알려져있다. 이 공간의 양쪽을 구부려 접으면 해시 링이 만들어진다.

해시 서버

• 이 해시 함수 f를 사용하면 서버 IP나 이름을 이 링 위의 어떤 위치에 대응시킬 수 있다.

해시 키

• 여기 사용된 해시 함수는 “해시 키 재배치 문제”에 언급된 함수와는 다르며, 나머지 연산 %은 사용하지 않고 있음을 유의하자.
• 캐시할 키 key0, key1, key2, key3 또한 해시 링 위의 어느지점에 배치할 수 있다.

서버 조회

어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계방향으로 링을 탐색해나가면서 만나는 첫번째 서버이다. 따라서 key0는 서버0에 저장되고, key1은 서버1에 저장된다.

서버 추가

• 서버가 추가되더라도 키 가운데 일부만 재배치하면 된다.
• 만약 서버 4가 추가된다면 key0만 재배치됨을 알 수 있다. 그 이유는 서버 4가 추가된 후에 key0의 위치를 기준으로 시계방향으로 순회했을 때 처음 만나게 되는 서버가 서버4이기 때문이다. 다른 키들은 재배치 되지 않는다.

서버 제거

• 서버가 제거되더라도 키 가운데 일부만 재배치됨.
• 서버1이 제거되었을 때 추가때와 마찬가지로 key1만이 서버2로 재배치된다.

기본 구현법의 두가지 문제

안정 해시 알고리즘의 기본절차

• 서버와 키를 균등분포 해시 함수를 사용해 해시 링에 배치한다.
• 키의 위치에서 링을 시계방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.

이 접근법에서 생기는 문제점은

• 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지 불가
  • 파티션은 인접한 서버 사이의 해시 공간이다. 어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당받는 상황이 가능하다는 것이다.
• 키의 균등 분포 달성 취약
  • 때에 따라 한 서버는 아무 데이터도 갖지 않는 반면, 대부분의 키를 한 서버에 보관하게 될 수 있다.
• 이를 해결하기 위해 제안된 기법이 가상노드(virtual node) 또는 복제(replica)

가상노드

• 가상노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상노드를 가질 수 있다.
• 하나의 서버가 3개의 노드를 가지게 된다면 각 서버는 하나가 아닌 여러개 파티션을 관리 해야 함. 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.
• 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다.
  • 가상 노드의 개수를 늘릴 수록 표준 편차의 값은 떨어지지만 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. 따라서 타협적 결정 (trade off)가 필요하다.

재배치할 키 결정

• 서버가 추가되거나 제거되면 데이터 일부의 재배치 필요성
• 서버 추가
  • 추가된 노드부터 그 반시계 방향에 있는 첫번째 서버
• 서버 삭제
  • 삭제된 노드부터 그 반시계 방향에 있는 첫번째 서버

안정 해시의 이점

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

안정 해시의 예시

• 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
• 아파치 카산드라 클러스터에서의 데이터 파티셔닝
• 디스코드 채팅 어플리케이션
• 아카마이 CDN
• 매그레프 네트워크 부하 분산기