Understanding Jump Consistent Hash: Principles, Implementation, and Performance

Consistent hashing distributes key‑value pairs across multiple nodes, but traditional modulo‑based hashing causes massive data movement when nodes are added. Jump consistent hash, introduced by Google, reduces the amount of data that needs to be moved to only about 1/n of the total when a new node joins.

The basic implementation starts node numbering from 1 instead of 0. For a single node, all keys map to node 1 ( ch(key,1)=1 ). When a second node is added, half of the keys are randomly moved to node 2; when a third node is added, one‑third of the keys are randomly moved to node 3, and so on, ensuring that each addition only moves a small fraction of data.

The algorithm uses a reproducible random sequence: the key itself is used as the seed for a random number generator, so the same key follows the same random decisions across different runs.

Mathematical induction describes the placement: for n nodes, a key stays on its current node unless a random value is less than 1/(n+1), in which case it jumps to the newly added node. This logic directly maps to a recursive function.

Example Go implementation:

func ch(r *rand.Rand, k int, i int) int {
    if i == 1 {
        // base case
        return 1
    } else {
        // inductive case
        b := ch(r, k, i-1)
        if rand.Float() < 1.0/float64(i) {
            return i
        } else {
            return b
        }
    }
}

func ch_wrapper(k int, i int) int {
    r := rand.Seed(k) // use key as random seed
    return ch(r, k, i)
}

In production code the recursion is usually replaced by an iterative loop for efficiency.

Performance-wise, the naive implementation scans all nodes (O(N)). The original paper presents a logarithmic‑time method that directly samples the next jump target according to a specific probability distribution, further reducing the computational cost.

Further details and the original paper "A Fast, Minimal Memory, Consistent Hash Algorithm" are linked at the end of the article.