Overshoot, Retries and Clocks: An Empirical Study of Redis-Based Rate Limiting Under Concurrency

Abstract

Rate limiters that share state through Redis are everywhere, and the guidance for building them warns, qualitatively, about races and burst behaviour. We measure those hazards. We implement eight common strategies (check-then-act, increment-then-check, optimistic WATCH/MULTI transactions with two retry budgets, and Lua scripts for fixed windows, token buckets, sliding-window logs and sliding-window counters) and evaluate them in 3,853 trials across concurrency (1 to 64 workers), network delay (round-trip times of 0.04 to 6.73 ms), adversarial and random arrival patterns, and clock skew. Under concurrency, every atomic strategy admitted exactly the limit in all of its trials. Check-then-act over-admitted at every concurrency level above one, by 29% on average with 64 workers, and under network delay its error follows a simple lockstep model, c·ceil(L/c) − L. Optimistic transactions avoided over-admission but, with a 10-retry budget, refused up to 42% of the capacity the limit promised, and under contention ran 12 to 30 times slower than a Lua script on the same key. Even with atomic decisions, fixed windows and token buckets configured as L per W admitted twice the limit within one window, and the sliding-window counter up to 1.66×; only the sliding-window log was exact. A token bucket fed timestamps by its callers admitted only 16% of its configured rate near the limit at 1 s of skew, while the same bucket on Redis's clock stayed exact. We turn the results into five rules for building limiters and release the harness, raw data and analysis.

Key findings

• Check-then-act (GET, compare, INCR) let through 29% more than its limit on average with 64 workers, and 37% in the worst trial.
• Under network delay that overshoot follows a lockstep model, c·ceil(L/c) − L, to within about one request.
• WATCH/MULTI never over-admitted, but with a 10-retry budget it refused up to 42% of requests that were within the limit.
• Fixed windows and token buckets set to L per W admitted 2× the limit within one window; the sliding-window counter up to 1.66×; only the sliding-window log was exact.
• Near the limit, a token bucket fed timestamps by its callers admitted 16% of its rate at ±1 s of clock skew; on Redis's own clock it stayed exact.

Code and data

The Go harness, the raw results of all 3,853 trials, and the analysis that produces every table and figure in the paper. ./run_all.sh reruns every experiment in about an hour. Download (.zip).