Ch05. 안정 해시 설계

해시 키 재배치 문제

N개의 캐시 서버가 있다고 가정하면, 이 서버에 부하를 균등하게 나누는 보편적인 방법은 해시 함수를 이용하는 것이다.

serverIndex = hash(key) % N(N=서버 갯수)

• 특정한 키가 보관된 서버를 알아내기 위해서는 나머지 연산을 적용해야 한다.
• 서버 풀의 크기가 고정되어 있을 때와 데이터 분포가 균등할 때는 잘 동작하나, 서버가 추가되거나 삭제되면 문제가 된다.

AS-IS

서버 인덱스	0	1	2	3
서버	server0	server1	server2	server3
키	key 0, key 4	key 1, key 5	key 2, key 6	key 3, key 7

To-BE(Server 1 장애)

서버 인덱스	0	1	2
서버	server0	server2	server3
키	key 0, key 1, key 5, key 7	key 2, key 4, key 6	key 3

 

안정 해시

안정 해시란? 해시 테이블 크기가 조절이 될 때 평균적으로 오직 k/n개의 기반 재배치하는 해시 기술이다.(k = 키의 개수, n = 슬롯의 개수)

 

해시 공간과 해시 링

해시 링

• 해시 공간: SHA-1 함수를 사용한다는 기준으로 출력 범위는 0 ~ 2^160-1이다.
• 해시 링: 해시 공간의 양쪽을 구부려 접으면 나오는 그림

해시 서버

• 해시 함수 f를 사용해 서버 IP나 이름을 링 어떤 위치에 대응시킬 수 있다.

해시 키

• 나머지를 구하는 연산을 하지 않고 해시 키는 위 어느 위치/지점에 배치가 가능하다.
• 해시 키를 f(x) 함수에 적용해 각 해시 링 위로 적용할 수 있다.

서버 조회

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

서버 추가

• 서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.
• 새로운 S4 번서버가 추가되더라도 K0번만 재배치된다.

서버 제거

• 하나의 서버가 제거되면 키 가운데 일부만 재배치된다.
• S1이 제거되어도 K1(키 1)만 S2로 재배치되는 것을 볼 수 있다.

문제점

1) 서버가 추가되거나 삭제되는 상황에서 파티션 크기가 균등하게 유지하는 게 불가능하다.

2) 키의 균등 분포를 달성하기 어렵다.

 

가상노드

• 가상노드란 실제 노드 또는 서버를 가리키는 노드로 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다
• 각 서버는 하나가 아닌 여러 개의 파티션을 관리한다.
• 키의 위치로부터 시계 방향으로 링을 탐색하다가 만나는 최초의 가상노드가 해당 키가 저장될 서버가 된다.
• 가상 노드의 개수를 늘리면 키의 분포는 점점 균등해진다.
  • 단 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것으로 적절한 갯수를 조절하는 것이 중요하다.