"""Stdlib-only tests (no pytest): plain asserts in functions called from a __main__ block. Run: `python3 test_hash_ring.py`. Every number asserted here also appears in commentary.html. If the commentary rots, these fail. The suite takes a few seconds because several tests build 100 rings and route 10,000 keys through each — that enumeration is the point of the toy, so it is worth the wall time. """ from collections import Counter from hash_ring import HASH_SPACE, Ring, balance, moved, ring_hash KEYS = [f"key{i}" for i in range(10000)] CANDIDATES = [f"newnode{i}" for i in range(100)] NODES8 = [f"node{i}" for i in range(8)] def test_hashing_is_deterministic_with_no_rng(): """No seeds, no RNG: these two integers are fixed forever, on any box.""" assert ring_hash("key0") == 2914119475 assert ring_hash("node0#0") == 3562214217 assert 0 <= ring_hash("anything") < HASH_SPACE def test_route_wraps_past_the_last_point(): """Keys hashing above the highest ring point belong to the *first* node — that is what makes the ring a ring. 147 of the 10,000 demo keys do.""" ring = Ring(NODES8, vnodes=1) points = ring.points() top, first_owner = points[-1][0], points[0][1] past_the_top = [k for k in KEYS if ring_hash(k) > top] assert len(past_the_top) == 147 assert {ring.route(k) for k in past_the_top} == {first_owner} def test_one_point_per_node_is_wildly_unbalanced(): """The headline: a perfectly good hash function, 8 nodes, and the busiest holds 74x the lightest.""" counts = Ring(NODES8, vnodes=1).distribution(KEYS) assert counts["node6"] == 4003 assert counts["node5"] == 54 lo, hi, over_fair, spread = balance(counts) assert (lo, hi) == (54, 4003) assert round(over_fair, 2) == 3.20 assert round(spread, 2) == 74.13 def test_load_is_arc_length_not_key_luck(): """Key counts merely sample the arcs. node6 owns 39.75% of the ring's 2**32 slots and holds 40.03% of the keys — and 10x more keys does not move max/fair, because it is converging on 8 x 0.3975 = 3.18.""" ring = Ring(NODES8, vnodes=1) arcs = ring.arcs() assert abs(sum(arcs.values()) - 1.0) < 1e-12 assert round(arcs["node6"] * 100, 2) == 39.75 counts = ring.distribution(KEYS) assert round(counts["node6"] / len(KEYS) * 100, 2) == 40.03 ceiling = 8 * max(arcs.values()) assert round(ceiling, 2) == 3.18 ten_x = [f"key{i}" for i in range(100000)] assert round(balance(ring.distribution(ten_x))[2], 2) == 3.19 def test_vnodes_collapse_the_spread(): """150 points per node turns 74x into 1.23x. This is what vnodes buy.""" lo, hi, over_fair, spread = balance(Ring(NODES8, vnodes=150).distribution(KEYS)) assert (lo, hi) == (1146, 1409) assert round(over_fair, 2) == 1.13 assert round(spread, 2) == 1.23 def test_vnodes_change_who_the_keys_come_from_not_how_many(): """Adding a 9th node: 19.76% of keys move with one point per node and 11.08% with 150 — the same order of magnitude. The donor count is what actually changes, from 1 node to all 8.""" before = Ring(NODES8, vnodes=1).route_all(KEYS) grown = Ring(NODES8, vnodes=1) grown.add("newnode0") m = moved(before, grown.route_all(KEYS)) assert len(m) == 1976 assert Counter(old for old, _ in m.values()) == Counter({"node0": 1976}) before = Ring(NODES8, vnodes=150).route_all(KEYS) grown = Ring(NODES8, vnodes=150) grown.add("newnode0") m = moved(before, grown.route_all(KEYS)) assert len(m) == 1108 assert len(Counter(old for old, _ in m.values())) == 8 def test_the_per_instance_spread_is_the_real_result(): """1/N holds on average and is useless per instance. Over 100 candidate joins at one point per node, one moves nothing at all and another moves 3617 keys; at 150 points the whole range is 876..1236.""" ring = Ring(NODES8, vnodes=1) before = ring.route_all(KEYS) counts = [] for candidate in CANDIDATES: trial = Ring(NODES8, vnodes=1) trial.add(candidate) counts.append(len(moved(before, trial.route_all(KEYS)))) assert (min(counts), max(counts)) == (0, 3617) ring = Ring(NODES8, vnodes=150) before = ring.route_all(KEYS) counts = [] for candidate in CANDIDATES: trial = Ring(NODES8, vnodes=150) trial.add(candidate) counts.append(len(moved(before, trial.route_all(KEYS)))) assert (min(counts), max(counts)) == (876, 1236) def test_adding_a_node_usually_does_not_relieve_the_busiest_one(): """The shock. At one point per node the busiest node's load is completely untouched by 64 of 100 possible joins; at 150 points, by none of them.""" for vnodes, expected in ((1, 64), (150, 0)): base = Ring(NODES8, vnodes=vnodes).distribution(KEYS) busiest = max(base, key=lambda node: base[node]) unchanged = 0 for candidate in CANDIDATES: trial = Ring(NODES8, vnodes=vnodes) trial.add(candidate) if trial.distribution(KEYS)[busiest] == base[busiest]: unchanged += 1 assert unchanged == expected, (vnodes, unchanged) def test_a_join_never_increases_any_existing_nodes_load(): """A new node only ever takes arcs away. No existing node can gain a key from a join, which is why a badly placed join is a no-op, not a hazard.""" base = Ring(NODES8, vnodes=1).distribution(KEYS) for candidate in CANDIDATES: trial = Ring(NODES8, vnodes=1) trial.add(candidate) after = trial.distribution(KEYS) assert all(after[node] <= base[node] for node in NODES8), candidate def test_remove_is_the_exact_inverse_of_add(): """Removing node3 moves exactly the keys node3 held; putting it back restores the routing bit for bit. Positions come from the label, so the ring has no memory of the order operations happened in.""" ring = Ring(NODES8, vnodes=150) before = ring.route_all(KEYS) ring.remove("node3") assert len(moved(before, ring.route_all(KEYS))) == 1146 ring.add("node3") assert moved(before, ring.route_all(KEYS)) == {} def test_ring_rejects_nonsense(): ring = Ring(NODES8, vnodes=1) for bad in (lambda: ring.add("node3"), lambda: ring.remove("nope"), lambda: Ring(NODES8, vnodes=0), lambda: Ring().route("k")): try: bad() except ValueError: pass else: raise AssertionError("expected ValueError") TESTS = [ test_hashing_is_deterministic_with_no_rng, test_route_wraps_past_the_last_point, test_one_point_per_node_is_wildly_unbalanced, test_load_is_arc_length_not_key_luck, test_vnodes_collapse_the_spread, test_vnodes_change_who_the_keys_come_from_not_how_many, test_the_per_instance_spread_is_the_real_result, test_adding_a_node_usually_does_not_relieve_the_busiest_one, test_a_join_never_increases_any_existing_nodes_load, test_remove_is_the_exact_inverse_of_add, test_ring_rejects_nonsense, ] if __name__ == "__main__": failed = 0 for test in TESTS: try: test() except AssertionError as exc: failed += 1 print(f"FAIL {test.__name__}: {exc}") else: print(f"PASS {test.__name__}") if failed: print(f"\n{failed} of {len(TESTS)} tests FAILED") raise SystemExit(1) print(f"\nAll {len(TESTS)} tests PASSED")