Practice problems

Every problem below reuses hash64 and HashRing from the implementation chapter (sorted points plus the owner map from position to node). Try each one yourself before reading the solution.

Problem 1. Each node's share of the ring

Given a ring, compute what fraction of the full 2^64 space each node owns. Vary the vnode count over 1, 10, 100 and 1000 and see how far the largest and smallest shares drift from the average.

Approach: each point owns everything after the previous point up to itself. Walk the sorted points and add (p - previous) mod 2^64 to the owner's total. The predecessor of index 0 is the last point, and Python's pts[-1] handles that wrap for free. A ring with a single point gives a difference of 0, so treat it separately.

RING_SIZE = 1 << 64

def ownership(ring: HashRing) -> dict[str, float]:
    pts = ring.points
    if len(pts) == 1:
        return {ring.owner[pts[0]]: 1.0}
    share: dict[str, int] = {}
    for i, p in enumerate(pts):
        arc = (p - pts[i - 1]) % RING_SIZE   # i == 0 wraps to the last point
        node = ring.owner[p]
        share[node] = share.get(node, 0) + arc
    return {node: s / RING_SIZE for node, s in share.items()}

for v in (1, 10, 100, 1000):
    r = HashRing(vnodes=v)
    for n in range(10):
        r.add(f"node-{n}")
    s = ownership(r)
    print(v, round(max(s.values()) * 10, 2), round(min(s.values()) * 10, 2))

Multiplying by the node count normalizes the average to 1. As vnodes increase, both extremes approach 1.

Problem 2. Replicas in distinct zones

Each node belongs to an availability zone. Pick R replicas for a key that are distinct physical nodes in distinct zones. If not enough qualify, return as many as you found.

Approach: walk clockwise from the key one point at a time, skipping nodes already chosen and zones already used. Stop after one full lap.

import bisect

def zone_replicas(ring: HashRing, zone_of: dict[str, str], key: str, n: int) -> list[str]:
    pts = ring.points
    start = bisect.bisect_left(pts, hash64(key))
    chosen: list[str] = []
    zones: set[str] = set()
    for step in range(len(pts)):
        node = ring.owner[pts[(start + step) % len(pts)]]
        if node in chosen or zone_of[node] in zones:
            continue
        chosen.append(node)
        zones.add(zone_of[node])
        if len(chosen) == n:
            break
    return chosen

zone_of = {"a1": "az-1", "a2": "az-1", "b1": "az-2", "b2": "az-2", "c1": "az-3"}
ring = HashRing(vnodes=50)
for node in zone_of:
    ring.add(node)
print(zone_replicas(ring, zone_of, "order:1001", 3))  # one node from each zone

Problem 3. A migration plan for a new node

Before adding a node, list which hash ranges it takes over and from which existing node. Return tuples where each range excludes start and includes end.