Token bucket
A token bucket admits a request only when its key has a token. Each key refills at a fixed rate, here 350 requests/s, so one noisy key cannot take the capacity of the others. The bucket depth sets how large a burst can pass.
See it on the board
The same traffic runs on two boards. The simulator measured both when this page was built.
| Measure | Goal | One shared queue for all keys | One token bucket for each key |
|---|---|---|---|
| p99 latency (*) | under 250 ms | 10.1 s Fail | 30 ms Pass |
| Availability (Bolt) | at least 99.5% | 88% Fail | 100% Pass |
| Availability (Cedar) | at least 99.5% | 89.1% Fail | 100% Pass |
| Monthly cost | 8 USD/mo | 10 USD/mo | |
| p99 latency | 10.1 s | 30 ms | |
| Error rate | 12% | 0% |
Key numbers
| Number | Value |
|---|---|
| Limiter check, median | 0.1 ms |
| Default bucket depth | 1,000 tokens |
| Default refill rate | 10,000 req/s |
Buffer 1,000 jobs · last job waits 1.0 s · 17% turned away
How it works
A shared API serves many callers. If one caller sends 8 times its normal rate, its requests fill the queue, and every other caller waits behind them. A limit for the whole API does not help, because the noisy caller uses it up.
A token bucket gives each key its own bucket. A request takes one token. Tokens come back at a fixed rate. When a bucket is empty, the request is rejected at once, which costs almost no CPU, and the caller can retry later.
In the mini board three partner keys share an API that serves about 1,000 requests/s. From 0:20 the key acme sends 8 times its normal 150 requests/s. Each bucket refills at 350 requests/s. That covers the 250 requests/s peak of bolt, and the API stays below 80 percent busy. Acme gets fast rejections for the excess.
The depth of the bucket is a second control. A deep bucket lets a large burst through at once. Keep it small, so a burst cannot fill the API queue.
Set the refill rate above the normal peak of each key and below its share of the capacity.
In the levels you place a limiter in front of the API and tune the rate and the depth.