Token Bucket Algorithm
What you'll learn: How the token bucket algorithm smoothly controls request rates while allowing controlled bursts of traffic.
The Core Idea
Imagine a physical bucket that holds tokens. Tokens are added to the bucket at a fixed, steady rate (e.g., 100 tokens per second). Each incoming request must "spend" one token to proceed. If the bucket is empty, the request is rejected or delayed. The bucket has a maximum capacity, so excess tokens overflow and are lost.
This simple mechanism provides two crucial features: sustained rate limiting and burst tolerance.
How It Works
The algorithm maintains:
- A bucket capacity (e.g., 500 tokens max)
- A refill rate (e.g., 100 tokens/second)
- A current token count
When a request arrives:
- Calculate how many tokens should have been added since the last check
- Add those tokens to the bucket (up to capacity)
- If at least one token exists, consume it and allow the request
- If no tokens exist, reject or throttle the request
Burst Handling
The bucket capacity allows bursts up to its size. A client could make 500 requests instantly if the bucket is full, then be rate-limited to the refill rate (100 req/s). This flexibility is crucial for handling legitimate traffic spikes while preventing sustained abuse.
Real-World Analogy
Think of a coffee shop giving customers punch cards. Cards are handed out at a steady rate (one per minute), and you can save up to 10 cards. If you arrive with 10 cards, you can buy 10 coffees immediately, then you're limited to one per minute thereafter.
Key Takeaway: The token bucket algorithm controls sustained request rates through steady token refills while permitting short bursts up to the bucket's capacity, making it ideal for practical rate limiting that accommodates natural traffic patterns.