Fixed Window Counter

The simplest real limiter: chop time into fixed, aligned windows — [0,10), [10,20), [20,30) for a 10-second window — keep one counter per client for the current window, and reset it when a new window begins.

Two details carry all the weight:

• (now // self.window) * self.window floors the timestamp to its window's start, so every client shares the same aligned boundaries — with window=3600, everyone's counter turns over exactly on the hour.
• Denied requests are not counted (the return False fires before the increment), so hammering while blocked doesn't extend the block. Some systems deliberately do count denials, to punish probing — that's a policy choice; make it consciously.

Why people use it: O(1) time and O(1) memory per client — one count plus one window start, and old windows are simply overwritten. It's the natural fit for calendar-aligned quotas: "10,000 requests per day" resets at midnight, and GitHub's REST API gives you 5,000 requests per hour with the reset instant published in X-RateLimit-Reset — a fixed window running in production. It also maps onto a single Redis INCR, which is exactly what the Distributed lesson builds.

The flaw: boundary bursts. The counter forgets everything at the boundary, so a client can spend a full budget at the very end of one window and another full budget at the very start of the next. Concretely, with limit=3, window=10, a fresh client sending at t = 9, 9, 9, 10, 10, 10 gets six ALLOWs in about one second — the reset at t=10 (win=10 > 0) wipes the count mid-burst. Worst case, a client achieves 2× the intended rate across any boundary. The next lesson exists to fix precisely this.

A second, sneakier effect: synchronized resets. Because windows are aligned for everyone, every blocked client's quota returns at the same instant. Clients that poll until unblocked all fire in the same second — a self-inflicted stampede every hour, on the hour. Real APIs soften this with jitter or by preferring token buckets.

Your exercise

Implement FixedWindow exactly as above, then verify it against this trace: limit=3, window=10, one client, requests at t = 0, 4, 9, 9, 10, 10, 11, 11. Your verdicts must be exactly:

ALLOW ALLOW ALLOW DENY ALLOW ALLOW ALLOW DENY

The two classic implementation mistakes both surface in this trace: an off-by-one in the limit check (> instead of >= after incrementing first) lets a fourth request through at t=9; forgetting the window reset makes the t=10 request come back DENY. Once the trace is exact, reproduce the boundary burst yourself — t = 9, 9, 9, 10, 10, 10 must produce six ALLOWs. That's the flaw the sliding window fixes next.