Round-Robin Load Balancing

A load balancer is the front door to a fleet: one address outside, N interchangeable backends inside. Every arriving request forces the same small decision: which backend gets this one? In this lesson your balancer starts answering that question with the oldest rule there is, handing out backends in a fixed cycle, and you will feed it a pool the way a config reload would.

The mechanism

Round-robin keeps one integer, the counter. A pick takes the backend at position counter mod N, then adds one to the counter.

pool:    [10.0.0.11:8080, 10.0.0.12:8080, 10.0.0.13:8080]      N = 3

counter  counter mod 3  answer
   0          0         10.0.0.11:8080
   1          1         10.0.0.12:8080
   2          2         10.0.0.13:8080
   3          0         10.0.0.11:8080      <- wrapped
   4          1         10.0.0.12:8080

The order matters twice. The backend is read before the counter moves, so the very first pick is position 0, not position 1. And the counter keeps growing instead of wrapping to zero by hand: the modulo does the wrapping, which means the pool can change size between picks without any extra bookkeeping.

That is the whole algorithm: O(1) time, one integer of state, and no feedback from the backends at all. It is the default for a reason. nginx's upstream block, HAProxy's balance roundrobin and AWS ALB all rotate this way unless told otherwise, and when requests cost about the same an even count is an even load.

Where it breaks

Round-robin is blind by design, and each blindness becomes a later lesson:

• It ignores cost. A two-second report export and a two-millisecond ping each count as one turn. Least-connections fixes this.
• It ignores health. A dead backend stays in the cycle and swallows every Nth request until health checks remove it.
• It ignores identity. One client visits a different backend on every request, so any state held in a backend's memory is lost. Sticky sessions fix this.

The traps

The empty pool. counter mod 0 is a division by zero. A real balancer has to decide what "a request with no backends" means (normally a 503). Here it prints EMPTY.

A pool change mid-cycle. If the pool shrinks from five backends to three while the counter stands at 4, the new pool is read at position 4 mod 3, which is not the start of anything. Real balancers rebuild their scheduler on a config reload. In this exercise a new POOL throws the old counter away, so the first pick after a reload is always the first backend listed.

Duplicates are weight. POOL a a b is not an error: a appears twice in the cycle, so it receives two turns out of three. Do not de-duplicate.

Concurrency. Two threads that both read the counter before either increments it pick the same backend. Production balancers use an atomic fetch-and-add on the counter, which makes read-and-advance one indivisible step. The grader here is single-threaded, so a plain integer is enough, but know why the real ones look different.

Your exercise

The starter already reads commands from standard input, one per line, and prints one line of output per command. You implement the selection. POOL <b1> <b2> ... replaces the backend list and resets the counter (prints OK). PICK prints the next backend, or EMPTY when the pool has none. RESET sets the counter back to zero without touching the pool (prints OK). Backends are opaque strings, usually host:port; split on whitespace and nothing else.

Mistakes the tests are built to catch:

• Advancing before reading. The first PICK after POOL s1 s2 s3 must print s1, not s2.
• Carrying the counter across a reload. After POOL alpha beta and three picks, a new POOL gamma delta epsilon must make the next PICK print gamma.
• Crashing on an empty pool. PICK before any POOL, and after a POOL with no names, both print EMPTY and the program carries on.