~/blog/jump-consistent-hash/ko.mdx

Jump Consistent Hash: 메모리 없이 다섯 줄로 하는 일관된 해싱

버킷을 10개에서 11개로 늘릴 때 mod-N은 키의 91%를 옮기고, Jump Consistent Hash는 9.1%만 옮깁니다. 링도 테이블도 없이 어떻게 그게 되는지 따라가 보고, 해시 링과 나란히 재 봤습니다.

샤드가 몇 개든 키를 골고루 나누고, 샤드를 하나 늘릴 때 옮겨야 하는 키는 최소로 줄이고 싶습니다. 보통 떠올리는 답은 가상 노드를 둔 해시 링입니다. 2014년 Google의 John Lamping과 Eric Veach가 낸 Jump Consistent Hash는 같은 일을 메모리 없이, 함수 하나로 합니다.1 이 글의 숫자는 모두 Go 1.21.13(linux/arm64, Apple Silicon 노트북의 Docker)에서 splitmix64로 만든 키 100만 개로 잰 값입니다.

mod-N이 문제인 이유

가장 단순한 방법은 hash(key) % n입니다. 고르게 나뉘지만 n이 바뀌면 거의 모든 키의 자리가 바뀝니다.

키 mod 10 → mod 11 Jump(10) → Jump(11) 90.8% 이동 9.1% 이동, 전부 새 버킷으로
방식10 → 11개로 늘릴 때 옮겨진 키비율
mod-N908,26290.8%
Jump Consistent Hash91,3599.1%
해시 링(노드당 가상 노드 100개)86,2508.6%
이상적인 값 (1/11)90,9099.1%

11번째 버킷이 가져가야 할 몫은 전체의 1/11입니다. 그보다 많이 옮기는 것은 모두 낭비이고, 캐시라면 그만큼 미스가 납니다. mod-N은 열 배를 옮겼습니다.

퀴즈새 버킷의 몫을 확인합니다

답을 고르면 해설이 나옵니다.

1문제 중 0개 맞힘

  1. 버킷을 끝에 하나 추가할 때 Jump의 이동 패턴은 무엇입니까?

다섯 줄짜리 함수

논문에 실린 코드를 Go로 옮기면 이렇습니다.

jump.go
func Jump(key uint64, n int32) int32 {
var b, j int64 = -1, 0
for j < int64(n) {
b = j
key = key*2862933555777941757 + 1
j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
}
return int32(b)
}

b는 이 키가 마지막으로 머문 버킷, j는 다음에 뛰어갈 버킷입니다. 처음에는 버킷 0에 있습니다.

키를 64비트 선형 합동 생성기의 씨앗으로 씁니다. 같은 키는 언제나 같은 난수열을 만듭니다.

핵심 줄입니다. 난수 r∈(0,1]r \in (0, 1]을 뽑아 다음 점프 위치를 ⌊(b+1)/r⌋\lfloor (b+1)/r \rfloor로 정합니다. 버킷이 하나씩 늘 때마다 키가 새 버킷으로 옮겨 갈 확률은 1/(새 버킷 수)인데, 그 사건을 하나하나 흉내 내지 않고 다음에 옮기는 지점으로 곧장 건너뜁니다.

점프 위치가 n을 넘으면 멈추고 직전 버킷을 돌려줍니다. 버킷 수가 n일 때 이 키가 있어야 할 자리입니다.

왜 건너뛰어도 되는지가 이 알고리즘의 전부입니다. 버킷이 b+1b+1개일 때 키가 bb에 있었다면, ii개가 될 때까지 한 번도 옮기지 않을 확률은 다음과 같습니다.

P(옮기지 않음)=∏k=b+2i(1−1k)=b+1iP(\text{옮기지 않음}) = \prod_{k=b+2}^{i} \left(1 - \frac{1}{k}\right) = \frac{b+1}{i}

곱의 앞뒤가 지워져 (b+1)/i(b+1)/i만 남습니다. 그러니 균등 난수 rr을 하나 뽑아 r≤(b+1)/ir \le (b+1)/i를 만족하는 가장 큰 ii, 곧 ⌊(b+1)/r⌋\lfloor (b+1)/r \rfloor까지 한 번에 뛰면 됩니다.

몇 번 도는가

버킷 수가 kk일 때 옮길 확률이 1/k1/k이므로, 기대 점프 수는 조화수 Hn≈ln⁡n+γH_n \approx \ln n + \gamma입니다. 잰 값도 같았습니다.

버킷 수평균 반복 횟수ln n + γ
102.932.88
1,0007.497.48
100,00012.0912.09

버킷이 1만 배 늘어도 반복은 네 배 남짓 늘어납니다.

얼마나 고르게 나누나

버킷 10개에 키 100만 개를 넣고 가장 적게 받은 버킷과 가장 많이 받은 버킷을 봤습니다. 이상적인 값은 10만 개입니다.

