1.
새벽에 일어나 글을 읽는데 제목이 눈에 들어옵니다.
A Fast, Minimal Memory, Consistent Hash Algorithm
Fast는 좋아하는 단어입니다. Minimal도 좋아합니다. 그런데 Consistent는 어렵습니다. 우선 Consistent Hash가 궁금했습니다. 페이스북으로 알고 있는 Mimul님이 이 년전에 Consistent Hash를 설명하는 글을 올리셨네요. 제가 설명하기 보다 직접 읽어보시면 이해가 쉬울 듯 합니다.
Memcached 에서의 Consistent Hashing도 쉽게 설명한 글이니까 같이 읽어보시길 바랍니다. 두 글을 읽으면 하나의 그림이 들어옵니다. 원(Ring)입니다.
Consistent Hash는 NoSQL에서 가용성을 구현하는 알고리즘으로 많이 사용하고 있다고 합니다. Casandra가 적용한 방법을 설명한 글입니다.
컨시스턴트 해싱은 메타 정보를 조회하지 않아도 클러스터에서 키가 저장된 노드를 바로 찾아갈 수 있는 방법이다. 키의 해시 값을 구해서 키를 찾고, 이 해시 값만으로 노드를 찾아갈 수 있다. 좀 더 자세히 살펴보면, 컨시스턴트 해싱은 일련의 해시 값을 가상의 링(ring)에 순서대로 나열했다고 가정하고 각 노드는 링에서 각자 맡은 범위만 처리하는 방법이다. 만약 노드를 추가하면 특정 노드(많은 데이터를 가진 노드)가 맡고 있던 범위를 분할하여 새 노드에 할당한다. 노드를 삭제할 때는 링에서 삭제된 노드가 맡고 있던 범위를 인접 노드가 맡는다. 따라서 서비스 중에 노드의 추가/삭제로 인해 영향을 받는 노드 수를 최소화할 수 있다
NoSQL 가용성과 운영 안정성중에서
2.
다시 본론입니다. 구글이 논문으로 발표한 Consistent Hash은 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; } |
혹 C로 구현한 Consistent Hash Library가 필요하시면?
