Jump Consistent Hash — Consistent Hashing

Overview

What this concept solves

Jump Consistent Hash, from Google (Lamping & Veach, 2014), takes a different angle. There's no ring, no virtual nodes, no lookup table — in fact, no stored state at all. It's a tiny function: give it a key and a bucket count N, and it returns a bucket in the range [0, N-1]. The whole thing is about five lines of code.

The idea is to simulate, very cheaply, where a key would land as the number of buckets grows from 1 upward. Starting at bucket 0, the algorithm repeatedly decides whether the key should jump to a higher bucket. Each jump's distance is driven by a pseudo-random number seeded from the key. When the next jump would land at or past N, it stops — and the last bucket it sat on is the answer.

Because the jump sequence is fixed for a given key, growing N can only ever pull a key forward into a new higher bucket — and only with the right probability. That gives near-perfect balance and minimal movement, using zero memory. The catch: buckets must be numbered 0…N-1, and you can only cheaply add or remove the last one.

Mechanics

How it works

Jump forward until you'd overshoot

Start at bucket b = -1 and candidate j = 0.
Set b = j (accept the candidate), then draw the next pseudo-random number from the key.
Compute the next candidate j — always a jump forward, and on average bigger jumps happen less often.
If j is still below N, loop. As soon as j ≥ N, stop: the answer is the current b.

The number of jumps grows like O(log N), so even for huge N it finishes in a few dozen steps. The prototype draws each accepted jump as an arc and each rejected (overshooting) jump as a dashed arc that flies off the end — the last solid landing is the chosen bucket.

Why adding a bucket barely moves anything

Go from N to N+1 buckets and a key only moves if its jump sequence would have reached the new bucket N — which happens with probability exactly 1/(N+1). So about 1/(N+1) of all keys move into the new bucket, and every other key stays put. That's the theoretical minimum: it's exactly the fraction the new bucket should hold. Slide N in the prototype and the narration shows the moved count landing right near that expectation.

The big limitation: buckets are numbered, tail-only

Jump hash returns a number 0…N-1, not a named node. You can cheaply grow to N+1 (add bucket N) or shrink to N-1 (remove the last bucket), but you can't remove an arbitrary bucket in the middle — doing so would renumber everything. That makes it ideal for sharded storage that scales at the tail, and a poor fit for a churny set of named cache servers.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Jump Consistent Hash

About this simulation

A key doesn't sit on a ring here — a formula decides its bucket. The key 'jumps' forward through bucket numbers, each jump's size set by a pseudo-random number from the key, until a jump would overshoot N — then it stops at the last bucket it landed on. Click a key to trace it, hit Play trace to animate the arcs, and drag N to watch how few keys move when a bucket is added or removed.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Trace one key's jumps

Click a key chip inside any bucket, then press Play trace. The arcs animate the key jumping forward through bucket numbers; the dashed arc that flies past the end is the jump that overshot N, so the algorithm stops at the previous (green) bucket. The step list shows the math for each jump.

try 02

Add a bucket, count the movers

Drag N up by one. Only the keys that jump into the brand-new last bucket move — the narration compares the actual moved count to the expected ~total/N. Everything already placed stays exactly where it was.

try 03

Watch the balance

Hit +5 keys a few times and scan the per-bucket counts. With no ring and no tuning, the buckets stay strikingly even — that natural, near-perfect balance (with zero memory) is jump hash's headline feature.

In practice

When to use it — and what you give up

When to reach for it

Sharded data stores where shards are numbered and you scale by adding shards at the end.
Memory- or cache-constrained lookups — it needs literally zero storage, just the key and N.
You want the best possible balance — its distribution is essentially perfectly even.
Stateless services that can recompute the mapping anywhere from just (key, N), with no shared ring to distribute.

Storage, not web caching

The paper itself notes the numbered-bucket constraint makes jump hash 'more suitable for data storage applications than for distributed web caching,' where servers come and go by name. Match the tool to that shape.

Pros

Zero memory — no ring, no table, no vnodes; just a ~5-line function.
Near-perfect balance across buckets.
Adding bucket N moves only ~1/(N+1) of keys — the theoretical minimum.
O(log N) lookups; fast even for very large N.

Cons

Buckets must be numbered 0…N-1 — it returns an index, not a named node.
You can only cheaply add/remove the last bucket; arbitrary removal renumbers everything.
No built-in weighting or replica selection (needs extra machinery).
Poor fit for a fluctuating set of named servers (classic web-cache churn).

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

jump_hash.go

// Jump Consistent Hash (Lamping & Veach, 2014).
// Returns a bucket in [0, numBuckets) using zero stored state.
package main

func jumpConsistentHash(key uint64, numBuckets int) int {
	var b int64 = -1
	var j int64 = 0
	for j < int64(numBuckets) {
		b = j
		// a 64-bit LCG step: the pseudo-random stream for this key
		key = key*2862933555777941757 + 1
		// next candidate jumps forward; bigger jumps are rarer
		r := float64((key >> 33) + 1)
		j = int64(float64(b+1) * (float64(int64(1)<<31) / r))
	}
	return int(b) // last bucket we landed on before overshooting
}

func main() {
	// Each key needs a 64-bit seed (hash the key once).
	jumpConsistentHash(0x123456789abcdef0, 6) // -> a bucket 0..5
	// Grow to 7 buckets: only ~1/7 of keys move, into the new bucket 6.
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. Sign in to save your best score.

question 01 / 03

How much state does jump consistent hash store?

question 02 / 03

When you grow from N to N+1 buckets, roughly what fraction of keys move?

question 03 / 03

What is jump hash's main limitation?

0/3 answered