Redis-backed distributed sliding-window rate limiter

A rate limiter that is correct across many app servers because the counting logic runs atomically inside Redis. Algorithm: sliding window log using a Redis sorted set, executed as a single Lua script.

Why not the simple approaches

Approach	How	Problem
Fixed window	INCR key:<minute> with TTL	Boundary burst: N requests at 12:00:59 + N at 12:01:00 = 2N in ~1s
Sliding window log (this)	sorted set of request timestamps; evict old, count rest	Exact, no boundary bug; costs one member per in-window request
Sliding window counter	weighted blend of current + previous fixed window	Cheaper memory, slightly approximate
Token bucket	refill tokens over time	Great for burst allowances; less "exactly N per window"

This implements the sliding window log because it's exact and the easiest to reason about: "the window" is always the last N milliseconds from right now, so there is no calendar boundary to exploit.

Why a Lua script (the crux of "distributed")

The algorithm is read-modify-write:

evict old entries  →  count remaining  →  if under limit, add this one

If two servers run those steps interleaved against shared Redis, both can read count = limit-1 and both add, letting limit+1 through. Redis executes a Lua script as a single atomic unit — nothing else runs mid-script — so the check-and-add can't interleave. That atomicity is what makes one shared limit hold across an entire fleet. See _SLIDING_WINDOW_LUA in limiter.py.

The script uses: ZREMRANGEBYSCORE (drop entries older than the window), ZCARD (count), ZADD (record this request), PEXPIRE (so idle keys expire).

Files

File	Role
limiter.py	SlidingWindowLimiter + the atomic Lua script
demo_fastapi.py	uses it as a FastAPI dependency → 429 + Retry-After + X-RateLimit-* headers
test_limiter.py	proves limit enforcement, window sliding, identity isolation

Run

docker run -d -p 6379:6379 redis:7-alpine
pip install -r requirements.txt
pytest -v                     # the behavioural proof

uvicorn demo_fastapi:app      # then:
for i in $(seq 1 6); do curl -s -o /dev/null -w "%{http_code}\n" localhost:8000/ping; done
# → 200 200 200 200 200 429   (5/10s limit; the 6th is blocked)

Design notes

• Unique member per request (<ms>-<uuid>) so two requests in the same millisecond don't collapse into one sorted-set entry and undercount.
• Blocked requests are not recorded — a client being throttled can't keep pushing its own window forward.
• PEXPIRE on every hit bounds memory: keys for clients that go quiet evaporate after one window instead of living forever.
• The limiter returns remaining so callers can emit X-RateLimit-Remaining.