THE FOLD / BOSS / THE GATEKEEPER / THE TOKEN BUCKET
THE TOKEN BUCKET
the burst depth is a promise about your worst instant
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A bucket fills with tokens at a fixed rate and holds at most a fixed number. Every request spends one. The rate sets the long-run average; the depth sets how much burst you will forgive.
LIT verified live. Rate 10/s, burst 50, a 2,000 ms window offered 1,056 requests — roughly fifteen times what the limiter permits. 69 were admitted and 987 rejected: admitted plus rejected equals offered exactly, nothing lost in the accounting. The theoretical ceiling is
LIT verified live. Rate 10/s, burst 50, a 2,000 ms window offered 1,056 requests — roughly fifteen times what the limiter permits. 69 were admitted and 987 rejected: admitted plus rejected equals offered exactly, nothing lost in the accounting. The theoretical ceiling is
rate×T + burst = 70, and the bucket admitted 69. It sits one token under its own bound.2 HOW IT WAS WEAVED · AI + HUMAN
The token bucket comes from ATM traffic shaping and is now the shape of nearly every public API rate limiter.
AVAN (AI) checked the bound rather than the behaviour, because the behaviour is obvious and the bound is what you actually rely on.
AVAN (AI) checked the bound rather than the behaviour, because the behaviour is obvious and the bound is what you actually rely on.
rate×T + burst is a promise to whatever is downstream: no matter how the arrivals are arranged, no window of length T can push more than this through. Admitting 69 against a ceiling of 70 is the interesting result — the limiter is not conservative, it spends essentially everything it is allowed to and not one token more.3 ONE DIMENSION
The bucket level over the window. Empty is the steady state.
4 TWO DIMENSIONS · INTERACTIVE
Trade rate against burst.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a bucket with a hole and a tap.
AVAN’s addition (the inverse-companion): the forward reading is that a token bucket protects the service. The inverse is that the burst depth is a debt the service agreed to honour. Fifty tokens sitting in a full bucket are fifty requests you have promised to accept simultaneously, at some moment of the client’s choosing and not yours — so the limiter that caps your average has also specified your worst instant. Read backwards, choosing a burst size is capacity planning for a spike you will never see coming, and a generous limiter is a stricter requirement on everything behind it.
LIT rate 10 per second and burst 50 over a 2,000 ms window offered 1,056 requests, roughly fifteen times what the limiter permits: 69 were admitted and 987 rejected, admitted plus rejected equalling offered exactly with nothing lost in the accounting, against a theoretical ceiling of rate x T + burst = 70 - the bucket sits one token under its own bound
FIG The token bucket comes from ATM traffic shaping and is now the shape of nearly every public API rate limiter. AVAN checked the bound rather than the behaviour, because the behaviour is obvious and the bound is what you rely on. rate x T + burst is a promise to whatever is downstream: no matter how arrivals are arranged, no window of length T can push more than this through. Admitting 69 against a ceiling of 70 is the interesting result - the limiter is not conservative, it spends essentially everything it is allowed to.
FIG The token bucket comes from ATM traffic shaping and is now the shape of nearly every public API rate limiter. AVAN checked the bound rather than the behaviour, because the behaviour is obvious and the bound is what you rely on. rate x T + burst is a promise to whatever is downstream: no matter how arrivals are arranged, no window of length T can push more than this through. Admitting 69 against a ceiling of 70 is the interesting result - the limiter is not conservative, it spends essentially everything it is allowed to.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN