Token Bucket

A token bucket limits a rate with two rules instead of a clock. Requests spend tokens from a bucket. Time refills the bucket at a fixed rate, up to a fixed capacity. A request that finds the bucket empty is turned away. That is the whole mechanism, and the figure above runs it.

The bucket in the figure holds six tokens and refills at two per second. Three workloads are queued: a burst of nine requests in just over a second, a steady drip under the limit, and a flood over it. Press play and watch the level. Then read on to see why the burst gets through and the flood does not.

Rate limits exist to protect the thing behind them. A backend that can serve a thousand requests per second should not see two thousand, however eager the clients are. The limiter stands in front and turns excess demand into a clear, cheap no, instead of a slow, expensive failure.

Two rules: spend and refill

Rule one: every request costs a token. No token, no service. Rule two: the bucket earns tokens at the refill rate, two per second in the figure, but never past capacity. A full bucket earns nothing, so idle time past full is thrown away.

Both rules run on arrival, not on a timer. When a request arrives, the limiter tops up the bucket for the seconds since the last request, then checks the balance. The state is two numbers: the level and the time of the last update. A token bucket therefore costs O(1) time and O(1) memory per request, however many requests have passed.

The whole limiter fits in one class. Like the figure, this bucket starts full:

class TokenBucket:
	def __init__(self, capacity, rate):
		self.capacity = capacity
		self.rate = rate
		self.tokens = capacity
		self.updated_at = 0.0

	def allow(self, now, cost=1):
		elapsed = now - self.updated_at
		self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
		self.updated_at = now
		if self.tokens >= cost:
			self.tokens -= cost
			return True
		return False

Starting full is a convention worth keeping. Idle time before the first request is as good as idle time after it, so the first burst should be allowed. A limiter that started empty would tax well-behaved clients for showing up early.

The cost need not be one token. A heavy report query can cost five while a ping costs one, and the same bucket then budgets work instead of count. The check stays the same: enough tokens or not.

Two implementation details are easy to get wrong. Use a monotonic clock, because a wall clock that jumps backward hands out free tokens. And compare with a small epsilon, or store milli-tokens as integers, because float dust can turn a token into 0.999999 tokens.

A burst spends saved time

The figure opens on the burst workload: nine requests inside 1.3 seconds, against a refill rate of two per second. A strict two-per-second limiter would pass the first two requests and reject the rest. The token bucket passes the first eight.

Step through the burst and watch the level. The bucket starts full at six. Each request spends one token, and each 0.15-second gap drips back 0.3. Request eight arrives to 1.1 tokens and spends down to 0.1. Request nine arrives to 0.4, needs a whole token, and is dropped. The eight that passed spent six saved tokens and two freshly dripped ones.

That is what capacity buys. The six tokens in a full bucket are three seconds of earlier quiet, saved and ready to spend in a fraction of a second. A burst is never free. It is paid for in advance.

The figure below replays the burst. Step backward and forward over request nine, the frame where the savings run out. Then switch the workload to Steady. One request every 0.6 seconds stays under the refill rate, so the bucket never leaves full and the limiter goes invisible. Well-behaved traffic never meets the limiter.

An empty bucket says no

Now switch to Flood: a request every 0.25 seconds, four per second against a refill of two. The first eleven requests get through on savings, and the bucket drains from full to empty in 2.75 seconds. From request twelve the limiter becomes a metronome: drop, allow, drop, allow. Every second request passes, which is exactly two per second. A flood cannot beat the rate. It can only spend the savings once.

Watch request thirteen. It passes only because a token dripped in during the 0.25 seconds after request twelve died. That sawtooth, drain then drip, is the refill rate made visible.

What happens to a dropped request is policy, not algorithm. If you have met this limiter as a user, it was as 429 Too Many Requests, often with a Retry-After header so the client knows when to come back. The header value is the deficit divided by the rate: half a token short at two per second means come back in 0.25 seconds. Systems that cannot lose work queue the request until a token arrives. Either way, two invariants hold: the level never goes negative, and no request borrows from the future.

If you are the client, honor the signal. Retrying at once spends another request against an empty bucket and pushes your own retry further out. Wait for the Retry-After interval, or back off exponentially when there is no header.

Sizing the bucket

The two knobs answer two different questions. The refill rate is the sustainable pace: the requests per second that may pass forever. The capacity is the burst allowance: how far above that pace traffic may spike. Rate is a speed. Capacity is a savings account.

Recovery time ties the knobs together. A bucket drained to empty needs capacity / rate seconds to refill: three seconds for the figure's six tokens at two per second. Pick the rate from what the backend can serve. Pick the capacity from the burst you want to absorb.

The common sizing mistake is a capacity of one. With no savings, every request must wait for its own drip, and the limiter degenerates into a leaky bucket: no bursts at all. Clients are bursty, so give the bucket room.

Per-key buckets scale the same way. A million users need a million pairs of numbers, and idle keys can be evicted: a key that has been quiet for capacity / rate seconds is full again, so its stored state is worth nothing.

The figure below plots the bucket level over twelve seconds for each workload. Drag the sliders. The rate tilts the slope of every climb, and the capacity raises the ceiling. The flood trace shows the shape to remember: a straight-line drain while savings last, then a sawtooth pinned to the refill rate.

For the burst workload at two tokens per second, capacity buys bursts of:

The table shows the refill at work. At this gap, every two extra tokens of capacity absorb about three more requests, because tokens keep dripping in during the burst. Capacity stretches a burst. It never raises the pace.

Token bucket and its neighbors

The token bucket is one limiter in a family, and the family differs on one question: what happens to a burst?

• Leaky bucket. Requests leave a queue at a fixed rate, so bursts are smoothed instead of absorbed. A leaky bucket cannot bank idle time. Choose it when downstream needs a perfectly even flow.

• Fixed window. A counter per window, such as 100 requests per minute, reset on the minute. Simple, but weak at the boundary: 100 requests at 10:00:59 and 100 more at 10:01:00 both pass, and the backend sees 200 in two seconds.

• Sliding log. Store the timestamp of every request and count the last window. Exact, but memory grows with the traffic being limited.

• Sliding window counter. Keep the current and previous window counts and weight them by where the window sits. Still O(1) memory, but the count is an estimate, and it can refuse honest traffic right after a burst.

The token bucket is the usual default because it keeps the two properties that matter, bounded memory and bursts allowed, for two numbers of state per key.

Where it earns its keep

The same two rules show up at every scale, from one endpoint to a continental network:

• API gateways. Envoy's local rate-limit filter is a token bucket, and Stripe has published its use of token-bucket limiters. Per-user quotas are one bucket per API key: a map from key to level and timestamp.

• Network shaping. The Linux traffic-control stack shapes packets with token buckets. The same math that throttles API calls smooths packet flows.

• Your own endpoints. One bucket per user id turns a rule like five invites per minute into six lines of code.

Keep the two rules straight and the practice problems below read as the same idea in new clothes: requests spend, time refills, empty says no. Number of Recent Calls is the measurement half of limiting, counting the requests in a trailing window. Task Scheduler is a cooldown, one task per label per interval, which is a rate limit in a costume.