Essay series · 1 essay
Fair Scheduling Across Queues with Deficit-Weighted Round Robin (DWRR)
When several producers share one consumer, something has to decide whose work goes next. Taking turns sounds fair until the turns are different sizes.
Deficit weighted round robin measures turns in work rather than in count, and it does so with almost no bookkeeping. It fits in a paragraph. An implementation that other people can rely on needs more than a paragraph: answers to every question the paragraph leaves open, and a way to show that the code gives those answers.
The first essay, Taking Turns, starts from the need, works through the questions the paragraph leaves open, and checks an implementation against a deliberately simple reference. Ports to other languages, held to one shared specification, are planned.
The Go implementation is dwrr.
-
Part 1
Taking Turns
Why taking turns isn't enough to share a consumer fairly, how deficit round robin measures turns in work, and how a deliberately simple reference shows that an implementation follows the rules.