Rate Limiting • Fixed vs Sliding WindowEasy⏱️ ~2 min
Fixed Window Counter: Simple Time Bucketing for Rate Limiting
Fixed window counters group requests into discrete, nonoverlapping time bins aligned to clock boundaries. When a request arrives, you compute which bin it belongs to (typically floor(current_time / window_size)), increment a counter for that key (user, IP, or API token) in that bin, and check if the count exceeds your threshold. Each request belongs to exactly one window, and counters reset at window boundaries.
The implementation is beautifully simple: maintain one or two counters per key (current window and optionally the previous window for smoother boundary handling). Memory footprint is tiny: with 10 million active keys and 8 byte counters, you need only about 160 MB for two windows plus overhead. Updates are O(1), enforcement is instant, and there is no need to store individual timestamps.
The critical weakness is boundary exploitation. A client can send N requests at second 59 of minute 0 and another N requests at second 1 of minute 1. From the perspective of your fixed window, both batches are legal (each minute sees only N requests), but the server experiences 2N requests in 2 seconds, a burst that can overwhelm downstream systems. Reddit's public API uses approximately 60 requests per minute limits; clients hitting boundaries can effectively double their rate briefly.
This approach works well when simplicity and low overhead matter more than perfect burst control. Amazon API Gateway deliberately avoids pure fixed windows, using token buckets instead to control both steady rate and bursts. Fixed windows shine in billing, compliance reporting, and batch analytics where deterministic boundaries align with business logic and burst tolerance is acceptable.
💡 Key Takeaways
•Memory efficient with O(1) space per key per window. With 10 million keys and 8 byte counters, just 160 MB for two active windows compared to sliding log which needs gigabytes.
•Boundary spike vulnerability allows clients to send 2N requests in short bursts by splitting across window edges. A 100 req/min limit can become 200 req/sec at boundaries.
•Reddit API uses approximately 60 requests per minute which clients can game at boundaries. Amazon API Gateway avoids this by using token buckets instead of pure fixed windows.
•Update and enforcement operations are O(1) with no timestamp storage required. Simply compute window_id = floor(current_time / window_size) and increment counter[key][window_id].
•Ideal for billing, compliance, and batch reporting where deterministic cutoffs matter and business logic aligns with window boundaries. Poor choice when burst control is critical.
•Clock skew of even 100 milliseconds across distributed enforcers can cause double counting or dropped events at window transitions in multi node deployments.
📌 Examples
Production implementation: key = "user:12345", window_size = 60 seconds. At timestamp 1699123459 (second 59), window_id = floor(1699123459/60) = 28318724. Increment counter["user:12345"][28318724]. At timestamp 1699123460 (second 0 of next minute), window_id = 28318725, a new counter starts.
Reddit rate limiting: 60 requests per minute per OAuth client. Client sends 60 requests at 00:00:59.5 (all counted in window 0), then 60 more at 00:01:00.5 (all counted in window 1). Server sees 120 requests in 1 second but both windows show 60, within limits.
Memory calculation: 10 million active users, 2 windows (current and previous), 8 bytes per counter, 8 bytes per key hash. Total: 10,000,000 × 2 × 16 bytes = 320 MB plus hash table overhead (typically 1.5 to 2 times for 480 to 640 MB).