Vnodes flatten the lumpy ring

1def tokensForNode(nodeId, vnodeCount):
2    out = []
3    for i in range(vnodeCount):
4        # pure arithmetic, no rng — same answer every render
5        t = ((nodeId * 1009 + i * 2017) * 137) mod 360
6        out.append(t)
7    return sorted(out)
8 
9# ring tokens = union of tokensForNode(n, k) for every node n

1def loadVariance(nodes, vnodeCount):
2    arcs = []   # (owner, size) per ring slice
3    for token in sorted(all_tokens(nodes, vnodeCount)):
4        arcs.append((owner(token), arc_size(token)))
5    per_node_total = sum_by_owner(arcs)
6    return stddev(per_node_total) / mean(per_node_total)
7 
8# law of large numbers: each node's stake is a sum of
9# vnodeCount random arcs, so variance ~ 1 / sqrt(vnodeCount).
10# 1 -> ~50% ; 4 -> ~20% ; 64 -> ~5%.

1def absorbDeadNode(dead):
2    for vnode in dead.tokens:
3        # each greyed wedge hands its keys to its own
4        # clockwise successor — a different physical node
5        # than the previous wedge, when vnodeCount is high.
6        successor = ring.successor(vnode + 1)
7        successor.adopt(vnode.keys)
8 
9# 1 token   -> 1 successor crushed
10# 64 tokens -> ~64 successors each take 1/64 of the load