Fixed Window Boundary Burst
An internal team implements a "100 requests per minute per API key"
limiter using a fixed window: key = f"{api_key}:{floor(now/60)}",
INCR the key, allow if the result is <= 100.
A client sends 100 requests at 08:59:58–08:59:59 and another 100 at 09:00:01–09:00:02.
- How many requests does the limiter allow in that 4-second span, and why?
- Redesign the check using the sliding window counter algorithm and show the estimate calculation for a request arriving at 09:00:02 (2 seconds into the new window), given the previous window ended with 100 requests and the current window has 5 so far.
- Would a sliding window log have been a better fix here? What would it cost?
1. What the fixed window allows
The first 100 requests fall in window 08:59 (count reaches 100,
still <= 100, all allowed). The next 100 fall in window 09:00 (a
fresh counter starting at 0, count reaches 100, all allowed again).
The limiter allows all 200 requests in a 4-second span, because
each request is only ever checked against the count within its own
60-second bucket — the algorithm has no memory of the previous
window. This is the classic boundary burst: up to 2× the intended
limit across any span that straddles a window edge.
2. Sliding window counter fix
With prev = 100, curr = 5, t_elapsed = 2s, W = 60s:
101.67 > 100 → DENY. The weighted estimate correctly treats most of the previous window's 100 requests as still "recent" this early into the new window, so the client is held back instead of being handed a fresh 100-request allowance the instant the clock ticks over.
3. Sliding window log comparison
A sliding window log (store every request timestamp, count those
within the trailing 60 s) would fix this exactly, with zero
approximation error — it would allow at most 100 requests in any
rolling 60-second span, full stop. The cost is memory: up to 100
timestamps per key (roughly 800 bytes at 8 bytes each) instead of two
integers, and a ZREMRANGEBYSCORE + ZCARD + ZADD round trip
instead of a single INCR. For a single API-key-scoped limit like
this (bounded at 100), the log is affordable and gives exactness; the
counter is preferred once limits or key cardinality get large enough
that O(limit) memory per key becomes real cost. Either is a legitimate
fix — the fixed window as implemented is not.
Share this question