Jump consistent hash: picking a shard number without a lookup table, and what it assumes

The simplest way to split key-value data across 10 shards is to take the key’s hash modulo 10, h(key) mod 10, and use that as the shard number. When the data grows and you need 12 shards, the formula becomes h(key) mod 12, and most keys now belong somewhere else.

How many? Assume the hash values are evenly spread and count. The two remainders agree only when h mod 60 is between 0 and 9. (60 is the least common multiple of 10 and 12. If both remainders equal some r, then h ≡ r (mod 60), and r has to be smaller than 10.) That is 10 cases out of 60: 1/6 of the keys stay put and 5/6 have to move.

John Lamping and Eric Veach use the same example in “A Fast, Minimal Memory, Consistent Hash Algorithm” (submitted to arXiv on 9 June 2014) and point out that rebalancing onto 12 shards only requires moving 1/6 of the data held by the 10. Their jump consistent hash picks shard numbers so that only that 1/6 moves, in about five lines of code. This article is based on that paper alone. All performance figures below are the paper’s own 2014 measurements; none were re-measured here.

The two promises

Jump consistent hash takes a 64-bit key and a number of buckets (shards) and returns a bucket number in [0, num_buckets). The paper says it satisfies two properties:

Balance: each bucket gets about the same number of keys.
Monotonicity: when the number of buckets increases, keys move only from old buckets to new ones. Old buckets never trade keys with each other.

Consistent hashing as a concept was introduced by Karger et al. in 1997 for web caching, with four properties. The paper explains that the other two, spread and load, describe what happens when each client may see a different subset of servers. Jump consistent hash assumes every client sees the same set of buckets, [0, num_buckets), and that restriction is what makes it possible.

The code from the paper

Figure 1 of the paper is the complete C++ implementation:

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

There is no table, no server list and nothing to build in advance. In the paper’s words, it needs no memory beyond what fits in a few registers. Why this gives balance and monotonicity is easiest to see from a slower version that adds buckets one at a time.

Adding one bucket at a time

Write ch(k, n) for the bucket of key k when there are n buckets. With one bucket the answer is 0. With two, half the keys must stay in 0 and half must move to the new bucket 1, or the split is uneven. In general, going from n to n+1 buckets, n/(n+1) of the keys stay where they are and 1/(n+1) “jump” to the new bucket n. The new bucket then gets its 1/(n+1) share, and every old bucket gives up the same fraction.

The paper shows three example keys as the bucket count grows (top row is the number of buckets):

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

Whenever a value changes, it changes to the newest bucket in that column (bucket count − 1). k3 jumps to 5 at six buckets, to 7 at eight and to 10 at eleven. It never moves sideways between old buckets.

Turned directly into code, this rule is the paper’s linear-time version. Seed a pseudo-random generator with the key, loop j from 1 to num_buckets − 1, and set the result to j whenever a uniform random number in [0, 1) is less than 1/(j+1). The same key always produces the same random sequence, so it always gets the same answer. The cost grows with the number of buckets.

Computing the next jump directly

For most j the result does not change; it only jumps now and then. So compute only the jumps. The paper’s derivation:

One step keeps the result with probability n/(n+1). Chain several steps and the product telescopes: for m ≤ n, the probability that ch(k, m) equals ch(k, n) is m/n. For example, 10/11 × 11/12 = 10/12.
Say the last jump set the result to b, and let j be the position just before the next jump. For any i > b, the probability that j ≥ i is the probability that ch(k, i) = ch(k, b+1), which is (b+1)/i.
Draw a uniform random r between 0 and 1 and declare j ≥ i exactly when r ≤ (b+1)/i. That gives the right distribution. Solving for i gives i ≤ (b+1)/r, so j = floor((b+1)/r).

The algorithm keeps computing the next jump until it reaches num_buckets or beyond, then returns the last jump destination b.

Here is how Figure 1 lines up with that derivation (the mapping is this article’s reading of the code):

key = key * 2862933555777941757ULL + 1 is one step of a 64-bit linear congruential generator (LCG). The key is the seed, and the state is updated on every iteration. The paper cites L’Ecuyer’s tables for this multiplier, which gives well-distributed values even when successive outputs are used together.
(key >> 33) + 1 is the top 31 bits of the state plus one, a value from 1 to 2³¹. Divide it by 2³¹ and call it r: r is greater than 0 and at most 1. It is never 0, so there is no division by zero.
(b + 1) * (2³¹ / ((key >> 33) + 1)) is (b+1)/r. Storing it in the int64_t j drops the fractional part, which gives floor((b+1)/r).
Because r ≤ 1, the new j is always at least b+1. j grows by at least 1 per iteration, so the loop always ends.

Cost: fewer than ln n + 1 iterations on average

From the paper’s analysis: the chance of a jump at bucket count i is 1/i, so the expected number of jumps to positions below n is the sum of 1/i for i from 2 to n, which is less than ln(n). One more iteration steps past n, so the expected number of iterations is less than ln(n) + 1. The paper notes this is a constant factor fewer than the log₂(n) comparisons of a binary search over n sorted keys. It is an expected value, not a bound on how many iterations a particular key takes.

