Sliding Window Algorithm
Relevant source files
The following files were used as context for generating this wiki page:
The Sliding Window algorithm is a high-precision rate limiting mechanism within the FastLimit library designed to provide a smoother and more accurate alternative to the Fixed Window approach. It functions by combining the request count of the current time window with a weighted portion of the previous window, effectively smoothing out request distributions across window boundaries and preventing the "boundary burst" problem.
In the context of the FastLimit project, this algorithm is implemented using a hybrid approach: Python handles high-level key generation and logic, while an atomic Lua script executed on the Redis backend performs the weighted calculations and counter increments. This ensures atomicity and consistency even in distributed environments with high concurrency.
Sources: fastlimit/algorithms/sliding_window.py:5-10, fastlimit/scripts/sliding_window.lua:14-19, README.md:120-128
Core Logic and Mathematical Formula
The algorithm estimates the number of requests in a sliding window by calculating a weighted average based on the requester's current position within the current time window.
Mathematical Formula
The weighted count is calculated as follows:
weighted_count = current_count + (previous_count * weight)
Where:
weight = (window_seconds - elapsed_in_window) / window_secondscurrent_count: Total requests made in the current fixed window.previous_count: Total requests made in the immediately preceding fixed window.elapsed_in_window: Time passed since the start of the current window.
Sources: fastlimit/algorithms/sliding_window.py:27-33, fastlimit/scripts/sliding_window.lua:20-24
Computational Implementation
To ensure high precision and avoid floating-point inconsistencies across different environments, the implementation uses fixed-point integer arithmetic with a 1000x multiplier.
Sources: fastlimit/scripts/sliding_window.lua:25-27, fastlimit/limiter.py:168-169
The flow shows how the system determines window boundaries and applies weighting to decide if a request is allowed.
Sources: fastlimit/scripts/sliding_window.lua:36-65, fastlimit/backends/redis.py:441-455
Architectural Components
Python Interface (SlidingWindow & RateLimiter)
The RateLimiter class serves as the entry point, routing requests to the SlidingWindow algorithm when specified. The SlidingWindow class manages the generation of Redis keys by appending window start timestamps to the base identifier.
| Component | Responsibility |
|---|---|
check() | Calculates window boundaries and calls the Redis backend. |
get_usage() | Retrieves weighted statistics for the current sliding window. |
reset() | Clears both current and previous window keys for a given identifier. |
Sources: fastlimit/algorithms/sliding_window.py:75-100, fastlimit/limiter.py:183-205
Redis Lua Backend (sliding_window.lua)
The Lua script ensures that the check and increment operations are atomic. It performs the following steps:
- Fetches
current_countandprevious_countfrom Redis. - Calculates the fixed-point weight based on the provided
current_timestamp. - Determines if the
costcan be accommodated. - If allowed, increments the current window counter and sets an expiry (usually
window_seconds * 2). - Returns a result set containing the allowed status, remaining capacity, and retry delay.
Sources: fastlimit/scripts/sliding_window.lua:36-150, fastlimit/backends/redis.py:430-440
Usage Statistics and Metadata
The algorithm provides detailed usage information, which is useful for debugging and for populating rate limit headers.
| Field | Description |
|---|---|
current | The total weighted request count (current + weighted previous). |
limit | The maximum requests allowed in the window. |
remaining | Available capacity before hitting the limit. |
weight | The decimal weight (0.0 to 1.0) applied to the previous window. |
current_window | Raw request count in the current fixed window. |
previous_window | Raw request count in the previous fixed window. |
Sources: fastlimit/algorithms/sliding_window.py:145-165, fastlimit/limiter.py:480-500
Retry-After Calculation
When a request is denied, the algorithm calculates exactly when enough capacity will become available. This is more sophisticated than the Fixed Window approach because capacity is "freed" continuously as the weight of the previous window decays.
The diagram illustrates the calculation of retry_after_ms based on the weight decay of the previous window.
Sources: fastlimit/scripts/sliding_window.lua:94-135, tests/test_sliding_window.py:140-155
Comparison with Other Algorithms
| Feature | Fixed Window | Sliding Window | Token Bucket |
|---|---|---|---|
| Accuracy | Good | Best | Good |
| Boundary Burst | Possible (2x) | None | None |
| Memory per key | ~100 bytes | ~200 bytes | ~150 bytes |
| Complexity | Low | Medium | Medium |
Sources: README.md:129-145, fastlimit/algorithms/sliding_window.py:53-65
Conclusion
The Sliding Window algorithm is the most accurate rate limiting method in FastLimit. By maintaining two Redis keys and applying a time-based weight, it provides a smooth transition between time windows, effectively preventing users from gaming window boundaries while maintaining strict enforcement of the specified rate.
Sources: fastlimit/algorithms/sliding_window.py:13-15, README.md:120-128