Part 1 of 1 · Fair Scheduling Across Queues with Deficit-Weighted Round Robin (DWRR)
Fair Scheduling Across Queues: Taking Turns
What fair means when several queues share one consumer, and how to check that an implementation agrees.
An MPEG transport stream is a sequence of 188-byte packets.1 Video, several audio tracks, captions, and the tables that describe them all travel in that one sequence, interleaved, each packet marked with the stream it belongs to. Taking a transport stream apart is mostly bookkeeping: read each packet and put it in the queue for its stream.
Putting streams back together is where it gets interesting. I wanted to build new channels from the streams of incoming ones, so the muxer for each output channel has several queues of packets waiting and one place to write them. Every time it writes a packet, it has to answer the same question: whose turn is it?
Whose turn is it?
The question isn’t specific to video. It shows up whenever several producers share one consumer: tenants sharing a job runner, users sharing a rate-limited API, requests sharing a model server. The answers that come to mind first each fail in their own way.
First in, first out serves work in the order it arrived. When one producer sends a burst, everything else waits behind it.
Strict priority serves the most important queue whenever it has work. A busy high-priority queue can keep the others waiting indefinitely.
Round robin takes turns: one item from each queue that has something waiting, then around again. That feels fair, and when every item costs the same, it is. But suppose two tenants share a network link. One sends 1,500-byte messages and the other sends 64-byte messages. Round robin alternates between them, so each round sends 1,564 bytes, and 1,500 of those belong to the first tenant. It gets about 96% of the bytes sent while the scheduler reports perfectly equal turns.
Taking turns is fair only when the turns are the same size.
Transport stream packets are all the same size, which is why the first version of my scheduler counted packets and nothing else. Counting was exactly right for that problem. It stops being right as soon as items differ, and most uses of a scheduler have items that differ.
Turns measured in work
Deficit round robin keeps the turns and changes what a turn means.2 Each queue has a running credit, called its deficit. When a queue’s turn begins, it receives a fixed allowance of credit, its quantum. It then serves items from the front of its queue for as long as its credit covers the next item’s cost, subtracting each cost as it goes. When it can’t afford the next item, its turn ends, and the unspent credit stays with it for the next round.
Run the two tenants through it with a quantum of 1,500 bytes each. The first tenant’s turn sends one 1,500-byte message and spends all its credit. The second tenant’s turn sends 23 messages of 64 bytes, 1,472 bytes in all, and carries the remaining 28 into its next turn. As long as both have work waiting, each tenant sends an average of 1,500 bytes per round. Give one of them a quantum of 3,000, and while both stay busy, it gets twice the bandwidth of the other.
Costs don’t have to be bytes. They can be tokens, estimated seconds of work, or simply 1 per item, which is the packet-counting scheduler again. The scheduler never needs to know what the costs mean. It only needs them to be measured in the same unit as the quanta.
What the paragraph leaves out
That description fits in a paragraph. An implementation that someone else can depend on needs more than a paragraph, because the paragraph leaves questions open:
- If a consumer asks for one item, and the queue whose turn it is could afford three, does the next request continue that turn or start a new one?
- If a queue’s weight changes in the middle of its turn, does the change apply now or at its next turn? What happens to the credit it already has?
- What happens when no queue can afford its next item this round?
- Does an empty queue keep the credit it saved?
Each question has a reasonable answer, and several have more than one. Two implementations can answer them differently, both correctly describe themselves as deficit round robin, and still disagree about which item goes next.
The answers are the specification. Some of them also turn out to matter more than they look.
One of my early answers was wrong. When a queue’s quantum changed, the scheduler reset its credit to zero. That seemed tidy: a new weight, a clean start. But consider a queue whose next item costs more than one quantum, so it has to save credit across several turns before it can afford it. If its weight is adjusted every round, as a system that tunes weights adaptively might do, its savings are erased every round. It never reaches the item. A test that changed such a queue’s weight before each of 1,000 retrievals found that its item was never served. The fix was to keep the credit and apply the new quantum at the queue’s next turn.
How do we know?
A scheduler worth using has optimizations that make it harder to read than the paragraph. The Go implementation skips empty queues using a bitmap. When a whole round can’t afford anything, it calculates how many rounds to skip rather than spinning through them. It keeps exact credit in 64-bit integers and relies on an argument about how large that credit can grow. Each optimization is a place where the code could quietly stop meaning what the paragraph says.
Reading the code carefully helps, but I don’t want correctness to depend on how carefully someone read it. So the test suite includes a second scheduler written to be obviously right rather than fast. It visits every queue in order, one at a time, never skips anything, and is short enough to check by reading. The tests give both schedulers the same long, random sequences of operations, including weight changes and removals in the middle of a turn, and require them to agree at every step. A fuzzer generates millions more sequences.
This only matters if the tests can fail. If the check that decides whether a queue can afford its next item is changed from < to <=, the comparison fails in under a second and prints the sequence of operations that exposes the difference.
The reference model has a limit, and the weight-change bug shows it. At the time, the reference followed the same reset-on-change rule as the implementation. The two agreed perfectly. The reference model could show that the code did what we said; it took a different question, whether a queue could go unserved, to show that we’d said the wrong thing.
The same answers in other languages
I want this scheduler in more than one language. Each port will reimplement the same optimizations, and each will face the same open questions. Its answers will be right only if they’re the same answers.
That suggests a different arrangement from writing tests separately for each language. The specification gets written down once. One reference model serves every implementation. One harness drives any implementation through a small program in that language that reads operations and writes results, and compares those results with the reference at every step. Every failure the harness finds is shrunk to a short sequence that still fails and saved, so a bug found through one implementation becomes a test case for all of them.
The Go implementation exists and is checked against its own reference today. A shared specification, reference, and harness come next, with the ports. They’ll have to deal with problems that only appear across languages. Credit that fits exactly in a Go uint64 doesn’t fit in a JavaScript number. And each language has its own idea of who should wait for work and how.
Fairness still means taking turns. Saying what a turn is takes more work than it first appears, and a slow, obvious reference keeps the fast version faithful to what we wrote down. Whether what we wrote down is fair is a different question, and we have to ask it on purpose.