Rate Limiter
Four algorithms compared with their exact failure modes, and the distributed counting problem that makes this harder than it looks
A rate limiter decides whether a request is allowed right now. The algorithm choice matters, because three of the four common ones have a specific, exploitable weakness.
1. Clarify and Scope
| Question | Assumption taken here |
|---|---|
| Limit by what? | API key, with per-endpoint overrides |
| Where does it run? | At the edge, before application servers |
| What happens when exceeded? | 429 with Retry-After |
| Must it be exact? | No — a small overshoot is acceptable |
| Distributed? | Yes, many limiter nodes |
That last pair matters more than it seems. Exactness is expensive, and accepting approximation unlocks much simpler designs.
2. Put Numbers On It
1 million API keys
10,000 requests/sec at peak
Per-key state: key + counter + timestamp ≈ 50 bytes
1M keys × 50 bytes = 50 MB ← trivially fits in memory
Latency budget: the limiter must add < 5 ms50 MB is the finding that shapes everything
All the state fits in memory on one machine, several times over. That rules out anything database-backed and points straight at Redis.
It also means the expensive algorithm — the sliding log — is affordable here, which is worth knowing before dismissing it.
3. Define the Interface
allow(key, endpoint) → { allowed, remaining, reset_at, retry_after }
Called in-process at the edge, before routing.
NOT an HTTP service — a network hop per request would cost more
than the work it is protecting.
On the way out, every response carries what the caller used:
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 887
X-RateLimit-Reset: 1735689600Why it returns four things and not just true/false
A bare true/false tells a client it was rejected but not when to come back. So it retries immediately, and keeps retrying — turning a rate limit into a tight loop that costs you more than the original traffic.
retry_after converts a rejection into an instruction. remaining lets a well-behaved client slow down before it is rejected at all.
The interface is doing real work here: it decides whether being limited teaches the client anything.
4. The Four Algorithms
Fixed window
Count requests per fixed clock interval. Reset at the boundary.
Limit: 100 per minute
10:00:00 – 10:00:59 count = 0 … 100
10:01:00 count resets to 0Simple and cheap — one counter per key. And it has a serious flaw.
Fixed windows allow double the limit
10:00:59 → 100 requests (window 1, now full)
10:01:00 → 100 requests (window 2, fresh counter)
200 requests in ONE SECOND, with a limit of 100 per minute.A client that learns your boundary can sustain twice the intended rate indefinitely by clustering requests around it. This is not theoretical — it is the standard way rate limits get abused.
Sliding log
Store the timestamp of every request. To decide, drop timestamps older than the window and count what remains.
Limit: 100 per minute. Now = 10:01:30
Keep timestamps after 10:00:30, count them.Perfectly accurate, with no boundary problem at all. The cost is memory: 100 timestamps per key, so 1M × 100 × 8 bytes = 800 MB. Affordable here, but it scales with the limit, which makes it fragile for generous limits.
Sliding window counter
The practical compromise. Keep two counters — the current window and the previous — and weight the previous one by how much of it is still in view.
Limit 100/min. Now = 10:01:15, so 25% of the way into the current window.
previous window (10:00–10:01): 80 requests
current window (10:01–10:02): 30 requests
estimate = 30 + 80 × (1 − 0.25) = 30 + 60 = 90 → allowed (90 < 100)Two numbers per key. No boundary exploit. The estimate assumes requests were spread evenly through the previous window, which is slightly wrong but close enough in practice.
Token bucket
A bucket holds tokens. Each request takes one. Tokens refill at a steady rate up to a maximum.
Capacity 100, refill 10 tokens/sec
Idle for a while → bucket fills to 100
Burst of 100 → all allowed instantly, bucket now empty
Then → 10 requests/sec sustainedToken bucket is usually the right choice
It is the only one of the four where bursting is a feature rather than a bug.
Real clients are bursty: a page load fires eight API calls at once, then nothing for thirty seconds. A strict per-second limiter rejects that legitimate pattern; a token bucket absorbs it while still capping the sustained rate.
Two numbers per key — token count and last refill time — and tokens are computed lazily on read, so no background timer is needed.
Side by side
| Fixed window | Sliding log | Sliding counter | Token bucket | |
|---|---|---|---|---|
| Memory per key | 1 number | 1 per request | 2 numbers | 2 numbers |
| Boundary exploit | Yes, 2× | No | No | No |
| Allows bursts | Accidentally | No | Slightly | By design |
| Accuracy | Poor | Exact | Good | Good |
| Complexity | Lowest | High | Medium | Low |
5. The Distributed Problem
One limiter node is easy. Several is where it gets interesting.
Read-then-write is a race, and it is the classic bug
Node A: GET count → 99 Node B: GET count → 99
Node A: 99 < 100, allow Node B: 99 < 100, allow
Node A: SET count 100 Node B: SET count 100
Two requests allowed, and the counter says 100 instead of 101.The fix is to make it one operation. Redis INCR returns the new value atomically, so you increment first and reject if the result exceeds the limit. For token buckets, which need arithmetic on two fields, use a Lua script — Redis runs scripts atomically.
Trading accuracy for latency
Calling Redis on every request adds a round trip. Two ways to avoid it:
| Approach | How | Cost |
|---|---|---|
| Local + sync | Count locally, reconcile with Redis every few hundred ms | Brief overshoot |
| Divide the budget | Each of N nodes gets limit / N | Under-utilised if load is uneven |
Accepting a small overshoot is usually correct
Rate limits exist to stop abuse, not to be arithmetically perfect. Allowing 105 requests against a limit of 100 harms nothing.
Say it explicitly: "we allow a small overshoot in exchange for not making a network call per request — a hard limit would cost 1 ms on every request to prevent a 5% overage." That is a trade-off, stated.
6. The Response
HTTP 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1719000060
Retry-After: 42Send the headers on successful responses too, so well-behaved clients can slow down before being rejected.
Fail open, not closed
If Redis is unavailable, what should the limiter do?
Fail closed — reject everything. Your rate limiter has just become a total outage.
Fail open — allow everything. You are unprotected for the duration, but the service stays up.
Almost always fail open. The limiter protects against abuse; it should not itself be able to take the system down. Pair it with a local fallback limit so you are not entirely unguarded.
7. What Was Traded Away
| Decision | Gained | Cost |
|---|---|---|
| Token bucket | Legitimate bursts allowed | Not a strict per-second cap |
| Shared Redis counters | Correct across nodes | +1 ms per request; a dependency |
| Accepting overshoot | No sync on every request | Limits are approximate |
| Fail open | Limiter cannot cause an outage | Unprotected while Redis is down |
Follow-on Questions
Related Reading
- APIs and Rate Limiting — status codes and headers
- Caching — Redis, and what happens when it is unavailable
- Reliability — failing open, and load shedding
- Consistency and CAP — why atomic operations matter here