제 5장 - 안정 해시 설계

이번 포스트에는 5장, 안정 해시 설계에 대한 내용을 정리할 예정입니다.

예상 핵심 키워드 : 해시 설계, 서버 균등 분배

해시 키 재배치 문제

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

serverIndex=hash % N

 

나머지연산을 통해 키 값이 연산 값에 따라 분산된다.

 

-> 서버 풀의 크기가 고정되어 있을때 동작

-> 서버가 추가되거나 삭제되면 문제 => 캐시 미스

 

안정 해시

위의 해시 키 재배치 문제를 보완한 방법이다.

해시 테이블 크기가 고정될 때, 평균적으로 k / n개의 키만 재배치하는 해시 기술. (k = 키 개수, n = 슬롯)

 

-> 슬롯의 수가 바뀌면 대부분 키를 재배치

 

가정 

 

1. 해시 공간

해시 공간을 양 끝은 만나게 하면 해시 링이 만들어 지고, 이 해시 링을 바탕으로 설명하게 된다.

 

2. 해시 함수 

해시 함수 f로 SHA-1을 사용한다.

 

---

 

해시 서버

해시 함수를 이용해서 링 위의 위치에 대응

 

해시 키

해시 키 또한 링 위의 어느 지점에 배치할 수 있다. (해시 키 재배치 문제의 계산된 값 x)

 

서버 조회

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

 

서버 추가

서버가 추가가 된다면 키들 중 일부분만 재배치된다. 다시말하자면, 서버 A가 저장이 되고 그 앞에 있던 키는 서버 A에 새롭게 배치된다.

 

서버 제거

서버 추가와 비슷하다. 일부 키는 서버가 삭제되었을때 시계방향으로 돌면서 다른 서버에 재배치 된다. 

 

구현법의 문제

1. 서버 추가 or 삭제 => 파티션 크기 균등 유지 불가능.

2. 키의 균등 분포를 달성하기 어려움.

 

해결 방법

가상 노드

 

서버가 링 위에 여러 개의 가상 노드를 가진다. 가상 노드가 키가 저장될 서버가 되는 것이고, 가상 노드의 개수를 늘리며 키의 분포를 균등하게 만드는 원리이다. 

 

재배치 키 결정

그렇다면 서버가 삭제, 추가될 때 재배치할 키는 어떻게 정할까? 

추가된 서버의 반시계 있는 서버 안에 있는 키가 모두 영향에 들어간다.