Jump consistent hash

소개

대용량 메시지 처리를 위한 인프라 시스템 설계 때문에 consistent hash에 관심이 많습니다. 마침 CHARSYAM 님이 Consistent Hashing에 대한 기초 문서를 올리신 것을 보고, 관련 글을 만들어 보기로 마음을 먹었습니다. CHARSYAM님의 글의 심화 버전? 정도로 보시면 될 것 같습니다.

먼저 Karger Consistent hash를 간단히 다루고 나서, Jump consistent hash를 비교 소개하도록 하겠습니다. Jump consistent hash는 대용량 메시징 시스템 개발에 응용하고 있는 consistent hash 알고리즘으로, 2014년 구글에서 공개했습니다. Karger Consistent hash는 개념만 다룹니다. 자세한 내용은 CHARSYAM님의 문서를 참고하시기 바랍니다.

Karger Consistent hash

Consistent hashing은 Key의 집합을 K, 슬롯의 크기를 N 이라고 했을 때, N의 갯수가 바뀌더라도 대부분의 키들이 슬롯을 그대로 사용 할 수 있도록 만들어주는 해싱 기법을 의미합니다. Key를 파일, 슬롯을 파일서버로 생각하면 이해가 쉬울 겁니다.

대량의 파일을 다루는 시스템이 있다고 가정해 보겠습니다. 파일의 양이 많아지면, 여러 서버로 분산해서 저장을 해야 할 겁니다. 이 경우 파일을 찾는데 상당한 시간이 걸릴 수 있습니다. 10억 혹은 100억 건의 이미지를 저장하고 찾는 서비스를 만든다고 가정해 보겠습니다. 쉽게 생각 할 수 있는 방법은 데이터베이스를 이용하는 겁니다. 데이터의 양이 많아질 수록, 유저가 많아질 수록 데이터베이스 관리에 많은 비용이 들어갈 거라는 걸 예상 할 수 있습니다.

"파일이 저장된 위치가 바뀌지 않는다면 즉 Consistent 하다면" 어떨까요. 여기에 Hash 함수를 이용 할 수 있다면 O(1)의 연산으로 파일의 위치를 찾을 수 있을 겁니다.

일반 Hash 함수는 어떨까요 ? 일반 Hash 함수는 O(1)을 만족하긴 하지만 Consistent 하지 않습니다. 가장 간단하게 사용 할 수 있는 Hash 함수는 "mod n"일 겁니다. % 연산을 하는 거죠. 노드의 갯수가 10 이고 파일의 id가 4라면 4%10 == 4, 4번 노드에 저장하는 겁니다. 노드의 갯수가 변하지 않는다면, 단 한번의 mod 연산으로 파일의 위치를 찾을 수 있습니다. 엄청나게 효율적이죠. 단점은 "노드의 갯수가 변하지 않을 때만" 제대로 작동한다는 겁니다.

노드가 꽉차서 11개로 노드를 늘리면 어떻게 될까요. 파일 분산을 위해서 새로 추가된 노드에 파일을 골고루 옮겨야 하기 때문에 거의 모든 파일에 대해서 % 11 연산을 해서 새로 배치해야 할 겁니다. 다이나믹한 환경의 인터넷 서비스에서 사용 할 수 있는 방법은 아닙니다.

이 문제를 해결 한 알고리즘이 Karger Consistent hash 알고리즘입니다. 이 알고리즘의 핵심은 CHARSYAM 님의 문서에 잘 나와 있으니 참고하시면 됩니다.

Jump Consistent Hash

최후의 질문에서 초 인공 지능인 코스믹AI는 이렇게 말합니다. "해결 할 수 없는 문제는 없다." 또 이런 말도 있죠. "모든 문제는 두 가지 이상의 방법으로 해결 할 수 있다."

Jump Consistent Hash는 "Fast, Minimal Memory"를 장점으로 내세우고 있는 Consistent hash Algorithm 입니다. 논문은 https://arxiv.org/pdf/1406.2294.pdf 에서 자유롭게 읽을 수 있습니다.

이 알고리즘은 단 5줄로 구현됩니다. 놀랍도록 단순합니다.

1
2
3
4
5
6
7
8
9
int32 _t JumpConsistentHash(uint64_t key, int32_t num_buckets) { 
	int64_t b =­-1, j = 0; 
	while (j < num_buckets) { 
		b = j; 
		key = key * 2862933555777941757ULL + 1; 
		j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1)); 
	} 
	return b; 
}

실제 작동하는 간단한 코드를 하나 만들었습니다. 8개의 버킷에 100,000개의 키를 분산 시켰습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <stdint.h>
#include <map>
using namespace std;
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
	uint64_t b =-1, j = 0;
	while (j < num_buckets) {
		b = j;
		key = key * 2862933555777941757ULL + 1;
		j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
	}
	return b;
}
int main(int argc, char **argv) {
	map<int, int> map1;
	map<int, int>::iterator mi;
	int32_t v;
	for (uint64_t i = 0; i < 100000; i++) {
		v = JumpConsistentHash(i, 8);
		mi = map1.find(v);
		if (mi == map1.end()) {
			map1[v] = 1;
		} else {
			mi->second++;
		}
	}
	for (mi=map1.begin(); mi !=map1.end(); ++mi) {
		cout << mi->first << " : " << mi->second << endl;
	}
}

실행결과입니다. 8 개의 버킷에 매우 균등하게 분포 된 것을 알 수 있습니다. Consistent hash는 key가 작을 때도 분산이 아주 잘 된다는 특징이 있습니다. key 의 값을 바꿔가면서 한번 테스트 해보시면 재미있을 겁니다. 논문에서도 key가 적건, 많건 매우 균등하게 분산 되는 걸 장점으로 기술하고 있습니다.

