· 개발

Jump Consistent Hash: 표 없이 샤드 번호를 정하는 일관된 해시와 그 전제 조건

샤드를 10개에서 12개로 늘릴 때 hash mod n은 키의 5/6을 옮기지만 꼭 옮겨야 하는 건 1/6입니다. Lamping·Veach 논문의 Jump Consistent Hash 코드, 동작 원리, 버킷을 늘리고 줄일 때 생기는 일을 정리했습니다.

개발알고리즘자료구조

키-값 데이터를 샤드 10개에 나눠 담는 가장 쉬운 방법은 키의 해시를 10으로 나눈 나머지, h(key) mod 10을 샤드 번호로 쓰는 것입니다. 데이터가 늘어 샤드를 12개로 늘리면 이 식은 h(key) mod 12가 되고, 대부분의 키가 다른 샤드로 가야 합니다.

얼마나 많이 옮겨야 할까요? 해시값이 고르게 퍼져 있다고 하고 직접 세어 보면, 두 나머지가 같은 경우는 h mod 60이 0부터 9 사이일 때뿐입니다(10과 12의 최소공배수가 60이므로, 두 나머지가 같은 값 r이면 h ≡ r (mod 60)이고 r은 10보다 작아야 합니다). 60가지 중 10가지, 즉 키의 1/6만 제자리에 있고 나머지 5/6은 옮겨야 합니다.

John Lamping과 Eric Veach의 논문 「A Fast, Minimal Memory, Consistent Hash Algorithm」(arXiv, 2014년 6월 9일 제출)은 같은 예를 들며, 12개 샤드에 고르게 나누는 데 꼭 옮겨야 하는 양은 10개 샤드에 있던 데이터의 1/6뿐이라고 지적합니다. 이 논문이 내놓은 Jump Consistent Hash는 그 1/6만 옮기도록 샤드 번호를 정하는 함수이고, 코드는 다섯 줄 남짓입니다. 아래는 이 논문만을 근거로 정리했습니다. 성능 수치는 모두 논문이 2014년에 보고한 값이며 이 글에서 다시 측정하지 않았습니다.

함수가 약속하는 두 가지

Jump Consistent Hash는 64비트 키와 버킷(샤드) 개수를 받아 [0, num_buckets) 범위의 버킷 번호를 돌려줍니다. 논문은 이 함수가 두 성질을 만족한다고 설명합니다.

  • 균형(balance): 각 버킷에 대략 같은 수의 키가 배정됩니다.
  • 단조성(monotonicity): 버킷 수를 늘리면 키는 기존 버킷에서 새 버킷으로만 옮겨 가고, 기존 버킷끼리는 키를 주고받지 않습니다.

일관된 해싱(consistent hashing)이라는 개념은 Karger 등이 1997년에 웹 캐시용으로 제안했고, 원래 네 가지 성질을 정의했습니다. 논문은 나머지 두 성질(spread, load)이 클라이언트마다 서로 다른 서버 집합을 볼 수 있다는 상황을 다룬다고 설명합니다. Jump Consistent Hash는 모든 클라이언트가 같은 버킷 집합 [0, num_buckets)를 본다고 가정하고, 그 제약 덕분에 성립합니다.

논문에 실린 코드

논문의 그림 1은 C++ 구현 전체입니다.

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;
}

표도, 서버 목록도, 미리 만들어 둘 자료구조도 없습니다. 논문의 표현으로는 “레지스터 몇 개에 들어가는 것 이상의 메모리가 필요 없다”는 것입니다. 이 코드가 왜 균형과 단조성을 갖는지는 버킷 수를 하나씩 늘려 가는 느린 버전부터 보면 이해하기 쉽습니다.

버킷을 하나씩 늘려 가며 생각하기

키 k의 버킷 수가 n일 때의 결과를 ch(k, n)이라고 합시다. 버킷이 하나면 답은 당연히 0입니다. 버킷이 2개가 되면 균형을 맞추기 위해 절반의 키는 0에 남고 절반은 새 버킷 1로 가야 합니다. 일반적으로 n개에서 n+1개로 늘릴 때 키의 n/(n+1)은 제자리에 있고, 1/(n+1)만 새 버킷 n으로 “점프”해야 합니다. 그래야 새 버킷도 1/(n+1)만큼의 키를 받고, 기존 버킷들은 각자 같은 비율만큼만 내줍니다.

