Distributed systems
Part 3 of 6 · Consistent hashingJump Consistent Hash: Dense Buckets, Almost No Memory
Jump hash maps a key onto 0..N-1 with almost no memory and ~K/N movement. Buckets must be a dense integer range — no arbitrary node ids, weights, or AZ walks.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Overview
Jump consistent hash (Lamping & Veach, 2014) is the algorithm you reach for when shards are a dense integer range and you want almost no memory. The only state is N, the bucket count. There is no vnode array, no Maglev table, no node-id list inside the hash. A 64-bit key plus N produces a bucket in 0 .. N-1.
It is not a general replacement for Cassandra-style rings. If your nodes have string ids, racks, or unequal disks, jump hash is the wrong primitive — use a ring or HRW and map through jump hash only if you first compact the cluster into 0..N-1.
Why jump hash wins for dense buckets
| Need | Ring + vnodes | HRW | Jump (this page) |
|---|---|---|---|
| Memory | Sorted token list, size ~N·V | Live node list | N as an integer |
| Lookup | O(log V) | O(N) hashes | Expected O(1) jumps |
| Add a bucket | Steal ~1/(N+1) arcs | New id wins ~1/(N+1) | Stay or jump to N |
| Remove arbitrary node | Delete its tokens | Drop the id | Not supported |
| Weights / AZ | Vnodes; RF walk | Score × weight | None |
| Node identity | Any string | Any string | Index 0..N-1 |
- 1
string node ids → O(N) hashes
HRW max-score
Wins when membership is a small set of named, weighted boxes. You pay a hash per node and you still do not get an AZ walk for free.
- 2
stateful replicas → clockwise RF
Ring + vnodes
Wins for databases that must stream ranges and skip racks. You own a token ring and a membership protocol.
- ?
Winner here: jump hash onto 0..N-1
Almost no memory, expected constant time, monotonic adds. Maglev still wins when you need a bounded-slot L4/L7 table. Jump hash is not Maglev and not a replica placer.
Core ideas
- Jump function — from the current bucket
b, compute the next bucket index the key would jump to as N grows. Loop until that jump is pastnumBuckets. - Dense buckets — indices 0 .. N-1 with no holes. Bucket 5 must exist if N is 8.
- Monotonicity — when N becomes N+1, a key either keeps its bucket or moves to the new bucket N. No third destination. That is why movement is ~1/(N+1) and why the algorithm is “consistent.”
- Add-only scaling — deleting bucket 3 would require every key currently at 4..N-1 to possibly shift. Jump hash refuses that. Retire traffic, then shrink from the end, or rebuild.
- Statelessness — inputs are
(key, N). Two processes with the same hash of the key and the same N agree.
The Lamping & Veach loop
Paper (C++, simplified): start b = -1, j = 0. While j < num_buckets, set b = j, scramble key with a 64-bit LCG, then set
j = floor( (b + 1) * (2^31 / ((key >> 33) + 1)) )
When the loop exits, b is the bucket.
Intuition. Imagine assigning the key with 1 bucket, then 2, then 3, … up to N. At count n, the key jumps to the newly added bucket with probability 1/n (so each of the n buckets stays equally likely). Computing every n would be O(N). The paper skips ahead: from current bucket b, the next jump landing is
next = floor( (b + 1) / r ) for r ~ Uniform(0, 1)
which is the same family as floor( (b + 1) * (1 / r) ). Teaching ports sometimes rearrange that jump as floor((b+1) * (1 - 1/newJump)) once r is written in terms of the LCG output. The LCG
key = key * 2862933555777941757 + 1 (mod 2^64)
turns the 64-bit key into a fresh r via (key >> 33) + 1 over 2^31. The constant is the paper’s multiplier; do not invent a different one and expect the same buckets.
Decisions
- 1
Start: 64-bit key, numBuckets N
- nextb = -1, j = 0
- 2
b = -1, j = 0
- nextj less than N?
- ?
j less than N?
- Yesb = j
- NoReturn bucket b
- 4
b = j
- nextLCG: key = key * 2862933555777941757 + 1
- 5
LCG: key = key * 2862933555777941757 + 1
- nextj = floor((b+1) * 2^31 / ((key>>33)+1))
- 6
j = floor((b+1) * 2^31 / ((key>>33)+1))
- nextj less than N?
- 7
Return bucket b
Lesson map
Jump Consistent Hash: Dense Buckets, Almost No Memory
Jump hash maps a key onto 0..N-1 with almost no memory and ~K/N movement. Buckets must be a dense integer range — no arbitrary node ids, weights, or AZ walks.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["Start: 64-bit key, numBuckets N"] b["b = -1, j = 0"] c["j less than N?"] d["b = j"] a -->|Start: 64-bit key, numBuckets N| b b -->|b = -1, j = 0 to j less than N?| c c -->|Yes| d
Expected time. The number of loop iterations is the number of jumps the key makes while N grows, which is small — O(1) expected, roughly logarithmic in the worst typical case. Memory is O(1).
Hash the key first. The algorithm wants a well-mixed 64-bit integer. Hash strings with xxHash / Murmur3, then jump. Using the string’s character codes as key will clump.
A tiny walk (N grows 1 → 5)
Fix a key whose successive jump landings (the j values after each LCG step) are 0, then 2, then 5. The algorithm’s b is always the last landing still strictly less than N.
| N | Landings still < N | Bucket | Vs previous N |
|---|---|---|---|
| 1 | 0 | 0 | first bucket |
| 2 | 0 | 0 | stayed |
| 3 | 0, 2 | 2 | moved to new index 2 |
| 4 | 0, 2 | 2 | stayed (next landing 5 ≥ 4) |
| 5 | 0, 2 | 2 | stayed (5 ≥ 5, not taken yet) |
| 6 | 0, 2, 5 | 5 | moved to new index 5 |
The quote on the board: when N becomes N+1, the bucket is either unchanged or exactly N. It never hops from 2 to 3. N=2→3 is a move-to-new-bucket; N=3→4 is a stay. You do not need the exact LCG digits.
Drain procedure when you must lose capacity:
- Stop assigning new work to bucket N-1 (the last index).
- Copy or wait out TTL for keys currently at N-1.
- Publish N' = N-1. That is the inverse of an add: only keys that lived on the last bucket remap, and they remap back to
jump(key, N-1). - Never publish a hole. If host 3 of 10 dies, swap it with host 9, then shrink, or keep N=10 and point the side table’s slot 3 at a survivor (weights via repeats — you left pure jump hash).
What jump hash cannot do
| Temptation | Why it breaks |
|---|---|
Node ids cache-a, cache-b | There is no id in the formula — only indices. Maintain a side table bucket → node that you compact on membership change (and then you reintroduced mapping state). |
| Remove node 2 of 10 | Holes break density; remaining keys are not monotonic. Drain, or remap explicitly. |
| Weight 3× on one host | No weight parameter. Repeat buckets in the side table (back to vnodes) or use HRW. |
| RF walk across AZs | Buckets are not topology. Place replicas with a topology-aware walk on real nodes. |
| Hot key | Bucket assignment is even across keys, not QPS. Bounded loads. |
Expected jump count
How many times does the while-loop run? Each jump skips a random factor of the remaining bucket axis; empirically the iteration count is tiny (single digits for N in the thousands, tens for huge N). That is the “expected O(1)” claim. It is not a hard O(1) bound like an array index — Maglev’s table lookup is the thing that is truly one load. If an interviewer traps you with “prove worst-case O(1),” say: expected constant, worst-case grows slowly, still far cheaper than O(N) HRW or O(log V) bisect for the dense-bucket use case.
Seed the pre-hash, not C. Two tenants that must not collide get xxhash(tenant || key) (delimiter again) into the 64-bit seed. Changing the LCG constant 2862933555777941757 is a different algorithm and remaps everyone.
Side-table compact after a death. N stays 10, slot 3’s host is gone: either point slot 3 at a survivor (uneven weights, not pure jump) or swap slot 3 with slot 9 and publish N=9 (drain slot 9 first). Publishing N=9 without swapping reassigns every key whose bucket was 9, which is correct only if slot 9 was the dead host.
Architecture
| Component | Responsibility | Properties |
|---|---|---|
| Hasher | 64-bit mix of the application key | Uniform, seedable, versioned |
| Jump function | LCG + floor jump | Integer-first; watch JS 53-bit mantissa |
| Bucket selector | Loop until j >= N | Expected O(1), monotonic on add |
| Side table (optional) | Index → physical node | Needed as soon as nodes are not “shard 7” |
| Metrics | Histogram of bucket loads; remap count on N++ | Stddev should sit near sqrt(K/N) |
Playground — paper loop, monotonic add, ~1/N move
BigInt holds the 64-bit LCG exactly (JS number cannot multiply 2862933555777941757 without rounding). The jump index itself fits in number.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Write the while j < N loop. Then argue N=10 → N=11: a key at bucket 4 either stays at 4 or becomes 10. Cross out “remove shard 3.” Draw the side table you would need to point buckets at cache-a … cache-j, and show what compacting that table after a death does to monotonicity.
Interview Q&A
What does jump hash guarantee when scaling from N to N+1 buckets?
Answer
Monotonicity. Each key either stays in its current bucket or moves to the newly added bucket N. No key moves from 2 to 7. Expected movement ~1/(N+1).
Why can you not remove a bucket in the middle of the range?
Answer
Density and monotonicity assume buckets are 0..N-1. Deleting index 3 leaves a hole; keys that hashed to 4..N-1 are no longer consistent with a smaller N, and there is no “stay or move to the hole” rule. Drain the bucket, or shrink from the last index (the inverse of an add).
How does jump hash achieve expected O(1) time and O(1) memory?
Answer
Memory: only N and the key. Time: the loop follows jumps, not every integer 1..N. Jump counts are small on average (geometric-like). Worst-case iteration count is still far below N for normal N.
What is the role of the constant 2862933555777941757?
Answer
It is the LCG multiplier from the paper. After key = key * C + 1 (mod 2^64), the top bits look uniform enough to form r. Changing C changes every bucket assignment. Version it like a hash algorithm.
Compare jump hash with HRW.
Answer
Jump: faster, O(1) memory, monotonic adds, requires dense integer buckets, no native weights. HRW: O(N) hashes, arbitrary ids, easy weights, add or remove any node with ~1/N remap. Pick jump for shard indexes; pick HRW for named caches.
How would you test uniformity?
Answer
Map K ≫ N random keys, histogram bucket counts, check mean ≈ K/N and relative stddev small (a few percent at large K). Also assert the monotonicity invariant: for every key, jump(key,N)==jump(key,N+1) or jump(key,N+1)==N.
JS Number is 53-bit. What breaks if you skip BigInt?
Answer
The product key * 2862933555777941757 does not fit in a IEEE double mantissa. You get a different (still maybe “ok looking”) mapping that disagrees with the paper, with other languages, and with itself after a code change. Use BigInt, wasm, or a 64-bit runtime. Signed >> vs unsigned >>> on 32-bit intermediates is the other classic bug.
Can jump hash place RF=3 replicas in three AZs?
Answer
Not by itself. It returns one integer. You could take jump(key,N), jump(key+seed,N), … but those buckets may share a host once you map through a side table, and nothing knows about racks. Use a topology-aware RF walk on physical nodes.
1M keys, 10 buckets, add an 11th. How many move, and where?
Answer
About 1M/11 ≈ 91k, and they all move to bucket 10. The other ~909k stay. If your side table maps bucket i → node i, that is the new node’s starting share.
Jump vs Maglev vs a vnode ring — when do you pick each?
Answer
Jump: compact shard ids, tiny state, append-only capacity. Maglev: L4/L7 with a bounded number of table slots per backend and O(1) array lookup. Ring: stateful storage, vnodes, streaming rebalance, rack-aware replicas.
Pitfalls
- Weak 64-bit mix of the application key — clustering before the LCG ever runs. Use xxHash / Murmur3.
- Overflow / Number — implement the LCG in 64-bit (BigInt or
uint64). - Signed shifts —
key >> 33on a signed 64 must be logical (zero-fill). - N = 0 — reject it.
- Middle remove — massive accidental remap; drain instead.
- Side table drift — two clients with different
bucket → nodearrays disagree even when jump agrees. - Weights via “repeat the host in a list” without compacting — you reinvented vnodes and lost O(1) memory.
- Hot keys — even buckets ≠ even QPS.
Deep dive · Floating-point, seeds, and compacting a side table
Production ports keep the paper’s double division (b+1) * (2^31 / ((key>>33)+1)). That is intentional: the jump is not a pure-integer reciprocal. Languages without 64-bit ints emulate with BigInt plus a Number (or float64) for the quotient.
If two logical partitions must not collide (tenant A vs tenant B), seed the pre-hash, not the LCG constant. Changing C is a different algorithm.
A practical pattern: jump hash onto M ≫ N virtual slots, then a compact array of length M pointing at N physical nodes (this is sliding toward Maglev). Membership changes rewrite the array. You paid memory to buy named nodes. At that point ask whether HRW or a vnode ring is the honest design.
Streaming the keys that moved when N increments is the same ops problem as any consistent hash: throttle, version N, do not split-brain. See vnode rebalancing.