Sliding Window vs Fixed Window Rate Limiting
Compare sliding window and fixed window rate limiting algorithms. Learn about the boundary burst problem and how sliding window counters solve it.
Detailed Explanation
Sliding Window vs Fixed Window Rate Limiting
The choice between sliding window and fixed window algorithms affects how your rate limiter handles traffic at window boundaries.
Fixed Window
The fixed window algorithm divides time into fixed intervals and counts requests within each interval.
Window 1: 12:00:00 - 12:00:59 → max 100 requests
Window 2: 12:01:00 - 12:01:59 → max 100 requests
The Boundary Problem:
A client can send 100 requests at 12:00:59 and another 100 at 12:01:00, effectively making 200 requests in 2 seconds while technically never exceeding the limit.
Sliding Window Log
The sliding window log algorithm tracks every request timestamp and counts requests within a rolling window.
At 12:01:30, count all requests from 12:00:30 to 12:01:30
Pros: Perfect accuracy, no boundary bursts Cons: O(n) memory per user (stores every timestamp)
Sliding Window Counter
The sliding window counter is a compromise. It uses two fixed windows and calculates a weighted count:
Estimated count = (Previous window count x overlap %) + Current window count
Example at 12:01:15 (25% into current window):
= (Previous window: 80 x 0.75) + (Current window: 30)
= 60 + 30 = 90 (under limit of 100)
Algorithm Comparison
| Feature | Fixed Window | Sliding Log | Sliding Counter |
|---|---|---|---|
| Accuracy | Low (2x burst) | Perfect | High (~98%) |
| Memory | O(1) | O(n) | O(1) |
| Complexity | Low | High | Medium |
| Best for | Simple APIs | Security-critical | Most APIs |
Use Case
You are implementing a rate limiter for a REST API used by mobile apps. You need to choose between fixed window and sliding window approaches, considering that your infrastructure uses Redis for state management and you have 100,000 concurrent users.