1
2
3
4
5
6
7
8
0 : 12496
1 : 12498
2 : 12503
3 : 12501
4 : 12470
5 : 12478
6 : 12496
7 : 12558

이제 jump consistent hash가 어떻게 작동하는지 살펴보도록 하겠습니다. 아래 그림을 보시죠.

jump consistent hash의 작동방식

Bucket size는 목적지까지의 거리입니다. Bucket size는 key를 분산할 컴퓨터 노드의 갯수라고 생각해도 괜찮습니다. key를 컴퓨터 노드에 consistent하게 배치하는게 우리의 목적입니다.

(주사위에 사용하는)말 이라고 가정하면 이해가 쉽습니다. 특수하게 제작된 주사위를 던져서 나온 갯수 만큼 앞으로(그림의 화살표 방향)으로 움직입니다. 그렇게 주사위를 몇 번 굴리다 보면, bucket size를 넘어가게 될 것입니다. "Bucket size를 벗어 날 때 까지 주사위를 굴린 수"가 hash 값입니다.

여기에서 중요한 점은 "주사위를 어떻게 잘 설계" 할 것인지입니다. 이 주사위는 대략 아래와 같이 설계됬습니다.

마작과 비슷하게 생긴 주사위 입니다. 이 주사위는 Bucket size 크기만큼을 준비합니다. Bucket size가 6이라면 6개를 준비하면 됩니다. 이것을 펼쳐서 눈의 값이 1인 위치까지가 "이동 거리"가 됩니다. 이동거리가 멀어질 수록 확률도 1/2, 1/3, 1/4 ... 이렇게 떨어집니다. 이 주사위를 bucket size를 넘어갈 때까지 던진 횟수를 계산하면 됩니다.

구글에서 공개한 5줄 짜리 코드의 핵심이 "주사위의 설계"에 있습니다. 코드를 다시 한번 살펴보겠습니다.

1
2
3
4
5
6
7
uint64_t b =-1, j = 0;
while (j < num_buckets) {
	b = j;
	key = key * 2862933555777941757ULL + 1;
	j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
}
return b;
  • num_buckets : 버켓의 크기입니다.
  • while j < num_buckets : j(jump 거리)가 num_buckets를 초과한 값을 리턴합니다.

key를 자세히 살펴보겠습니다. key = key * 2862933555777941757ULL + 1 는 unsigned long long 64bit 데이터입니다. 이 값을 2진수로 변환하면

1
10011110111011001011101110011010000111101100001011000011111101

이 됩니다. 2862933555777941757 * 2를 하면 이 연산은 대부분의 경우 오버플로우 됩니다. 이 값을 double((key >> 33)) 연산을 해서 double로 형변환을 하면 랜덤 값을 얻을 수 있습니다. 이 값을 분모로 나누기를 하면, 1/N으로 확률이 감소하는 주사위를 얻을 수 있습니다. (b + 1)을 해서 최소한 1칸은 움직이도록 했으니, 루프가 num_buckets를 초과하지 않을 겁니다. 마법스러워 보이지만 shift 연산을 이용한 바이너리 값이 (거의)랜덤 하다는데 착안한 알고리즘 입니다.

Karger Consistent hash 와의 비교

Karger consistent hash는 가상노드를 포함한 해시링(hash ring)을 만들어서 object의 위치를 찾습니다. 따라서 해시링 데이터를 어딘가에 저장하고 있다가 object를 찾아주는 proxy가 있어야 합니다.

Object가 많아지면 Ring의 크기도 커지고 그만큼 메모리도 차지할 테고, 찾기 성능에도 영향을 줄겁니다. Ring 데이터의 관리에도 신경을 써야 합니다. Rebuild 역시 전체 object에 대해서 수행해야 하기 때문에 컴퓨터 자원을 많이 소비하게 됩니다. Hash Ring이 "중앙 서버"에 저장되기 때문에 발생하는 문제입니다.

Jump consistent hash를 이용하면 이러한 문제를 피해 갈 수 있습니다. "Hash 의 분산" 입니다.

애플리케이션은 bucket-size와 자신이 관리하는 object(파일 같은)의 key를 알고 있다면, Hash(bucket-size, key)를 돌려서, object가 저장된 node의 위치를 proxy의 도움없이 찾을 수 있습니다. 해시 테이블과 이와 관련된 연산이 애플리케이션으로 분산되는 겁니다. 물론 bucket-size에 대한 동기화가 필요하겠지만, 주키퍼 같은 분산 코디네이터를 이용하면 그리 어려운일도 아닙니다(정말 ?).

Hash 연산을 Proxy에서 대신하는 방법도 있습니다. 이렇게 하면 클라이언트 애플리케이션에 bucket-size를 동기화 하는 등의 작업이 필요 없을 겁니다. 하지만 유저 요청이 올 때마다 key에 대한 hash 연산을 해야 하는 부담이 있습니다. 이 부담은 관리하는 key들에 대해서 jump hash 값을 미리 구해서 메모리에 저장해 두거나 한번 연산한 key의 hash를 캐시하는 등의 방법으로 없앨 수 있을겁니다. Proxy를 두더라도 Karger consistent hash 보다는 더 빠르고, 더 작은 메모리를 소비합니다. 자세한 수치는 논문을 참고하시면 됩니다.

Popit은 페이스북 댓글만 사용하고 있습니다. 페이스북 로그인 후 글을 보시면 댓글이 나타납니다.