Smooth Weighted Round Robin (Rust)
Topics: scheduling, load balancing, fairness
Problem
A load balancer spreads requests across backends with different capacities, given as integer
weights. Plain weighted round robin sends a long burst to the heavy backend; smooth weighted
round robin interleaves them — a a b a c a a — so the load is even at every point in time.
pub struct Wrr { /* ... */ }
impl Wrr {
pub fn new(weights: &BTreeMap<String, i64>) -> Self;
pub fn next(&mut self) -> String;
}
new 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; iterate the
BTreeMap in sorted order so ties break consistently.
{a:5, b:1, c:1} → a a b a c a a (then repeats)
{a:1, b:1, c:1} → a b c a b c … (never twice in a row)
The algorithm (the one 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 — pushing it back in line so the others get a turn.
Sign in to submit your solution.