Designing a Distributed Rate Limiter: Token Bucket, Sliding Window, and the Redis Trade-off Nobody Mentions

"Rate limit this endpoint to 100 requests per minute per user" sounds like a single Redis INCR. It's actually four different algorithms with genuinely different accuracy/cost trade-offs, and most production outages I've seen from rate limiters come from picking the simplest one and hitting its one well-documented flaw anyway.

Fixed window counter — simple, and exploitable at the boundary

Increment a counter keyed by user:minute-bucket, reject once it crosses the limit, let the key expire. One command, effectively free. The flaw: a client can send 100 requests in the last second of one window and another 100 in the first second of the next — 200 requests in two seconds against a "100/minute" limit, because the algorithm only ever looks at one window at a time.

Sliding window log — accurate, but memory-hungry

Store a timestamp per request in a sorted set, trim anything older than the window on every check, and count what's left. This is exactly correct — no boundary bug — but it's O(n) in both memory and per-request work, where n is the request count in the window. At 10,000 requests/minute per key, that's a genuinely large sorted set to trim on every single call.

Sliding window counter — the practical middle ground

Keep two fixed-window counters (current and previous) and weight the previous window's count by how much of it still overlaps the sliding window:

estimated_count = current_window_count
                 + previous_window_count * (1 - elapsed_fraction_of_current_window)

This is an approximation, not exact — but it's O(1) storage and it closes the fixed-window boundary-burst problem to within a small, bounded error. This is what most rate limiting middleware (including Cloudflare's public writeups on their own limiter) actually ships.

Token bucket — the one that tolerates real traffic patterns

A bucket holds up to capacity tokens, refills at a steady rate, and each request consumes one token — rejected only when the bucket is empty. Unlike the window-based approaches, it explicitly allows bursts up to the bucket size while still enforcing a long-run average rate. This is why it's the default at AWS API Gateway and Stripe's API: real client traffic is bursty (a page load fires ten requests at once, then goes quiet), and a hard "100 evenly-spaced requests per minute" rule punishes normal usage patterns that a token bucket handles gracefully.

The atomicity bug that ships anyway

Whichever algorithm you pick, if it's backed by Redis and implemented as "read the counter, check it, then INCR or set an expiry" in separate round trips, you have a race: two concurrent requests can both read a count just under the limit, both pass the check, and both increment — silently letting through more than the limit under concurrency. This is the single most common bug in home-grown Redis rate limiters, and it only shows up under real load, never in a single-threaded test.

The fix is to make the check-and-increment a single atomic operation via a Lua script, which Redis guarantees runs without interleaving:

-- KEYS[1] = rate limit 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
end
return 1

That's the fixed-window version; the sliding-window-counter and token-bucket variants follow the same principle — do the read-modify-write as one script, not as separate commands your application code stitches together.

One more honest trade-off: centralized vs local counting

A single Redis instance backing every node gives you one true global count, at the cost of a network round trip per request and a single point of contention under very high QPS. Some systems accept an approximation instead: each node keeps a local counter and only syncs to Redis periodically, trading perfect accuracy for near-zero added latency. For a strict billing or abuse-prevention limit, pay for the round trip and get it exactly right. For a soft "protect the backend from overload" limit, the approximate local-counter approach is usually the better trade — and it's worth deciding which one you actually need before writing a line of code, because retrofitting exactness into an approximate limiter later is a much bigger rewrite than starting with the right one.