Token Bucket
Token Bucket Algorithm
The Token Bucket is one of the most commonly used rate-limiting algorithms. It is simple, memory-efficient, and allows short bursts of traffic while still controlling the overall request rate.
How Does It Work?
A token bucket is a container with a fixed capacity. Tokens are added to the bucket at a predefined rate.
- The bucket has a maximum capacity.
- Tokens are added at a fixed refill rate.
- Each request consumes one token.
- If a token is available, the request is allowed.
- If no token is available, the request is rejected.
- Once the bucket is full, additional tokens are discarded.
The Token Bucket algorithm mainly depends on two parameters:
- Bucket Size: The maximum number of tokens that can be stored in the bucket.
- Refill Rate: The number of tokens added to the bucket over a given period.
For example: Bucket Size = 100 tokens, Refill Rate = 10 tokens/second
This means the system can handle a short burst of up to 100 requests if the bucket is full, while tokens are continuously replenished at 10 tokens per second.
How Many Buckets Do We Need?
The number of buckets depends on how we want to apply the rate limit.
- Per API endpoint: A user may need different buckets for different APIs.
- Per IP address: If the limit is based on IP address, each IP can have its own bucket.
- Global limit: If the entire system allows a maximum number of requests, a single shared bucket can be used.
Advantages
- Simple to implement: The logic is straightforward.
- Memory efficient: It only needs to maintain the bucket state rather than storing every request.
- Supports burst traffic: If tokens have accumulated in the bucket, multiple requests can be processed quickly until the available tokens are consumed.
Disadvantages
- Requires careful tuning: The bucket size and refill rate need to be configured properly for the application's traffic and requirements.
Key Takeaway
Token Bucket allows requests as long as tokens are available. Tokens are continuously refilled at a fixed rate, which controls the long-term request rate while still allowing short bursts of traffic.