Token Bucket Algorithm
Relevant source files
The following files were used as context for generating this wiki page:
The Token Bucket Algorithm is a high-performance rate limiting mechanism implemented within FastLimit to provide smooth traffic distribution and support for bursty workloads. Unlike the Fixed Window algorithm, which can allow double the limit at window boundaries, the Token Bucket refills tokens continuously over time, ensuring a more consistent request flow and a better user experience.
Within the project, this algorithm is implemented using a hybrid approach: Python logic handles the high-level configuration and rate parsing, while an atomic Lua script executed in Redis manages the bucket state (tokens and timestamps) to prevent race conditions in distributed environments.
Sources: fastlimit/algorithms/token_bucket.py:1-40, README.md:95-115
Architecture and Core Logic
The implementation relies on a "bucket" that holds tokens up to a maximum capacity. Tokens are added to the bucket at a fixed refill rate based on the configured window. Each incoming request attempts to consume a specific "cost" (defaulting to 1 token). If the bucket contains sufficient tokens, the request is allowed; otherwise, it is denied.
Multiplier-Based Precision
To avoid floating-point inaccuracies and support low rates (e.g., 1 request per hour), the system uses an internal 1000x multiplier for all token calculations. A request with a cost of 1 is treated as 1000 units, and a limit of 100 requests becomes a capacity of 100,000 units.
Sources: fastlimit/scripts/token_bucket.lua:1-25, fastlimit/limiter.py:165-175, README.md:25-30
Logic Flow Diagram
The following diagram illustrates the lifecycle of a rate limit check using the Token Bucket algorithm:
The diagram shows the transition from Python-side preparation to the atomic execution within Redis via Lua.
Sources: fastlimit/scripts/token_bucket.lua:28-85, fastlimit/limiter.py:160-200
Implementation Details
Python Interface: TokenBucket Class
The TokenBucket class in fastlimit/algorithms/token_bucket.py serves as the bridge between the RateLimiter and the RedisBackend.
| Component | Description |
|---|---|
check() | Orchestrates the check by calculating the refill_rate_per_second and calling the backend Lua script. |
reset() | Removes the Redis key associated with the bucket, effectively refilling it to full capacity. |
get_usage() | Retrieves current token counts and timestamps, converting them back from the 1000x multiplier for display. |
calculate_refill_rate() | Utility to determine tokens added per second: requests / window_seconds. |
Sources: fastlimit/algorithms/token_bucket.py:53-120, fastlimit/limiter.py:355-380
Redis Lua Script
The script token_bucket.lua ensures atomicity. It uses HMGET to retrieve the current token count and the last_refill_ms timestamp in a single operation.
- Refill Calculation:
tokens_to_add = (refill_rate_per_second * time_elapsed_ms) / 1000. - State Persistence: Uses
HMSETto store the new token count and the current timestamp. - Expiry: Sets a TTL of
window_seconds * 2 + 60to ensure keys are eventually evicted from Redis.
Sources: fastlimit/scripts/token_bucket.lua:38-65, fastlimit/backends/redis.py:270-320
Configuration and Parameters
The algorithm is configured through the standard limiter.limit() decorator or manual check() calls.
Parameters Table
| Parameter | Type | Internal Multiplier | Description |
|---|---|---|---|
max_tokens | int | Yes (1000x) | The capacity of the bucket (the "Limit"). |
window_seconds | int | No | The time period over which the limit is defined. |
refill_rate | int | Yes (1000x) | max_tokens / window_seconds. |
cost | int | Yes (1000x) | Tokens consumed per request (default 1). |
Sources: fastlimit/scripts/token_bucket.lua:6-15, fastlimit/algorithms/token_bucket.py:75-85
Usage Example
# 100 requests per minute allows a burst of 100,
# then refills at ~1.67 tokens/second.
@limiter.limit("100/minute", algorithm="token_bucket")
async def bursty_endpoint(request: Request):
return {"status": "ok"}
Sources: README.md:100-105, fastlimit/limiter.py:230-250
Performance Characteristics
Based on project benchmarks and implementation details, the Token Bucket algorithm provides the following characteristics:
- Latency: Approximately 1.0ms (p50) to 2.2ms (p99).
- Throughput: 12,000+ requests per second.
- Memory Usage: Approximately 150 bytes per key in Redis (storing a Hash with two fields).
- Burst Handling: Allows immediate consumption of the full
max_requestsif the bucket is full.
Sources: README.md:145-155, benchmarks/performance.py:230-250
Conclusion
The Token Bucket implementation in FastLimit provides a robust, atomic, and high-precision rate limiting solution. By offloading the state management to Lua scripts in Redis, it maintains consistency across distributed nodes while supporting complex features like cost-based limiting and smooth sub-second refills. It is the recommended algorithm for most user-facing APIs where traffic smoothness and burst allowance are valued.
Sources: fastlimit/algorithms/token_bucket.py:40-50, README.md:135-140