[Algorithm] consistent hash (hash ring)

#자료구조/알고리즘

consistent hash은 DB의 샤딩 같은 분산 저장에 응용되는 테크닉이다. hash ring이라고도 부른다.

대표적인 대형 분산 DB인 Dynamo와 Cassandra가 이 방식으로 샤딩을 구현한다.

문제

예를 들어, 데이터를 특정 조건을 기준으로 각각의 노드-샤트에 나눠서 저장한다고 가정해보자.

https://binux.tistory.com/119
그러면 데이터의 특정 샤드 키를 기준으로 해시값을 생성하고, 그 값을 각각의 샤드에 저장하는 것이 일반적인 방법이다.

가령, 샤드 키가 정수고 샤드가 3개라면 나머지 연산(x%3) 을 통해 0~2의 해시값을 추출해서 저장할 수 있을 것이다.

그런데 샤드가 2개 늘어서 5개가 된다면 어떨 것 같은가?
그러면 해시 계산법도 샤드 개수에 맞춰 변경될텐데, (x%5) 기존 저장 데이터들을 바뀐 해시값으로는 매칭시킬 수가 없다.

그렇다고 샤드가 바뀔때마다 해시값에 맞춰서 데이터 재배치를 계속 돌리는 것도 말이 안되는 방법이다.

hash ring은 조금 독특한 방법으로 이러한 문제틀을 해결한다. 재배치를 아예 피하지는 못하고, 좀 줄이는 정도다.

https://binux.tistory.com/119
일단 유한한 범위를 가지는 실수 해시값을 추출하게끔 만든다. 예를 들어 0~1로 범위를 잡을 수 있겠다.

그리고 샤드가 3개라면, 각각의 샤드는 해시값 영역을 가진다. 1샤드는 0~0.3, 2샤드는 0.3~0.6, 3샤드는 0.6~1 같은 식으로 할당하고, 각각의 해시값을 저 범위에 들어가는 샤드로 매칭시키는 것이다.

https://binux.tistory.com/119
이 구조에서 샤드가 추가되면, 적당히 어느 범위에 새로운 샤드의 영역을 부여해준다.
0.6~1를 차지하던 3샤드의 범위를 가져가서 0.8~1 영역을 배정하고, 해당 위치로 매칭되던 항목들만 재배치해주면 된다.

https://binux.tistory.com/119
그리고 샤드가 제거될 때는 그 영역에 있던 매칭 항목만 재배치해주면 된다.

근데 여기에는 문제가 있다. 위의 그림 2가지만 봐도 알겠지만, 샤드가 추가되거나 줄어들다보면 샤드가 갖고있는 영역이 불균등하게 분포될 수 있다는 것이다.
hash ring은 이러한 단점을 극복하기 위해 vnode라는 매커니즘을 사용한다.

가상 노드라는 말인데, 그렇게 거창하지는 않다.

그냥 실제 샤드 하나마다 여러개의 vnode 영역을 잡아놓고, 자잘하고 랜덤하게 영역을 차지하게 두는 것이다.
그래서 해시값이 나오면 그 주변에 위치한 vnode의 실제 샤드에 저장하도록 한다.

범위를 더 잘게 쪼개고 흩뿌려서 집중을 줄이는 간단한 방법론이다.