Rate limiting, and why the counter you'd reach for first is broken
The obvious "count requests per minute" quietly lets through double the limit at the worst possible moment. The fix is a bucket that thinks in refill rate, not windows.
Cap a client at 100 requests a minute. First instinct?
A counter. One per client, increment each request, reset every minute, reject past 100.
Good enough?
It's the right place to start, because its flaw is the whole lesson.
What flaw? Hits 100, you reject. Sounds exact.
Exact only if you ignore the window edge. Watch the boundary.
Show me.
100 requests at 12:00:59. Another 100 at 12:01:01. Both minutes are legal.
But that's 200 in two seconds.
Right. The fixed window lets a client double the rate right at the seam.
So how do you kill the seam?
A token bucket. It holds 100 tokens and refills at a steady rate.
And a request?
Spends one token. No token, rejected.
Why is that better than counting?
A window has edges you can game. A refill rate has none. The average is capped, full stop.
What about a real burst?
A full bucket absorbs it. That's the point: burst size and sustained rate become two separate dials.
capacity: 100 tokens
refill: +1.67 / sec (100 / min)
request -> take 1 token -> allow ; empty -> rejectNow scale it. Ten servers, each running the bucket in memory. Same limit, right?
No. You don't have a 100 limit. You have a 1000 limit.
Because?
The client's requests spread across all ten servers, each counting to 100 on its own.
So the state has to be shared.
One bucket in Redis, keyed by client. Every server reads the same view.
Doesn't a Redis call per request add latency and a failure point?
It does. That's the real tension. Keep it one atomic command, and choose your failure mode on purpose.
Meaning?
Fail-open protects your availability. Fail-closed protects the service downstream. Pick deliberately.
And if someone demands exactness, no seam at all?
A sliding-window log. A timestamp per request, count the trailing 60 seconds. Exact, but memory-heavy.
The whiteboard line?
Don't count requests in boxes of time. Meter them against a refill rate, in shared state, as one global limit.
↑ answer it in your head first ↑
Traps
- ⚠ The fixed-window counter. Two bursts either side of a window boundary let through up to twice the limit in a short span.
- ⚠ Storing counters in each server's memory. With N servers behind a load balancer, a client gets N times the intended limit.
- ⚠ Assuming the limiter must be perfectly exact. A little burst tolerance is usually fine; strict global exactness costs latency most APIs won't pay.