Bridge WAF
Rate limiting algorithms: four ways to count requests
Four algorithms cover nearly every limit in use, and they allow the same average traffic while behaving completely differently at the edges. The choice between them does not decide how much a client may send. It decides what shape of sending is allowed, which is what ordinary clients notice.
What the algorithm decides
Not the number, but the meaning of «too often».
Every limit has a rate and a period. What the algorithm adds is the answer to what happens when requests arrive unevenly, which they always do: whether a client may spend its whole allowance at once, whether a quiet hour earns anything, and what happens at the moment a period ends. Those edges are where real clients live, and they are the reason two limits with identical numbers can produce completely different complaints.
A browser loading a page requests many things at once and then nothing for a minute. An API client syncing on start does the same in a shorter span. A scheduled job does all of its work in one stretch and sleeps for a day. None of those is misbehaving, and every one of them looks like a spike to a counter that expects an even flow.
Fixed window
The simplest to implement and the easiest to get surprised by.
on request(key):
now_window = floor(current_time / WINDOW)
if counter[key].window != now_window:
counter[key] = { window: now_window, count: 0 }
counter[key].count += 1
return counter[key].count <= LIMITOne counter per client per period, reset when the period rolls over. Cheap in memory and trivial to reason about.
Its failure is at the seam. A client that spends its whole allowance at the end of one window and its whole allowance at the start of the next has sent twice the limit across a span shorter than a single window, entirely within the rules. Whether that matters depends on what the limit protects: for fairness it is a nuisance, for capacity it can be the exact event you were trying to prevent.
Sliding window
The fix for the seam, in two versions with very different costs.
The log version keeps the timestamp of every request and counts those inside the trailing period. Exact, and it pays for that in storage proportional to the traffic it allows.
The counter version keeps the current and previous window counts and weights the previous one by how much of it still lies inside the trailing period:
on request(key):
w = floor(current_time / WINDOW)
position = (current_time mod WINDOW) / WINDOW
estimate = previous[key] * (1 - position) + current[key]
if estimate < LIMIT:
current[key] += 1
return allow
return refuseApproximate, and cheap enough to run at any scale. It assumes traffic was spread evenly inside the previous window, which is wrong in detail and close enough in aggregate for almost every purpose a limit serves.
Token bucket
The one that matches how ordinary clients behave.
on request(key):
refill(key) # add REFILL_RATE * elapsed, cap at CAPACITY
if bucket[key].tokens >= 1:
bucket[key].tokens -= 1
return allow
return refuseTokens accumulate at a steady rate up to a ceiling; each request spends one. A client that has been quiet has a full bucket and may send a burst; a client that has been busy is held to the refill rate. That is close to a description of a normal application: idle, then a flurry when somebody opens a page, then idle again, which is why this shape produces the fewest complaints from legitimate traffic. The subject is covered further under bursts.
It also gives you two dials with distinct meanings: the capacity is how big a burst you tolerate, and the refill rate is the sustained rate you are willing to serve. Being able to state those separately is most of the value.
Leaky bucket
The same picture from the other side: instead of controlling what is admitted, control what leaves.
on request(key):
if queue[key].length >= CAPACITY:
return refuse
queue[key].append(request) # drained at a constant RATE
on tick:
for key in queue:
release up to RATE * elapsed requestsOutput is smoothed to a constant rate regardless of how arrivals bunch up. Where the queue is genuinely queued rather than dropped, the client experiences delay instead of refusal, which is gentler but hides the limit and can turn a burst into a growing wait nobody chose.
Side by side
| Algorithm | Memory | Burst allowed | Seam problem | Client experiences |
|---|---|---|---|---|
| Fixed window | Lowest | Full allowance instantly | Yes, up to double at the boundary | Sudden refusal, then a clean slate |
| Sliding log | Highest, grows with traffic | Full allowance instantly | No | Refusal that eases gradually |
| Sliding counter | Low | Full allowance instantly | Largely removed | Same, approximated |
| Token bucket | Low | Up to CAPACITY after idle | No | Burst tolerated, then steady |
| Leaky bucket | Low, plus the queue | None, arrivals are smoothed | No | Delay rather than refusal |
Choosing one
Start from what you are protecting.
If you are protecting capacity, something behind you that falls over at a certain rate, a leaky bucket or a token bucket with a modest capacity matches the problem, because both describe an outflow you can sustain.
If you are protecting fairness, ensuring no single client can consume a shared resource, a sliding counter is usually the honest choice, since it prevents the boundary trick without pretending to more precision than it has.
If you are protecting an interface used by ordinary applications, a token bucket almost always produces the fewest false alarms, because its shape matches the shape of legitimate traffic rather than fighting it.
Whichever you pick, check it against traffic you already have rather than against an idea of traffic. Take a period from your own records, replay the arrival pattern of your busiest legitimate client against the algorithm on paper, and see whether it would have been refused. That exercise costs an afternoon and settles arguments that otherwise run until somebody's customer complains, and it usually reveals that the number was never the problem.
What none of them fixes
Three things the algorithm cannot decide for you.
Who is counted. Every algorithm above counts against a key, and choosing that key is a separate decision with larger consequences, set out under per-IP versus per-user.
What a request costs. All four treat requests as equal. Where a cheap read and an expensive search are counted the same, the limit is measuring the wrong thing whichever algorithm computes it.
What the client is told. The algorithm decides the refusal; how it is communicated decides what the client does next, which is the subject of 429.
Questions
Which algorithm should I use?
Token bucket for interfaces used by ordinary applications, since it tolerates the bursts real clients produce while holding the sustained rate. Sliding counter when fairness between clients matters most. Leaky bucket when you are protecting something downstream that needs a genuinely constant rate.
Why does the fixed window let clients exceed the limit?
Because its counter resets at a fixed moment. A client can spend its full allowance just before the reset and again just after, sending twice the limit across a span shorter than one window without breaking any rule the algorithm enforces.
Is the sliding counter accurate enough?
For almost every purpose, yes. It assumes the previous window's traffic was spread evenly, which is wrong in detail and close in aggregate, and it costs a fraction of what an exact log costs. Use the log only where exactness has a concrete consequence.
Does the algorithm choice matter more than the number?
They matter differently. The number sets how much a client may send; the algorithm sets what shape of sending is allowed. Ordinary clients are bursty, so a poorly chosen algorithm refuses them at a number that would otherwise have been generous.