Consistent Hashing

Consistent hashing addresses a specific problem: when members change, how can most keys retain their original ownership? The term "consistency" here describes the nature of mapping changes and is not the same concept as linear consistency in databases.

First, separate two levels: the mapping algorithm answers "where should it be placed now"; the migration protocol ensures "reads and writes remain correct when moving from the original location." Modifying the hash function or member list does not automatically move the data.

Why direct modulo is prone to large-scale remapping

Let bucket = hash(key) % N. When increasing from 3 buckets to 4 buckets, the remainder of the same hash value may change. For example, 5 changes from bucket 2 to bucket 1, 6 changes from bucket 0 to bucket 2, while 1 remains in bucket 1. Not all keys move, but the changes far exceed the data the new bucket needs to receive.

Under the assumption of uniformly distributed hash values and unchanged bucket numbering, when moving from N to N+1, only N out of every consecutive N(N+1) integers retain the same remainder. Therefore, approximately N/(N+1) of the keys change ownership. Ideal balanced expansion only requires the new bucket to receive about 1/(N+1) of the keys; this is the gap that needs to be closed. This calculation counts the number of keys; if object sizes differ, the byte volume does not scale proportionally.

Hash Ring: Ownership is determined by the first token encountered clockwise

Imagine the hash space as a circle where the start and end connect. Nodes possess tokens on the ring; the first token encountered clockwise by a key's hash value determines its ownership; after exceeding the maximum value, it wraps around to the minimum. If the previous token is p and the current token is q, the interval is typically written as (p, q].

For easier calculation, we use a small space from 0 to 99 below: tokens for A, B, and C are 20, 60, and 90 respectively. After adding D with token 40, the interval (20, 40], originally belonging to B, now belongs to D, while the main ownership of the rest remains unchanged.

Queries can maintain a sorted array of tokens, using binary search to find the first token not less than the key's hash value; if none exists, select the first item in the array. It is essential to unify key encoding, hash algorithm, token sorting, and endpoint rules; otherwise, different clients will calculate different ownerships.

This example only discusses the primary ownership of a single piece of data. Replication systems also need to select subsequent replicas, skipping tokens belonging to the same physical node, and satisfying rack or availability zone isolation. Member changes may affect the replica set; even if the primary ownership hasn't changed, replica replenishment may still be required.

Writing boundary, wrap-around, and physical replica deduplication as code

The following implementation directly receives hash positions from 0–99, facilitating traversal of all positions to verify changes. The ring is sorted at initialization, and queries use binary search for positioning; identical tokens are rejected directly to avoid different clients handling collisions with different rules.

from bisect import bisect_left

class Ring:
    def __init__(self, entries):
        self.entries = sorted(entries)
        self.positions = [position for position, _ in self.entries]
        if (not self.positions or len(set(self.positions)) != len(self.positions)
                or any(not 0 <= p < 100 for p in self.positions)):
            raise ValueError("Requires non-empty, unique tokens located between 0–99")
        self.node_count = len({node for _, node in self.entries})

    def replicas(self, position, count=1):
        if not 0 <= position < 100 or not 1 <= count <= self.node_count:
            raise ValueError("Invalid position or physical replica count")
        start = bisect_left(self.positions, position)
        result = []
        for step in range(len(self.entries)):
            node = self.entries[(start + step) % len(self.entries)][1]
            if node not in result:
                result.append(node)
                if len(result) == count:
                    return result
        raise AssertionError("Valid ring should have enough physical replicas")

before = Ring([(20, "A"), (60, "B"), (90, "C")])
after = Ring([(20, "A"), (40, "D"), (60, "B"), (90, "C")])
assert before.replicas(20) == ["A"]  # Right endpoint belongs to current token
assert before.replicas(21) == ["B"]
assert before.replicas(99) == ["A"]  # Wrap around after exceeding the end
moved = [p for p in range(100) if before.replicas(p) != after.replicas(p)]
assert moved == list(range(21, 41))
assert all(after.replicas(p) == ["D"] for p in moved)
assert before.replicas(10, 2) == ["A", "B"]
assert after.replicas(10, 2) == ["A", "D"]
vnodes = Ring([(20, "A"), (40, "A"), (60, "B"), (90, "C")])
assert vnodes.replicas(10, 3) == ["A", "B", "C"]

After adding D, exactly 20 positions move, rather than the average share of 25 for four nodes: the actual migration volume is determined by the position where D is inserted. When the replica count is 2, the primary node for position 10 is still A, but the second replica changes from B to D. Therefore, counting only primary ownership changes will miss the work of replica replenishment.

The last assertion ensures that two virtual tokens on the same physical node do not act as two independent replicas. This implementation only deduplicates physical nodes and does not have cross-rack or availability zone constraints; if fault domain dispersion is required, the selected subsequent nodes must continue to satisfy placement policies. Member table updates and data replication are also not included in the query function; returning D does not mean D already possesses the data.

Which keys actually change ownership when adding D?

Below, the ring is unrolled into cells arranged by hash position, making it easy to directly count the range of changes. D is inserted in front of B, taking over only (A, D]; positions exactly equal to D belong to D, and positions exactly equal to A still belong to A. Comparing the number of changed cells after adjusting tokens helps avoid mistaking the ideal uniform share for a ratio that is precisely met by every real insertion.

