Jump Consistent Hash

The ring costs memory (every node times its points), a binary search per lookup, and a structure that every client must agree on. In 2014 John Lamping and Eric Veach at Google published a function that needs no memory at all, takes O(log N) expected time, and still moves the minimum number of keys when the bucket count grows. Your program will implement it and measure it.

The idea: replay the history of growth

Picture buckets being added one at a time: 1 bucket, then 2, then 3, up to N. A perfectly fair scheme must move exactly 1/(m+1) of all keys into bucket m when it appears, and nothing between older buckets. Jump hash replays that history for one key, and only records the moments when the key jumps.

For one key we only need to know: "while the count grows, in which bucket does the key sit, and when does it next jump?" The key's mth decision must be "stay" with probability m/(m+1). Multiply those chances from bucket b+1 up to n and they telescope to (b+1)/n. So if the key currently sits in bucket b, the first bucket count at which it jumps is j = floor((b+1) / r) for a uniform random r in (0, 1]. Check: the key survives to n buckets when j >= n, that is when r <= (b+1)/n, which has probability (b+1)/n.

A key must make the same random choices every time, so r comes from a tiny deterministic generator seeded by the key.

The algorithm in steps

1. Start with b = -1 and j = 0.
2. While j < n: set b = j, then advance the generator one step: key = key * 2862933555777941757 + 1, modulo 2^64.
3. Turn the new state into r by taking its top bits: r = ((key >> 33) + 1) / 2^31. Then the next jump target is j = floor((b + 1) / r), computed in double-precision floating point.
4. When the loop ends, b is the answer.

Here is key 42, tracked as the bucket count grows. It sits in each bucket until the count reaches the listed value:

buckets n :   1    2    3    23    34    41    44    572
bucket    :   0    1    2    22    33    40    43    571

Only seven jumps happen between 1 and 800 buckets. That is why the loop runs O(log N) times in expectation. The result for n = 100 is bucket 43.

What you get and what you give up

When N grows to N+1 a key either stays or jumps into the new bucket, never between two old ones. Each key moves with probability 1/(N+1), which is the theoretical minimum. That is an expectation, not a certainty: over ten keys you may see one move where 1/(N+1) predicts a fraction. Count real differences.

The catch is that buckets are integers 0..N-1. You cannot add a node called cache-west-7 or remove bucket 3 without renumbering; you can only grow or shrink at the top. That suits sharding a table, a queue or a range of user ids, and does not suit a named cache fleet. Guava's Hashing.consistentHash is this algorithm, and ClickHouse exposes it as jumpConsistentHash.

The 64-bit trap

The multiplication must wrap at 64 bits. C, C++, Go and Rust (with wrapping_mul) have fixed-width unsigned types, and a Rust plain * panics on overflow. JavaScript numbers are doubles and Python integers never wrap, so mask or BigInt the key after each step. Unmasked, the state grows without bound, the top bits stop being random, and the loop does not end.

Common mistakes

• No 64-bit wrap. HASH 18446744073709551615 100 (the largest key) and the large-key vectors hang or give wrong buckets.
• Integer division. The factor 2^31 / ((key >> 33) + 1) is floating point. Integer division gives a different bucket.
• Wrong separators. Lines are <key>: <bucket> with a colon and one space; a moved key prints <key>: <old> -> <new>.
• Using theory for moved. Count the keys whose buckets differ; do not print N/(N+1)-style estimates.

Your exercise

Implement the hash and three reports built on it. The starter reads the commands and parses the keys.