STANDARDwalkthrough
Sliding Window Counter
The constraint: sliding window log gives us exact counts but costs 12 KB per user. Fixed window counter uses one key per user but has a boundary burst flaw.
The sliding window counter is a hybrid: we keep a count for the current fixed window and the previous fixed window, then weight them based on how far into the current window we are. If the previous window allowed 100 requests and had 84 hits, and we are 30% into the current window, the estimated count is (84 x 0.7) + current window count.
“We need something in between.”
This weighted formula uses only two counters per user instead of hundreds of timestamps. Implication: memory drops from 12 KB (sliding window log) to roughly 48 bytes per user, an 86% reduction at the same request volume.
We chose sliding window counter (not sliding window log) because Cloudflare's engineering team measured the error rate of this approximation and found it stays below 0.003% for typical API traffic patterns. Real traffic rarely clusters exactly at window boundaries, which is the only case where the approximation diverges.
Trade-off: we gave up mathematical exactness for a 250x memory reduction. GitHub uses this approach for their REST API rate limiting (5,000 requests per hour for authenticated users). Two Redis keys per user, two INCR operations per request, and a single TTL handles cleanup automatically.
No sorted sets, no timestamp storage, no ZRANGEBYSCORE scans. What if the interviewer asks: 'When does the 0.003% error matter?' It matters when we are rate-limiting financial transactions where even one extra request could cause a duplicate charge.
For those endpoints, we fall back to sliding window log.
Formula & tradeoffs
Formula
Related concepts