논문은 세 키가 버킷 수에 따라 어떻게 바뀌는지 예를 표로 보여 줍니다(맨 윗줄이 버킷 수).

버킷 수 1 2 3 4 5 6 7 8 9 10 11 12 13 14
k1 0 0 2 2 4 4 4 4 4 4 4 4 4 4
k2 0 1 1 1 1 1 1 7 7 7 7 7 7 7
k3 0 1 1 1 1 5 5 7 7 7 10 10 10 10

값이 바뀌는 칸을 보면 항상 그 열의 새 버킷 번호(버킷 수 − 1)로 바뀝니다. k3은 버킷이 6개가 될 때 5로, 8개가 될 때 7로, 11개가 될 때 10으로 점프합니다. 기존 버킷 사이를 오가는 일은 없습니다.

이 규칙을 그대로 코드로 옮긴 것이 논문의 선형 시간 버전입니다. 키를 시드로 한 의사 난수 생성기를 두고, j = 1부터 num_buckets − 1까지 돌면서 [0, 1) 난수가 1/(j+1)보다 작으면 결과를 j로 바꿉니다. 같은 키는 항상 같은 난수열을 만들므로 같은 키에는 같은 답이 나옵니다. 다만 버킷 수에 비례하는 시간이 걸립니다.

다음 점프 위치를 한 번에 구하기

결과는 대부분의 j에서 그대로이고 가끔만 바뀝니다. 그러니 바뀌는 지점만 계산하면 됩니다. 논문의 유도는 이렇습니다.

  1. 한 단계에서 결과가 유지될 확률은 n/(n+1)입니다. 여러 단계를 이으면 곱이 약분되어, m ≤ n일 때 ch(k, m)과 ch(k, n)이 같을 확률은 m/n입니다. 예를 들어 10/11 × 11/12 = 10/12입니다.
  2. 직전 점프로 결과가 b가 되었다고 합시다. 다음 점프 직전의 위치를 j라고 하면, 임의의 i > b에 대해 j ≥ i일 확률은 ch(k, i) = ch(k, b+1)일 확률, 즉 (b+1)/i입니다.
  3. 0과 1 사이에서 균일한 난수 r을 하나 뽑아 “r ≤ (b+1)/i일 때 j ≥ i”로 정하면 이 분포가 맞습니다. 부등식을 i에 대해 풀면 i ≤ (b+1)/r이므로 j = floor((b+1)/r)입니다.

이렇게 다음 점프 위치를 계속 구하다가 그 값이 num_buckets 이상이 되면 멈추고, 마지막으로 점프한 위치 b를 답으로 돌려줍니다.

그림 1의 코드를 이 유도에 맞춰 읽으면 다음과 같습니다(이 대응은 이 글의 해석입니다).

  • key = key * 2862933555777941757ULL + 1은 64비트 선형 합동 생성기(LCG) 한 단계입니다. 키 자체가 시드이고, 반복할 때마다 상태가 갱신됩니다. 논문은 이 곱수가 연속된 값을 묶어 쓸 때도 고르게 분포하는 값이라며 L’Ecuyer의 LCG 표를 인용합니다.
  • (key >> 33) + 1은 상태의 상위 31비트에 1을 더한 값으로 1부터 2³¹ 사이입니다. 이를 2³¹로 나눈 값을 r이라고 하면 r은 0보다 크고 1 이하입니다. 0이 나오지 않으므로 0으로 나누는 일이 없습니다.
  • (b + 1) * (2³¹ / ((key >> 33) + 1))은 (b+1)/r이고, 이를 int64_t인 j에 넣을 때 소수점 아래가 버려지므로 floor((b+1)/r)이 됩니다.
  • r ≤ 1이므로 새 j는 항상 b+1 이상입니다. j가 매 반복 적어도 1씩 커지므로 루프는 반드시 끝납니다.

비용: 기대 반복 횟수 ln n + 1 미만

논문의 분석에 따르면 버킷 수 i에서 점프가 일어날 확률은 1/i이므로, n보다 작은 위치로의 점프 횟수 기댓값은 i = 2부터 n까지 1/i의 합이고 ln(n)보다 작습니다. 마지막에 n 이상으로 넘어가는 반복이 하나 더 있으므로 기대 반복 횟수는 ln(n) + 1 미만입니다. 논문은 이것이 n개의 정렬된 키에서 이진 탐색이 하는 log₂(n)번의 비교보다 상수 배만큼 적다고 덧붙입니다. 이것은 기댓값이고, 특정 키에서 반복이 몇 번 일어날지를 보장하는 상한은 아닙니다.

