Token Bucket Algorithm
What you'll learn: How the token bucket rate limiting algorithm controls bursty traffic while maintaining smooth average throughput.
Core Concept
The token bucket algorithm is a rate limiting technique that uses a bucket holding tokens. Each incoming request consumes one token (or more, depending on request weight). Tokens are added to the bucket at a fixed rate. If the bucket is full, new tokens are discarded. If a request arrives and no tokens are available, the request is rejected or delayed.
Think of it like a coin-operated arcade game: the machine drips coins into a bucket at a steady rate (say, 10 per minute). You can spend coins as fast as you want, even in bursts, but once the bucket empties, you must wait for more coins to accumulate.
Configuration Parameters
Bucket capacity: Maximum tokens the bucket can hold. This determines the maximum burst size—how many requests can be processed instantly.
Refill rate: How many tokens are added per time unit (e.g., 100 tokens/second). This sets your sustained throughput limit.
Token cost: How many tokens each request consumes (usually 1, but can vary by request type).
When to Use Token Bucket
Token bucket excels for bursty traffic patterns common in cloud systems:
- API gateways where clients may send bursts of requests followed by quiet periods
- User-facing services where traffic naturally varies (e.g., morning login spikes)
- Video streaming where initial buffering requires bursts, then steady playback
Unlike fixed-window rate limiting (covered in Rate Limiting Fundamentals), token bucket allows temporary bursts above the average rate, provided the bucket has accumulated tokens during quiet periods. This prevents artificially throttling legitimate traffic spikes while still protecting against sustained overload.
Key Takeaway: Token bucket rate limiting uses a refillable token pool to permit controlled bursts while enforcing average throughput limits—ideal for naturally bursty cloud workloads.