Rate Limiting Algorithms Comparison

Relevant source files

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

• README.md
• fastlimit/limiter.py
• fastlimit/algorithms/sliding_window.py
• examples/algorithms_demo.py
• benchmarks/performance.py
• tests/test_edge_cases.py
• tests/test_fixed_window.py

FastLimit provides three distinct rate limiting algorithms: Fixed Window, Token Bucket, and Sliding Window. Each algorithm is designed to address specific performance, accuracy, and user experience requirements. All algorithms utilize Redis as a backend and leverage Lua scripts to ensure atomic operations, preventing race conditions in distributed environments.

The choice of algorithm impacts how traffic bursts are handled, memory consumption, and the strictness of the rate limit enforcement. Users can specify the algorithm at the RateLimiter initialization level or override it per-request using the check() or limit() methods.

Sources: README.md:46-48, fastlimit/limiter.py:38-42

Core Algorithm Comparison

The following table summarizes the key characteristics and trade-offs of the three supported algorithms.

Feature	Fixed Window	Token Bucket	Sliding Window
Simplicity	High	Medium	Medium
Boundary Bursts	Possible (2x)	None	None
Memory Usage	Low (~100 bytes)	Medium (~150 bytes)	Medium (~200 bytes)
Traffic Smoothness	Choppy	Smooth	Smooth
Accuracy	Good	Good	Best
Redis Keys Used	1 per window	1 persistent	2 (current + previous)

Sources: README.md:113-122, fastlimit/algorithms/sliding_window.py:61-64

Performance Metrics

Based on project benchmarks, the algorithms exhibit the following performance profiles:

Metric	Fixed Window	Token Bucket	Sliding Window
Latency (p50)	0.8ms	1.0ms	1.2ms
Latency (p99)	2.0ms	2.2ms	2.8ms
Throughput	15,000+ req/s	12,000+ req/s	10,000+ req/s

Sources: README.md:213-220, benchmarks/performance.py:284-305

---

Fixed Window Algorithm

The Fixed Window algorithm is the default implementation in FastLimit. It divides time into fixed buckets (e.g., 60-second intervals) and maintains a counter for each bucket.

Logic and Architecture

The algorithm uses the current Unix timestamp to determine the window boundary. Requests are mapped to a specific key representing that window. When the window expires, the counter is reset.

Pros: Simple implementation, minimal memory footprint, and strict enforcement within specific time boundaries.
Cons: Vulnerable to "boundary bursts" where a user can send their full limit at the end of one window and again at the start of the next, effectively doubling the allowed rate for a short duration.

---

Token Bucket Algorithm

The Token Bucket algorithm allows for smoother rate limiting and supports bursty traffic by maintaining a "bucket" of available tokens that refills at a constant rate.

Logic and Architecture

• Capacity: The maximum number of tokens the bucket can hold (defined by the rate limit).
• Refill Rate: Tokens are added continuously based on the time elapsed since the last request.
• Consumption: Each request consumes a defined "cost" of tokens (default is 1).

FastLimit uses integer math with a 1000x multiplier to maintain high precision for sub-second refills without floating-point errors.

Pros: Handles bursts gracefully, provides a smoother user experience, and eliminates boundary burst issues.
Cons: Slightly higher complexity and memory usage compared to Fixed Window.

---

Sliding Window Algorithm

The Sliding Window algorithm provides the highest accuracy by calculating a weighted average of requests across the current and previous time windows.

Logic and Architecture

The algorithm maintains counts for the current window ($current_count$) and the previous window ($previous_count$). It calculates the request count using the formula:
$$weighted_count = previous_count \times (1 - \frac{t}{T}) + current_count$$
Where $t$ is the time elapsed in the current window and $T$ is the window duration.

Pros: Most accurate enforcement, prevents gaming of boundaries, and ensures a fair distribution of requests.
Cons: Highest CPU and memory usage as it requires tracking two Redis keys and performing weighted calculations.

---

Technical Implementation Details

Precision and Units

To avoid floating-point inaccuracies, FastLimit utilizes Integer Precision. All internal calculations for requests and costs are multiplied by 1000.

• max_requests: requests * 1000
• cost: cost * 1000
• refill_rate: tokens per millisecond calculated at 1000x scale.

Sources: README.md:222-225, fastlimit/limiter.py:176-177

Algorithm-Aware Operations

Operations such as reset() and get_usage() are algorithm-aware, meaning they identify and clear or retrieve the correct keys based on the algorithm's specific storage structure.

• Fixed Window Reset: Deletes the specific time-bucket key.
• Token Bucket Reset: Deletes the persistent bucket key.
• Sliding Window Reset: Deletes both the current and previous window keys.

Sources: fastlimit/limiter.py:339-364, tests/test_edge_cases.py:291-325

Implementation Summary

The RateLimiter.check_with_info method serves as the central router for these algorithms, ensuring that the correct logic is applied based on the requested algorithm.

# Selection Logic in limiter.py
if algorithm == "fixed_window":
    # bucket key logic
    result = await self.backend.check_fixed_window(...)
elif algorithm == "token_bucket":
    # persistent key logic
    result = await self.backend.check_token_bucket(...)
elif algorithm == "sliding_window":
    # multi-key weighted logic
    result = await self.backend.check_sliding_window(...)

Sources: fastlimit/limiter.py:179-233

Conclusion

FastLimit offers a versatile suite of algorithms to balance the needs of simple, low-overhead rate limiting against high-precision, smooth traffic requirements. For most standard web applications, Token Bucket is the recommended starting point due to its balance of UX and performance, while Sliding Window is reserved for scenarios requiring maximum accuracy and strict SLA compliance.