codejump
MediumPythonJavaScriptTypeScript

System Design — Smooth Weighted Round Robin

System DesignLoad BalancingAlgorithms

A load balancer in front of servers with different capacities. Plain weighted round robin
sends bursts to the heavy server (a a a a a b c); the smooth variant used by nginx
spreads the picks out (a a b a c a a).

solve(args, ops) builds new WeightedBalancer(servers) — args = [servers] where
servers is a list of [name, weight] pairs in priority order — and replays ops:

  • next() — return the name of the next server.

Algorithm: every server has a current value starting at 0. On each call:

1. add each server's weight to its current;
2. pick the server with the largest `current` (on a tie, the one listed first);
3. subtract the total weight of all servers from the picked server's current.

Example — [["a",5],["b",1],["c",1]], seven calls to next():

a, a, b, a, c, a, a

Sample tests

Test #1The nginx example
Input: [[[["a",5],["b",1],["c",1]]],[["next"],["next"],["next"],["next"],["next"],["next"],["next"]]]
Output: ["a","a","b","a","c","a","a"]
Test #2Equal weights alternate
Input: [[[["x",1],["y",1]]],[["next"],["next"],["next"],["next"]]]
Output: ["x","y","x","y"]
Test #3Two to one
Input: [[[["p",2],["q",1]]],[["next"],["next"],["next"],["next"],["next"],["next"]]]
Output: ["p","q","p","p","q","p"]
← All challenges