5장 - 안정 해시 설계

목표

수평적 규모 확장성을 달성하기 위해서 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.
➡️ 안정해시 설계를 통해 위의 목표를 달성해보자 = 안정해시에 대해 알아보자

안정해시에 대해 알아보기전에 기존 해시의 문제점에 대해 알아보자
보편적으로 N개의 캐시 서버가 있을때 serverIndex = hash(key) % N를 이용하여 특정 캐시서버에 접속하도록 분배한다.

서버 풀의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때는 잘 작동한다.

하지만 장애가 발생하면 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다.
대규모 캐시 미스가 발생하게 되는데 안정해시는 이를 해결하는 기술이다.

안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 해시 기술

k = 키의 객수 / n = 슬롯의 갯수

해시 테이블의 예시, bucket수는 4이고, slot수는 3이다.

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

안정해시 동작

동작원리를 알아보기위해 해시함수로 SHA-1을 사용 가정

출력값의 범위를 x0~xn까지로 가정하였을 때 해시 공간(버킷?)을 그림으로 표현하면 다음과 같다.

해시 공간을 양쪽으로 구부려 접어 해시 링이 만들어 진다.

해시 함수를 이용하여 서버를 링 위의 어떤 위치에 대응

해시할 키 또한 해시 링 위의 어느 지점에 배치 할 수 있다.

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

위의 규칙을 바탕으로 서버추가와 서버제거하면 다음과 같이 배치된다.

시계 방향으로 링을 탐색했을 때 만나는 첫 번째 서버를 키가 저장되는 서버로 사용한다면
아래와 같이 서버가 추가되었을때 k0의 서버는 s0에서 s4로 바뀌게 된다.

서버를 추가하더라도 키 가운데 일부만 재배치하게된다.

서버가 제거되면 일부만 재배치된다.

기본구현법 절차

이 접근법에는 두가지 문제가 있다.

서버가 추가 되거나 삭제되는 상황에서 파티션의 크기를 균등하게 유지하는게 불가능하다.
(위의 서버 제거 그림 참조 ➡️ 재배치 한 만큼의 파티션크기증가)
키의 균등 분포를 달성하기 어렵다.

문제를 해결하기 위해 제안된 기법이 가상 노드 기법이다.
가상 노드는 실제노드를 가리키는 노드로 하나의 서버는 여러 개의 가상 노드를 가질 수 있다.

아래는 3개의 가상노드를 갖는 가정하여 나타낸 그림이다. 실제로는 훨씬 큰값이 사용된다.

가상노드에서 접근도 크게 다르지 않다.

가상 노드의 개수를 늘리면 키의 분포가 점점 더 균등해진다.
표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다.

그러나 가상 노드가 증가하면 데이터를 저장할 공간은 더 필요하게 될 것으로 타협적 결정(trade off)가 필요

서버가 추가되거나 제거될때 어느 범위의 키들이 재배치 되어야할까?

안정 해시의 이점

실제 사용 예시