Weighted Round-Robin

Real pools are rarely uniform. A 16-core machine should take more traffic than a 4-core one, and a canary running the next release should take a trickle next to the production fleet. Weights say how much more. After this lesson your balancer takes a pool whose members carry weights and hands out turns in proportion, without ever sending a long run of consecutive requests to one machine.

Why not just repeat the big one?

The naive implementation expands the pool by weight and round-robins through the expansion:

weights 5 : 1        expansion:  big big big big big small        (period 6)

The ratio is exactly right and the order is terrible. big takes five requests in a row while small sits idle, then small takes one. Bursts are what you bought a balancer to avoid: they create queues on one machine while its neighbours do nothing.

Smooth weighted round-robin

nginx's upstream module spreads the turns out. Every backend carries a running score called current, starting at 0, next to its fixed weight. One pick does three things, in this order:

1. Add each backend's weight to its current.
2. The winner is the backend with the highest current. On a tie, the one listed first in the pool wins.
3. Subtract the total of all weights from the winner's current.

Worked trace for weights a=3, b=1 (total 4):

pick   current after step 1   winner   current after step 3
 1         [ 3,  1]             a         [-1,  1]
 2         [ 2,  2]             a  (tie)  [-2,  2]
 3         [ 1,  3]             b         [ 1, -1]
 4         [ 4,  0]             a         [ 0,  0]

sequence: a a b a      and the scores are back to zero

Three facts let you check any implementation by eye:

• After step 3 the scores always sum to zero, because step 1 added exactly total and step 3 removed exactly total.
• The sequence repeats with period equal to the sum of the weights, and each backend wins exactly weight times per period.
• The turns are spread. With weights 10 : 1 the small backend is served in the middle of the period instead of at its end.

With equal weights the rule degrades to plain round-robin, because every tie goes to the earliest backend and the winner's penalty then puts it last in line.

Reading a pool line

Pool entries look like nginx's weight= option: 10.0.0.11:8080=5 is the address 10.0.0.11:8080 with weight 5. The address already contains a colon, so split at the last =. An entry with no = has the default weight 1. Weight 0 means "configured but receives nothing"; it is never picked, and a pool whose weights are all 0 has nobody to pick.

Common mistakes

• Subtracting only the winner's own weight. The scores stop summing to zero, the ratio drifts, and the sequence turns bursty again.
• Adding weight only to the winner, or only to the others. Step 1 credits every backend on every pick.
• Resetting the scores between picks. They are long-lived state. Only POOL clears them, and a second PICKN must carry on from where the first stopped.
• Letting a zero-weight backend win a tie. Its score never rises above 0, while the total is positive, so it can only win if your comparison is wrong.

Your exercise

The starter parses the commands and prints the results. You implement the pick. POOL <entry> ... sets the backends (prints OK), PICK prints one backend, PICKN <n> prints n picks on one line separated by commas with no spaces, and both print EMPTY when nothing can be picked.