Part 3 · System design · Design problems
Distributed rate limiter
Limit each API key to N requests per minute, across a fleet of API servers.
Ask first
- Limit per user, per IP, per key, per endpoint?
- Must it be exact, or is slightly over fine?
- What does a rejected caller get? 429 with Retry-After?
- If the limiter breaks, should traffic be blocked or allowed?
Numbers
| traffic | say 50k requests per second across 30 servers |
| state | 2 counters per key per window, a few bytes each |
| Redis | one INCR per request; one shard does about 100k operations a second, so shard by key past that |
API
Middleware, not an endpoint: allow(key) true or false Response headers: X-RateLimit-Limit, X-RateLimit-Remaining, Retry-After
Data
Redis: rl:{key}:{window} count, with EXPIRE of 2 windows
(or a Lua script, so read and increment happen in one step)Deep dive: Which algorithm?
Fixed window is simplest but lets 2N through around the window boundary. Sliding log is exact but stores every timestamp. Sliding window counter weights the previous window by how much of it still overlaps: two integers per key and close to exact. Token bucket allows controlled bursts.
Why not count in each server's memory?
Each server sees only its share of traffic, so local counters let N x servers through. A local limiter is still a useful cheap first layer.
Race conditions?
GET then SET races between servers. Use INCR, which is atomic, or a Lua script that reads and updates in one step.
What does it cost per request?
One Redis round trip, about 1 ms in the same zone. To go cheaper, count locally and sync every 100 ms, trading accuracy for speed.
See the core idea run
Core logic (JavaScript, tested)
// Sliding window counter: the previous fixed window counts in proportion to how much of it still overlaps.
// Two integers per key per window, so it fits Redis: INCR rl:{key}:{window}, EXPIRE 2 windows.
class SlidingWindowLimiter {
constructor(limit, windowMs, now = Date.now) {
Object.assign(this, { limit, windowMs, now, counts: new Map() });
}
allow(key) {
const t = this.now(), win = Math.floor(t / this.windowMs);
const cur = this.counts.get(`${key}:${win}`) ?? 0;
const prev = this.counts.get(`${key}:${win - 1}`) ?? 0;
const overlap = 1 - (t % this.windowMs) / this.windowMs; // share of the previous window still inside
if (prev * overlap + cur >= this.limit) return false; // caller answers 429 + Retry-After
this.counts.set(`${key}:${win}`, cur + 1);
return true;
}
}Failures
| Redis is down | Fail open (allow and log) for most APIs. Fail closed for login and other abuse targets. |
| One abusive key | It hits one Redis shard hard; a local limiter in front absorbs it. |
| Clock skew between servers | Take window ids from one clock, such as Redis TIME. |
Trade-offs
- Accuracy costs a network hop on every request.
- Fail open favours availability; fail closed favours protection.
Say out loud: A sliding window counter in Redis: two integers per key, atomic INCR, a TTL for cleanup. Rejected calls get 429 with Retry-After. If Redis is down I fail open for normal APIs and closed for login.