How it works

This chapter walks through a small ring by hand: lookups, adding and removing nodes, virtual nodes and replica selection. To keep the numbers readable, assume a tiny hash space from 0 to 99. Real implementations use something like 0 to 2^64 - 1.

Step 1: place the nodes

Hashing the names of nodes A, B and C gives these positions.

Once the positions are sorted, each node's range follows. The rule is "the first node at or after the key", so a node owns everything after its predecessor up to and including its own position.

Step 2: look up keys

Binary-search the sorted array for the key's position. If you run off the end, wrap to index 0.

import bisect

points = [10, 45, 80]
owner = {10: "A", 45: "B", 80: "C"}

def lookup(h: int) -> str:
    i = bisect.bisect_left(points, h)   # first point >= h
    if i == len(points):
        i = 0                           # wrap around
    return owner[points[i]]

print([lookup(h) for h in (7, 33, 52, 91, 45)])  # ['A', 'B', 'C', 'A', 'B']

Step 3: add a node

A new node D lands at position 60. The only range that changes is between D's predecessor B(45) and D(60), that is 46-60. That range used to belong to C, so only some of C's keys move to D. Not a single key owned by A or B moves.

The giver is always the new node's clockwise successor and the receiver is always the new node. That is the "old nodes never trade keys" property in action.

Step 4: remove a node

Now suppose B fails. Its range 11-45 passes to its clockwise successor; everything else stays. The catch is that a single neighbour absorbs the whole range, so its load can nearly double overnight.

Step 5: spread the load with virtual nodes

Several points per node soften that problem. Hash A as A#0, A#1 and A#2 to get three points, and do the same for B and C.

If B now leaves, its three ranges go to the owners of the next points: A, A and C. With more points, the orphaned share is split across more nodes. Running the code below for 10 servers, one point per node leaves the busiest node with more than 3 times the average and another almost idle; with 100 points the shares fall within roughly 0.86 to 1.17 times the average, and with 1,000 points within about 0.93 to 1.05 (one run; exact numbers depend on the hash function and node names).

import bisect, hashlib

def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

RING = 1 << 64
for v in (1, 10, 100, 1000):
    pts = sorted((h(f"node{n}#{i}"), n) for n in range(10) for i in range(v))
    share = [0] * 10
    for j, (p, n) in enumerate(pts):
        share[n] += (p - pts[j - 1][0]) % RING   # arc owned by this point
    ratios = [s / RING * 10 for s in share]
    print(v, round(max(ratios), 2), round(min(ratios), 2))

Step 6: choose replicas

Dynamo-style stores do not keep a key on one node; they replicate it to several nodes following the ring clockwise. With virtual nodes, consecutive points can belong to the same physical machine, so skip machines already chosen and collect R distinct nodes. In the table above, two replicas for a key at position 30 are B (41) then A (55).

def replicas(points, owner, h, r):
    start = bisect.bisect_left(points, h)
    chosen = []
    for step in range(len(points)):
        node = owner[points[(start + step) % len(points)]]
        if node not in chosen:
            chosen.append(node)
            if len(chosen) == r:
                break
    return chosen

The same job with rendezvous hashing

Rendezvous hashing gets the same guarantees without a ring. For each key, compute hash(node:key) for every node and pick the top score. When a node leaves, only keys where it ranked first move, each to its runner-up; when a node joins, only keys where it now ranks first move to it. For replicas, take the top R scores.

def rendezvous(key: str, nodes: list[str]) -> str:
    return max(nodes, key=lambda node: h(f"{node}:{key}"))

Summary

• A lookup is a sorted array, a binary search and a wrap-around.
• Adding a node changes only the range in front of it; removing one changes only its own ranges.
• Virtual nodes shrink the variance and spread a departed node's load over many peers.
• Replicas come from walking clockwise and collecting distinct physical nodes.