Sliding Log: Exact Timestamps for Precise Counting

When You Need Perfect Accuracy
Sliding counters approximate. What if you need exact counts for billing, compliance, or security audits? Store every individual request timestamp. This is the sliding log approach: instead of counting, maintain a complete record and count matching timestamps on each request. The trade-off is significantly higher memory usage for guaranteed precision.
How Sliding Log Works
For each user, maintain a list of timestamps for all requests. When a new request arrives: (1) remove timestamps older than your window (e.g., 60 seconds), (2) count remaining, (3) if under limit, add current timestamp and allow, (4) if at or over limit, reject with 429. Use Redis sorted sets with timestamps as scores: ZREMRANGEBYSCORE key 0 (now - window), ZCARD key, ZADD key now now.
Memory Implications
If a user is allowed 1,000 requests/minute and each timestamp is 8 bytes, that is 8 KB per user at peak. With 100,000 active users, that is 800 MB for rate limiting state. Compare to sliding counter at 16 bytes per user. Sliding log uses 500x more memory. This is why sliding log is reserved for high value use cases where accuracy justifies the cost.
Processing Cost
Each request requires O(k) time where k is requests in the window. With Redis sorted sets, cleanup is O(log n + m) where m is entries removed, counting is O(log n). Still fast but more expensive than O(1) counter increment. For very high rate limits (10,000+/sec), this overhead is significant.
When to Use Sliding Log
Use sliding log when: exact counts are required for billing or compliance, rate limits are low enough that memory is acceptable, audit trail of individual requests is valuable, or you need to answer questions like "show me all requests in the last hour." For most API rate limiting where approximate fairness is the goal, sliding window counter is more practical.

💡 Key Takeaways

✓Memory is O(rate times window_size) per key. At 1,000 req/sec over 60 seconds, 60,000 timestamps at 8 bytes each equals 480 KB per key. Compare to 120 bytes for bucketed sliding counter with 60 buckets.

✓Perfect accuracy with zero approximation error. Every request is counted exactly within the rolling window, eliminating boundary spikes and bucket granularity issues.

✓Practical only for low rate scenarios like authentication (10 login attempts per 10 minutes per user). With 100,000 active login sessions, 10 timestamps times 8 bytes times 100,000 equals 8 MB, manageable.

✓Eviction cost is O(expired_count) per request. Under uniform traffic this amortizes well, but bursty traffic causes spikes. Use sorted sets or deques with efficient range deletion.

✓Distributed deployment requires either centralized state (single point of failure, added latency) or complex log replication and merging. Most production systems avoid this by using approximations.

✓High cardinality keys cause state explosion. A credential stuffing attack with 1 million attempted usernames times 10 failed attempts times 8 bytes equals 80 MB. Sustainable, but scaling to millions of req/sec is not feasible.

📌 Interview Tips

1Authentication rate limiting: allow 5 failed login attempts per 300 seconds per username. Store timestamps [1699100105, 1699100147, 1699100203, 1699100298, 1699100310] for user alice. At t=1699100400, evict timestamps < 1699100100 (none in this case after initial eviction), count = 5, deny next attempt.

2Redis sorted set implementation: ZADD ratelimit:alice 1699100105 req1, ZADD ratelimit:alice 1699100147 req2, etc. On new request at t: ZREMRANGEBYSCORE ratelimit:alice 0 (t - 300). Then ZCARD ratelimit:alice. If count < 5, ZADD and allow; else deny.

3Memory explosion at scale: API key with 10,000 req/sec, 5 minute window. 10,000 × 300 = 3,000,000 timestamps × 8 bytes = 24 MB per key. With 1,000 hot keys, 24 GB just for rate limit state, plus Redis overhead pushes past 50 GB.

← Back to Fixed vs Sliding Window Overview