Consistent Hashing 일관된 해싱

배경

분산 처리 기법 중의 하나이다.
파티셔닝이나 로드 밸런싱 등 분산 처리에서 사용하는 방법 중 하나라고 할 수 있다.
Karger 등이 소개한 기법이고, 해당 논문은 여기서 볼 수 있다.

 

파티셔닝이나 로드 밸런싱을 할 때 Key를 기반으로 하면 문제가 생겨서 나온 방법이다.
예를 들어, 이름을 A~Z 로 정렬한 데이터를 파티셔닝 한다고 해보자.
이때 key를 ‘A’, ‘B’ … ‘Z’로 잡아서 파티셔닝을 하면 다음과 같은 문제가 생긴다.
파티셔닝의 목적은 데이터를 각 DB 노드들이 균등하게 들고 있을 때가 Best Case이다.
하지만 key를 특정 알파벳으로 하면, ’S’, T’ 등 특정 알파벳으로 데이터가 쏠리고(skewed), ‘X’, ‘Y’ 등 잘 쓰이지 않는 알파벳을 가진 DB 노드에는 데이터가 적게 들어가게 된다.

 

따라서 키 범위 기준으로 파티셔닝을 하면, 특정 패턴으로 hotspot 이 생긴다는 단점이 있다.
Consistent Hashing 은 이것을 해결하기 위해 나온 방법 중 하나라고 볼 수 있다.

 

 

Consistent Hashing 이 그래서 무엇일까

위에서는 키를 직접 범위로 잡으면 데이터가 쏠리는 문제가 있다고 했다.
Consistent Hashing 은 키를 직접 사용하는 대신, 키에 Hash 함수를 적용한다.
그리고 이 Hash 값에 DB 노드의 개수 n을 나머지 연산하여 나온 값으로 데이터를 저장한다.
말로 설명하는 건 어려우니 sudo 코드로 대충 작성하면 다음과 같다.

 

n = node_count
h = hash(key)
save( mod(h, n), data )

 

그림으로 나타내면 다음과 같다.

(데이터 중심 애플리케이션 설계 그림 6-3 을 참조했다.)

 

이렇게 하면 key의 범위에 상관없이 모든 DB 서버에 균등하게 데이터를 저장할 수 있다는 아이디어이다.
당연히 단점도 있는 방법인데, 아래에서 살펴보자.

 

단점

첫 번째 단점은 이렇게 파티셔닝을 하면 range로 검색하기 어려워진다는 것이다.
예를 들어, “Ab* ~ “Ac*”인 이름을 검색해야 한다면, Hashing 되어 있는 값으로 검색해야 하기 때문에 범위를 특정하기 어렵다.
대신 Hashing 값과 key 값을 미리 indexing 해놓는다면, range로 검색하는 것도 가능해진다.

하지만, 파티셔닝이나 로드밸런싱에서 가장 중요한 문제 중 하나인 Rebalancing에 단점이 있다.

 

Rebalancing 이란, “특정 노드를 추가하거나 제거해야 할 때, 기존에 파티셔닝 되어 있는 데이터를 어떻게 재분배할 것인가” 하는 문제이다.

Rebalancing 은 최소 아래처럼 실행할 수 있기를 기대한다.

• Rebalancing 이후에도 데이터가 균등하게 분포되어야 하고, 데이터 읽기/쓰기 요청 시 부하도 균등하게 분포되어야 한다.
• Rebalancing 도중에도 데이터는 읽기와 쓰기가 가능해야 한다.
• Rebalancing 은 빠르게 실행되어야 하고, 실행되는 도중에 네트워크와 CPU 부하를 최소화하면서 데이터를 옮겨야 한다.

 

하지만 Consistent Hashing 방법은 세 번째를 만족하지 못한다.
Rebalancing 이 오래 걸리고 이동해야 할 데이터가 너무 많기 때문이다.

 

예를 들어, 노드를 8대로 운영 중이라고 해보자.
그중 한 대가 문제가 생겨서 정상적으로 데이터를 받아올 수 없다고 하자.
그러면 문제가 생긴 노드의 데이터를 옮겨주어야 한다.
그런데 이제 노드는 7대이다. 그러면 모든 데이터의 hash 값에 대해서 mod 연산을 다시 해주고, 데이터를 옮겨야 할까?

 

이렇게 한다면 매우 오래 걸리고 비효율적이다.
실제로는 한 서버가 죽으면 바로 옆의 서버로 (7번 서버가 죽으면 8번 서버로. 위키피디아에서는 clockwise 방향이라고 하는 것 같다.) 일시적으로 데이터를 옮기고,
옮겨진 데이터만을 rebalancing 하거나 하는 방법 등으로 처리한다.
하지만 Consistent Hashing 아이디어 자체가 rebalancing 이 어렵긴 하다.

 

결론

당연히 모든 알고리즘은 장단점이 있겠지만,
파티셔닝뿐만 아니라 언어 레벨이나 로드밸런싱 등에서 가끔 등장하는 용어라서 알아두어서 나쁠 건 없을 것 같았다.
특히 분산처리 알고리즘에는 여러 가지가 있어서 흥미가 동하기도 했다.
부족한 내용이나 잘못 적은 내용은 추후에 수정하려고 한다.

 

 

참고 자료

• Consistent hashing - Wikipedia
• 데이터 중심 애플리케이션 설계 - 마틴 클레프만