Your Rate Limiter Is a Stampede at the Window Boundary

The fixed window lets double the traffic through at the boundary, the distributed counter is an agreement problem in disguise, and the token bucket is the honest answer.

The page came at 00:00:37 on a Tuesday. The database was falling over and the rate limiter's dashboard said everything was fine. Limit: 5,000 requests per minute. Busiest minute on record: 4,800.

The limiter was telling the truth. The database was dying anyway. Somewhere around 23:59:59, twenty-five hundred requests landed in the last second of one window. At 00:00:01, twenty-three hundred more landed in the first second of the next. Each window reported "under the limit." The database received forty-eight hundred requests in about two seconds.

That is the stampede. It is not a bug in your limiter. It is the design, working exactly as specified.

Two Bad Defaults and a Third Option That Ships

Most services I see run one of two defaults, and both fail the same way: quietly, at the boundary, under load you actually care about.

The first default is no limiter at all. The API is open, the clients are known, until the day someone is not. One misconfigured cron job, one retry loop with a short fuse, one partner's viral moment, and your database is doing the job the limiter was supposed to do. This wins for simplicity. You pay for it with the first incident.

The second default is the fixed-window counter. One key per client, one counter, one expiry. At the top of each minute the counters reset. It is simple, it is cheap, and it has a hole you can drive a stampede through: the limit is enforced per window, but your downstream experiences time as a continuum. Anything that straddles the boundary gets counted twice against nothing.

I understand why the second default survives. It is one INCR and one TTL, and it fits in a middleware in an afternoon. When your downstream can absorb twice the limit for one window, it is arguably fine. But "twice the limit, briefly, at :00, every hour" is a strange thing to leave to chance, and chance decides which clients fire at the boundary.

The third option is to stop rating the average and start rating the burst: pick the algorithm by the worst second you can tolerate, not the average minute you want.

Here is the gap this piece fills. Every tutorial shows you five algorithms and a Redis snippet. Almost none of them say which guarantee each algorithm actually gives you at the boundary, what breaks when the counter has to live on more than one machine, or what the client is supposed to do when you say no. Those three questions are the whole job.

Name the Algorithms by Their Guarantee

A rate limiter is a clock and a counter. The counter is honest. The clock is the part that lies.

Fixed window. One counter per key, reset every N seconds. Guarantee: at most L requests per window. The part nobody prints on the box: up to 2L requests in any N-second span that straddles a boundary. The numbers, on a simulated clock:

from rate_limiter import FixedWindow

lim = FixedWindow(limit=100, window_s=60.0)
allowed = 0
for _ in range(100):
    allowed += lim.allow(59.9)   # last tenth of a second of window N
for _ in range(100):
    allowed += lim.allow(60.1)   # first tenth of a second of window N+1
print(allowed)  # 200

Two hundred requests allowed inside a 0.2-second span, under a limit of 100 per 60 seconds. The limiter kept its promise. The promise was the problem. Drawn as a timeline, the hole is obvious:

59.0s         59.5s         59.9s  |  60.0s         60.1s         61.0s
                                   |
requests:                  2,500 ##|## 2,300
window N count:   ... 4,700 -> 5,000, then reset
window N+1 count:                  0 -> 2,300 ...

Each window, the limiter says: under the limit.
The database, across the boundary: 4,800 requests in two seconds.

Sliding window log. Store a timestamp per request, evict anything older than N seconds, count what remains. Guarantee: at most L requests in any rolling N-second span, exactly. The price is memory: one timestamp per request per key until it expires.

Sliding window counter. Keep two counters, current and previous window, and estimate: count = current + previous * (1 - elapsed_fraction). Approximately L per rolling window, no 2x blowup, two integers of state; Cloudflare described this design for their edge in 2017. The estimate errs in the friendly direction, which should make you slightly nervous.

Token bucket. Two numbers: tokens in the bucket, and the last refill time. Each request costs one token. Tokens refill at a steady rate, and the bucket caps accumulation. Guarantee: long-run average of R requests per second, with bursts up to the bucket size allowed on purpose. The burst is not a bug here. It is the parameter you chose. Here it is on a real clock:

from rate_limiter import TokenBucket

b = TokenBucket(capacity=10, refill_per_s=2.0)
burst = sum(b.allow() for _ in range(15))
# burst of 15 -> 10 allowed immediately, 5 denied
time.sleep(3.0)
after = sum(b.allow() for _ in range(10))
# after 3s idle, 10 quick requests -> 6 allowed

