Developer/RateLimiting/SlidingWindow/Fundamentals/sliding-window-rate-limiting

Sliding Window Rate Limiting: Log vs. Counter, and Cloudflare's Weighting Formula

Concept

Sliding window exists to fix fixed window's specific, well-known flaw — the boundary-burst problem, where a client can send up to 2x the nominal limit by timing requests around a window edge (see Fixed Window Counter for the exact mechanics). Sliding window fixes it by evaluating the limit against a window that moves continuously with the current time instead of resetting at fixed boundaries — but "sliding window" actually names two different implementations with very different cost profiles.

Sliding Window Log — store a timestamp for every request (typically in a Redis sorted set, scored by timestamp). On each new request: remove all timestamps older than now - window_size, count what's left, allow the request if the count is under the limit, and add the new timestamp. This is exact — no approximation, no boundary artifact at all — but the storage cost is O(requests) per client per window, not O(1). A client sending thousands of requests inside the window means thousands of stored timestamps, all of which have to be pruned on every subsequent check.

Sliding Window Counter — the approximation almost every production system actually ships, because it gets very close to the log's accuracy at fixed-window's O(1) memory cost. It keeps exactly two counters per client: the current fixed window's count and the previous fixed window's count. The estimated request count in the trailing window is computed by weighting the previous window's count by how much of it still falls inside the current trailing window:

estimated = current_window_count + previous_window_count × (1 − elapsed_fraction_of_current_window)

Cloudflare's published analysis of this exact formula, run across 400 million real requests from 270,000 sources, measured a 0.003% total error rate against exact sliding-window-log accounting, with zero false positives — the approximation is close enough in practice that the memory savings (roughly two integers plus a window-start timestamp per client, on the order of 24 bytes, versus a full timestamp log that can run into kilobytes per active client) are essentially free.

Tradeoffs

Implementation	Memory per client	Precision	Where the cost actually goes
Fixed Window Counter	O(1) — one counter	Poor (2x boundary burst)	Cheapest, but the boundary flaw is real and easily triggered
Sliding Window Log	O(requests in window)	Exact	Storage and pruning cost scale with request volume, not with client count — the expensive case is exactly the high-traffic clients a rate limiter most needs to handle cheaply
Sliding Window Counter (weighted approximation)	O(1) — two counters + timestamp	~99.997% accurate in Cloudflare's measured data	Small, bounded approximation error in exchange for fixed-window-like memory cost
Token Bucket	O(1)	Good, burst-aware by design	Different tradeoff axis entirely — see Token Bucket

The sliding window counter's approximation error isn't random noise — it comes specifically from assuming requests are evenly distributed across the previous window, which is usually a reasonable assumption for typical traffic but can be measurably wrong for a client whose requests all cluster at one edge of the previous window rather than spreading across it. Cloudflare's own writeup is explicit that this is a known, bounded source of error, not a hidden flaw.

When to use / when not to

Default to the sliding window counter approximation for any abuse-sensitive endpoint where fixed window's boundary burst is a real, exploitable gap but a full request log is too expensive to maintain per client at scale — this is the practical middle ground almost every production rate limiter converges on.
Reach for the exact sliding window log only when precision genuinely matters more than memory cost and request volume per client is bounded and low — e.g., a strict per-minute limit on a low-frequency, high-stakes action (password reset requests, payment retries) where a handful of timestamps per client is cheap and the exactness is worth it.
Don't default to sliding window log for high-request-volume endpoints — the per-request timestamp storage becomes the bottleneck the rate limiter itself exists to protect the system from, the same failure mode called out in Rate Limiting Algorithms's common pitfall.
If burst tolerance for idle-then-active clients matters more than precise boundary enforcement, token bucket is usually the better fit than either sliding window variant — sliding window's goal is accurate rate enforcement, not rewarding burstiness.

Common pitfall

Implementing "sliding window" by literally sliding a fixed-size log and never checking what that costs at real traffic volume — teams sometimes reach for the log variant because it's the more intuitive one to reason about (it's just "count requests in the last N seconds," no weighting formula to get right), without noticing that a client making dozens of requests per second turns "prune and count timestamps" into real per-request latency and memory pressure. The counter variant requires understanding and correctly implementing the weighting formula, which is a genuine extra step, but it's the one that actually survives production traffic volume — reaching for the simpler-to-understand log implementation by default, then discovering the cost only under load, is the recurring mistake.

Engineering Lens

Cloudflare publishing the actual measured error rate of their approximation (0.003% across 400M real requests) rather than just asserting "close enough" is the more transferable lesson here: any time a system trades exactness for a cheaper approximation, the strong design-review answer is showing the approximation was measured against the exact version at realistic scale, not just argued to be reasonable. The same pattern shows up anywhere a system swaps an exact-but-expensive data structure for a compact approximation — HyperLogLog for cardinality estimation, Bloom filters for set membership, or this weighted-counter approximation for a sliding window. The interesting engineering judgment isn't "we chose the cheap approximation," it's knowing exactly how wrong it can be and confirming that bound holds under real traffic, not synthetic benchmarks.