Expand description
Implementation of the JumpBackHash consistent hash algorithm (Ertl, 2024, https://arxiv.org/abs/2403.18682).
Distributed systems need efficient ways to map keys to buckets. The naive modulo approach is fast but unstable: changing the bucket count remaps most keys, causing traffic spikes. Consistent hash algorithms minimise remappings, but existing ones are either slow, require floating-point arithmetic, or depend on hash-function families not found in standard libraries. JumpBackHash avoids all of these: it borrows the concept of active indices from consistent weighted sampling to guarantee consistency, generates those indices in reverse order to eliminate floating-point operations, and minimises the number of random values consumed — making it both simple and fast with an expected constant runtime.
This crate implements only the bucketing algorithm itself. The caller is responsible for
choosing and seeding the rand_core::RngCore passed to bucket.
Functions§
- bucket
- Maps an RNG state to a bucket index in
[0, num_buckets)using JumpBackHash (Ertl, 2024, https://arxiv.org/abs/2403.18682).