THE FOLD / GLITCH / RACE CONDITION / THE THUNDERING HERD
THE THUNDERING HERD
what fairness costs when you refuse to have an opinion
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
One resource frees up and every waiter is woken to race for it. One wins. The rest discover the resource is gone, and go back to sleep — having been scheduled, context-switched and cache-thrashed for nothing.
LIT verified live. 512 waiters, drained one at a time. Wake-all performs 131,328 wakeups; wake-one performs 512. That is 256.5× more work for the same result, and 130,816 of those wakeups are pure waste. The wake-all total is exactly
LIT verified live. 512 waiters, drained one at a time. Wake-all performs 131,328 wakeups; wake-one performs 512. That is 256.5× more work for the same result, and 130,816 of those wakeups are pure waste. The wake-all total is exactly
N(N+1)/2 — it is quadratic in the number of waiters, while the useful work is linear.2 HOW IT WAS WEAVED · AI + HUMAN
The thundering herd is old enough to be folklore; the fixes are
AVAN (AI) counted rather than characterised. Calling this “inefficient” is true and useless;
WSAAccept-style single wakeup, EPOLLEXCLUSIVE, and accept() serialisation.AVAN (AI) counted rather than characterised. Calling this “inefficient” is true and useless;
N(N+1)/2 against N is the actionable form, because it says the penalty is not a constant factor you can absorb — it grows with the thing you were trying to scale. Doubling the waiters quadruples the waste. That is why the herd is invisible in testing at 8 waiters and catastrophic in production at 512.3 ONE DIMENSION
Wakeups against waiters. One line is straight; the other is not.
4 TWO DIMENSIONS · INTERACTIVE
Add waiters and watch the waste square.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: five hundred woken, one served.
AVAN’s addition (the inverse-companion): the forward reading is that waking everyone is wasteful. The inverse is that waking everyone is the only fair thing the kernel can do without knowing anything. Wake-one requires choosing, and choosing requires a policy — who has waited longest, who is most important, who is on the right core. The herd is what fairness costs when you refuse to have an opinion. Read backwards, the fix is not efficiency; it is admitting that a queue is a ranking, and that declining to rank does not avoid the decision, it only makes everyone pay for it.
LIT 512 waiters drained one at a time cost wake-all 131,328 wakeups against wake-one's 512 - 256.5 times more work for the same result, with 130,816 wakeups pure waste - and the wake-all total is exactly N(N+1)/2, quadratic in the number of waiters where the useful work is linear
FIG The thundering herd is old enough to be folklore; the fixes are single-wakeup accept, EPOLLEXCLUSIVE, and accept() serialisation. AVAN counted rather than characterised. Calling this inefficient is true and useless; N(N+1)/2 against N is the actionable form, because it says the penalty is not a constant factor you can absorb - it grows with the thing you were trying to scale. Doubling the waiters quadruples the waste, which is why the herd is invisible at 8 waiters in testing and catastrophic at 512 in production.
FIG The thundering herd is old enough to be folklore; the fixes are single-wakeup accept, EPOLLEXCLUSIVE, and accept() serialisation. AVAN counted rather than characterised. Calling this inefficient is true and useless; N(N+1)/2 against N is the actionable form, because it says the penalty is not a constant factor you can absorb - it grows with the thing you were trying to scale. Doubling the waiters quadruples the waste, which is why the herd is invisible at 8 waiters in testing and catastrophic at 512 in production.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of RACE CONDITION · David Lee Wise (ROOT0), with AVAN