jump-back-hash

Rust implementation of the JumpBackHash consistent hash algorithm (Ertl, 2024, arXiv:2403.18682).

What problem does it solve?

Distributed systems need to map keys to buckets (shards, nodes, partitions). The naive approach — key % n — is fast but unstable: when n changes, almost every key gets remapped, causing traffic spikes across the whole system.

Consistent hash algorithms minimise remappings so that only the theoretically unavoidable keys move. When the bucket count grows from n to n+1, at most 1/(n+1) of all keys need to move — and JumpBackHash achieves exactly that bound.

Existing consistent hash algorithms pay for this property with floating-point arithmetic, non-standard hash-function families, or high constant-factor overhead. JumpBackHash avoids all of those: it generates candidate bucket indices in reverse order using only integer arithmetic and a standard pseudorandom generator, and has an expected constant runtime.

Usage

The crate exposes a single function:

pub fn bucket<R: rand_core::RngCore>(rng: &mut R, num_buckets: u64) -> u32

You are responsible for seeding rng from your key. This keeps the crate agnostic about which pseudorandom generator you use. Any RngCore implementation works; a good-quality generator such as SplitMix64 is recommended.

use jump_back_hash::bucket;

// Seed your RNG from the key hash, then call bucket().
// Here we use a hypothetical `my_rng_from(key)` — any RngCore will do.
let mut rng = my_rng_from(key_hash);
let shard = bucket(&mut rng, num_shards);

The function returns a value in [0, num_buckets). num_buckets == 0 or num_buckets == 1 both return 0.

Consistency guarantee

When the bucket count grows from n to n+1, only the keys that were assigned to bucket n are redistributed among all n+1 buckets. All other keys stay on the same bucket. This means exactly 1/(n+1) of keys move — the theoretical minimum.

This property is verified by a statistical test in the test suite: 10 000 random keys are hashed into n buckets and into n+1 buckets, and the fraction that changed assignment is compared against 1/(n+1) within ±4 standard deviations of the expected binomial distribution.

References

O. Ertl, "JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets", 2024. https://arxiv.org/abs/2403.18682

License