"""Stdlib-only tests (no pytest): plain asserts in functions called from a __main__ block. Run: `python3 test_load_balancer.py`. The headline tests pin the demo's two worlds and the arithmetic the commentary derives from them (commentary.html §6). The rest are the swept counterfactuals from §6.5 and §7, so a knob the page calls inert fails loudly if it stops being inert. """ from load_balancer import (Backend, LeastConn, PeakEwma, PeakEwmaOverSuccess, RoundRobin, pct, simulate) TICKS, LAM, SEED = 20000, 0.32, 1 SLOW, FAST, N = 10, 1, 4 def fleet(healthy4, slow=SLOW, fast=FAST, slots=1, cv=0.0, n=N): f = [Backend("ok%d" % i, slow, True, slots, cv) for i in range(n - 1)] f.append(Backend("fast3", fast, healthy4, slots, cv)) return f def run(policy, healthy4=False, **kw): return simulate(policy, fleet(healthy4, **kw), TICKS, LAM, SEED) # --- the defining property of a broken backend ------------------------- def test_failing_takes_exactly_as_long_as_succeeding(): """`dispatch` branches on `healthy` for the verdict and never for the duration. This is the equivalence the whole toy rests on.""" good, bad = Backend("g", 7, True), Backend("b", 7, False) assert good.dispatch(0, None) == (7, True) assert bad.dispatch(0, None) == (7, False) def test_the_balancer_never_reads_the_outcome(): """peak-ewma's score and observe use latency and in-flight only. Feeding the identical latency with opposite verdicts must leave the same state.""" a, b = Backend("a", 10), Backend("b", 10) p = PeakEwma() p.observe(a, 3, True) p.observe(b, 3, False) assert a.ewma == b.ewma assert p.score(a) == p.score(b) # --- the headline ------------------------------------------------------ def test_broken_backend_is_invisible_to_the_balancer(): """THE load-bearing test (§6.1). Same fleet, same trace, one boolean. Every routing decision, every belief and every latency sample is identical between a world where fast3 is genuinely 10x faster and a world where it fails in 1 tick. Only the goodput differs. """ a, b = fleet(True), fleet(False) ra = simulate(PeakEwma(), a, TICKS, LAM, SEED) rb = simulate(PeakEwma(), b, TICKS, LAM, SEED) assert ra["sent"] == [4, 1, 0, 6402], ra["sent"] assert rb["sent"] == [4, 1, 0, 6402], rb["sent"] assert [x.ewma for x in a] == [x.ewma for x in b] assert [x.ewma for x in a] == [10.0, 10.0, 10.0, 1.3036593805578662] assert ra["all"] == rb["all"] assert ra["good"] == 6407 and rb["good"] == 5 def test_all_four_policies_route_identically_in_both_worlds(): """Not just peak-ewma: no policy in the toy can tell the worlds apart.""" for p in (RoundRobin, LeastConn, PeakEwma): assert run(p(), True)["sent"] == run(p(), False)["sent"], p def test_headline_arithmetic(): """4806 -> 5 is 961.2x; 41 -> 3 ticks is 13.67x the other way.""" rr, pe = run(RoundRobin()), run(PeakEwma()) assert rr["good"] == 4806 and pe["good"] == 5 assert round(rr["good"] / pe["good"], 1) == 961.2 assert pct(rr["all"], .99) == 41 and pct(pe["all"], .99) == 3 assert round(pct(rr["all"], .99) / pct(pe["all"], .99), 2) == 13.67 def test_goodput_is_the_literal_sum_of_the_healthy_backends(): """5 is not a statistic: it is 4 + 1 + 0. One healthy backend of three received nothing at all in 20000 ticks.""" r = run(PeakEwma()) assert sum(r["sent"][:3]) == r["good"] == 5 assert r["sent"][2] == 0 def test_round_robin_share_is_one_in_n(): """4806 = 6407 x 3/4, rounded to whole requests.""" r = run(RoundRobin()) assert abs(r["broken_share"] - 0.25) < 0.001 assert r["good"] == 4806 assert abs(r["good"] - r["total"] * 3 / 4) < 1.0 # --- §6.2: every latency metric ranks the policies backwards ----------- def test_p99_ranking_is_the_reverse_of_the_goodput_ranking(): """The best policy by p99 is the worst by goodput, and vice versa.""" res = [run(p) for p in (RoundRobin(), LeastConn(), PeakEwma(d=2), PeakEwma())] by_p99 = [r["policy"] for r in sorted(res, key=lambda r: pct(r["all"], .99))] by_good = [r["policy"] for r in sorted(res, key=lambda r: -r["good"])] assert by_p99[0] == by_good[-1] == "peak-ewma" assert by_p99[-1] == by_good[0] == "round-robin" def test_throwing_the_errors_away_does_not_help(): """p99 over successful responses only still ranks peak-ewma first.""" res = [run(p) for p in (RoundRobin(), LeastConn(), PeakEwma(d=2), PeakEwma())] order = [r["policy"] for r in sorted(res, key=lambda r: pct(r["ok"], .99))] assert order[0] == "peak-ewma" assert [pct(r["ok"], .99) for r in res] == [43, 19, 23, 10] # --- §6.3: share == d/N ------------------------------------------------ def test_power_of_d_choices_is_the_blast_radius(): """Every extra choice is another chance for the beacon to be visible.""" got = {} for d in (1, 2, 3, 4): r = run(PeakEwma(d=d)) got[d] = round(100 * r["broken_share"], 2) assert got == {1: 26.02, 2: 50.40, 3: 75.98, 4: 99.97}, got for d, share in got.items(): assert abs(share - 100 * d / N) < 1.1, (d, share) def test_broken_backend_wins_every_sample_it_appears_in(): """The mechanism behind d/N, as a count rather than a probability.""" class Counted(PeakEwma): def __init__(self, d): PeakEwma.__init__(self, d) self.sampled = self.won = 0 def pick(self, f, now, rng): w = PeakEwma.pick(self, f, now, rng) if any(not x.healthy for x in self.last): self.sampled += 1 self.won += not w.healthy return w p = Counted(3) simulate(p, fleet(False), TICKS, LAM, SEED) assert p.won == p.sampled == 4871, (p.won, p.sampled) # --- §6.5: the boundary ------------------------------------------------ def test_boundary_error_latency_equal_to_service_latency(): """At err == service the failure is invisible to the signal, so the share lands on 1/N and peak-ewma IS round-robin.""" for s in (10, 20, 40): r = run(PeakEwma(), slow=s, fast=s) assert abs(r["broken_share"] - 1 / N) < 0.005, (s, r["broken_share"]) assert run(PeakEwma(), slow=10, fast=10)["good"] == 4785 assert run(RoundRobin(), slow=10, fast=10)["good"] == 4806 def test_the_sign_flips_past_the_boundary(): """A failure slower than a success makes peak-ewma the best policy here: 6026 against round-robin's 4806, a 25.4% win.""" pe, rr = run(PeakEwma(), fast=50), run(RoundRobin(), fast=50) assert pe["good"] == 6026 and rr["good"] == 4806 assert pe["good"] > rr["good"] assert round(100 * (pe["good"] / rr["good"] - 1), 1) == 25.4 assert round(100 * run(PeakEwma(), fast=50)["broken_share"], 2) == 5.95 # --- §7: the fix, and the knobs that do nothing ------------------------ def test_the_success_rate_term_beats_round_robin(): """One term in one expression: 4806 -> 5 -> 5871.""" assert run(RoundRobin())["good"] == 4806 assert run(PeakEwma())["good"] == 5 fixed = run(PeakEwmaOverSuccess()) assert fixed["good"] == 5871 assert fixed["good"] > run(RoundRobin())["good"] assert round(100 * fixed["broken_share"], 2) == 8.37 def test_a_bigger_fleet_does_not_dilute_a_black_hole(): """Round-robin's blast radius is 1/N and shrinks; peak-ewma's does not.""" rr = [run(RoundRobin(), n=n)["good"] for n in (2, 4, 20, 50)] assert rr == sorted(rr) and rr[0] == 3204 and rr[-1] == 6279, rr for n in (3, 4, 8, 20, 50): assert run(PeakEwma(), n=n)["good"] == 5, n def test_concurrency_makes_it_strictly_worse(): """Real backends serve many at once, and then the in-flight term in the score never bites at all: goodput is exactly zero.""" for slots in (2, 4, 20): r = run(PeakEwma(), slots=slots) assert r["good"] == 0 and r["broken_share"] == 1.0, slots assert run(PeakEwma(), slots=1)["good"] == 5 def test_service_time_variance_does_not_save_it(): """An inert knob: jitter on every backend leaves the share above 94%.""" assert round(100 * run(PeakEwma(), cv=2.0)["broken_share"], 2) == 94.44 assert run(PeakEwma(), cv=2.0)["good"] == 361 def test_the_ewma_is_not_handed_the_answer(): """Seeding every belief pessimistically at 1000 changes nothing: the policy learns the 1-tick latency and black-holes anyway.""" f = fleet(False) for b in f: b.ewma = 1000.0 r = simulate(PeakEwma(), f, TICKS, LAM, SEED) assert r["broken_share"] > 0.99, r["broken_share"] assert r["good"] == 5 def test_output_is_deterministic(): """No clock, no unseeded RNG: two runs are identical, and a different seed moves the numbers without moving the result.""" assert run(PeakEwma())["all"] == run(PeakEwma())["all"] for seed in (2, 7, 42, 12345): r = simulate(PeakEwma(), fleet(False), TICKS, LAM, seed) assert r["good"] / r["total"] < 0.002, (seed, r["good"]) TESTS = [ test_failing_takes_exactly_as_long_as_succeeding, test_the_balancer_never_reads_the_outcome, test_broken_backend_is_invisible_to_the_balancer, test_all_four_policies_route_identically_in_both_worlds, test_headline_arithmetic, test_goodput_is_the_literal_sum_of_the_healthy_backends, test_round_robin_share_is_one_in_n, test_p99_ranking_is_the_reverse_of_the_goodput_ranking, test_throwing_the_errors_away_does_not_help, test_power_of_d_choices_is_the_blast_radius, test_broken_backend_wins_every_sample_it_appears_in, test_boundary_error_latency_equal_to_service_latency, test_the_sign_flips_past_the_boundary, test_the_success_rate_term_beats_round_robin, test_a_bigger_fleet_does_not_dilute_a_black_hole, test_concurrency_makes_it_strictly_worse, test_service_time_variance_does_not_save_it, test_the_ewma_is_not_handed_the_answer, test_output_is_deterministic, ] 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")