Weighted Round-Robin

Real pools are rarely uniform. A 16-core box should take more traffic than a 4-core one; a canary instance should take a trickle next to the production fleet. Weights express that:

backends: [(s1, weight=4), (s2, weight=2), (s3, weight=1)]
distribution: 4/7 to s1, 2/7 to s2, 1/7 to s3

The naive implementation expands the list — [s1, s1, s1, s1, s2, s2, s3] — and round-robins through it. The ratio is right, but the order is bursty: s1 receives four consecutive requests, then goes idle while s2 and s3 catch up. Bursts are exactly what you buy a balancer to avoid: they create queueing spikes on one machine while others sit idle.

Smooth weighted round-robin

nginx's upstream module solves this with smooth WRR. Every backend carries a running current counter, initially 0. Each pick does three steps:

1. Add each backend's configured weight to its current.
2. Pick the backend with the highest current.
3. Subtract the total of all weights from the winner's current.

For weights [s1=4, s2=2, s3=1] (total = 7):

step 1: current=[4,2,1]  -> pick s1, current=[-3,2,1]
step 2: current=[1,4,2]  -> pick s2, current=[1,-3,2]
step 3: current=[5,-1,3] -> pick s1, current=[-2,-1,3]
step 4: current=[2,1,4]  -> pick s3, current=[2,1,-3]
step 5: current=[6,3,-2] -> pick s1, current=[-1,3,-2]
step 6: current=[3,5,-1] -> pick s2, current=[3,-2,-1]
step 7: current=[7,0,0]  -> pick s1, current=[0,0,0]

sequence: s1 s2 s1 s3 s1 s2 s1

Three invariants are worth internalizing, because they let you sanity-check any implementation:

• The current values always sum to zero (step 1 adds total, step 3 removes total).
• The sequence repeats with period = total weight, and each backend appears exactly weight times per period.
• Picks are spread out, not clumped: with weights 10:1, smooth WRR emits big five times, then small, then big five more — the naive expansion would emit ten big in a row first.

Ties: when two backends share the highest current, the winner is the one that appears earliest in the pool order. This falls out naturally if you scan the list with a strict > comparison (or use Python's max, which keeps the first maximum). With equal weights a:1 b:1 c:1, smooth WRR degrades to plain round-robin: a, b, c, a, b, c.

The traps

• Subtracting the winner's own weight instead of the total. The ratio drifts and the currents no longer sum to zero — the sequence goes bursty again.
• Adding weight only to the winner (or only to non-winners). Step 1 credits every backend, every pick.
• Resetting current between picks. The counters are long-lived state; only POOL resets them.

Your exercise

Implement SmoothWeightedRR.pick() for the starter's command loop: POOL <name>:<weight> ... (prints OK), PICK (prints one backend), and PICKN <n> (prints n picks on one line, comma-separated, no spaces).

What the grader checks:

• POOL s1:4 s2:2 s3:1 then PICKN 7 must print exactly s1,s2,s1,s3,s1,s2,s1 — the smooth interleaving above, not a burst.
• POOL a:1 b:1 c:1 then PICKN 6 must print a,b,c,a,b,c — ties go to the earliest pool entry.
• POOL a:5 b:1 c:1 then PICKN 7 must print a,a,b,a,c,a,a — note b lands at pick 3 and c at pick 5, spread through the period.
• State persists across commands: after PICKN 7 on the 4:2:1 pool, a following PICKN 14 starts a fresh period (s1,s2,...) only because 7 picks returned the currents to zero — not because you reset anything.