Search
4 results for “token-bucket”
Search results
Rate Limiting Algorithms
How the token bucket algorithm AWS API Gateway actually uses separates a steady-state rate from a burst allowance, and why a request only fails once the bucket is genuinely empty, not the instant the average rate is exceeded.
In the token bucket algorithm, what do the "rate" and "burst" settings each actually control?
The rate is how many tokens get added to the bucket per second, the steady-state throughput the API is designed to sustain indefinitely. The burst is the bucket's total capacity, the maximum number of tokens that can accumulate and therefore the largest spike of concurrent requests the API will accept in a single instant before it starts rejecting anything further. A request consumes one token; as long as the bucket has a token available, the request proceeds immediately, rate and burst are two independent numbers, not one combined setting, because sustained throughput and tolerance for short spikes are genuinely different things to configure.
A client sends a sudden spike of requests that exceeds the configured rate, but the API doesn't immediately reject any of them. Why not, and when does rejection actually start?
The token bucket has accumulated capacity up to the burst limit, if the client had been under the rate limit recently, unused tokens built up in the bucket, and that reserve absorbs a short spike without any request failing, exactly the point of separating burst capacity from steady-state rate. Rejection (a 429 response) only starts once the bucket is actually empty, every accumulated token has been consumed and the spike is sustained long enough that the rate of token consumption keeps exceeding the rate of token replenishment. This is why a token bucket, unlike a hard per-second cap, tolerates brief bursts gracefully while still enforcing a real steady-state ceiling.
Why would a system use a sliding window rate limiter instead of a token bucket, and what problem does it fix?
A naive fixed window (say, "100 requests per minute, resetting on the minute") allows a client to send 100 requests in the last second of one window and another 100 in the first second of the next, 200 requests in a two-second span despite the stated 100/minute limit, an artifact of the window boundary rather than actual demand. A sliding window rate limiter instead evaluates the limit over a continuously moving time range rather than fixed, discrete buckets, which avoids that boundary-doubling effect at the cost of typically more state to track (timestamps of recent requests, not just a single counter) compared to a token bucket's simpler accumulator model.