Research paper: Overshoot, Retries and Clocks: An Empirical Study of Redis-Based Rate Limiting Under Concurrency · code and data · DOI 10.5281/zenodo.23467402
I build rate limiting for a living, and most advice about Redis limiters says the same three things: don't race, beware fixed windows, use Lua. All true, but I couldn't find anyone who had measured how big each problem is. So I did: eight implementations, four experiments, 3,853 trials, and every number generated from the raw data. The full paper is here; this is the short version.
The race has a formula
The classic bug is GET, compare, INCR. Two workers read 99, both see room, both increment. With 64 concurrent workers and a limit of 100, it let through 128.7 requests on average, 29% more than the limit, and 137 in the worst trial.
The surprise came with network delay. Once round trips are long, the workers fall into lockstep: each wave reads the same value and increments together, so the counter grows in steps of the worker count. The overshoot then follows a formula, c·ceil(L/c) − L: 4 extra requests for 8 workers, 12 for 16, and 28 for both 32 and 64. The measurements matched it to within about one request. It also means the bug depends on how your limit divides by your worker count, so it can pass every test and appear after a config change.
Optimistic transactions trade one failure for another
WATCH/MULTI never over-admits: if another client touched the key, the transaction aborts and retries. But with a 10-retry budget, 64 workers and 6.7 ms round trips, it admitted only 58 of 100 requests. 42% of legitimate traffic was refused because the retries ran out. With 1,000 retries it was exact, but on a hot key it ran 12 to 30 times slower than a Lua script.
Atomic is not the same as keeping your promise
Every atomic strategy admitted exactly 100 in all 2,520 of its concurrency trials. But "100 per second" means different things to different algorithms. Here is the most each one let through in any single second:
- Fixed window: 200 requests within a few milliseconds when two bursts straddle a window boundary, twice the limit.
- Token bucket (capacity 100, refill 100 per second): 1.99× the limit in one second after a quiet spell. That is by design, but it is not what a capacity plan assumes.
- Sliding-window counter: close, but 1.31× on average under a burst followed by sustained traffic, and 1.66× in the worst trial.
- Sliding-window log: exact under every pattern.
Never let callers supply the time
A token bucket needs "now" to compute its refill. When the script took it from the calling server instead of Redis's TIME, clock differences barely mattered under overload, at most 1.3% off. Near the limit, with ±1 s of skew between servers, the bucket collapsed and admitted only 16% of the traffic it should have. Clocks running behind produce negative refills that nothing caps, while positive refills are capped at the bucket's size, so the bucket drains. The same bucket on Redis's clock was exact in every setting.
What I'd do
- Make the decision one atomic step: a Lua script, or a single
INCRwhen the algorithm allows it. - Choose the algorithm by the promise. Use a sliding-window log if downstream capacity means at most L in any window, and a token bucket when bursts are intended, with its capacity set as a burst budget.
- Read the time inside the script with
TIME. - Put
INCRandEXPIREin one step, so a crash can't leave a counter that never expires. - Keep
WATCHaway from hot keys.
Paper, data and code
The paper covers the method, every table and figure, and the threats to validity: read the PDF. It is archived on Zenodo with a permanent DOI, 10.5281/zenodo.23467402, which is the link to cite. The harness, the raw data and the analysis are in one download; ./run_all.sh reruns every experiment in about an hour.
Originally published at yashsuthar.dev. I'm Yash Suthar, a backend developer in Mumbai building LimitYourAPI, ScopeCI and StartupDeckAI.
