[가상면접 사례로 배우는 대규모 시스템 설계] 안정 해시

1. 해시 키 재배치 문제에 대해 이해한다
2. 안정 해시에 대해 이해한다.
   a. 안정 해시의 문제점과 해결 방법에 대해 이해한다.

해시 키 재배치 문제

캐시 서버가 3개이고 나머지 연산을 사용해서 해시함수를 만든 경우를 가정해서 해시 테이블을 작성하면 아래와 같다.

나머지 연산을 이용한 해시 함수 ?
server_idx = hash_key % N (N은 서버의 개수)

key	hash key	server idx
apple	123841	1
yujin	123482	2
seju	123153	3
study	123224	1
..	..	..

이때 만약 서버의 개수를 1개 줄인다면? (server_idx=3 삭제)

key	hash key	server idx
apple	123841	1
yujin	123482	2
seju	123153	1
study	123224	2
..	..	..

study 는 원래 server_idx=1 이었는데, 2로 변경되었다.

영향을 받아야 하는건 server_idx=3 에 해당하는 key들 뿐 인데, 모든 key에 대해 영향을 주게 되었다. study는 server_idx=1 에 캐시되어 있었는데 이제 2에서 조회하게 되었으므로, cache miss 가 발생하게 된다.

안정 해시

• 안정 해시는, 서버가 죽었을때, 서버에 연결된 키들만 재배치하는 해시 기술이다
• 전체 해시key 공간에 대해 원으로 이어 붙이고 그 곳곳에 서버를 배치한다. (균등분포)
  • 원으로 이어 붙이고 를 이해하기 (야매 예시)
    0~128 까지 공간을 해시 키로 가질 수 있을 때, 0~128을 직선 위에 차례로 배치한다.
    그 후 직선의 양 끝을 잡고 원으로 만들어 0과 128을 만나게 한다.

특징

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다
• 핫스팟 키 문제를 줄인다

흐름

키는 키의 위치로부처 시계방향으로 링을 탐색해 가장 처음 만난 서버를 사용한다.

서버가 추가되는 경우

• s0으로 가던 key0 이 s4를 향하게 됨
• s3~s0 사이에 있던 key들이 s4를 기점으로 나뉘어짐
  • s3~s4 영역의 key는 s4를 사용
  • s4~s0 영역의 key는 s0를 사용
• 이 구획 외의 다른 키들은 영향을 받지 않음

서버가 삭제되는 경우

• key1은 원래 s1을 향했는데, s1이 사라짐
• key1은 시계방향으로 서버를 탐색하고, s2를 만남
• 다른 키들은 재배치되지 않음

안정 해시의 문제점

1. 파티션의 크기를 균등하게 유지하는 것이 불가능하다.
   • 파티션은, 하나의 서버가 맡고 있는 해시 공간의 크기이다.
2. 키의 균등분포를 달성하기 어렵다
   • 상황에 따라 s1에게 할당된 key의 개수는 100개인데, s2에게 할당된 key의 개수는 2개일 수 있다.

책에서 제안한 해결방법

가상 노드(virtual node) 사용하기

• 실제 노드 또는 서버를 가리키는 노드
• 하나의 서버는 링 위에서 여러개의 가상 노드를 가질 수 있다.
  • 가상 노드의 개수를 늘릴수록 키의 분포는 점점 균등해진다.( 표준편차가 작아지면서 데이터가 고르게 분포)
• 노드가 너무 많은건 공간 낭비이니 적절히 조정해야 한다.
• consistent-hashing-why-are-vnodes-a-thing