Sliding Window Log

The fixed window's boundary burst happens because the counter forgets when requests arrived. The sliding window log forgets nothing: store the timestamp of every allowed request, and admit a new one only if fewer than limit timestamps fall inside the last window seconds — measured from this instant, not from an aligned boundary.

The eviction predicate defines the window precisely: log[0] <= now - window drops anything at or older than now − window, so the live interval is (now − window, now] — half-open. A request made exactly window seconds after an old one frees that old slot. Note also that denied requests are never appended: being blocked doesn't keep you blocked.

The guarantee: at no moment do more than limit allowed requests fall within any window-length interval. No boundaries, no 2× trick — this is what everyone actually means by "100 per minute."

The cost: memory. Each client holds up to limit timestamps. A million clients with a 1,000/min limit is up to 10⁹ timestamps — about 8 GB of raw 8-byte floats before any container overhead. In Redis this pattern is a sorted set per client (ZADD the timestamp, ZREMRANGEBYSCORE to evict, ZCARD to count): precise, but heavyweight at scale.

The compromise: sliding window counter

Keep only two numbers per client — the current and previous fixed-window counts — and estimate the sliding count by assuming the previous window's requests were spread evenly:

Worked example with window=60, limit=100: the previous minute had 80 requests, the current minute has 30, and we're 15 s in. Overlap weight = (60 − 15) / 60 = 0.75, estimate = 80 × 0.75 + 30 = 90 → under 100, allow. At 45 s in, the same counts give 80 × 0.25 + 30 = 50. O(1) memory, smooth boundary behavior; the estimate only misleads when the previous window's traffic was very lopsided, and it degrades gracefully. Cloudflare chose exactly this algorithm for their rate limiting product after measuring the approximation's error as negligible on production traffic. (Stripe, by contrast, runs token buckets — next lesson.)

The trap: clocks. Both versions trust now to move forward. Wall-clock time doesn't promise that — NTP can step the clock backwards, and then now − window moves backwards too: eviction stalls and valid clients get denied. Measure intervals with a monotonic clock (time.monotonic() in Python) and keep wall-clock time only for reporting things like X-RateLimit-Reset. The second trap is the eviction comparison: write < instead of <= and a slot frees one instant later than the definition says — invisible in casual testing, visible in the trace below.

Your exercise

Implement SlidingWindowLog, then run one client through limit=2, window=10, requests at t = 0, 5, 9, 10, 14, 15. Exact verdicts:

ALLOW ALLOW DENY ALLOW DENY ALLOW

The checks that catch real bugs: t=10 must be ALLOW — the t=0 entry expires exactly then, which is your <= at work — and t=14 must be DENY, because t=5 is still live (14 − 10 = 4 < 5). If t=10 or t=15 comes back DENY, either your eviction uses < or you're appending denied requests to the log.