Power of Two Choices

Full least-connections has two costs that bite at scale. It scans every backend on every request, which is real money when the pool has a thousand pods and the balancer makes a million decisions a second. And it trusts state that does not exist: with several balancers in front of one pool, each only knows its own in-flight requests, so when all of them agree that backend 7 looks idle they all send their next request to backend 7 at once. Chasing the minimum creates the hotspot it was meant to avoid. This is the herd effect.

The mechanism

Power of two choices (P2C) is almost embarrassingly simple. Pick two backends at random, compare their in-flight counts, and send the request to the one with fewer.

pool (in flight):  a=8  b=1  c=5  d=9  e=2
sample two at random  ->  c and e
c=5, e=2              ->  choose e

Why does so little work help so much? Throw n requests at n backends completely at random and the unluckiest backend ends up with about log n / log log n requests. Let each request look at just two random backends and take the emptier, and the worst case collapses to about log log n, which for any real pool is effectively a constant. To land on one of the busiest backends, both random samples have to come from that crowd, so the busy ones become quadratically harder to hit.

The herd dissolves too. Different balancers draw different random pairs, so they do not converge on one apparent minimum. P2C is why nginx offers random two least_conn, HAProxy offers balance random(2), and Envoy's least-request policy samples two hosts by default.

The price: P2C compares two numbers instead of N, and in exchange it is nearly optimal instead of optimal. Every production system takes that trade.

A random generator you can reproduce

A grader cannot test real randomness, so this exercise fixes the generator. It is a linear congruential generator over 31 bits:

state = (state * 1103515245 + 12345) mod 2^31       the seed is the first state
draw  = state >> 16                                  the top 15 bits

To sample two different backends from a pool of n, make two draws:

i = draw1 mod n
j = draw2 mod (n - 1)
if j >= i: j = j + 1          # skips over i, so j can never equal i

For seed 1 and a pool of 4 the first two draws are 16838 and 5758, which give i = 2 and j = 1, so the candidates are the third and the second backend in pool order. Both indexes count from 0 and refer to the pool order given in POOL.

Choosing between the two

The candidate with fewer in-flight requests wins. On a tie the lexicographically smaller name wins, whichever candidate was drawn first, so the answer does not depend on the order of the draws. The winner's count goes up by one immediately, or two consecutive picks would not alternate.

Common mistakes

• Tie-break by argument order. With PICK beta alpha and both at 0, the answer is alpha.
• Drawing the same backend twice. Without the j >= i step, one draw in n picks a candidate against itself and the comparison means nothing.
• Forgetting the small pools. One backend has nothing to compare, so it is simply chosen. An empty pool answers EMPTY.
• Wasting draws. A pool with one backend takes no draws, so a later PICK on a bigger pool must see the generator exactly where the seed left it.

Your exercise

The starter holds the pool, the counts and the generator. PICK <a> <b> compares two named backends (a name not in the pool answers ERR). PICK with no arguments draws its own two candidates with the generator above. You write the comparison-and-commit step that both forms share, and the sampling for the second form.