Virtual Nodes: Breaking large intervals into multiple small intervals

If each physical machine only places one random token, it is easy for one machine to occupy a very long interval while another occupies a very short one. Giving each machine multiple tokens can split capacity into many scattered shares. When node capacities differ, different numbers or sizes of shares can be allocated.

Virtual nodes reduce the bias caused by random interval sizes, but do not guarantee uniform request load: if a key accounts for most of the access, no matter how uniform its hash, it still falls into a single primary ownership. More tokens also increase the amount of routing metadata, interval maintenance, and recovery tasks.

In engineering, there are two different designs: generating new tokens when adding machines, or pre-establishing a large number of logical partitions and then reassigning some partitions to new machines. Both can refine migration granularity, but they differ in member changes, token stability, and metadata maintenance methods. Do not treat the default number of vnodes in a specific product version as an algorithm constant.

Rendezvous Hash: Let candidate nodes compete one by one

Rendezvous Hash, also known as HRW, calculates a deterministic score for each candidate node: score = H(key, stable_node_id), selecting the maximum. Implementation requires stable node identifiers, unambiguous input encoding, and deterministic sorting rules for tie-breaking scores.

Why do member changes only affect some keys? When deleting node X, for keys where the winner was not X, their candidate scores and the winner remain unchanged; when adding X, only keys where X defeats the original winner change ownership. Under the ideal assumptions of independent, uniformly distributed scores and identical node weights, the expected share received by the new node is 1/(N+1).

Weighting cannot simply be written as "divide hash value by weight and take the maximum," as that would actually suppress the scores of high-weight nodes. An explicit weighted construction is: map each node's hash result to Uᵢ∈(0,1), calculate Tᵢ = -ln(Uᵢ) / wᵢ, and select the node with the smallest T, where wᵢ>0. Because P(Tᵢ>t)=exp(-wᵢt), the exponential competition among independent candidates makes the node's winning probability wᵢ / Σw. This is a derivation under a given random model; actual implementations also need to handle hash quality and floating-point boundaries.

HRW does not require a hash ring, but still requires a consistent member list and weights. A naive implementation traverses N nodes for each query, with a computational cost of O(N); "stateless" does not mean "no cluster metadata."

HRW's stability comes from unchanged scores of old candidates

The following uses length-prefixed UTF-8 field encoding to avoid ("ab","c") and ("a","bc") producing the same input after concatenation. Scores use SHA-256, and in case of score collisions, stable node IDs are compared; the example shows equal-weight distribution and does not include the weighted variant above.

from hashlib import sha256

def encoded(key, node):
    fields = [part.encode("utf-8") for part in (key, node)]
    return b"".join(len(field).to_bytes(4, "big") + field for field in fields)

def winner(key, nodes):
    if not nodes:
        raise ValueError("No candidate nodes")
    return max(nodes, key=lambda node: (sha256(encoded(key, node)).digest(), node))

assert encoded("ab", "c") != encoded("a", "bc")
for i in range(5000):
    key = f"order-{i}"
    old = winner(key, ["A", "B", "C"])
    added = winner(key, ["A", "B", "C", "D"])
    assert added == old or added == "D"
    assert winner(key, ["C", "B", "A"]) == old
    removed = winner(key, ["A", "C"])
    assert old == "B" or removed == old

During expansion, the scores of old nodes A, B, and C do not change; D can only win or lose, and will not cause A's keys to inexplicably change to B. When deleting B, keys originally belonging to A and C still retain their ownership. If node IDs are regenerated on every deployment, or if key encoding or hash seeds change, this reasoning premise is broken, and large-scale remapping may occur even if no machines change.

The 5000 samples are used to check these properties of the implementation; the expected migration share of 1/4 comes from the independent uniform score model, and does not mean that exactly 1250 out of any 5000 business keys migrate, nor does it mean that the migration byte volume or hot request proportion is exactly one quarter.

Jump Consistent Hash: Only record the bucket count

Jump Hash maps keys to consecutively numbered buckets 0…N-1. It uses a deterministic jump process to find the final bucket, does not require saving a token array, has an expected computational complexity of O(log N), and an algorithmic extra space complexity of O(1).

The key constraint is that bucket numbers are continuous: when increasing from N to N+1, the new bucket is the last one, N; shrinking removes the last bucket. It does not directly solve the problem of "any physical machine exiting while other machine numbers remain unchanged." An additional mapping layer between buckets and physical machines can be added, but this layer of metadata and migration strategy needs to be designed separately. The algorithm and full implementation are in the Jump Hash original paper.

Quick Selection Guide

The above migration ratios all assume balanced conditions. Adding just one token at an arbitrary position on the ring determines how much moves based on the actual interval, not a fixed 1/N. Capacity weight changes, fault domain adjustments, and hotspot handling will also introduce additional migrations.

Continue reading: Sharding Strategies discusses choosing what key; Dynamic Rebalancing discusses how to migrate safely.

References

• Dynamo Original Paper: Combination of partitioning, virtual nodes, and replication.
• Jump Consistent Hash Original Paper: Algorithm and analysis under continuous bucket numbering.

Keywords: consistent hashing, hash ring, vnode, rendezvous hashing, HRW, jump hash