원형 해시 링과 비교하면

Karger 등의 알고리즘은 버킷마다 단위 원 위에 무작위 점을 여러 개 찍어 두고, 키를 원 위에 올린 뒤 시계 방향으로 처음 만나는 점의 버킷을 고릅니다. 점이 적으면 버킷 크기가 고르지 않으므로 점을 많이 찍어야 하고, 그만큼 메모리가 듭니다. 논문은 2014년 당시 Intel Xeon E5-1650에서 측정한 결과를 이렇게 보고합니다.

  • 버킷당 점 1000개를 쓴 링에서도 버킷 크기의 99% 신뢰 구간이 평균의 0.92배에서 1.09배였고, Jump Consistent Hash는 0.99999998배에서 1.00000002배였습니다.
  • 버킷당 점 1000개, 버킷 1000개일 때 링 자료구조는 구현에 따라 46MB(STL map) 또는 7.6MB(정렬된 벡터)였습니다. Jump Consistent Hash는 저장할 자료구조가 없습니다.
  • 버킷이 1000개 이하일 때 Jump Consistent Hash가 점 1000개짜리 링보다 3~4배 빨랐습니다.

버킷을 하나 추가할 때의 차이도 있습니다. 논문에 따르면 Jump Consistent Hash에서는 새 버킷이 기존 모든 버킷에서 같은 비율만큼 키를 받습니다. 버킷이 1000개라면 기존 버킷 각각이 키 공간의 거의 정확히 0.1%를 내놓습니다. 링에서는 새 버킷의 점이 떨어진 자리의 버킷들만 데이터를 내놓습니다. 버킷당 점이 10개라면 많아야 10개 버킷이 관여합니다. 과부하 걸린 버킷을 덜어 주려고 버킷을 추가했는데 그 버킷이 관여하지 않을 수도 있다는 뜻입니다.

버킷 수를 바꿀 때 실제로 일어나는 일

늘릴 때

n개에서 n+1개로 늘리면 바뀌는 키는 모두 새 버킷 n으로 갑니다. 10개에서 12개로 늘리면 이 규칙이 두 번 적용되므로, 버킷이 바뀌는 키는 모두 10번이나 11번 버킷으로 갑니다. 앞의 확률 계산대로 ch(k, 10)과 ch(k, 12)가 같을 확률은 10/12이니, 옮겨야 하는 키는 2/12 = 1/6입니다. 처음에 본 mod의 5/6과 비교하면 이동량이 5분의 1입니다.

줄일 때

반대로 n개에서 n−1개로 줄이는 경우는 단조성에서 바로 따라 나옵니다(이 글의 유도). n−1개에서 n개로 늘릴 때 바뀌는 키가 모두 버킷 n−1로 갔으므로, 거꾸로 줄일 때는 마지막 버킷 n−1에 있던 키만 다른 버킷으로 흩어지고 나머지 키는 그대로입니다.

가운데 버킷은 뺄 수 없다

줄일 수 있는 것은 항상 마지막 번호의 버킷입니다. 버킷 10개 중 3번 서버가 죽었다고 num_buckets를 9로 바꾸면, 3번의 키는 여전히 3번에 배정되고 9번에 있던 키가 흩어집니다. 함수가 돌려주는 것은 서버 이름이 아니라 0부터 시작하는 번호이기 때문입니다.

이 함정은 서버 목록 배열과 함께 쓸 때 잘 드러납니다. servers[JumpConsistentHash(key, servers.size())]처럼 써 놓고 목록 가운데에서 서버 하나를 지우면, 지운 자리 뒤의 서버들이 한 칸씩 당겨집니다. 함수의 결과가 거의 바뀌지 않더라도 번호와 서버의 대응이 바뀌어 대부분의 키가 엉뚱한 서버로 갑니다(이 글의 유도).

