Consistent Hashing

How to minimize data migration when the number of nodes changes? Consistent hashing maps nodes and data to the same ring, with each key finding the nearest node clockwise—adding or removing nodes only affects adjacent intervals. Virtual nodes further balance the load, at the cost of a larger routing table.

Problem: Minimizing Data Migration When Node Count Changes

With standard hash(key) % N: N nodes → add/remove nodes → the mapping for all keys changes → all data must be migrated. Consistent hashing solves this: when adding or removing nodes, only K/N of the keys need to be migrated (where K is the total number of keys).

Hash Ring + Virtual Nodes (Chord/Dynamo Approach)

Algorithm

1. For each node: compute hash(node_id) → map to ring [0, 2^32)
2. For each key: compute hash(key) → map to ring
3. Key is assigned to: the first node encountered clockwise from the key's position

Adding/Removing Nodes:
  - Add node: only keys between the new node and its counter-clockwise neighbor need to be migrated to the new node
  - Remove node: the node's keys are migrated to the next clockwise node

Virtual Nodes (Vnodes)

When the number of physical nodes is small (e.g., 5), node distribution on the ring is uneven → data skew. Virtual nodes: each physical node corresponds to V virtual nodes (typically 100-200), randomly distributed on the ring.

• More vnodes per physical node → more balanced load
• Vnode count is independent of physical node count → when adding a physical node, only some vnodes need to be reassigned to the new physical node

Dynamo/Cassandra: each physical node has 256 vnodes on the ring.

Jump Hash (Google Approach)

No need to store ring structure; O(log N) computation to determine which bucket a key belongs to:

int jump_consistent_hash(uint64_t key, int num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        double r = random_next(key, j);  // deterministic PRNG
        j = floor((b + 1) / r);
    }
    return b;
}

Properties: each bucket has equal probability (1/num_buckets). When adding or removing buckets, only 1/num_buckets of the keys need to be migrated. No ring data structure required.

Limitations: buckets must be consecutively numbered (0..N-1), does not support arbitrary node_ids. Does not support weighting (all buckets have equal weight).

Google uses it for CDN cache sharding and storage bucket allocation.

Rendezvous Hash (HRW: Highest Random Weight)

For each key, compute a score for each node, and select the highest score:

for each node N:
    score = hash(key, node_id)
assign key to: node with highest score

Adding/Removing Nodes: only affects keys whose highest-scoring node changes. An important difference from jump hash: even if the number of nodes changes, only the keys originally assigned to that node are affected—the winner for other keys remains unchanged.

Features: naturally supports weighting (score = hash(key, node_id) / weight). No global state required.

Applications: Apache Ignite, HAProxy (consistent balancing with balance url_param).

Comparison

References

• Paper: "Consistent Hashing and Random Trees" (Karger et al, 1997)
• Paper: "A Fast, Minimal Memory, Consistent Hash Algorithm" (Lamping & Veach, 2014 — jump hash)
• Dynamo: "Dynamo: Amazon's Highly Available Key-value Store" (2007, section 4.5)

Keywords: consistent hashing, hash ring, virtual nodes, vnodes, jump hash, rendezvous hash, highest random weight