Sliding window algorithms

The fixed window's boundary burst comes from dividing time into blocks. A request lands in one block or another, and a stretch of clock crossing the join can carry twice the limit.

Stop using blocks and the problem disappears. Both algorithms here measure against a window that ends at the request being decided, and they differ only in how much they remember.

Sliding window log

Keep a timestamp for every accepted request. When a new one arrives, look back one window length, count what's in there, and decide.

The window is calculated fresh each time, so it slides along behind every request. Same car park, thirty-second window, limit of five:

Time	Arrives	Window looks back to	Count in window	Outcome
0s	1	0s	0	Accepted
5s	2	0s	1	Both accepted, count now 3
15s	2	0s	3	Both accepted, count now 5
25s	1	0s	5	Rejected, at the limit
35s	1	5s	4	Accepted, the 0s request has aged out
40s	3	10s	3	Two accepted, the third rejected

At 35 seconds the window starts at 5, so the request from 0 falls outside it and no longer counts. That ageing-out is the whole mechanism: capacity returns gradually as old requests leave, rather than all at once on a reset.

No stretch of thirty seconds ever contains more than five requests. That's the guarantee a fixed window cannot make.

JunoSliding window log The difference from a fixed window is where the window's edge is. A fixed window's edge sits on the clock, in the same place for everyone.

Here the edge sits behind the request being decided, so it moves every time. Nobody gets a reset, and nobody has to wait for one either.

JunoSliding window log This also fixes the drought. A client who spends their whole budget at once gets capacity back one request at a time as each ages out, instead of waiting for a block to end.

That's much closer to what people expect a rate limit to feel like, and it's why the accuracy is worth paying for on endpoints where refusing a legitimate client is expensive.

JunoSliding window log What you pay is memory proportional to the limit, per client. A limit of 5 stores five timestamps; a limit of 10,000 stores ten thousand, for every client, and the old entries need pruning or the list grows without end.

In Redis this is usually a sorted set per client keyed by timestamp, with the expired range trimmed on each request.

That's several operations where a fixed window is one atomic increment, and it still has to be atomic, or concurrent requests each read a count that is already stale.

At small limits it's cheap and clearly correct. At large ones it's the algorithm that makes your rate limiter the expensive part of the request.

Sliding window counter

The log's cost is the list of timestamps. The counter gets most of the accuracy for two integers.

Go back to fixed windows, keep a count for the current one and the previous one, then weight the previous count by how much of it still falls inside a sliding look-back:

x        = how far into the current window we are, as a fraction
weighted = (1 - x) * previousCount + currentCount

accept if weighted + 1 <= limit

With a thirty-second window, a limit of 5, and a previous window that filled up completely:

Time	Into window	1 - x	Weighted	Plus this request	Outcome
35s	5s, so 1/6	5/6	5/6 × 5 + 0 = 4.17	5.17	Rejected, over 5
40s	10s, so 1/3	2/3	2/3 × 5 + 0 = 3.33	4.33	Accepted
40s again	10s, so 1/3	2/3	2/3 × 5 + 1 = 4.33	5.33	Rejected

The (1 - x) * previousCount term is the estimate: as the current window fills, less of the previous one remains in view, so its contribution fades out smoothly.

Two counters per client, and no timestamps at all.

JunoSliding window counter The formula is doing something simple. Early in a window, most of the previous window still counts against you. Later, less of it does.

Rather than checking which specific requests are still in range, it assumes they were spread evenly and takes a fraction. Cheaper, and nearly right.

JunoSliding window counter Notice the third row. Two requests at the same instant get different answers, because the first one accepted increments currentCount and the second is measured against the new total.

Which is correct, and worth knowing when you're testing: firing requests in a tight loop gives results that depend on how many were already accepted this millisecond.

JunoSliding window counter The approximation is good enough to run at internet scale. Cloudflare published figures from 400 million requests across 270,000 sources: 0.003% were allowed or limited differently from an exact count, with no false positives.

Three sources slightly over the threshold were let through, and the average gap between the real rate and the approximation was 6%.

For that error you get two integers per client instead of a list, which is the trade that makes it the common production choice.

Measured against a fixed window's 200 across a boundary, the log allows exactly 100 and the counter 101. The counter's one extra request is the approximation showing up, and it is not the thing that will hurt you.

Where they disagree

The counter assumes the previous window's requests were evenly spread. They rarely are, and which algorithm is more lenient depends on where they actually clustered.

Requests near the start of the previous window. The log looks back a real thirty seconds, sees those early requests fall outside it, and allows more. The counter still charges a fraction of them, so it refuses.

The log is more lenient here, because the counter is treating capacity as more constrained than it is.

Requests near the end of the previous window. Now the log still has them in view and refuses, while the counter has faded most of the previous count away. Here the counter is more lenient, because it is underestimating how recent that traffic was.

So the error goes both ways, which is what makes it acceptable. It is not a systematic bias in favour of clients or the server.

JunoWhere they disagree The counter is not keeping track of when anything happened. It only knows how many, and it guesses at when.

Sometimes that guess is generous and sometimes it is strict, and which one depends entirely on when the requests really arrived.

JunoWhere they disagree Worth knowing the direction of the error when you pick. On an endpoint where letting slightly too much through is dangerous, the counter's leniency against end-loaded traffic is the case to think about.

On one where refusing a legitimate client is expensive, its strictness against front-loaded traffic is the one that will generate support tickets.

JunoWhere they disagree Both are exploitable in principle by shaping traffic to the window, and the counter more so, since its blind spot is predictable: bunch requests at the end of a window and the next window's estimate underweights them.

In practice this needs the attacker to know your window length and boundary alignment, which is inferable but effortful, and the payoff is a handful of extra requests. Not worth defending against directly.

Worth defending against by not relying on any single limiter. A per-second limit alongside a per-minute one closes most window-shaping games, because a burst engineered against one window is still a burst against the other.

Try it

A thirty-second window, a limit of 5, and a previous window that accepted 5 requests. No requests yet in the current window.

1. Using the counter, is a request at 33 seconds accepted?
2. At what point in the current window does the first request become acceptable?
3. Same traffic, but the previous window's 5 requests all arrived in its first second. Which algorithm allows the request at 33 seconds, and why?

Compare your answers

1. Rejected. At 33 seconds you're 3 seconds into a 30 second window, so x is 1/10. The weighted count is 0.9 × 5 + 0 = 4.5, and adding this request gives 5.5, over the limit of 5.

2. At 36 seconds. You need (1 - x) × 5 + 1 <= 5, so (1 - x) × 5 <= 4, so 1 - x <= 0.8 and x >= 0.2. A fifth of a thirty-second window is 6 seconds, putting the first acceptable request at 36 seconds.

3. The log allows it; the counter still refuses. The log looks back to 3 seconds. All five previous requests arrived before that, so they've aged out and the count is 0.

The counter has no idea when they arrived, assumes an even spread, and still charges 4.5 against them. That's the approximation's cost made concrete: the client sent nothing at all in the last thirty seconds and is refused anyway.

Where this goes next

Both algorithms enforce an average, and both treat a burst as something to prevent. Plenty of traffic is legitimately bursty, though: a page loading six resources at once is not abuse.

Token bucket takes the opposite view, allowing a burst on purpose and then making the client wait to earn another one.