kingsubin

안정 해시 설계

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.

 

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 있다고 할 때, 이 서버들에 부하를 균등하게 나누는 보편적 방법은 serverIndex = hash(key) % N이다.

이 방법은 server pool의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때는 잘 동작한다. 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.

server pool의 크기가 변하면 키에 대한 해시 값은 변하지 않지만 나머지 연산을 적용한 서버 인덱스 값은 변할 것이다. 그 결과 대부분의 키가 재 분배되며, 대규모 cache miss가 발생할 수 있다.

안정 해시는 이러한 문제를 효과적으로 해결하는 기술이며 아래에서 다룬다.

 

안정 해시

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

 

해시 공간과 해시 링

해시 함수 f로 SHA-1를 사용한다고 하고 그 출력 값 범위는 x0, x1, … xn과 같다고 하자.

SHA-1의 hash space 범위는 0부터 (2^160 - 1)로 알려져 있다.

위 예시를 그림으로 표현하면 아래와 같다. hash space의 양쪽을 구부려 접으면 아래 그림과 같은 hash ring이 만들어진다.

 

예시

해시 서버, 해시 키 배치

예시로 서버 4개와 키 4개를 해시 함수 f를 사용하여 링 위의 어떤 위치에 배치했다.

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

 

서버 추가

서버 제거

 

기본 구현법의 두 가지 문제

안정 해시 알고리즘의 절차:

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

 

이 접근법의 문제점:

• 서버가 추가되거나 삭제되는 상황을 감안하면 partition의 크기를 균등하게 유지하는 게 불가능하다.
• 키의 uniform distribution를 달성하기 어렵다. 이 문제를 해결하기 위해 제안된 기법이 virtual node 또는 replica라 불리는 기법이다.

 

가상 노드

하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

아래 예시는 두 개의 서버 s0, s1 각각 3개의 가상 노드를 만들어 해시 링에 배치했다.

k1가 저장되는 서버는 링을 시계방향으로 탐색하다 만나는 최초의 가상 노드 s1_1가 나타내는 서버 1이다.

 

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. standard deviation가 작아져서 데이터가 고르게 분포되기 때문이다. 100~200개의 가상 노드를 사용했을 경우 표준 편차 값은 평균의 5%~10%라고 한다. 가상 노드의 개수를 늘릴수록 표준 편차의 값은 떨어지지만 가상 노드 데이터를 저장할 공간이 더 많이 필요하게 되어 tradoff가 필요하다.

 

안정 해시의 이점

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

 

---

참고: 가상 면접 사례로 배우는 대규모 시스템 설계 기초