A token bucket admits at most b + r·t in any window of length t: a sustained rate r with a burst allowance b on top of it. A fixed window of the same nominal limit admits nearly twice the limit across a boundary — on the lesson's trace, nine in one second while advertising five.
Core ideas
A rate limit is a promise about every window, not about the windows a counter happens to be keeping.
Tokens arrive at r a second and each admission spends one. Because the level carries over between arrivals, the limiter has memory of how much of its allowance has recently been used — which is what lets it be precise about every window rather than about aligned ones.
The level is capped at b, so an idle hour buys exactly b tokens and not one more. Without that cap a quiet night would pay for an unbounded morning and the b + r·t guarantee would be gone. The cap is the difference between a burst allowance and a savings account.
Counting to limit and resetting at each boundary admits limit at the end of one window and limit again at the start of the next, so a client that straddles the boundary gets up to twice the advertised rate in one window's width. The advertised number is true only of the windows the counter is aligned to.
The material
How a bucket admits, what it guarantees over every window, and what the same trace does to a fixed-window counter.
A bucket has a capacity b and refills at r tokens per unit time. Between two arrivals separated by Δt, the level rises by r·Δt and is then capped at b. An arrival is admitted if at least one whole token is present, and it spends one; otherwise it is rejected and the level is unchanged.
Over any window of length t, the number of admissions is at most b + r·t: the tokens that were in the bucket at the start, plus the tokens that arrived during the window.
That bound is the reason a bucket is used at all. It holds for every window — not for aligned windows, not on average — because every admission consumed a token, and the tokens available in an interval are the starting level plus the refill, with the starting level capped at b. With r = 5 a second and b = 3, no second anywhere in any trace carries more than 8 admissions.
The two limiters admit almost the same number of requests overall, which is what makes the comparison interesting: they differ in when. The window admitted fewer requests in total and let nine of them through in one second, because the trace was built to straddle a boundary. The bucket's worst second was seven, under its own bound of eight.
The number that matters to whatever sits behind the limiter is the worst second, not the total: it is the one that sets the queue of the previous lessons, and a limiter advertising five that delivers nine has sized the downstream system's headroom incorrectly by a factor of nearly two. A bucket's worst case is b + r·t, which is a number you chose.
With r = 1 a second and b = 3, a bucket left alone for twenty seconds holds three tokens, not twenty. Seven arrivals at once therefore see three admitted and four refused. The cap is what makes b mean “the burst I am willing to absorb” rather than “whatever has accumulated since the last quiet period”.
Choosing the two parameters is a design conversation with two separate questions in it. r is the sustained rate the downstream system can carry — a capacity question, answered by the earlier courses. b is how much bunching you are willing to pass through in one go, and its cost is paid by the queue behind it: the burst arrives, and everything this course has said about waiting says what that does to it.
Two smaller points worth knowing. Rate limiting is loss, not delay: a rejected request is refused immediately, which is a bounded, honest failure that a client can retry — and retries are exactly the c_a² that the variability lesson warns about, so they want jitter. And a bucket can also be run as a shaper rather than a limiter, holding arrivals until a token appears instead of refusing them, which converts the same bound back into waiting.
Token levels here are exact fractions of a token computed from integer millisecond gaps, not floating-point approximations, so a long trace cannot drift. That matters for a limiter more than for most arithmetic on this course: a drift of a thousandth of a token per arrival is a different limit after a million requests.
Interactive
b + rt in any window, and what a fixed window does instead
Method
Pick the sustained rate and the burst separately; they answer different questions.
This is a capacity number, and it is the one the earlier courses compute. A limiter set above the sustained capacity is a limiter that does not limit.
The worst second the downstream service can see is b + r, and that is the number its headroom must cover. Choosing b is choosing that peak.
Admissions, rejections and the largest burst in any window. A trace that straddles a boundary is the one worth running, because it is the case a fixed window fails.
No window of length t may exceed b + r·t. If one does, the implementation is not a token bucket — most often because the level was allowed to exceed b.
The trace bunches at 900 ms and again at 1000 ms, straddling a window boundary on purpose. Both limiters advertise five a second.
Both limiters passed about the same volume. Only one of them kept its promise about every second, and the one that did not is the one that is easier to implement — a counter and a timestamp — which is why it is so common.
The bucket's worst second of seven is under its bound of eight rather than equal to it, because the trace's bunching does not line up perfectly with the refill. The bound is what you design against; seven is what this particular trace produced.
For a faded rehearsal, keep the trace and set b = 1. The supplied first move is that the bound becomes 1 + 5 = 6 per second. Predict whether the total admitted goes up or down, and what happens to the largest second.
You should be able to run a trace through a bucket by hand, state the b + r·t bound and check a trace against it, show how a fixed window doubles its advertised limit across a boundary, and choose r and b from two separate design questions.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.