방식최소최대최대/평균
Jump Consistent Hash99,715100,4561.005
해시 링, 가상 노드 1개10,700319,1243.19
해시 링, 가상 노드 10개36,440166,5841.67
해시 링, 가상 노드 100개91,164112,7571.13
해시 링, 가상 노드 1,000개96,498103,3431.03
"링 v1" "링 v10" "링 v100" "링 v1000" "Jump" 1 1.5 2 2.5 3 배 가장 많이 받은 버킷 / 평균

해시 링이 Jump만큼 고르려면 노드당 가상 노드를 1,000개 넘게 둬야 합니다. 버킷 1,000개짜리 클러스터라면 링에 점이 100만 개 찍힙니다. Jump는 아무것도 저장하지 않습니다.

조회 비용

방식버킷 수ns/op들고 있는 상태
Jump1018.1없음
Jump1,00047.6없음
Jump100,00070.5없음
링(가상 노드 100개)1019.2항목 1,000개
링(가상 노드 100개)1,00051.7항목 100,000개

링은 정렬된 배열을 이진 탐색하므로 O(log⁡nv)O(\log nv)이고, Jump는 O(log⁡n)O(\log n)입니다. 시간은 비슷하지만 Jump는 메모리를 쓰지 않고, 노드 목록이 바뀔 때 다시 만들 자료구조도 없습니다.

대신 포기하는 것

Jump는 버킷에 이름을 붙이지 않습니다. 돌려주는 것은 0부터 n-1까지의 번호뿐이고, 버킷은 끝에서만 늘리고 줄일 수 있습니다. 가운데 3번 노드가 죽었다고 3번만 빼면 그 뒤 번호가 모두 밀려 mod-N과 같은 일이 벌어집니다.

그래서 맞는 자리가 정해져 있습니다.

  • 샤드 번호가 고정된 저장소. 샤드 하나가 죽으면 복제본이 같은 번호를 이어받습니다.
  • 번호와 실제 주소의 매핑을 따로 두는 시스템. 노드가 바뀌면 매핑만 고칩니다.
  • 노드가 수시로 들고 나는 캐시 클러스터라면 해시 링이나 rendezvous 해싱이 더 맞습니다.

가중치도 직접 지원하지 않습니다. 큰 노드에 번호를 여러 개 주는 식으로 흉내 낼 수는 있지만, 그 순간 번호표를 따로 관리해야 해서 Jump의 장점이 줄어듭니다.

정리

옮기는 키의 양은 해시 링과 같고, 분포는 가상 노드 1,000개짜리 링보다 고르고, 메모리는 0입니다. 대가는 버킷을 끝에서만 붙이고 뗄 수 있다는 제약 하나입니다. 샤드 번호가 고정된 시스템이라면 링을 만들기 전에 이 다섯 줄을 먼저 떠올려 볼 만합니다.

퀴즈샤드를 늘리고 교체한다면

답을 고르면 해설이 나옵니다.

2문제 중 0개 맞힘

  1. 가운데 샤드의 서버가 죽었습니다. Jump의 기존 배치를 유지하면서 복제본으로 넘기려면 어떻게 합니다?

  2. 버킷 수를 늘리면 Jump도 버킷마다 링 항목을 하나씩 만들거나 순서대로 검사해야 합니까?

각주

  1. John Lamping, Eric Veach, “A Fast, Minimal Memory, Consistent Hash Algorithm”, arXiv:1406.2294 (2014). 상수 2862933555777941757은 논문 코드 그대로입니다. ↩

~/blog/jump-consistent-hash/en.mdx

Jump Consistent Hash: consistent hashing in five lines and no memory

Growing from 10 to 11 buckets, mod-N moves 91% of keys and Jump Consistent Hash moves 9.1%. How it does that with no ring and no table, measured next to a hash ring.

Whatever the shard count, we want keys spread evenly, and when a shard is added we want to move as few keys as possible. The usual answer is a hash ring with virtual nodes. Jump Consistent Hash, published by John Lamping and Eric Veach at Google in 2014, does the same job with one function and no memory.1 Every number in this post was measured with Go 1.21.13 (linux/arm64, Docker on an Apple Silicon laptop) on one million keys generated by splitmix64.

Why mod-N hurts

The simplest scheme is hash(key) % n. It spreads evenly, but when n changes almost every key lands somewhere else.

key mod 10 → mod 11 Jump(10) → Jump(11) 90.8% moved 9.1% moved, all to the new bucket
SchemeKeys moved going 10 → 11Share
mod-N908,26290.8%
Jump Consistent Hash91,3599.1%
Hash ring (100 virtual nodes per node)86,2508.6%
Ideal (1/11)90,9099.1%

The eleventh bucket should take 1/11 of the keys. Anything moved beyond that is waste, and in a cache every wasted move is a miss. mod-N moved ten times the ideal.

QuizCheckpoint: the new bucket's share

Choose an answer to see the explanation.

0 of 1 right

  1. When you append a bucket, what relocation pattern does Jump produce?

A five-line function

Here is the paper’s code in Go.

jump.go
func Jump(key uint64, n int32) int32 {
var b, j int64 = -1, 0
for j < int64(n) {
b = j
key = key*2862933555777941757 + 1
j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
}
return int32(b)
}

b is the bucket the key last sat in, j is the next bucket it jumps to. It starts in bucket 0.

The key seeds a 64-bit linear congruential generator, so the same key always produces the same random sequence.

The core line. Draw r∈(0,1]r \in (0, 1] and set the next jump to ⌊(b+1)/r⌋\lfloor (b+1)/r \rfloor. Each time a bucket is added, the key moves to the new bucket with probability 1/(new bucket count). Instead of simulating each of those events, the function skips straight to the next one that moves the key.

Once the jump passes n, stop and return the previous bucket. That is where the key belongs when there are n buckets.

Why skipping is allowed is the whole algorithm. If the key sat in bb with b+1b+1 buckets, the probability it never moves until there are ii buckets is:

P(no move)=∏k=b+2i(1−1k)=b+1iP(\text{no move}) = \prod_{k=b+2}^{i} \left(1 - \frac{1}{k}\right) = \frac{b+1}{i}

The product telescopes to (b+1)/i(b+1)/i. So draw one uniform rr and jump straight to the largest ii with r≤(b+1)/ir \le (b+1)/i, which is ⌊(b+1)/r⌋\lfloor (b+1)/r \rfloor.

How many iterations

With kk buckets the move probability is 1/k1/k, so the expected number of jumps is the harmonic number Hn≈ln⁡n+γH_n \approx \ln n + \gamma. The measurements agree.

BucketsMean iterationsln n + γ
102.932.88
1,0007.497.48
100,00012.0912.09

Ten thousand times more buckets costs a bit over four times more iterations.

How evenly it spreads

One million keys into 10 buckets, looking at the lightest and heaviest bucket. Ideal is 100,000.

SchemeMinMaxMax/mean
Jump Consistent Hash99,715100,4561.005
Hash ring, 1 virtual node10,700319,1243.19
Hash ring, 10 virtual nodes36,440166,5841.67
Hash ring, 100 virtual nodes91,164112,7571.13
Hash ring, 1,000 virtual nodes96,498103,3431.03
"ring v1" "ring v10" "ring v100" "ring v1000" "Jump" 1 1.5 2 2.5 3 x Heaviest bucket / mean

For a ring to match Jump it needs more than 1,000 virtual nodes per node. With 1,000 buckets, that is a million points on the ring. Jump stores nothing.

Lookup cost

SchemeBucketsns/opState held
Jump1018.1none
Jump1,00047.6none
Jump100,00070.5none
Ring (100 virtual nodes)1019.21,000 entries
Ring (100 virtual nodes)1,00051.7100,000 entries

The ring binary-searches a sorted array, O(log⁡nv)O(\log nv); Jump is O(log⁡n)O(\log n). Time is similar, but Jump uses no memory and has no structure to rebuild when the node list changes.

What you give up

Jump does not name buckets. It returns a number from 0 to n-1, and buckets can only be added or removed at the end. If node 3 in the middle dies and you just drop it, every number after it shifts and you are back to mod-N.

So it fits particular places:

  • Stores with fixed shard numbers, where a replica takes over a dead shard’s number.
  • Systems that keep a separate number-to-address mapping and only update that mapping when nodes change.
  • For cache clusters where nodes come and go freely, a hash ring or rendezvous hashing fits better.

It has no weights either. You can fake them by giving a big node several numbers, but then you are managing a number table and most of the appeal is gone.

Summary

It moves as few keys as a hash ring, spreads more evenly than a ring with 1,000 virtual nodes, and uses zero memory. The price is a single constraint: buckets are only added or removed at the end. If your shard numbers are fixed, these five lines are worth considering before building a ring.

QuizGrowing and replacing shards

Choose an answer to see the explanation.

0 of 2 right

  1. A server for a middle shard dies. How do you hand it over to a replica while preserving Jump's existing placement?

  2. As the bucket count grows, must Jump create a ring entry per bucket or inspect every bucket in order?

Notes

  1. John Lamping, Eric Veach, “A Fast, Minimal Memory, Consistent Hash Algorithm”, arXiv:1406.2294 (2014). The constant 2862933555777941757 is taken from the paper’s code. ↩

ko.mdx

단축키Keyboard

/ ⌘K
글 검색Search posts
t
밝은/어두운 테마Light or dark theme
l
한국어/영어, 읽던 자리 유지Korean or English, keeping your place
[ ]
이전/다음 절Previous or next section
?
이 목록This list

↑↓ 이동move↵ 열기openesc 닫기close