수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.
해시 키 재배치 문제 (rehash)
해시 키 재배치 문제는 안정 해시 기술로 풀고자 하는 문제이다.
N 개의 캐시 서버가 있을 경우, 균등하게 부하를 나누기 위해서는 보편적으로 아래의 해시 함수를 사용한다.
특정 키가 보관된 서버를 알아내기 위해, 나머지 연산을 f(key) % N 과 같이 적용한 결과를 활용할 수 있다. 예를 들어 hash(key0) % 4 = 1 이면, 클라이언트는 캐시에 보관된 데이터를 가져오기 위해 서버 1에 접속해야 한다.
이 방법은 서버 풀 (server pool) 의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작하지만 서버가 추가되거나 기존 서버가 삭제될 경우에 문제가 생긴다. 예를 들어 기존 서버 1 이 동작을 중단한다면 서버 풀의 크기는 3으로 변동된다. 그 결과로 키에 대한 해시 값은 변하지 않지만 나머지 연산을 적용해 계산한 서버 인덱스 값은 달라질 것이다. 이렇게 될 경우 문제가 있던 서버 1 에 보관되어 있던 키 뿐만 아니라 대부분의 키가 재분배된다. 서버 1이 죽으면 대부분 캐시 클라이언트가 엉뚱한 서버에 접속하게 되며, 그 결과로 대규모 캐시 미스가 발생하게 될 것이다.
안정 해시는 이 문제를 효과적으로 해결하는 기술이다.
안정 해시
“안정 해시(consistent hash) 는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술이다. k 는 키의 개수이고, n 은 슬롯(slot) 의 개수다. 이와 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치한다.” - 위키피디아
해시 공간과 해시 링
해시 함수 f 로는 SHA-1 를 사용하고, 그 함수의 출력 값 범위는 x0, x1, … , xn 과 같다고 하자. (SHA-1 의 해시 공간(hash table) 범위는 0 ~ 2^160 - 1 까지로 알려져 있다.) 일렬로 x0 부터 xn 까지 공간을 나열하고 양쪽을 구부려 만나도록 접으면 해시 링(hash ring) 이 만들어진다.
해시 링 위에 해시 서버와 해시 키를 어느 지점에 배치하게 되면, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 가장 먼저 만나는 서버에 해시 키를 저장한다. 서버 조회 시에도 동일하게 해당 키의 위치로부터 탐색해 나가며 가장 먼저 만나는 서버가 해시 키가 저장된 서버이다.
만약 서버를 추가하게 되면 키 가운데 일부만 재배치하게 된다. 서버를 추가한 후 어떠한 키는 가장 먼저 만나게 되는 서버가 달라질 수 있으며, 이런 경우에 해당하는 키만 재배치 되고 나머지 키는 기존과 같은 서버에 남는다. (재배치 되지 않는다.) 서버 제거 시에도 키 가운데 일부만 재배치 되며 나머지 키는 영향이 없다.
기본 구현법의 두가지 문제
안정 해시 알고리즘은 MIT 에서 처음 제안되었으며, 기본 절차는 다음과 같다.
- 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다.
이 접근법에는 두 가지 문제가 있다.
- 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(인접한 서버 사이의 해시 공간)의 크기를 균등하게 유지하는 게 불가능하다.
어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 가능하다. 예를 들어 s0 과 s2 사이의 s1이 삭제되었을 경우 s2의 파티션이 다른 파티션 대비 거의 두 배로 커질 수 있다. - 키의 균등 분포를 달성하기 어렵다.
예를 들어 k1 의 시계 방향으로 s0, s1 가 있다면 가장 먼저 만나는 s0 에 k1 가 저장되고 s1 에는 아무 데이터도 저장되지 않을 것이다. k2, k3, k4 의 위치 사이에 서버가 존재하지 않으면 k4 다음에 존재하는 서버에 대부분의 키가 저장될 것이다.
이러한 문제를 해결하기 위해 제안된 기법이 가상 노드(virtual node) 또는 복제(replica) 기법이다.
가상 노드 (virtual node)
가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
s0 과 s1 은 각각 3개의 가상 노드를 갖는다고 하자. s0 을 링에 배치하기 위해 s0 하나만 쓰는 대신, s0_0, s0_1, s0_2 의 세 개의 가상 노드를 사용한다. 따라서 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 한다. 키의 위치로부터 시계 방향으로 링을 탐색하다 최초로 만나는 가상 노드가 해당 키를 저장할 서버가 된다.
가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 표준 편차(standard deviation)가 작아져 데이터가 고르게 분포되기 때문이다. 표준 편차는 데이터가 어떻게 퍼져 나갔는지를 보이는 척도다.
https://tom-e-white.com/2007/11/consistent-hashing 에 따르면 100~200 개의 가상 노드를 사용했을 경우 표준 편차 값은 평균의 5~10% 사이다. 가상 노드의 개수를 더 늘리면 표준 편차의 값은 더 떨어진다. 그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. 이에 대한 tradeoff 가 필요하며 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야 할 것이다.
재배치할 키 결정
서버가 추가되거나 제거되면 데이터 일부를 재배치 해야 한다. 어느 범위의 키들이 재배치 되어야 하는지 확인할 수 있다. 서버가 추가되거나 제거되면 반시계 방향에 있는 이전 서버 이후에 배치되어 있는 키들이 영향을 받는다.
안정 해시의 이점
- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포되므로 수평적 규모 확장성을 달성하기 쉽다.
- 핫스팟(hotspot) 키 문제를 줄인다. 특정한 샤드(shard) 에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다. 안정 해시는 데이터를 좀 더 균등하게 분배하기 때문에 이런 문제가 생길 가능성을 줄인다.
안정 해시 실사용 예시