Ten through immediately, five denied, and three idle seconds buy you exactly six tokens back. The math is boring in the way that production systems should be boring.

Leaky bucket. The mirror image: requests pour in, the bucket drains at a fixed rate, overflow is rejected or queued. As a meter it behaves like the token bucket. As a queue, it smooths traffic on the way out instead of rejecting it on the way in. That is what nginx does with limit_req: excess requests are delayed to fit the rate, not dropped, unless you say otherwise.

Rate the burst, not the average: the bucket size is the decision, the refill rate is just the budget.

Real Tools With Real Commands

Theory is cheap. Here is what the tools actually give you.

nginx implements the leaky bucket, and the two knobs that matter are burst and nodelay:

limit_req_zone $binary_remote_addr zone=mylimit:10m rate=10r/s;

server {
    location /api/ {
        limit_req zone=mylimit burst=20 nodelay;
        proxy_pass http://backend;
    }
}

Ten per second sustained, twenty extra as a burst. With nodelay, the burst is processed immediately. Without it, excess requests are delayed so the backend still sees a smooth 10 per second. That one flag decides whether your limiter protects latency or throughput, and they are not the same thing.

Redis is where most hand-rolled limiters live, and the classic INCR pattern has a race the Redis docs themselves call out: a client that crashes between INCR and EXPIRE leaves a counter with no expiry, a leak that only grows. The fix is a Lua script so the check, increment, and expiry happen atomically:

-- KEYS[1]: counter key, ARGV[1]: limit, ARGV[2]: window seconds
local current = redis.call("INCR", KEYS[1])
if current == 1 then
    redis.call("EXPIRE", KEYS[1], ARGV[2])
end
if current > tonumber(ARGV[1]) then
    return {0, current}   -- denied
end
return {1, current}       -- allowed

One round trip, atomic, no leak. If your limiter is not atomic, you do not have a limiter. You have a suggestion.

redis-cell is the serious version: Brandur Leach's module implements GCRA, the Generic Cell Rate Algorithm, the token bucket done with exact virtual scheduling time instead of approximate refill math. One command does the whole job:

CL.THROTTLE user123 15 30 60

That reads: bursts of 15, sustained 30 per 60 seconds, for key user123. The reply is five integers: limited or not, the limit, remaining, seconds until retry, seconds until full reset. Everything a client needs to behave well, in one round trip.

The headers are finally getting standardized, slowly. draft-ietf-httpapi-ratelimit-headers, draft 11 as of May 2026 and still not an RFC, defines two fields: RateLimit-Policy, which advertises the quota ("default";q=100;w=60), and RateLimit, which reports current state ("default";r=15;t=23). Cloudflare adopted the draft in September 2025; GitHub still emits the legacy X-RateLimit-* family, 5,000 requests an hour for authenticated users. The draft itself warns that a naive fixed-window reset encourages cyclic burst-pause behavior: the stampede wearing formal clothes. Emit the headers even before the standard settles. A client that can see the limit can pace itself; a client flying blind can only guess, and guesses come in bursts.

The client side is the half everyone forgets. Netflix's concurrency-limits library runs an adaptive limiter inside the client: it watches round-trip times against a long-term minimum and shrinks its own concurrency budget when latency climbs, backing off before the server has to say no. The server-side limiter is the guardrail. The client-side limiter is the driver who slows down before the curve. You want both.

To see your own limiter misbehave, generate load and watch the headers:

hey -q 300 -c 50 -z 20s https://staging.example.com/api/search
curl -sI https://staging.example.com/api/search | grep -i -E "ratelimit|retry-after"

If the 429s cluster at the top of the minute and your p99 spikes with them, you have found your stampede. Ten minutes of measurement, and the argument is over.

The Distributed Question Nobody Prices In

One machine, one counter, one clock: easy. The moment the counter has to live on more than one machine, you have an agreement problem wearing a rate-limiting costume.

The naive answer is to divide: N nodes, each enforces limit/N. Traffic is never even, so the node holding the hot key throttles legitimate users while the other N-1 sit on idle quota. You paid for the full limit and you use the smallest slice. It fails the other direction too: a client that spreads requests across nodes gets N times the limit, because nobody counts the total.

The standard answer is the shared counter: every node checks the same Redis. The counter is now correct and the hot path pays a network round trip on every request. Redis is single-threaded, so your "distributed" limiter has a single-threaded heart, and that heart is the throughput ceiling of your API. Correctness costs a round trip; the round trip costs latency plus a new bottleneck. There is no version where the distributed counter is free.

