5장. 안정해시

5장. 안정해시

해시 키 재배치 문제

서버들에 부하를 균등하게 나누는 보편적인 방법

ServerIndex = hash(key) % N(서버개수)

• 이 방법은 서버 풀 크기가 고정되어 있고, 데이터 분포가 균동할 때는 잘 동작한다.
• 서버가 추가되거나 기존 서버가 삭제되는 경우 N의 개수가 변경되어 데이터의 분배가 한쪽으로만 치우질수 있는 문제가 발생한다.

안정 해시

수평적 규모 확장성을 달성하기 위해서 요청 또는 데이터를 서버에 균등하게 나누기 위한 보편적인 기술

정의

• 해시 키 재배치 문제를 효과적으로 해결할 수 있는 기술.
• 안정 해시는 해시 테이블의 크기가 조정될 때 평균적으로 오직 K(키의개수)/N(슬롯개수)개의 키만 재배치하는 해시 기술
• 전통적 해시 테이블은 슬롯의 수가 변경되면 대부분의 키를 재배치

작동원리

해시 공간과 해시 링

위의 해시 공간을 구부려 놓으면 원 형태의 해시 링이 만들어진다.

해시서버

서버를 링위에 배치한다.

해시 키

캐시할 키를 링의 어느 지점에 배치할 수 있다.

서버조회

해당 키의 위치로 부터 시계방향으로 돌며 지정된 서버를 찾는다.

서버 추가

서버가 추가되면 일부 키만 재배치하면 된다.

서버 제거

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

기존 구현법의 2가지 문제점

기본절차

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

문제점

• 서버가 추가되거나 삭제되는 경우 파티션의 크기를 균등하게 유지하는게 불가능하다.
• 파티션: 인접한 서버와 서버 사이의 해시공간
• 어떤 서버는 큰 해시 공간을 할당 받고 어떤 서버는 작은 해시 공간을 할당받는다.
• 키의 균등 분포 또한 달성하기 힘들다.
• 이 문제를 해결하기 위해 가상 노드 또는 복제 기법이 등장한다.

가상노드

실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러개의 가상 노드를 가질 수 있다.

• 서버 0은 서버 0_0, 0_1, 0_2 3가지의 가상 노드를 갖고 있으며
• 서버 1도 서버 1_0, 1_1, 1_2 3가지의 가상 노드를 갖고 있다.
• 키가 각각의 가상노드에 접근하게 되면 가상 노드는 실 서버로 연결해준다.
• 가상 노드 개수를 늘리면 키의 분포는 점점 균등해진다.
• 그러나 저장 공간이 그만큼 늘어나기 때문에 가상 노드 개수를 적절히 조정해야 한다,

재배치할 키 결정

서버가 추가되거나 제거시에는 키는 시계 방향 기준으로 인접한 서버에 재배치 되어야 한다.

안정 해시 장점

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

사진 출처: https://donghyeon.dev/%EC%9D%B8%ED%94%84%EB%9D%BC/2022/03/20/%EC%95%88%EC%A0%95-%ED%95%B4%EC%8B%9C-%EC%84%A4%EA%B3%84/