Power of Two Choices (P2C)

Full least-connections has two costs that bite at scale:

1. It scans every backend on every request. O(N) per decision is real money when N is a thousand pods and you make a million decisions a second.
2. It trusts global state that doesn't exist. With several balancer instances in front of one pool, each LB only knows about its own in-flight requests. Worse, if all LBs agree that backend 7 looks idle, they all send their next request to backend 7 simultaneously — the "herd" effect, where chasing the minimum creates the very hotspot you were avoiding.

Power of two choices is the fix, and it is almost embarrassingly simple: pick two backends uniformly at random, send the request to whichever of the two has fewer in-flight connections.

backends: [a:8, b:1, c:5, d:9, e:2]
sample 2 at random -> (c, e)
c=5, e=2 -> choose e

Why two random picks are nearly as good as a full scan

The math (Mitzenmacher's "power of two choices" analysis) says that with purely random placement of n requests onto n backends, the most-loaded backend ends up with about log n / log log n requests. Sampling just two and taking the smaller drops that to about log log n / log 2 — a doubly-logarithmic quantity that is effectively constant. The intuition: to land a request on a backend among the k most-loaded, both random samples must come from that top-k set, which happens with probability (k/N)² instead of k/N. Heavily-loaded backends become quadratically harder to hit.

And the stale-state problem dissolves: because the two candidates are random, different LB instances don't converge on the same "apparent minimum," so no herd forms. That is why P2C is the default in modern proxies: nginx's random two least_conn, HAProxy's balance random(2), and Envoy's LEAST_REQUEST policy (which uses P2C whenever choice_count is the default 2). Service meshes inherit it from there.

The trade: P2C compares 2 numbers instead of N, at the price of being nearly optimal instead of optimal — a trade every production system takes.

Determinism note

Real P2C picks its two candidates with a random number generator, which a grader can't test. In this exercise the two candidates are passed in explicitly (PICK a b), so you implement exactly the comparison-and-commit step that sits inside the real algorithm.

The traps

• Tie-breaking is by name, not by argument order. When both candidates have equal load, the lexicographically smaller name wins. PICK beta alpha with both at 0 must print alpha — if you default to "first argument wins" you'll print beta and fail.
• Count the winner immediately. Increment its active count before returning, or consecutive picks won't alternate: PICK a b twice from zero must print a then b.

Your exercise

Implement pick(a, b) in the starter: compare the two named backends' active counts, choose the smaller (tie → lexicographically smaller name), increment the winner, print it. DONE <backend> decrements (floor 0, prints OK); STATUS prints <name>:<active> per backend sorted by name.

Reference sequence the grader runs: on POOL a b c, PICK a b → a (tie, a < b), PICK a c → c (0 < 1), PICK b c → b (0 < 1), leaving STATUS at exactly a:1, b:1, c:1. And the argument-order test: POOL alpha beta, then PICK beta alpha twice prints alpha then beta.