논문은 이것을 이 알고리즘의 주된 한계로 명시합니다. 버킷은 순서대로 번호가 매겨져야 하고, 그래서 분산 웹 캐시보다 데이터 저장소에 알맞다는 것입니다. 데이터 저장소에서는 샤드가 그냥 사라지면 안 되므로 복제본을 두거나 빠르게 대체하는 식으로 서버 장애를 처리하고, 데이터 재배치는 용량을 바꿀 때만 일어난다는 것이 논문의 전제입니다. 임의의 서버를 아무 순서로 넣고 빼야 한다면 논문이 관련 연구로 드는 Karger 등의 링이나 Thaler와 Ravishankar의 랑데부(rendezvous) 해싱처럼 임의의 버킷 ID를 지원하는 방식이 맞습니다. 논문에 따르면 랑데부 해싱의 원래 버전은 버킷마다 h(key, bucket)을 계산해 가장 큰 값을 고르므로 버킷 수에 비례하는 시간이 듭니다.

쓰기 전에 확인할 것

  • num_buckets는 1 이상이어야 합니다. 그림 1의 코드는 0이나 음수를 받으면 루프에 들어가지 않고 -1을 돌려줍니다(코드를 읽어서 알 수 있는 동작입니다). 배열 인덱스로 바로 쓰면 범위 밖 접근이 되므로 호출 전에 막아야 합니다. 인자가 int32_t이므로 버킷 수의 상한은 2³¹ − 1입니다.
  • 키는 64비트 정수입니다. 논문은 64비트에 들어가지 않는 키는 64비트 해시를 먼저 구해 넣으라고 합니다. 이미 정수인 키는 내부 LCG가 반복마다 다시 섞어 주므로 따로 해시할 필요가 없다고 설명합니다. 해시 함수가 무엇을 보장하고 무엇을 보장하지 않는지는 해시 함수란 무엇인가에서 다뤘습니다.
  • 모든 클라이언트와 모든 실행에서 같은 키 해시가 나와야 합니다. 이 알고리즘은 같은 키를 받은 모든 클라이언트가 같은 버킷을 계산한다는 데 기대고 있습니다. 실행할 때마다 시드가 바뀌는 해시(예: Python str의 해시 무작위화)를 넣으면 프로세스를 다시 띄울 때마다 키가 다른 샤드를 가리킵니다.
  • 모든 클라이언트가 같은 num_buckets를 써야 합니다. 일부 클라이언트만 새 값을 쓰는 구간에는 같은 키가 두 샤드를 가리킬 수 있습니다. 함수는 어떤 키가 옮겨 가는지를 알려 줄 뿐 데이터 이동이나 전환 순서는 운영 쪽 몫입니다.
  • 다른 언어로 옮길 때는 연산 폭을 맞춥니다. 곱셈은 2⁶⁴로 나눈 나머지만 남기는 부호 없는 64비트 연산이고, >> 33은 부호 없는 값의 시프트이며, 나눗셈은 배정밀도 부동소수점입니다. 셋 중 하나라도 다르면 C++ 구현과 다른 버킷이 나옵니다.

예를 들어 Python의 정수는 크기 제한이 없으므로 곱셈 뒤에 64비트 마스크를 직접 씌워야 합니다. 아래는 그림 1을 옮긴 이 글의 코드이며, 0 이하의 버킷 수는 예외로 처리했습니다.

MASK64 = (1 << 64) - 1

def jump_consistent_hash(key: int, num_buckets: int) -> int:
    if num_buckets <= 0:
        raise ValueError("num_buckets must be positive")
    key &= MASK64
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = (key * 2862933555777941757 + 1) & MASK64
        j = int((b + 1) * ((1 << 31) / ((key >> 33) + 1)))
    return b

이 글을 쓰면서 CPython과 컴파일한 그림 1의 C++ 코드에 같은 입력 28,001개를 넣어 봤고, 이 환경에서는 결과가 모두 같았습니다. 다만 이것은 시험한 환경 하나에서 확인한 결과일 뿐입니다. 두 피연산자가 작은 정수라는 사실만으로 언어가 달라도 나눗셈과 정수 변환 결과가 같다고 말할 수는 없습니다. 실제 서비스에 넣기 전에는 배포할 언어·컴파일러·플랫폼에서 C++ 구현과 여러 키·버킷 수로 결과를 직접 대조해야 합니다.

참고한 논문

Karger 등(1997), Thaler·Ravishankar(1997), L’Ecuyer의 논문은 원문을 열어 보지 않았고, 이 글에서 그 연구들에 대해 쓴 내용은 모두 위 논문의 설명을 옮긴 것입니다. 논문은 2026년 10월 19일에 확인했습니다.

블로그로