안정 해시 설계

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

1. 해시 키 재배치(rehash) 문제

• N개의 캐시 서버가 있을때, 해당 서버에 부하를 균등하게 나누는 보편적 방법은 해시 함수를 사용하는 것
  • serverIndex = hash(key) % N (N은 서버의 갯수)
• 위 방법은 서버 풀 (server pool)의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때 잘 동작
• 하지만 서버가 추가 or 삭제되면, 문제 발생
  • moudular 값을 N -> N-1 or N+1 로 변경
  • 기존 키가 대부분 재분배 -> 캐시 미스 발생

2. 안정 해시

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

해시 공간과 해시 링

• 해시 함수 f로 SHA-1을 사용한다고 가정했을 때, 출력 값의 범위는 $0$ ~ $2^{160}-1$ 이라고 알려져 있음 -> 해시 공간 (hash space)
• 해당 출력의 양 끝단을 이어서 ring 형태로 만들면 그것을 해시 링 (hash ring)이라고 한다.

해시 서버

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

해시 키

• 캐시할 키 key0, key1, key2, key3또한 해시 링 위의 어느 지점에 배치 가능 (그림 5-6)

서버 조회

• 어떤 키가 저장되는 서버는 해당 키의 위치로부터 시계방향으로 링을 탐색해 나가면서 만나는 첫 서버 (그림 5-7)

서버 추가

• 위 2. 안정 해시 설명에 의하면 서버 추가 시 일부 키만 재할당 되어야 함
• 그림 5-8을 보면 서버 4가 추가된 이후 key0만 재배치되는 것을 알 수 있다.

서버 제거

• 서버 제거시에도 일부 키만 재배치
• 그림 5-9를 보면 서버1이 제거 되었을 때, key1만이 서버 2로 재배치 됨

기본 구현법의 2가지 문제

• 안정 해시 알고리즘은 MIT에서 처음 제안

기본 절차

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

문제점

1. 서버가 추가되거나 삭제되는 상황을 감안하면, 파티션의 크기를 균등하게 유지하는 것이 불가능
2. 키의 균등 분포(uniform distribution)를 달성하기 어렵다.

해결법 : 가상 노드

• 가상 노드(virtual node)는 실제 노드 또는 서버를 가리키는 노드로써, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
• 가상 노드의 개수를 늘리면 키의 분포는 점점더 균등해짐
  • 표준편차(standard deviation)가 작아져서 데이터가 고르게 분포되기 때문
• 문헌에 따르면, 100~200개의 가상 노드를 사용했을 경우 표준 편차 값은 평균의 5~10% 사이임
• 가상 노드 개수 증가 -> 표준 편차 감소하지만, 데이터를 저장할 공간은 줄어듦
  • tradeoff 결정이 필요

3. 마치며

안정 해시의 이점

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화
• 데이터가 보다 균등하게 분포하므로, 수평적 규모 확장성 달성 용이
• 특정 샤드에 대한 접근이 지나치게 발생하는 핫스팟(hotspot) 키 문제를 줄임

안정해시를 사용하는 제품

• Amazon DynamoDB의 파티셔닝 관련 컴포넌트
• Apache Cassandra 클러스터에서의 데이터 파티셔닝
• Discord 채팅 어플리케이션
• Akamai CDM
• Meglev 네트워크 부하 분산기

참고자료

• 알렉스 쉬, 가상 면접 사례로 배우는 대규모 시스템 설계 기초 5장