STANDARDwalkthrough
Jump Consistent Hashing
Google published Jump Hash in 2014 as a zero-memory alternative to ring-based consistent hashing. The algorithm uses a PRNG seeded by the key to 'jump' through bucket assignments, producing a bucket number in time with no ring or vnode table.
When N changes from 100 to 101, exactly of keys remap. Why not always use jump hash?
“Output is perfectly uniform: each of N buckets gets exactly of keys.”
It assumes sequential bucket numbering 0 to N-1. You cannot remove bucket 47 and keep 0-46 and 48-100.
Removal cascades. This makes jump hash ideal for append-only scaling but unsuitable for clusters where nodes fail at arbitrary positions.
We chose ring + vnodes because our cache cluster needs arbitrary node removal. Jump hash fits better for static datasets like log partition assignment.
Trade-off: jump hash has zero memory and perfect distribution, but cannot handle arbitrary removal.