[2019.03.14] Consistent hashing

Consistent hashing 이 나온 배경

DB의 부하 분산을 구현한다 생각해보자

가장 먼저 생각할 수 있는 것이 노드(=DB) 갯수에 따라 나머지 연산을 해쉬로 사용하는 것이다.

그런데 이런 경우 문제점이 노드 갯수가 추가되거나 삭제되었을 때를 생각해보자.

모든 노드에 저장 되어 있는 모든 아이템 i 개를 다시 해쉬 함수를 돌려 다시 저장해야한다.

확장성이 매우 떨어진다.

즉 위 방법에서는 노드의 추가 삭제가 발생하면 i개의 아이템 전부 다 저장 장소를 바꿔야한다.

이러한 아이템의 이동 횟수를 어떻게 줄일 수 없을까?

노드가 추가 삭제되어도 기존에 있는 노드들의 경우, 노드 안의 아이템들의 큰 위치 이동없이 일관되게 할 수 없을까?  

그래서 나온것이 Consistent hashing 이다.

Consistent hashing

아이템이 8개 있고 해쉬함수를 돌리면 0 ~ 1 사이의 값이 나온다 하자

노드 3개를 추가한다.

위의 경우 주어진 아이템 별로 반시계 방향에 있는 가장 인접한 노드가 해당 아이템을 책임진다.

만약 C노드가 사라질 경우 B가 4,8,3을 부담한다.

즉 노드 하나가 사라질 때 8개의 아이템을 전부 새로운 노드에 재할당하는 것이 아니라 인접한 노드가 책임을 져주는 구조다.

단 여기서 문제는 노드 C가 사라지면서 아이템 4, 8, 3을 노드 B가 혼자 전부 부담한다는 것이다.

그래서 A, B, C 노드를 2개로 분할해서 vNode 6개를 만든다. 

그리고 이를 링 적절히 or 랜덤하게 배치한다.

이렇게 되면 노드 C가 사라져서 vNode C-1, C-2가 사라진다해도 아이템 2, 3 을 A와 B가 나눠서 부담한다.

이런식으로 vNode 를 촘촘히 배치해서 문제를 해결하기도한다.

Consistent hash는 서버의 Load Balancing 에도 많이 사용된다.