Atomic Operations with Lua Scripts
Relevant source files
The following files were used as context for generating this wiki page:
Atomic operations are a cornerstone of the FastLimit library, ensuring that rate limiting logic remains consistent and race-condition-free in distributed environments. By offloading the core algorithm logic to Redis via Lua scripts, FastLimit guarantees that multiple concurrent requests are processed as a single indivisible unit of work.
These scripts handle the complex arithmetic required for different rate limiting strategies—Fixed Window, Sliding Window, and Token Bucket—while maintaining high performance through integer-only math and script caching (EVALSHA).
Sources: fastlimit/backends/redis.py:34-40, README.md:21-21, tests/test_concurrency.py:10-15
Architectural Integration
The RedisBackend class serves as the bridge between the Python application and the Lua scripts stored in Redis. During initialization, the backend loads these scripts from the filesystem and registers them with the Redis server using SCRIPT LOAD. This generates a SHA-1 hash for each script, allowing subsequent calls to use EVALSHA, which reduces network overhead and parsing time.
The diagram shows the lifecycle of a rate limit check, from script registration to atomic execution.
Sources: fastlimit/backends/redis.py:46-55, fastlimit/backends/redis.py:126-140, fastlimit/backends/redis.py:165-180
Script Communication Interface
All Lua scripts in FastLimit follow a standardized input and output format to ensure compatibility with the RedisBackend.
Standardized Inputs
Scripts receive parameters through two primary arrays:
- KEYS: Used for Redis keys (e.g., window identifiers or bucket state).
- ARGV: Used for algorithm parameters like request limits, window durations, and current timestamps.
Standardized Outputs
Every script returns a table (list) containing three specific values:
- allowed: Integer (1 for True, 0 for False).
- remaining: Estimated tokens or requests remaining (scaled by 1000x multiplier).
- retry_after_ms: Milliseconds until a subsequent request might be allowed.
Sources: fastlimit/scripts/fixed_window.lua:1-13, fastlimit/scripts/sliding_window.lua:1-14, fastlimit/scripts/token_bucket.lua:1-12, fastlimit/backends/redis.py:198-208
Rate Limiting Algorithms
Fixed Window Atomic Logic
The Fixed Window algorithm uses INCRBY to increment a counter. On the first request of a window, it uses EXPIREAT to align the key's expiration with the exact end of the time boundary, preventing drifts caused by network latency.
The flow ensures that expiration is set only once and that the check is atomic.
Sources: fastlimit/scripts/fixed_window.lua:18-30, fastlimit/backends/redis.py:149-160
Token Bucket Atomic Logic
The Token Bucket script manages state using a Redis Hash (HMSET). It calculates token refills based on the difference between the current time (provided in milliseconds) and the last_refill_ms stored in the hash.
| Parameter | Logic |
|---|---|
| Refill Calculation | math.floor((refill_rate * time_elapsed_ms) / 1000) |
| Capacity Enforcement | math.min(max_tokens, current_tokens + tokens_to_add) |
| Atomic Update | HMSET key tokens new_tokens last_refill_ms current_time_ms |
Sources: fastlimit/scripts/token_bucket.lua:28-40, fastlimit/scripts/token_bucket.lua:53-55
Sliding Window Atomic Logic
The Sliding Window is the most complex atomic operation, requiring two keys (KEYS[1] for current window, KEYS[2] for previous window). It uses fixed-point arithmetic to calculate a weighted count across boundaries.
-- Weighted count = current_count + (previous_count * weight) / 1000
local remaining_in_window = window_seconds - elapsed_in_window
local prev_weight_fp = math.floor((remaining_in_window * 1000) / window_seconds)
local weighted_previous = math.floor((previous_count * prev_weight_fp) / 1000)
local weighted_count = current_count + weighted_previous
Sources: fastlimit/scripts/sliding_window.lua:42-50, fastlimit/backends/redis.py:321-335
Integer Precision Strategy
To avoid floating-point inconsistencies between Python and Lua, FastLimit uses a 1000x multiplier for all rate calculations. This allows the system to represent fractional costs or rates (like 1.5 requests per second) using pure integer math.
- Cost of 1: Represented as
1000. - Max Requests: A limit of 100 is passed as
100000. - Time: Millisecond precision is used for
retry_after_msand Token Bucket refills to prevent crashes on low rates (e.g., 1 request per hour).
Sources: fastlimit/scripts/sliding_window.lua:20-25, fastlimit/scripts/token_bucket.lua:10-12, CHANGELOG.md:23-26
Concurrency and Resilience
The atomicity of Lua scripts ensures that even under high load (e.g., 500+ concurrent requests), the limits are strictly enforced. In multi-tenant scenarios, scripts ensure that one tenant's burst does not interfere with another's, even if they share the same Redis instance.
If a script is evicted from Redis memory, the RedisBackend catches the NoScriptError and falls back to a full EVAL call, re-registering the script for future use.
Sources: tests/test_concurrency.py:27-45, fastlimit/backends/redis.py:186-193, tests/test_concurrency.py:205-220
Conclusion
By utilizing Lua scripts, FastLimit achieves zero race conditions and high throughput. This architecture allows the library to perform complex calculations—such as sliding window weight decay or continuous token refills—directly on the storage layer, minimizing network round-trips and ensuring absolute consistency across distributed application nodes.