수평 확장을 위해서 분산 처리를 효율적이게 해야한다. 균등하게 분배해야하며 그 과정에서 해싱은 중요하다.

The rehashing problem

어떤 서버에게 요청을 처리하게 할지 hash로 한다 가정하자

$serverIndex = hash(key) \% n$

$hash(key)$	$hash(key) \% 4$
17	1
12	3
14	2
10	2
1	1
4	0

serverIndex 기준으로 아래와 같다.

0	1	2	3
4	17	10, 14	12

그러면 만약에 1번 서버가 죽어서 $\% 4$를 $\% 3$으로 변경했다 가정하자

$hash(key)$	$hash(key) \% 3$
17	2
12	0
14	2
10	1
1	1
4	1

serverIndex 기준으로 아래와 같다.

0	1	2	3
12		1, 4, 10	14, 17

모든 기기들이 새로운 서버에 배치되었다. 그러면 기존에 연결되어있던 기기들은 캐시가 아무런 의미가 없어지게 되었고 fetch도 새로해야할 것이다.

서버 1에 연결된 것들만 남은 서버에 배치하면 되는 것이 오히려 성능을 감소시킨 것이다.

이렇든 rehashing을 할 때, 일관성있게 해시값을 주는 것이 중요하다.

Consistent hashing

위키피디아에 기반한 설명도 있지만 내 멋대로 해석하겠다.

slot이 resizing 되었을 때 k/n 만큼만 이동하게 하는 것

위에서 처럼 resize 되었다고 많은 변화가 일어나지 않게 하는 것

위키피디아 링크:

Consistent hashing - Wikipedia

en.wikipedia.org

---

다음과 같이 $x_0$ ~ $x_n$ 까비 해쉬 값이 들어 갈 수 있는 공간을 원으로 표현해보자.

그리고 이제 각 구역별로 해당되는 Hash 서버를 배치하자!

그런 다음에 각 hash 서버에 키를 매핑하면 아래와 같을 것이다. 위에서 얘기한 것과 달리 moduler 연산이 들어가지 않는다.

대신 매핑 방식은 시계방향으로 제일 가까이 있는 hash 서버에 매핑하는 거다.

만약 새로운 hash 서버가 생긴거나 삭제된다면 아래 두 사진과 같이 매핑이 변경될 것이다.

---

문제점

1. 파티션 크기 불균형

아래 이미지와 같이 서버가 추가되거나 삭제되면 파티션 간 크기 불균형이 온다.

2. 데이터(key) 분포의 불균형

해시 함수가 항상 고르게 분포되게 할 수 없고 어느 한 곳에만 집중될 수 있다.

결국 모든 문제는 해싱 때문에 하나의 서버로의 부하가 집중된다는 문제로 귀결된다.

하지만 이것도 Virtual Node 로 해결 가능하다고 한다.

---

Virtual Node

가상 노드를 구성하면 아래 이미지와 같을 것이다.

가상 노드가 많을 수록 노드 사이의 파티션의 크기가 고르게 분포될 것이다. 보통 100-200개를 두면 표준 편차가 5-10%정도라고 한다.

Find affected keys

서버가 삭제되거나 추가될 때 어떤 키를 재배치 해야할 까?

추가될 때: 추가된 서버를 기준으로 반시계 방향으로 서버가 나오기 전까지의 데이터(key)를 새로운 서버에 매핑 -> ($server_{prev}$, $server_{new}$] 를 $server_{new}$로

삭제할 때: 삭제되는 서버를 기준으로 반시계 방향으로 서버가 나오기 전까지의 데이터를 다음 서버에 매핑 -> ($server_{prev}$, $server_{removed}$] 를 $server_{next}$로

---

고전 Ring 형식의 Consistent Hashing

위에서 계속 얘기한 방식은 고전 방식의 Ring을 사용한 Consistent Hashing 전략이다.

https://www.cs.princeton.edu/courses/archive/fall09/cos518/papers/chash.pdf

cs.princeton.edu

최신 전략

updating…