Part 4 of 7 · 4 min read
Window counters and logs
Counting requests in time windows, the boundary problem, and two cures.
Think of a gym that allows 100 visits an hour. The simplest way to count is to reset a clicker on every hour. The weakness is at the hour boundary: 100 people can enter at 10:59 and another 100 at 11:01.
The book calls this the fixed window counter.
Fixed window counter
A fixed window counter divides time into equal windows, keeps one counter for each window, and refuses requests once the counter reaches the limit. The counter resets at the start of each window.
Example: a limit of 5 per minute. The counter resets at every whole minute.
It is memory-light and easy to understand. The flaw is the edge of the windows. The book shows 5 requests allowed per minute, with 5 requests just before 2:01:00 and 5 just after. Between 2:00:30 and 2:01:30, 10 requests go through, twice the limit.
A worked example. Limit 100 per minute. A client sends 100 requests at 12:00:50 and 100 more at 12:01:10.
- Each minute has 100 requests, so both windows pass.
- In the 20 seconds from 12:00:50 to 12:01:10, 200 requests arrive. The service sees twice the intended rate.
The sliding window log removes the flaw.
Sliding window log
A sliding window log stores the time of each recent request. For a new request it drops times older than the window, then accepts the request only if the number left is under the limit.
Example: limit 3 per minute. The log holds the times of the requests of the last 60 seconds.
A worked example. Limit 3 per 60 seconds.
| Time | Log before (after removing old) | Count with new | Result |
|---|---|---|---|
| 0:05 | empty | 1 | accept |
| 0:20 | 0:05 | 2 | accept |
| 0:41 | 0:05, 0:20 | 3 | accept |
| 0:50 | 0:05, 0:20, 0:41 | 4 | refuse |
| 1:10 | 0:05 is older than 60 seconds and is removed | 3 or 4, see the text | accept or refuse |
At 1:10 the window runs from 0:10 to 1:10. The entry 0:05 is removed. The entry 0:50 belonged to a refused request, but the book notes that a refused request's time may still be stored, which wastes memory. If refused times are kept, the log shows 0:20, 0:41, 0:50 and the count with the new one is 4, so the request is refused. If refused times are not stored, the log has 0:20 and 0:41, the count is 3, and the request is accepted. Both choices are possible. The choice should be written in the rule.
The log is exact in any rolling window, but it costs memory. Compare for 10 million users with a limit of 100 per minute, 8 bytes per time stamp (made up):
- Log: up to 100 × 8 = 800 bytes per user, 10,000,000 × 800 = 8,000,000,000 bytes = 8 GB.
- Fixed counter: one counter and one window start, about 16 bytes per user, 160 MB.
The third approach is a mix.
Sliding window counter
A sliding window counter keeps counts for the current and the previous window, and estimates the rolling count as: current count + previous count × the share of the previous window that still overlaps the rolling window.
Example: limit 10 per minute, previous minute 6 requests, current minute 4, and 40 percent of the current minute has passed. The overlap with the previous minute is 60 percent. Estimate: 4 + 6 × 0.6 = 7.6, rounded down to 7. A request is allowed.
The book's example uses the same formula. It is cheap in memory, smooths spikes and approximates the true rate by assuming that requests in the previous window were spread evenly. The book reports a test by Cloudflare: among 400 million requests, only 0.003 percent were wrongly allowed or limited.
| Algorithm | Memory | Accuracy | Notes |
|---|---|---|---|
| Fixed window counter | Very small | Poor at window edges | Simple |
| Sliding window log | Large | Exact | Stores timestamps |
| Sliding window counter | Small | Very close | Good default when bursts are not wanted |
| Token bucket | Small | Allows bursts | Popular |
| Leaky bucket | Small | Smooths output | Needs a queue |
Common mistake
Choosing the fixed window because it is simple and forgetting the edge. A client that learns the window can double its rate at each boundary. Use a sliding method when the limit protects something fragile.
Check yourself:
- What is the weak point of a fixed window counter?
- Why does a sliding window log cost more memory than a counter?