Under the Hood: Eliminating the Boundary Burst Flaw
Rate limiting algorithms prevent system overload by bounding request frequency over time. Naive Fixed Window Counters suffer from the 2x burst vulnerability: if a limit allows 100 requests/minute, an attacker can dispatch 100 requests at 00:59 and another 100 requests at 01:00, forcing 200 requests within a 2-second window without triggering any rate limit violation.
Rate Limiting Algorithms Compared
Sliding Window Counter Mathematics & Implementation
The Sliding Window Counter combines the memory efficiency of fixed windows with the smoothness of a continuous sliding window. It tracks request counts across only two keys (the current window and the previous window) and calculates an interpolated estimate:
Estimated Count = (Previous Window Count * (1 - Current Offset Ratio)) + Current Window Count
Where Current Offset Ratio = (Current Timestamp - Window Start) / Window DurationConcrete Numeric Example:
Suppose the limit is 100 requests per 60-second window. The previous window recorded 80 requests. We are currently 15 seconds into the new window (25% through), and have registered 30 requests so far:
Estimated Count = (80 * (1 - 0.25)) + 30 = (80 * 0.75) + 30 = 60 + 30 = 90 requests (Allowed, 90 < 100)Atomic Redis Execution with Lua
Because multiple concurrent application servers query the rate limiter simultaneously, checking and incrementing counters across network hops introduces race conditions. Production architectures wrap the lookup and increment logic inside an atomic Redis Lua Script, guaranteeing single-threaded atomic execution with zero distributed lock contention.
Algorithm comparison
| Algorithm | State per key | Accuracy | Burst behaviour | Used by |
|---|---|---|---|---|
| Fixed window counter | 1 integer | Allows up to 2x the limit at window boundaries | Bursts at window edges | Simple quotas, daily caps |
| Sliding window log | One entry per request (up to the limit) | Exact | None beyond the limit | Low limits where exactness matters (login attempts) |
| Sliding window counter | 2 integers | Approximate; Cloudflare reported about 0.003% of requests wrongly allowed or limited in its production analysis | Smooth | Cloudflare rate limiting |
| Token bucket | Token count + last refill time | Exact for its model | Allows bursts up to the bucket size, then the average rate | Stripe, AWS API Gateway, Envoy local rate limit |
| GCRA (generic cell rate) | 1 timestamp | Exact for its model | Like a token bucket | redis-cell; the algorithm comes from ATM (Asynchronous Transfer Mode) networking |
Worked example: why the counter needs the weighting
The limit is 100 per 60 s. In the window from 12:00:00 to 12:01:00 there were 90 requests, and all of them arrived after 12:00:50. It is now 12:01:10, so we are 10 s (one sixth) into the current window, which has 20 requests so far.
- Fixed window: the counter sees 20 and allows the request, even though 110 requests actually arrived in the last 20 s.
- Sliding window counter: 90 x (1 - 1/6) + 20 = 75 + 20 = 95, so the request is allowed, and only 5 more will be allowed right now.
- Sliding window log (exact): the real count for 12:00:10 to 12:01:10 is 90 + 20 = 110, so the request is rejected.
This is the worst case for the approximation: the previous window's traffic was all bunched at its end. With the more typical evenly spread traffic, the estimate is very close to the true count. That is why Cloudflare found the error acceptable at its scale.
Atomic implementation sketch (Redis)
Keys are rl:{client}:W, where W is floor(now / window). The Lua script does the following:
INCRthe current window key, and setEXPIREto twice the window length on the first increment.GETthe previous window key (treat missing as 0).- Compute
prev x (1 - elapsed/window) + curr. If it exceeds the limit,DECRthe current key and return "rejected" together with a retry-after value.
Everything runs in one round trip, and Redis executes scripts one at a time, so no race is possible. Take now from the Redis TIME command instead of each application server's clock, so clock skew between servers does not shift the windows.
Scaling notes
- At 1 million active keys, two counters each (2 million small keys with expiries) take very roughly 150 to 250 MB in Redis including overhead. A sliding log with a limit of 1,000 could take hundreds of times more.
- For global limits across regions, either accept per-region limits (the global limit divided by the number of regions) or sync counters asynchronously and accept some overshoot.