Token Bucket
A rate limiting algorithm with two settings: tokens refill at a fixed rate up to a bucket capacity, and each request spends one token. A full bucket admits a burst as large as the capacity, while the refill rate sets the long-term average. Unlike a leaky bucket, it permits bursts.
Full Explanation
A token bucket is a rate limiting algorithm. It has two settings: a fill rate and a bucket capacity. Tokens accumulate up to the capacity. Each request spends one token. A request that finds the bucket empty is refused until tokens refill. A full bucket therefore lets a client burst up to the capacity. After that, the fill rate caps the sustained average. It is not a windowed counter. There is no clock boundary that resets anything. It is also not a leaky bucket. A leaky bucket enforces a strict drain rate and allows no bursts. The two are duals: a token bucket starts full and spends tokens, while a leaky bucket starts empty and fills with arriving requests. The model is older than HTTP rate limiting. RFC 2211 section 5 gives the IETF's token bucket traffic descriptor as a bucket rate r and a bucket depth b. Both are measured in bytes rather than in requests.
How it works
Two parameters define the whole algorithm:
- the fill rate: tokens added per second, the sustained average limit. RFC 2211 calls it the bucket rate r.
- the capacity: the largest burst a full bucket admits. RFC 2211 calls it the bucket depth b.
With a fill rate of 100 tokens per second and a capacity of 200, a client whose bucket is full can send 200 requests at once. After that it can send no more than 100 per second while the bucket refills. After two idle seconds it has 200 tokens again. Nothing needs to be counted per request. Per client, the implementation stores only the current token count and the timestamp of the last refill. It derives the tokens gained from the time elapsed since that timestamp. Redis's reference implementation keeps exactly those two fields in a hash. It runs the whole refill-check-consume cycle inside one Lua script. This makes the check atomic in a single round trip (Redis token bucket tutorial).
What happens to a request that arrives at an empty bucket is an implementation choice. HTTP limiters normally refuse it. Traffic shapers queue it instead. The Linux Token Bucket Filter (tc-tbf(8)) queues packets up to a configured limit. It then throttles until the first queued packet can be sent. There, a token corresponds roughly to a byte rather than to a request. This is the general case: a token is a unit of cost. One request per token is only the common convention.
Why it matters for a CDN
The limiter runs on the edge server, in front of the origin. Excess requests are therefore shed before they consume origin compute and billable traffic. Fastly describes its own edge primitives as controlling the rate of requests sent to Fastly services and origin servers from individual clients or from clients forming a single identifiable group. Real client traffic is bursty. A mobile app that batches requests on launch is the canonical case. A token bucket admits that burst while still capping the average. A rigid per-second limit rejects it instead. Each client gets its own bucket, keyed by client identity. Kong's rate limiting plugin shows the usual precedence. It keys on the authenticated consumer when an authentication plugin is configured. It falls back to the client IP address when there is none (Kong rate limiting).
What CDNs do
Most CDN rate limiting products are not token buckets. They count requests over a window. Checked against each vendor's current documentation:
- Cloudflare rate limiting rules take a period and a number of requests per period. The counting model is the number of requests (Enterprise Advanced Rate Limiting can count a complexity score instead). Once the rate is reached, the default behaviour blocks for the whole configured mitigation timeout regardless of the rate during that period. This is unlike a token bucket, where a client is refused only until its tokens refill. Only some Enterprise customers can switch the rule to throttle requests above the rate. Counting periods are plan-dependent: 10 seconds on Free, up to 65,535 seconds on Enterprise.
- AWS WAF rate-based rules count requests inside a rolling evaluation window of 60, 120, 300 or 600 seconds (default 300), looking back from the current time. The window sets how far back AWS WAF looks, not how often it looks. It checks the rate about every ten seconds, so mitigation lags the burst (RateBasedStatement).
- Fastly's rate counters convert accumulated counts into an estimated rate over a 1-, 10- or 60-second window, always expressed in requests per second. They are documented as designed to count high volumes of traffic quickly rather than precisely. The Edge Rate Limiting product must be enabled on the account by Fastly before the VCL primitives are available.
- The API gateway layer supplies the counter-example, though not uniformly. AWS API Gateway throttles REST APIs with a literal token bucket. A token counts for a request. The throttling rate is the rate at which tokens are added, and the throttling burst is the capacity of the bucket. Account-level rate and burst limits apply by default per Region. Per-API, per-stage and per-client limits are opt-in, the last of these keyed on API keys through a usage plan. Other gateways choose differently. APISIX's limit-req plugin documents the leaky bucket algorithm. Kong's rate limiting plugin limits requests per period of seconds through years, offering sliding or fixed windows only in its advanced version. So verify the algorithm rather than assuming it from the product category.
Watch out for
- Do not assume a limiter is a token bucket because it has a burst setting. Cloudflare, AWS WAF and Fastly all count requests over a window. Window length trades detection speed for accuracy. Fastly states that a shorter window detects attacks sooner at the expense of accuracy.
- A fixed-window counter allows double the intended burst at a boundary. 10 requests at second 9 and 10 more at second 11 both pass a limit of 10 per 10 seconds. That is 20 requests in 2 seconds. A sliding window log removes that at the cost of higher memory use (Redis rate limiting tutorial). A token bucket has no boundary to straddle, but a full bucket still admits a burst the size of the capacity at any moment. So choose the capacity deliberately.
- Nginx's limit_req is a leaky bucket, not a token bucket. It delays excess requests until their number exceeds the maximum burst size. It then terminates them, by default with status 503. The maximum burst size defaults to zero, so an unqualified limit_req allows no burst at all.
- Distributed counters multiply the limit. When each node counts for itself, the effective ceiling is roughly the configured limit times the number of instances the traffic spreads across (APISIX limit-req). Cloudflare is explicit that it has no global counters. Each data center maintains its own. Only data centers associated with the same geographical location share them (request rate calculation).
- Sharing counter state costs a round trip. Kong's cluster policy is accurate, but it forces a read and a write on the data store for every request. That is its largest performance impact. Its local policy has minimal impact, but it diverges as the node count grows unless a consistent-hashing load balancer sits in front of the gateway.
- Even a genuine token bucket is not a hard ceiling. AWS documents API Gateway throttles and quotas as applied on a best-effort basis. They should be thought of as targets rather than guaranteed request ceilings.
- Counting by IP address alone collapses every client behind one shared address into a single bucket. Cloudflare offers an IP with NAT support counting characteristic for this. It is only available on Business plans and above.
Best practice
- Size the capacity to the largest burst the origin can absorb. The capacity is the burst allowance, so an over-generous capacity licenses a client to hit the origin at full speed.
- Set the fill rate to the sustained average you are willing to serve, not to the peak. The bucket absorbs peaks. The rate sets the ceiling.
- Key on authenticated identity for API traffic: API key, consumer, or account. Treat the client IP address as the fallback it is.
- Refuse with 429, not 503. RFC 6585 section 4 defines 429 Too Many Requests for exactly this condition. It says the response representations SHOULD explain it. It allows a Retry-After header indicating how long to wait. A token bucket can derive that value from its fill rate. Redis's implementation returns the ceiling of one divided by the refill rate. Nginx and APISIX both default to 503, so set the status explicitly.
- Share counter state only where exactness matters, such as billing or quota enforcement. Where the goal is protecting the origin, per-node approximation is cheaper and usually good enough.
Examples
# Python: simple token bucket implementation
import time
class TokenBucket:
def __init__(self, rate, capacity):
self.rate = rate # tokens per second
self.capacity = capacity # max burst
self.tokens = capacity
self.last_refill = time.monotonic()
def allow(self):
now = time.monotonic()
elapsed = now - self.last_refill
self.tokens = min(
self.capacity,
self.tokens + elapsed * self.rate
)
self.last_refill = now
if self.tokens >= 1:
self.tokens -= 1
return True
return False
# Usage: 10 req/sec, burst of 20
bucket = TokenBucket(rate=10, capacity=20)
for i in range(25):
print(f"Request {i}: {'allowed' if bucket.allow() else 'denied'}")
# Nginx: rate limiting (leaky bucket with burst)
http {
# 10 requests/sec per IP, bucket size 20
limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;
server {
location /api/ {
limit_req zone=api burst=20 nodelay;
# nodelay: process burst immediately
# without nodelay: queue burst requests
}
}
}
# Redis: distributed token bucket
# Lua script for atomic token bucket check
local key = KEYS[1]
local rate = tonumber(ARGV[1]) -- tokens/sec
local capacity = tonumber(ARGV[2]) -- max tokens
local now = tonumber(ARGV[3])
local tokens = tonumber(redis.call('hget', key, 'tokens') or capacity)
local last = tonumber(redis.call('hget', key, 'last') or now)
local elapsed = now - last
tokens = math.min(capacity, tokens + elapsed * rate)
if tokens >= 1 then
redis.call('hset', key, 'tokens', tokens - 1, 'last', now)
return 1 -- allowed
end
return 0 -- deniedFrequently Asked Questions
A rate limiting algorithm with two settings: tokens refill at a fixed rate up to a bucket capacity, and each request spends one token. A full bucket admits a burst as large as the capacity, while the refill rate sets the long-term average. Unlike a leaky bucket, it permits bursts.
# Python: simple token bucket implementation
import time
class TokenBucket:
def __init__(self, rate, capacity):
self.rate = rate # tokens per second
self.capacity = capacity # max burst
self.tokens = capacity
self.last_refill = time.monotonic()
def allow(self):
now = time.monotonic()
elapsed = now - self.last_refill
self.tokens = min(
self.capacity,
self.tokens + elapsed * self.rate
)
self.last_refill = now
if self.tokens >= 1:
self.tokens -= 1
return True
return False
# Usage: 10 req/sec, burst of 20
bucket = TokenBucket(rate=10, capacity=20)
for i in range(25):
print(f"Request {i}: {'allowed' if bucket.allow() else 'denied'}")
# Nginx: rate limiting (leaky bucket with burst)
http {
# 10 requests/sec per IP, bucket size 20
limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;
server {
location /api/ {
limit_req zone=api burst=20 nodelay;
# nodelay: process burst immediately
# without nodelay: queue burst requests
}
}
}
# Redis: distributed token bucket
# Lua script for atomic token bucket check
local key = KEYS[1]
local rate = tonumber(ARGV[1]) -- tokens/sec
local capacity = tonumber(ARGV[2]) -- max tokens
local now = tonumber(ARGV[3])
local tokens = tonumber(redis.call('hget', key, 'tokens') or capacity)
local last = tonumber(redis.call('hget', key, 'last') or now)
local elapsed = now - last
tokens = math.min(capacity, tokens + elapsed * rate)
if tokens >= 1 then
redis.call('hset', key, 'tokens', tokens - 1, 'last', now)
return 1 -- allowed
end
return 0 -- deniedRelated CDN concepts include:
- Rate Limiting — Rate limiting caps how many requests one client may make in a given period, keyed …
- WAF (WAF) — Web application firewall: a reverse proxy that inspects HTTP(S) requests against rule sets and blocks …
- API Gateway — An API gateway is the single front door for API traffic: a reverse proxy that …