The honest answers, in increasing order of machinery:

1. Sticky routing. Send each key to the same node and keep the counter local. Exact counts, memory-speed hot path, and the agreement problem moves into the router. Works until a node dies and its keys move, and every moved key gets a fresh counter and a fresh burst.

2. Local buckets, small. Each node runs a token bucket at limit/N. You accept the uneven-traffic waste in exchange for no hot-path round trip. This is what most large APIs actually do; the waste is the price of the latency.

3. Shared counter via GCRA. redis-cell's CL.THROTTLE, one round trip, exact. Pay the latency when the downstream is expensive enough to deserve it: a database, a GPU endpoint, a third-party API that bills per call.

Notice the shape: who holds the counter, who agrees on the count, what happens when a holder dies. The same questions as leader election and quorum, with smaller numbers. The limiter is a tiny consensus system about how many requests happened, and like every consensus system, it charges you for the agreement.

Where This Breaks

No hedging. These are the failure modes I have watched in production.

• A limiter cannot tell a good burst from a bad one. Deploys, cron jobs firing at :00, a legitimate flash of traffic: all of it looks like an attack. You will 429 your own deploy pipeline at least once. Plan the allowlist before the incident, not during it.
• Retry-After without jitter synchronizes the retries. Every denied client waits the same number of seconds and returns at the same instant. You built a second stampede out of the first one's survivors. Jitter the wait, always.
• The limiter sits on the hot path. A shared Redis counter adds a round trip to every request, including the 99 percent that were never going to be limited. Measure that latency. It is the real price of the feature.
• Per-IP limits punish everyone behind a NAT. Per-key limits miss aggregate abuse. Key cardinality is unbounded, because an attacker rotates keys faster than you can count them. Cap the keys or the limiter is a memory leak with extra steps.
• Fixed windows punish the innocent at the boundary and reward the strategic: fire at :59 and :01 and the limiter applauds. Token buckets need per-key state and a refill clock per key.
• Skewed clocks move the boundary per node. Monotonic clocks for measuring rates, wall clocks for agreeing on windows, never the reverse.
• The headers are advisory. The IETF draft says the values MAY be ignored, and "5 remaining" promises nothing. Emit them anyway, but never build correctness on a client reading them.
• Limiters protect rate, not cost. One hundred cheap cache hits and one hundred full-table scans count the same. If the work per request varies by orders of magnitude, weight the tokens by cost.

Build It If, Skip It If

Build it if you have a shared expensive downstream, noisy multi-tenant neighbors, or a public API with clients you did not choose. Those are the three situations where one actor's burst becomes everyone's outage, and the limiter is cheaper than the incident.

Skip it if the service is single-tenant and internal behind auth, with clients you can fix. Fix the client. Also skip it if traffic is already shaped upstream: your CDN or WAF probably rate-limits better than your application will.

The minimal viable version fits in an afternoon. An in-process token bucket per key, no Redis, no shared anything. On deny, return 429 with a jittered Retry-After. Teach exactly one client to read the header and back off. Run hey against staging and watch the boundary. Only add the shared counter when you have more than one node and traffic uneven enough to notice. Most teams add Redis on day one and debug clock skew on day thirty. Reverse that order.

Rate the Burst, Not the Average

Pick the burst size first. Write it in the config next to the rate, as a number you chose instead of a default you inherited. Then generate load against staging, watch the window boundary, and let the measurement argue with the dashboard. The average is the easy part. The boundary is the whole job.

What is the worst 429 you have ever caused, or received? The one where the limiter was technically correct and the outage happened anyway. I read every reply.

Resources

1. RateLimit header fields for HTTP, draft-ietf-httpapi-ratelimit-headers: draft 11, May 2026, still a draft; defines the RateLimit and RateLimit-Policy fields.
2. redis-cell by Brandur Leach: Redis module implementing GCRA; the CL.THROTTLE command is the serious version of the Lua script above.
3. nginx limit_req module documentation: leaky bucket with burst and nodelay, and the difference between delaying and dropping.
4. Netflix concurrency-limits: client-side adaptive limiting with the gradient algorithm; the other half of the story.
5. RFC 6585: defines status 429 Too Many Requests.
6. RFC 9110: HTTP semantics, including the Retry-After field.
7. Related pieces in this series: retry storms, backpressure, idempotency keys, clock skew, and the quorum tax.