A theme park ride that lets in 20 people every 5 minutes. Everyone else waits or is told to come back later. The ride never gets overloaded, and one big group can't hog every slot.
Problem Statement
Design a rate limiter that caps how many requests a client can make in a time window ("100 requests per minute per API key"), shared across a fleet of API servers. It protects services from abuse and overload and enforces paid plan limits. It sits on every request, so it must be fast and must not become the thing that takes the API down.
Functional Requirements
Limit requests per key (user id, API key, IP) per rule (e.g. 100/min, 10/s burst).
Different rules per endpoint and per plan (free vs paid).
Rejected requests get HTTP 429 with headers telling the client when to retry.
Rules can change without redeploying.
Non-Functional Requirements
Low overhead: a few milliseconds at most added per request.
Accurate enough across servers: limits are global, not per server; small overshoot is acceptable, large is not.
Highly available: if the limiter fails, the API should keep working (fail open, usually).
Scale: e.g. 1M requests/s across 10M active keys.
Memory estimate: 10M keys x ~100 bytes of counter state = ~1 GB -> fits in a Redis cluster
Throughput: 1M checks/s -> a sharded Redis cluster (~100K ops/s per node) -> 10-20 nodes
Counter / bucket state: per (key, rule): tokens and last refill time, or window counts.
Client: the identity being limited.
API Design
Internal (called by the gateway / middleware for every request):
check(key, rule_id, cost=1) -> { allowed: bool, remaining: int, reset_at: ts }
To clients (HTTP headers on responses):
429 Too Many Requests
Retry-After: 20
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1727600000
Admin:
PUT /v1/rules/{id} { limit, window, burst, scope }
High-Level Design (HLD)
Every request checks a shared counter first; rejected requests never reach the backend.
client --> API gateway / middleware --check()--> [ Redis cluster ]
| allowed? (counters, sharded by key)
|-- no -> 429 + headers
|-- yes -> backend services
[ rules store (DB) ] --> pushed / polled into each gateway's memory
Enforce at the edge (API gateway or middleware) so rejected requests cost almost nothing.
Counters live in a shared, in-memory store so all gateway instances see the same counts.
Rules are cached in each gateway and refreshed on change.
Low-Level Design (LLD)
The whole read-refill-decide-write runs as one atomic Redis script, so concurrent requests can't overspend.
Choosing an algorithm
Algorithm
How
Pros
Cons
Fixed window
counter per key per minute
simplest, 1 key
2x burst at window edges
Sliding log
timestamps of each request
exact
memory per request
Sliding window counter
current + previous window, weighted
smooth, 2 counters
approximate
Token bucket
tokens refill at rate r, capacity b
allows bursts, smooth rate
2 fields, needs atomic update
Leaky bucket
queue drained at fixed rate
smooth output
adds queueing delay
Token bucket is the usual answer: it expresses "average 100/min, bursts up to 20", and state is two numbers per key.
Atomic token bucket in Redis (Lua script)
-- KEYS[1] = "rl:{api_key}:{rule}" ARGV = rate/s, capacity, now_ms, cost
local b = redis.call("HMGET", KEYS[1], "tokens", "ts")
local rate, cap, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local tokens = tonumber(b[1]) or cap
local ts = tonumber(b[2]) or now
tokens = math.min(cap, tokens + (now - ts) / 1000 * rate) -- refill
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end
redis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("PEXPIRE", KEYS[1], math.ceil(cap / rate * 1000) + 1000)
return { allowed and 1 or 0, math.floor(tokens) }
The script runs atomically on the Redis node, so concurrent requests from different gateways can't both spend the last token. Keys expire when idle, so memory tracks active clients only. Use a single clock source (the gateway's time is fine if clocks are synced; or Redis TIME).
Call Redis with a tight timeout (a few ms). On timeout or error: fail open (allow) for general APIs, since the limiter shouldn't cause an outage; fail closed for abuse-sensitive endpoints (login, OTP).
As a backstop, each gateway also keeps a coarse local limiter so a Redis outage can't let unlimited traffic through.
Follow-up Questions
Round trips to Redis add latency on every request. Can you avoid it?
Batch: each gateway keeps local counters and syncs with Redis every ~100 ms, or leases a slice of the limit (e.g. 10 tokens at a time). You trade some accuracy (small overshoot) for far fewer network calls.
Multi-region: is the limit global or per region?
Usually per region with the limit split (or per region with independent limits), since synchronous cross-region counters would add ~100 ms. Global exactness is rarely worth that; periodic async sync of counts gets close.
How do you rate-limit by IP when many users share one NAT IP?
Prefer authenticated identities (user id, API key); use IP limits only for unauthenticated endpoints, with higher thresholds, and combine with other signals (device, behaviour).
Fixed window allows 200 requests in 2 seconds across a boundary. Why, and does it matter?
100 at 11:59:59 and 100 at 12:00:00 are in different windows. For abuse protection a sliding window or token bucket avoids it; for billing quotas fixed windows are often fine.