Fixed Window Algorithm

Relevant source files

The following files were used as context for generating this wiki page:

• fastlimit/scripts/fixed_window.lua
• tests/test_fixed_window.py
• fastlimit/limiter.py
• fastlimit/backends/redis.py
• fastlimit/utils.py
• README.md

The Fixed Window algorithm is the default rate limiting strategy within FastLimit. It divides time into discrete, fixed intervals (windows), such as a specific minute or hour, and tracks the number of requests made within that specific bucket. Once the window expires, the counter resets for the next interval.

This algorithm is preferred for its simplicity, low memory footprint (approximately 100 bytes per key), and strict enforcement of limits within a given time period. However, it is susceptible to "boundary bursts," where a user can potentially double their allowed rate by making requests at the very end of one window and the beginning of the next.

Sources: README.md:92-108, fastlimit/limiter.py:46

Architecture and Logic

The implementation relies on a coordinated flow between the Python RateLimiter class, the RedisBackend, and an atomic Lua script executed on the Redis server.

Key Components

Component	Responsibility
RateLimiter	Orchestrates the request, parses rate strings (e.g., "100/minute"), and generates window-aligned keys.
RedisBackend	Manages connection pooling and executes the fixed_window.lua script using EVALSHA.
fixed_window.lua	Performs atomic incrementing, TTL management, and limit checking within Redis.
utils.py	Provides get_time_window to align timestamps to the start of the fixed interval.

Sources: fastlimit/limiter.py:126-154, fastlimit/backends/redis.py:127-145, fastlimit/scripts/fixed_window.lua:1-12

Data Flow and Window Alignment

When a request is initiated via limiter.check(), the system calculates the current window boundary. For a 60-second window, a timestamp like 1700000142 is aligned to 1700000100. This aligned timestamp becomes part of the Redis key, ensuring all requests within that minute increment the same counter.

The diagram shows the sequence from an incoming request to the final allowance or denial based on the aligned time window.
Sources: fastlimit/limiter.py:136-154, fastlimit/scripts/fixed_window.lua:14-43

Technical Implementation

Lua Script Atomicity

The core logic resides in fixed_window.lua. It uses INCRBY to add the request cost to the counter and EXPIREAT to ensure the key expires exactly at the end of the window boundary, rather than relative to the first request.

-- Increment counter atomically
local current = redis.call('INCRBY', key, cost)

-- Set expiration on first request
if current == cost then
    redis.call('EXPIREAT', key, window_end)
end

Sources: fastlimit/scripts/fixed_window.lua:19-25

API Parameters

The RedisBackend.check_fixed_window method and the Lua script require the following arguments:

Parameter	Type	Description
key	String	The unique identifier including the window timestamp.
max_requests	Integer	The limit (multiplied by 1000 for integer precision).
window_seconds	Integer	Total duration of the window in seconds.
window_end	Integer	Epoch timestamp when the current window expires.
cost	Integer	The weight of the request (default 1000).

Sources: fastlimit/backends/redis.py:146-155, fastlimit/scripts/fixed_window.lua:3-12

Features and Limitations

Precision and Multi-tenancy

The algorithm uses integer math with a 1000x multiplier to maintain precision across operations. It supports multi-tenant isolation by incorporating tenant_type into the generated Redis key, allowing different tiers (e.g., "free" vs "premium") to have independent counters for the same resource.
Sources: fastlimit/limiter.py:121-131, tests/test_fixed_window.py:73-100

Performance Metrics

Benchmarks indicate that the Fixed Window algorithm is the highest-performing option in the library due to its minimal Redis operations.

• Latency (p99): ~2.0ms
• Throughput: 15,000+ requests per second
• Memory: ~100 bytes per key

Sources: README.md:213-221

Boundary Burst Behavior

While efficient, the algorithm allows for a burst of up to 2x the limit at window boundaries. If a user exhausts their limit at the very end of Window A and immediately sends a full burst at the start of Window B, the effective rate over that short duration exceeds the intended limit. Users requiring smoother enforcement should consider Sliding Window Algorithm or Token Bucket.
Sources: README.md:105-108, tests/test_fixed_window.py:38-55

Usage Example

Manual check using the Fixed Window algorithm:

try:
    # Key is 'user:123', limit is 5 requests per minute
    await limiter.check(
        key="user:123", 
        rate="5/minute", 
        algorithm="fixed_window"
    )
    # Process request...
except RateLimitExceeded as e:
    print(f"Retry after {e.retry_after} seconds")

Sources: tests/test_fixed_window.py:18-36, fastlimit/limiter.py:84-118

Conclusion

The Fixed Window algorithm provides a high-performance, low-overhead solution for standard rate limiting needs. By leveraging Redis Lua scripts and precise time-window alignment, it ensures atomicity and distributed consistency, making it suitable for high-throughput Python applications.