A naive way to do weighted load balancing is to expand the weights into a repeated list ([A, A, A, A, A, B, C] for weights 5/1/1) and round-robin over that -- but that sends 5 requests to A in a row before B or C ever see traffic, which is a bad burst pattern for A and a long wait for B/C. Real proxies (nginx's smooth weighted round-robin in particular) use an algorithm that interleaves picks smoothly instead.

The algorithm: every backend tracks a running current weight, starting at 0. Each call to next():

1. Add each backend's own weight to its current.
2. Pick whichever backend now has the highest current.
3. Subtract the TOTAL weight (sum of every backend's weight) from just the picked backend's current.
4. Return the picked backend's name.

Implement WeightedLoadBalancer.next().

Example

With weights A=5, B=1, C=1 (total 7), the first 7 picks are exactly: A, A, B, A, C, A, A -- A appears 5 times total, evenly spread out, not clustered at the start.

Constraints

• Over any sum(weights)-sized window of picks, each backend is chosen exactly as many times as its weight (not approximately -- exactly, by construction of the algorithm).

Real-world grounding

• nginx's smooth weighted round-robin (the exact algorithm this exercise implements) is documented in nginx's own commit history and used by many derived proxies; Envoy's weighted round-robin load balancer implements the same idea: source/common/upstream/load_balancer_impl.cc