Smooth Weighted Round Robin (Go)
Topics: scheduling, load balancing, fairness
Problem
A load balancer spreads requests across backends with different capacities, expressed as integer
weights. Plain weighted round robin (a a a a a b c) sends a long burst to the heavy backend
before touching the others. Smooth weighted round robin interleaves them — a a b a c a a —
so the load is even at every point in time, not just on average.
type WRR struct { /* ... */ }
func NewWRR(weights map[string]int) *WRR
func (w *WRR) Next() string
NewWRR takes name -> weight (every weight ≥ 1, map non-empty).- Over any window of
sum(weights) calls, each name is returned exactly weight times.
- The sequence is smooth: the heaviest name is spread out, not returned in one run.
- Selection is deterministic — given the same weights,
Next always yields the same sequence.
{a:5, b:1, c:1} → a a b a c a a (then repeats)
{x:1, y:1, z:1} → x y z x y z … (never twice in a row)
The trick (the algorithm Nginx uses): give each entry a running current weight. On every call, add
each entry's static weight to its current weight, pick the entry with the highest current weight,
then subtract the total weight from the winner. That subtraction is what pushes the heavy entry
back in line so the others get their turn.
Sign in to submit your solution.