Rate Limiting: The Algorithm Is the Easy Part
Everyone compares token bucket to sliding window and stops there. The decisions that actually determine whether a rate limiter works are what you key it on, whether your Retry-After header is quietly scheduling a thundering herd, and whether a client that gets a 429 can safely retry at all.
Key takeaways
- A fixed-window counter resets at hard boundaries, so a client can spend its full allowance at the end of one window and again at the start of the next, permitting up to double the intended rate across the boundary.
- A token bucket refills at a steady rate up to a maximum capacity, so it absorbs short bursts while still enforcing the long-run average, which is why it suits user-facing traffic better than a strict window.
- A sliding window always reflects the trailing N seconds rather than resetting abruptly, giving better accuracy at the cost of more bookkeeping per request.
- What you key the limit on matters more than the algorithm, because keying on IP address collapses every user behind a corporate NAT or mobile carrier gateway into one bucket while doing nothing to stop a distributed caller.
- A Retry-After header with no jitter tells every blocked client to return at the same instant, which converts one overload into a synchronised second one.
- Rate limiting is only safe to retry against if the endpoint is idempotent, because a client rejected or timed out mid-write cannot tell whether the write happened.
Search for how to build a rate limiter and you get the same three algorithms every time: fixed window, sliding window, token bucket. That comparison is real and it is below, with the one genuine gotcha in it.
It is also the easy part. I have seen rate limiters with a textbook token bucket that failed completely in production, and the reason was never the algorithm. It was what the limit was keyed on, or what the response told clients to do next.
The Three Algorithms, and the Gotcha
Fixed window. Count requests per calendar interval, reset on the boundary. Trivial to implement and it has one specific flaw worth knowing: because the counter resets abruptly, a client can spend its entire allowance in the last moment of one window and its entire allowance again immediately after the reset. Across that boundary it just sent double the rate you configured.[1]
If you picked the number because it is what your database can take, a limiter that permits twice it at every boundary is not doing the job you hired it for.
Sliding window. Instead of resetting, the window moves continuously, so the count always reflects the trailing N seconds.[1]Accurate, and no boundary effect. You pay in bookkeeping: you are tracking timestamps rather than incrementing one integer.
Token bucket. A bucket holds up to some maximum number of tokens and refills at a steady rate. Each request spends one; an empty bucket means rejection.[1] The reserve is the point: it absorbs a short burst while still enforcing the long-run average.
That last property is why token bucket usually wins for user-facing traffic. Real usage is bursty. Someone opens your app and it fires fourteen requests to paint one screen. A strict window rejects the fourteenth; a bucket with capacity absorbs it and then throttles anyone who keeps going. Choose the algorithm that matches the shape of your traffic, not the one with the best worst case.
What You Key On Decides Whether Any of It Works
This is the decision that actually matters and it barely appears in the algorithm posts.
Keying on IP address is usually wrong. An IP is not a user. Corporate NAT and mobile carrier gateways put hundreds or thousands of people behind a single address, so an IP-keyed limit punishes an entire office because one person ran a script. Meanwhile the caller you were worried about, the one with a pool of residential proxies, is not constrained by a per-IP limit in any meaningful way.
It fails in both directions at once: too harsh on legitimate users who share infrastructure, too weak on anyone who can distribute.
“An IP-keyed limit is strict with the people who share an office and lenient with anyone who can rent a second address.”
Key on an authenticated identity where you have one. A user ID or API key is the thing you actually want to bound. That means rate limiting belongs after authentication in the request path, which has a consequence people miss: your unauthenticated endpoints, login and password reset and signup, are the ones that most need a limit and the ones where you have the least to key on. Those are where a coarse IP limit plus something like a bot score earns its place, precisely because there is no better key available.
Limit per endpoint, not per API. One global number treats a cheap read and an expensive report generation as equivalent. They are not. If one endpoint costs a hundred times more, it needs its own budget, and the honest version of this is limiting on cost rather than on request count.
Your Retry-After Is Scheduling the Next Outage
Return a 429 with a Retry-After header, in seconds or as an HTTP date, plus headers for the limit and remaining quota so well-behaved clients can slow down before they get rejected.[2] All standard advice, all correct.
Now consider what happens when you shed load from ten thousand clients and tell every one of them Retry-After: 60. They are well-behaved. They comply. In sixty seconds, all ten thousand return simultaneously.[1]
You did not resolve the overload. You scheduled it, and made it sharper, because the arrivals are now synchronised rather than merely heavy. This is the failure mode where the fix creates the next incident.
Why this matters
Retry-After you emit too. The same reasoning applies to every retry policy: a fixed doubling produces synchronised waves, and randomised backoff is what breaks them up.The Coupling Nobody Mentions: Idempotency
Here is the one I think is genuinely underdiscussed, because it lives on the boundary between two topics that get written about separately.
“Retry after 60 seconds” is only safe advice if retrying is safe. A client rejected cleanly before its request was processed can retry without consequence. But a client that timed out partway through a write does not know whether the write landed. Its options are to retry and risk duplicating, or not retry and risk losing the operation.
On a payment, an order, or a message send, that is not an abstract problem. It is a double charge.
Which means a rate limiter on a mutating endpoint is incomplete without idempotency keys: the client generates a unique key per logical operation, sends it with the request, and the server recognises a repeat and returns the original result rather than performing the action twice. That is what makes retry-after-rejection safe to tell people to do. Without it you are handing clients an instruction that can corrupt your data. The mechanism, and the four places implementations of it go wrong, is in idempotency keys.
And the mirror image of everything here is protecting yourself from the services you call rather than from the ones calling you, which is the circuit breaker.
Distributed State, Briefly
Once you have more than one server, per-process counters mean your real limit is the configured number multiplied by your instance count, and it changes when you autoscale. Redis is the standard shared store for this.[2]
The trade-off is that you have put a network call in front of every request, which is latency added to the hot path in order to enforce a limit. Sometimes that is right. Often a hybrid is better: a generous local limit that catches obvious abuse without a round trip, and the shared counter for the accurate ceiling. It is the same reasoning as any other caching decision, and the same tension between accuracy and latency.
Takeaway
Token bucket for bursty user traffic, sliding window when the ceiling must be exact, and never a plain fixed window where the number matters, because it permits double at the boundary. Then spend your real attention elsewhere: key on an authenticated identity rather than an IP, budget per endpoint rather than per API, put jitter in your Retry-After so compliance does not synchronise the next overload, and do not tell clients to retry a mutating endpoint that has no idempotency key.
Rate limiting is also one control among several, and it is not the one that stops the most serious problems. Broken authorization outranks everything on the OWASP API list, and for machine callers, which is increasingly what your traffic is, the budget question is part of the wider model in agent governance and RBAC.
Sources and further reading
- 1.ReportingAPI7, "From token bucket to sliding window: pick the perfect rate limiting algorithm". Source for the fixed-window boundary doubling, the burst tolerance of token bucket, the accuracy-versus-bookkeeping trade in sliding windows, and the synchronised-retry problem that jitter solves.
- 2.ReportingRequestly, "API rate limiting: how to handle 429 errors". Source for the 429 response contract, Retry-After in seconds or as an HTTP date, and Redis as the standard distributed store.
- 3.PrimaryMDN, "429 Too Many Requests". The specification-level behaviour of the status code and the Retry-After header.
Frequently asked questions
- Which rate limiting algorithm should I use?
- Token bucket for user-facing traffic, because it absorbs the short bursts real usage produces while still holding the long-run average, and sliding window when you need the limit enforced precisely. Avoid a plain fixed window for anything where the exact ceiling matters, since it permits up to double the intended rate across a window boundary.
- What is the fixed window boundary problem?
- A fixed-window counter resets on a hard schedule, so a client can consume its entire allowance in the final moment of one window and its entire allowance again immediately after the reset. Across that boundary it has sent twice the intended rate, which defeats the purpose if you chose the number for capacity reasons.
- Should I rate limit by IP address?
- Rarely on its own, because an IP is not a user. Corporate NAT and mobile carrier gateways put thousands of people behind one address, so an IP limit punishes an entire office for one heavy user, while an attacker with a pool of addresses is not constrained by it at all. Key on an authenticated identity where you have one, and treat IP as a coarse outer layer.
- What should a 429 response include?
- A Retry-After header telling the client how long to wait, either in seconds or as an HTTP date, plus headers describing the limit and remaining quota so a well-behaved client can self-regulate before it gets rejected. A 429 with no guidance leaves the client guessing, and clients guess badly.
- Why does Retry-After need jitter?
- Because if every rejected client honours the same Retry-After value precisely, they all return at the same instant and recreate the overload you just shed. Adding randomised jitter to the client's wait spreads those retries out, and the same reasoning is why retry backoff should be randomised rather than a fixed doubling.
- Is it safe for clients to retry after a 429?
- Only if the endpoint is idempotent. A client rejected before its request was processed can retry safely, but one that timed out mid-write does not know whether the write landed, so retrying a payment or an order risks duplicating it. Idempotency keys are what make retry-after-rejection a safe instruction to give.
Written by
Tech Talk News Editorial
Computer engineering background. Writes about software, AI, markets, and real estate, and the places where the three meet.
More about the author