Sliding Window Log

The fixed window forgot when requests arrived, which let a client double its budget across a boundary. This lesson's gateway forgets nothing: it remembers the time of every allowed request, so "5 per minute" means 5 in any 60 seconds, measured back from this very instant.

The mechanism

For each client keep a log: the timestamps of its allowed requests, oldest first. On every request:

1. Evict from the front every timestamp that is no longer inside the window.
2. If the log still holds a full budget of entries, refuse.
3. Otherwise append the current time and allow.

The window is the half-open interval (now - W, now]. An entry made exactly W seconds ago is outside it, so a request made exactly W seconds after the oldest entry frees that slot. Write the comparison with the wrong strictness and the slot frees one instant late: invisible in casual testing, wrong on the exact-boundary request.

A worked trace with budget 2 and W = 10, different numbers from your exercise:

Refused requests never enter the log, so being blocked does not keep you blocked.

Headers that are exactly true

A sliding window has no fixed end, so the headers need a precise definition:

• Retry-After is when the oldest logged entry leaves the window: oldest + W - now, rounded up. Wait that long and a slot is guaranteed free.
• X-RateLimit-Reset is that same instant as an epoch timestamp, rounded up: the moment the oldest logged request leaves the window and a slot frees.
• X-RateLimit-Remaining is the budget minus the log length after this request.

The guarantee, and its price

At no moment do more than budget allowed requests fall inside any window-length interval. No boundary exists to exploit, which is what people mean by "100 per minute".

The price is memory: up to budget timestamps per client. A million clients at 1,000 per minute is a billion 8-byte floats, about 8 GB before any container overhead. In Redis the same idea is a sorted set per client: add the time, remove the old range by score, count what is left.

The compromise: the sliding window counter

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

estimate = previous_count * (W - seconds_into_current) / W + current_count

With W = 60, a budget of 100, 80 requests last minute and 30 so far this minute, 15 seconds in: 80 * 45/60 + 30 = 90, under budget, allow. At 45 seconds in: 80 * 15/60 + 30 = 50. It is O(1) memory with a smooth boundary, and it misleads only when the previous window was very lopsided. Cloudflare publicly describes running this approximation in production after measuring its error on real traffic.

The clock trap

Both versions trust now to move forward. Wall-clock time does not promise that: an NTP step backwards moves now - W backwards too, eviction stalls, and valid clients are refused. Measure intervals with a monotonic clock and keep wall-clock time only for display, such as X-RateLimit-Reset.

Common mistakes

• Logging refused requests. The log fills with entries that were never served and the block never ends.
• Evicting with the wrong strictness, so the request at exactly oldest + W is refused.
• Computing Retry-After from the window length instead of from the oldest live entry.

Your exercise

Replace the fixed counter with the log: 5 requests per client in any 60 seconds, with the three headers and Retry-After defined above.