Stage 2: Fixed Window Counter

Objective:Implement the simplest production-viable rate limiter and understand its boundary-burst flaw — the tradeoff every team accepts when they choose it for its O(1) Redis footprint.

A fixed window counter divides time into discrete windows (e.g., each minute, each hour) and counts requests per window. When the count exceeds the limit, reject requests until the next window starts.

The boundary burst problem: A window resets at T=0:00. A client sends limit requests at T=59s (just before reset) and another limit requests at T=0:01 (just after reset). In 2 seconds, they sent 2 × limit requests while technically never exceeding the per-minute limit. This is why sliding window algorithms exist — but fixed window is still used because the exploit requires precise timing and the simplicity wins.

Redis implementation (for context):

INCR rate:{user_id}:{window_start}
EXPIRE rate:{user_id}:{window_start} {window_size_seconds}

One key per user per window. The key auto-expires. O(1) storage per user.

---

Implement create_fixed_window(limit, window_seconds) returning:

• allow(user_id, current_time) — return True if the request is within the limit for the current window, False otherwise. current_time is a Unix timestamp (float), injected for deterministic testing.
• reset_at(user_id, current_time) — return the Unix timestamp when the current window resets (the start of the NEXT window).

Why this matters in production

Redis's rate limiter (INCR + EXPIRE), GitHub's basic API rate limits, and most per-minute/per-hour quota systems use fixed window. It's the default because it's dead simple: one Redis key per user per window. The boundary burst problem is real but accepted because bursts of 2× the limit for a few seconds rarely matter for API abuse prevention.