Compared with a hash ring

Karger et al.’s algorithm places several random points per bucket on the unit circle, maps the key onto the circle and walks clockwise to the first point, returning that point’s bucket. With few points, bucket sizes are uneven, so you need many points and the memory that goes with them. The paper reports these results, measured in 2014 on an Intel Xeon E5-1650:

Even with 1000 points per bucket, the 99% confidence interval for bucket size was 0.92× to 1.09× the average. For jump consistent hash it was 0.99999998× to 1.00000002×.
With 1000 points per bucket and 1000 buckets, the ring data took 46 MB (STL map) or 7.6 MB (sorted vector), depending on the implementation. Jump consistent hash has no data structure to store.
Up to 1000 buckets, jump consistent hash was 3–4× faster than a ring with 1000 points per bucket.

Adding a bucket also behaves differently. According to the paper, with jump consistent hash the new bucket takes an equal share from every existing bucket: with 1000 buckets, each existing bucket hands over almost exactly 0.1% of its key space. On a ring, only the buckets where the new bucket’s points land give up data; with 10 points per bucket, at most 10 buckets take part. If you added the bucket to relieve one overloaded bucket, that bucket may not be among them.

What happens when the bucket count changes

Growing

Going from n to n+1 buckets, every key that changes goes to the new bucket n. Going from 10 to 12 applies that rule twice, so every key that changes ends up in bucket 10 or 11. From the probability above, ch(k, 10) and ch(k, 12) agree with probability 10/12, so 2/12 = 1/6 of the keys move. Against the 5/6 of mod from the start, that is a fifth of the traffic.

Shrinking

Going from n down to n−1 follows directly from monotonicity (this article’s derivation). When growing from n−1 to n, every key that changed went to bucket n−1. Reversing that, shrinking redistributes only the keys that were in the last bucket, n−1, and every other key stays where it is.

You cannot remove a bucket in the middle

The bucket you can remove is always the highest-numbered one. If server 3 of 10 dies and you set num_buckets to 9, server 3’s keys still map to 3, and it is bucket 9’s keys that get redistributed. The function returns a number counting from 0, not a server name.

This trap shows up when the result indexes a server list. Write servers[JumpConsistentHash(key, servers.size())], delete a server from the middle of the list, and every server after it shifts down one slot. Even though the function’s output barely changes, the mapping from numbers to servers does, and most keys now go to the wrong server (this article’s derivation).

The paper names this as the algorithm’s main limitation: buckets must be numbered sequentially, which makes it a better fit for data storage than for distributed web caching. Its premise is that in a storage system a shard cannot simply vanish, so server failure is handled with replicas or fast replacement, and data is reallocated only when capacity changes. If you need to add and remove arbitrary servers in any order, the approaches the paper lists as related work support arbitrary bucket IDs: Karger et al.’s ring, or Thaler and Ravishankar’s rendezvous hashing. The paper notes that the original rendezvous algorithm computes h(key, bucket) for every bucket and picks the largest, which takes time proportional to the number of buckets.

Before you use it

num_buckets must be at least 1. Given 0 or a negative number, the Figure 1 code never enters the loop and returns -1 (you can see this by reading the code). Used directly as an array index, that is an out-of-bounds access, so reject it before calling. The parameter is int32_t, so the bucket count tops out at 2³¹ − 1.
The key is a 64-bit integer. The paper says keys that do not fit in 64 bits should be hashed to 64 bits first. Keys that are already integers need no extra hashing, it explains, because the built-in LCG remixes the key on every iteration. What a hash function does and does not guarantee is covered in What a hash function does.
Every client and every run must produce the same key hash. The algorithm relies on every client computing the same bucket for the same key. Feed it a hash whose seed changes per run (for example, Python’s randomized str hash) and keys point at different shards after every restart.
Every client must use the same num_buckets. While only some clients have switched to a new value, the same key can point at two different shards. The function tells you which keys move; moving the data and ordering the cutover is up to you.
Match the arithmetic when porting. The multiply is unsigned 64-bit arithmetic that keeps only the remainder mod 2⁶⁴, >> 33 shifts an unsigned value, and the division is double-precision floating point. Get any of the three wrong and you get different buckets from the C++ version.

Python integers, for instance, have no size limit, so you have to apply the 64-bit mask yourself after the multiply. This is this article’s port of Figure 1, with non-positive bucket counts rejected:

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

For this post, the same 28,001 inputs were run through this port on CPython and through the Figure 1 C++ code compiled locally, and every result matched in that environment. That is one tested environment, nothing more. The operands being small integers does not by itself show that the division and the integer conversion give the same result across languages. Before using it in production, compare it with the C++ version on your own language, compiler and platform, across a range of keys and bucket counts.

Paper used

John Lamping, Eric Veach, A Fast, Minimal Memory, Consistent Hash Algorithm, arXiv:1406.2294v1 [cs.DS], submitted 9 June 2014 (PDF)

The papers by Karger et al. (1997), Thaler and Ravishankar (1997) and L’Ecuyer were not opened for this article; everything said about them here is the account given in the paper above. The paper was checked on 19 October 2026.