Designing a distributed rate limiter

A full system-design note: requirements, algorithm comparison, the maths of the token bucket, two diagrams, production code and a launch checklist.

Requirements

• Limit each API key to 100 requests per minute, across 20 app servers.
• Decision in under 2 ms; when the limiter is down, fail open.
• Return 429 Too Many Requests with a Retry-After header.

Choosing an algorithm

• Fixed window: simple, but allows 2× bursts at window edges.
• Sliding log: exact, but stores every timestamp — $O(n)$ memory per key.
• Sliding window counter: weighted mix of two windows; cheap and close enough.
• Token bucket: allows controlled bursts, $O(1)$ state. ✅ Our pick.

Token bucket maths

A bucket holds at most $b$ tokens and refills at rate $r$ tokens per second. At time $t$, after the last update at $t_0$:

A request is allowed if $\text{tokens}(t) \ge 1$, then one token is removed. Over any interval of length $T$ at most $b + rT$ requests pass. For 100/min with bursts of 20: $r = \tfrac{100}{60} \approx 1.67$, $b = 20$.

Architecture

flowchart LR
  C[Clients] --> G[API gateway]
  G --> L{Rate limiter}
  L -- allowed --> S[App servers]
  L -- 429 --> C
  L <--> R[(Redis cluster)]
  S --> DB[(Database)]

One request, atomically

sequenceDiagram
  participant G as Gateway
  participant R as Redis
  G->>R: EVALSHA token_bucket key, now, rate, burst
  R-->>G: allowed=1, tokens=13
  Note over G,R: read + refill + decrement in one Lua script — no race
  G->>R: EVALSHA token_bucket key, now, rate, burst
  R-->>G: allowed=0, retry_after=0.6s

The Lua script

-- KEYS[1] = bucket key; ARGV = now, rate, burst
local now, rate, burst = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local b = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(b[1]) or burst
local ts = tonumber(b[2]) or now
tokens = math.min(burst, tokens + (now - ts) * rate)
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end
redis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("PEXPIRE", KEYS[1], math.ceil(burst / rate * 1000))
if allowed then return {1, tokens} end
return {0, (1 - tokens) / rate}

Failure modes

• Redis down: fail open with a local in-memory bucket per server ($\tfrac{1}{20}$ of the limit).
• Hot key: one abusive key hammers one shard — add a local pre-check cache.
• Clock skew: use Redis TIME, not the app server clock.

Launch checklist

• Shadow mode: log decisions for a week without blocking
• Dashboards: allowed vs blocked per key, p99 latency
• Per-plan limits loaded from config, not code
• Alert when more than 5% of traffic is blocked

Start in shadow mode. A rate limiter that blocks real customers on day one is worse than none.