Consistent Hashing (안정 해시)

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 존재할 때 이 서버들에 부하를 균등하게 나누는 보편적인 방법

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

이는 서버가 추가되거나 기존 서버가 삭제되면 문제가 된다.

serverIndex = hash(key) % (N-1) (-1: 삭제된 서버)

장애가 발생한 서버에 보관되어 있는 키뿐만 아니라 대부분의 키가 재분배되게 된다. 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 되는 것이다.

즉 노드 삭제 및 추가가 있는 경우 hash(key) % N 결과에 미치는 영향이 너무 커서 많은 수의 요청이 실패하여 캐시된 데이터가 다시 로드된다는 것이다. → 대규모 캐시 발생

---

안정 해시(consistent hash)

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

(전통적 해시 테이블은 노드의 수가 바뀌면 거의 대부분 키를 재배치한다.)

→ 재배치되는 키의 수가 최소화

 

이는 핫스팟 키 문제(불균형하게 부하가 높은 파티션)를 줄인다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버에 과부하 문제가 생길 수 있다.

 

안정 해시 기본적인 절차

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

 

https://faun.pub/consistent-hash-algorithm-and-go-implementation-a5a01d84845a

노드 추가 및 삭제가 데이터 범위에 미치는 영향을 살펴보자

 

노드 추가

 

https://faun.pub/consistent-hash-algorithm-and-go-implementation-a5a01d84845a

 

추가된 노드(node 5)와 이전 노드(node 4) 사이의 데이터에만 영향을 주게 된다.

 

노드 삭제

https://faun.pub/consistent-hash-algorithm-and-go-implementation-a5a01d84845a

삭제된 노드(node 3)와 이전 노드(node 2) 사이의 데이터에만 영향을 주게 된다.

 

위의 접근법에는 두가지 문제가 존재한다.

• 파티션의 크기를 균등하게 유지할 수 없다.
  • 파티션: 인접한 서버 사이의 해시 공간이다.
  • 어떤 서버는 굉장히 작은 해시 공간을 할당받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 가능하다는 것이다.
  • → 특정 서버가 삭제되면 한 서버의 파티션이 다른 파티션 대비 두배로 커지는 상황이 나타날 수 있다.
• 키의 균등 분포를 달성하기 어렵다.

 

위 문제를 해결하기 위해 제안된 기법은

가상 노드(복제) 기법

실제 노드 또는 서버를 가리키는 노드 (하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.)
→ 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 한다.

 

가상 노드의 개수가 늘어날 수록 표준 편차값이 떨어져 데이터가 고르게 분포된다. 가상 노드 개수는 100~200개를 사용할 경우 표준 편차 값이 평균의 5%~10% 사이다.

 

가상 노드의 개수를 늘리면 키의 분포는 더 균등해지지지만 (→ 수평적 규모 확장성을 달성하기 쉽다.),
가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. (tradeoff 가 필요)

🔗 참고

Consistent Hash Algorithm and Go Implementation

Memcached 에서의 Consistent Hashing