수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술임
해시 키 재배치 문제
N개의 캐시 서버가 있다고 하자. 이 서버들에 부하를 균등하게 나누는 보편적 방법은 아래의 해시 함수를 사용하는 것임
serverIndex = hash(Key) % N (N은 서버의 개수이다)
키 | 해시 | 해시 % 4 (서버 인덱스) |
key0 | 18358617 | 1 |
key1 | 26143584 | 0 |
key2 | ㅤ | 2 |
key3 | ㅤ | 0 |
key4 | ㅤ | 1 |
key5 | ㅤ | 3 |
key6 | ㅤ | 2 |
key7 | ㅤ | 3 |
server 0 : key1, key3
server1 : key0, key4
server2: key2, key6
server3 : key5, key7
- 위의 방법은 서버 풀의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작한다.
- 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생김
- 예를 들어 1번 서버가 장애를 일으켜 동작을 중단했다면, 서버 풀의 크기는 3으로 변하고 그에 따라 키에 대한 해시값이 바뀌지는 않지만 나머지(%) 연산을 적용하여 계산한 서버 인덱스 값은 달라짐
server0 : key0, key1, key5, key7
server2: key2, key4, key6
server3: key3
위에 보이는 것과 같이 장애가 발생한 1번 서버에 보관되어 있는 키 뿐 아니라 대부분의 키가 재분배됨 → 대규모 캐시 미스가 발생.
안정 해시는 이 문제를 효과적으로 해결하는 기술임
안정 해시
위키피디아 : 안정해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술임
여기서 k는 키의 개수이고, n 은 슬롯(slot)의 개수다. 이와는 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치함
해시 공간과 해시 링
해시 함수 f 로는 SHA-1을 사용한다고 하고, 그 함수의 출력 값 범위를 x0 … xn 과 같다고 하면, 그 해시 값의 범위를 해시 공간으로 나타낼 수 있고 그 해시 공간을 구부려 접으면 해시 링으로 나타낼 수 있음
해시 서버
해시 함수 f를 사용하면 서버IP나 이름을 이 링위의 어떤 위치에 대응시킬 수 있다.
해시 키
캐시할 키 key0, key1, key2, key3 또한 해시 링 위의 어느 지점에 배치할 수 있다
서버 조회
어떤 키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.
서버 추가
위의 설명 내용에 따르면 서버를 추가하더라도 키 가운데 일부만 재배치하면 됨. 시계 방향으로 탐색해 나가면서 만나는 서버가 새로 추가한 서버가 아닌 기존 서버라면 재배치할 필요가 없으니까.
서버 제거
하나의 서버가 제거되면 키 가운데 일부만 재배치됨. 서버 1이 삭제되었을 때, 그 서버 1의 반시계 방향에 있는, 그리고 다른 서버 전에 있는 키들만 서버2로 재배치되고 다른 키들은 영향이 없음
기본 구현법의 두 가지 문제
기본 절차
- 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버임
위 접근법에는 두 가지 문제가 있음
- 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 게 불가능하다는 것. 여기서 파티션은 인접한 서버 사이의 해시 공간임. 어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 가능함
- 키의 균등 분포(uniform distribution)를 달성하기는 어렵다는 것
이 문제들을 해결하기 위해 제안된 기법이 가상 노드(virtual node) 또는 복제(replica)라 불리는 기법임
가상 노드
- 가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있음. 서버 0을 링에 배치하기 위해 S0 하나만 쓰는 대신 s0_0, s0_1, s0_2 세 개의 가상 노드를 사용. 마찬가지로 서버 1을 배치하기 위해 s1_0, s1_1, s1_2의 세 개 가상 노드를 사용함
- 따라서 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 함
- 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다. 그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 됨 ⇒ tradeoff임
마치며
안정해시의 이점
- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다
- 핫스팟(hotspot) 키 문제를 줄인다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다. 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄인다.