Consistent hashing algorithm
High level design에서 consistent hashing은 아래와 같이 동작한다.
- 해시 함수의 출력은 해시 링에 배치됨
- 노드의 해시값은 해시 링에서 노드의 위치를 할당하는데 사용됨
- 데이터 개체의 키는 동일한 해시 함수를 사용해 해시 링에서 키의 위치를 찾기 위해 해시됨
- 해시 링은 노드가 발견될 때까지 키 위치에서 시작해 시계 방향으로 탐색됨
- 데이터 객체는 발견된 노드에서 저장되거나 검색됨
Requirements
Funtional Requirements
- 캐시 서버를 수평적으로 확장하는 알고리즘 설계
- 알고리즘은 네트워크에서 핫스팟 발생을 최소화 해야 함
- 트래픽의 부하를 동적으로 처리해야 함
- TCP/IP와 같은 기존 네트워크 프로토콜을 재사용
Non-Functional Requirements
- 확장성
- 고가용성
- 짧은 지연시간
- 신뢰성
Consistent Hashing
일관된 해싱은 데이터와 노드를 해시 링에 할당하여 동작하는 분산 시스템 기술이다. 일관된 해싱은 총 노드 수가 변경될 때 리해싱을 해야하는 키의 수를 최소화 한다. MurmurHash와 같은 가볍고 빠르고 균등한 해시 함수를 사용해 해시 링에서 노드 및 키의 위치를 찾는다. 해시 함수의 출력 범위는 충돌을 방지하는 적절한 크기로 주어져야 한다.
해시 함수의 출력 공간은 해시 링을 형성하기 위해 고정된 원형 공간으로 간주된다. 해시 링은 유한한 수의 위치를 갖는 것으로 간주된다. 해시 함수가 2^10의 범위를 생성한다고 가정하면 해시 링은 0부터 1023까지의 숫자 범위를 가진 가상 원이다.
데이터의 키는 동일한 해시 함수를 사용해 해시 링에서 키의 위치를 찾기 위해 해시된다. 해시 링은 키의 위치부터 노드를 찾을 때 까지 시계 방향으로 이동한다. 데이터는 발견된 노드에 저장된다. 노드의 장애는 장애가 발생한 노드에서 바로 인접한 노드로 데이터를 시계 방향으로 이동 시키는 결과를 낳는다. 해시 링의 나머지 노드는 영향을 받지 않는다.
새 노드가 프로비저닝되어 해시 링에 추가되면 새 노드의 범위 내에 있는 키는 바로 옆 노드에서 시계 방향으로 이동한다. 일관된 해싱은 이런 특성으로 인해 노드당 평균적으로 number of data / number of node의 데이터를 저장한다.
일관된 해시에서 노드가 균일하게 분포되지 않을 가능성도 존재한다. 매우 많은 양의 트래픽을 수신하는 노드는 핫스팟이 되어 노드에 연쇄적인 장애를 발생시킬 수 있다. 이런 문제를 회피하기 위해 일관된 해싱 알고리즘은 가상 노드라는 개념을 도입해 시스템의 로드 밸런싱을 개선하고 핫스팟을 방지한다. 가상 노드에 대응되는 노드는 노드의 성능에 따라 결정된다. 즉, 용량이 더 큰 노드에는 해시 링에서 더 많은 위치가 할당된다.
노드가 제거되거나 추가될 때 데이터를 인접한 노드에 복제해 데이터 이동을 최소화 시킬 수 있다. 일관된 해싱은 이런 특성을 통해 동적으로 부하 문제를 해결한다.
BST를 통해 데이터 구조는 해시 링에 노드 위치를 검색할 수 있게 된다. BST는 중앙 집중식 고가용성 서비스에 저장되거나, 각 노드에 저장되며 노드 간의 상태 정보는 가십 프로토콜을 통해 동기화 한다.
What Is The Asymptotic Complexity Of Consistent Hashing?
| Operation | Time Complexity |
|---|---|
| Add a node | O(k/n + logn) |
| Remove a node | O(k/n + logn) |
| Add a key | O(logn) |
| Remove a key | O(logn) |
Pros and cons of Consistent Hashing
Pros
- 수평적 확장성
- 노드 수 변경 시 데이터 이동 최소화
- 데이터의 빠른 복제 및 분할
- 가상노드의 장점 :
- 노드 추가 / 제거 시 균등한 부하 분산
- 이기종 노드 간 공정한 부하 분산
Cons
- 핫스팟으로 인한 계단식 장애
- 노드와 데이터의 불균일 분포
- 노드 성능의 이질성을 인식하기 어려움
- 가상노드의 단점 :
- 특정 데이터가 hot일 경우 해당 데이터에 대한 요청은 모두 동일한 노드로 전달됨
- 가상 노드의 용량 계획이 어려움
- BST의 유지 및 관리로 인한 복잡성 증가
- 고유한 물리 노드 식별을 위한 추가 복잡성으로 인해 복제가 어려움
- 가상 노드의 다운타임이 링의 여러 노드에 영향을 미침
Consistent Hashing Optimization
Multi-Probe Consistent Hashing
Multi-Probe Consistent Hashing(MPCH)는 키를 한 노드가 아닌 여러 노드에 매핑할 수 있도록 허용하여 노드 수가 적은 경우에 발생하는 불균형에 의한 부하를 대처한다.
MPCH는 각 키에 대해 해시 값에 가장 가까운 지점을 가진 노드에서 시작해 원을 중심으로 이동하면서 원 안의 여러 노드에 대해 조사한다. 처음 발견되는 k개의 노드를 식별해 키를 저장하게 된다. 키를 여러 노드에 매핑할 수 있도록 허용함으로써 MPCH는 노드 수가 적은 경우 기존의 일관된 해싱보다 더 나은 부하 분산을 달성할 수 있다. 하지만 각 키가 여러 노드에 저장되는 부분에 대한 스토리지 오버헤드가 발생한다.
Consistent Hashing With Bounded Loads
Consistent Hashing With Bounded Loads(CHBL)은 전체 해시 링의 평균 부하를 기준으로 해시 링의 노드가 받는 부하에 상한을 설정한다. 노드에 과부하가 걸리지 않는 한 요청의 분포는 일관된 해싱과 동일하다.
특정 데이터가 hot이 되면 특정 노드에 많은 양의 트래픽이 몰리며 서비스 저하가 발생할 수 있다. 노드에 과부하가 걸리면 들어오는 요청은 폴백 노드로 위임된다. 폴백 노드는 목록은 동일한 요청 해시에 대해 동일하다. 폴백 노드를 통해 hot 데이터의 오브젝트 캐싱 문제를 해결한다. 노드에 과부하가 걸리면 일반적으로 요청 해시마다 폴백 노드 목록이 달라지게 된다. 그러므로 과부하가 걸린 노드에 대한 요청은 단일 폴백 노드 대신 사용 가능한 노드에 분산된다.
