Jump consistent hash

Deep dive

How it works

In: a well-mixed 64-bit key and a bucket count n · Out: bucket in 0..n−1 · State: none · Cost: O(ln n) expected iterations, O(1) memory

Let ch(k, n) be the bucket for key k. Required: ch(k, 1) = 0, and going from n to n+1 the key either stays or moves to bucket n, with probability 1/(n+1).

1. Seed a PRNG with the key. Track b = current bucket (last jump destination) and j = next jump destination.
2. With current bucket b, the probability that the next jump lands at or beyond bucket i is P(j ≥ i) = (b+1)/i (product of the per-step stay probabilities). So draw r ∈ (0,1] and set j = floor((b+1)/r).
3. Repeat while j < n; the answer is the last b.

The 64-bit LCG key = key * 2862933555777941757 + 1 provides r from its top 31 bits.

n:      1   2   3   4   5   6   7   8
key k:  0   0   2   2   2   2   6   6     (jumps at n=3 and n=7 only)

Code

/// Lamping & Veach jump consistent hash. `key` must already be a well-mixed 64-bit hash.
pub fn jump_hash(mut key: u64, buckets: u32) -> u32 {
    assert!(buckets > 0);
    let (mut b, mut j): (i64, i64) = (-1, 0);
    while j < buckets as i64 {
        b = j;
        key = key.wrapping_mul(2862933555777941757).wrapping_add(1);
        // r = ((key >> 33) + 1) / 2^31 in (0, 1]; next jump at floor((b + 1) / r).
        j = ((b + 1) as f64 * ((1u64 << 31) as f64 / ((key >> 33) + 1) as f64)) as i64;
    }
    b as u32
}

/// Hash arbitrary bytes first (FNV-1a + splitmix64 finalizer, stable everywhere).
pub fn key_hash(b: &[u8]) -> u64 {
    let mut h: u64 = 0xcbf29ce484222325;
    for &x in b { h = (h ^ x as u64).wrapping_mul(0x100000001b3); }
    h = (h ^ (h >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
    h = (h ^ (h >> 27)).wrapping_mul(0x94d049bb133111eb);
    h ^ (h >> 31)
}

/// Shards are logical; a table maps shard -> live node so nodes can fail anywhere.
pub struct Placement { pub shard_to_node: Vec<String> }

impl Placement {
    pub fn node_for(&self, key: &[u8]) -> &str {
        let shard = jump_hash(key_hash(key), self.shard_to_node.len() as u32);
        &self.shard_to_node[shard as usize]
    }
}

fn main() {
    // Movement check: growing 10 -> 11 buckets should move ~1/11 of keys, all to bucket 10.
    let (mut moved, mut wrong) = (0u32, 0u32);
    for i in 0..1_000_000u64 {
        let k = key_hash(&i.to_le_bytes());
        let (a, b) = (jump_hash(k, 10), jump_hash(k, 11));
        if a != b { moved += 1; if b != 10 { wrong += 1; } }
    }
    println!("moved {:.4} (expect {:.4}), wrong {wrong}", moved as f64 / 1e6, 1.0 / 11.0);
}

Complexity and constants

• Iterations: expected below ln(n) + 1, because jump destinations grow geometrically. n = 1,000 → ~8; n = 10⁶ → ~15.
• Per iteration: one 64-bit multiply, one f64 division (order of 10-15 cycles latency), a convert: total order of 10-50 ns for realistic n; branch mispredicts on loop exit dominate for small n.
• Memory: none. Compared with a ring of 10⁵ points (≈ 1.6 MB), it never misses cache.
• Balance: per-bucket load is binomial; no systematic skew.

Efficiency

• Cost: about ln(n) + 1 iterations per key (8 at n = 1,000; 15 at n = 10⁶), each one 64-bit multiply plus one f64 division: order of 10-50 ns per call on a modern core, no memory traffic. State is zero bytes, against about 1.6 MB for a ring of 10⁵ points. Bound: compute (division latency, loop-exit branch mispredicts).
• Levers:
  • hash the key once and reuse the 64-bit value across lookups — drops repeated byte hashing (order of) — keys that are looked up many times
  • fewer, larger logical shards plus a shard → node table — iterations grow only with ln(shards), and a node failure moves no keys (above) — clusters with failures
  • keep n small and stable per rollout — fewer iterations and no remapping mid-rollout (above) — config-driven shard counts
  • a fast 64-bit mixer such as the splitmix64 finalizer — a few cycles, enough for balance (above) — clustered or sequential IDs
• Naive → standard → state of the art:
  • hash(key) % n · O(1) but remaps about n/(n+1) of keys when n grows
  • ring with virtual nodes · O(log(nodes × vnodes)) lookup, memory per vnode
  • jump hash over logical shards plus a table · O(ln n), zero memory, 1/(n+1) keys moved (Lamping and Veach 2014)

Implementation notes

• Feed it a good 64-bit hash: the LCG alone does not fix clustered input keys like sequential IDs (key_hash above does).
• Keep the bucket count as the source of truth in config; every client must agree on n at the same time (version the shard map).
• To survive arbitrary node failures, make buckets logical shards and keep a small shard → node table (shown); failover rewrites a table entry and moves no keys between shards.
• Shrinking from n to n−1 moves only the keys of bucket n−1, evenly spread over the others.
• Keep the paper's exact constants and f64 arithmetic when several languages must agree; faithful ports give identical bucket numbers.

Pitfalls

• Removing a middle bucket by renumbering: shifts every higher bucket and remaps far more than 1/n of keys.
• Passing a 32-bit hash or small integers directly: the LCG warms up, but low-entropy keys still give visibly worse distribution; mix first.
• Different clients using a different n during a rollout: keys flip between shards; coordinate the change.
• Using it for weighted nodes: it has no weight support; give heavy nodes several shards instead.

Variants and alternatives

In production

ClickHouse (jumpConsistentHash SQL function, used for sharding expressions), Guava Hashing.consistentHash (the same LCG jump scheme), widely ported libraries in Go, Java, C++ and Rust for client-side shard selection.

Implementations

Sources

• John Lamping, Eric Veach, A Fast, Minimal Memory, Consistent Hash Algorithm, arXiv 1406.2294, 2014. paper
• Ben Appleton, Michael O'Reilly, Multi-Probe Consistent Hashing, arXiv 1505.00062, 2015. paper
• Gal Mendelson et al., AnchorHash: A Scalable Consistent Hash, IEEE/ACM Transactions on Networking, 2021. paper