Least-Connections

Round-robin assumes every request costs the same. Real traffic is nothing like that: a /health ping returns in 2 ms while a /report export holds a connection for 2 seconds. Under round-robin, the backend that keeps drawing the expensive requests falls behind while its neighbors idle — the request count is even but the load is not.

Least-connections uses the balancer's own bookkeeping as a live load signal: dispatch each request to the backend with the fewest currently active connections.

Increment on dispatch, decrement on completion. A backend that is slow — for any reason: GC pause, cold cache, noisy neighbor — automatically accumulates connections and stops receiving new ones until it drains. The feedback loop is the whole point.

Two design notes from production systems:

• The counts are the balancer's local view. The backend doesn't report anything; the LB counts what it has in flight. With several LB instances in front of the same pool, each has a partial picture — a problem the next lesson (power of two choices) turns into a feature.
• Long-lived connections make this essential. For WebSockets or gRPC streams, a connection can live for hours. Round-robin would happily stack thousands of immortal streams onto a backend that was slow at connect time; least-connections self-corrects. HAProxy's docs recommend balance leastconn for exactly these long-session workloads, nginx offers least_conn, and AWS ALB's version is called least outstanding requests — same idea, counting in-flight HTTP requests. (A cousin, NGINX Plus's least_time, picks by observed latency instead of connection count — you'll build that in the EWMA lesson.)

Tie-breaking

At startup every backend has 0 active connections — everything is a tie. Production balancers round-robin among the tied backends; always taking the first one in the list would dump the whole initial burst onto backend 1. Your exercise deliberately uses the simpler rule — the first tied backend in pool order — so the output is deterministic and testable. Know that the "real" answer is round-robin among ties; the quiz will ask.

The traps

• Counting too late. Increment the winner before returning it. If you don't, ten simultaneous decisions all see count 0 and pile onto one backend. (In the grader: PICK PICK PICK on POOL a b c must print a b c, which only happens if each pick records itself.)
• Going negative. A stray DONE for a backend with 0 active must floor at 0, not drift to -1 — a negative count makes that backend win every future pick.

Your exercise

Implement pick() and done() in the starter. Commands: POOL <b1> <b2> ... (all counts 0, prints OK), PICK (select least-loaded, tie → first in pool order, increment, print name), DONE <backend> (decrement with floor 0, prints OK), STATUS (one <name>:<active> line per backend, sorted by name).

The grader's reference sequence: on POOL a b c, four PICKs print a b c a; then DONE a drops a to 1 so all three tie, and the next PICK prints a again (first in pool order) — final STATUS is exactly:

a:2
b:1
c:1

Note the two orderings: tie-breaking uses pool order, but STATUS prints sorted by name. Mixing them up passes the small tests and fails the larger ones.