0002 · Traffic · 8 min
· Alex Xu, System Design Interview Vol 1, Ch. 4
A rate limiter caps how many requests a client may make in a window. Put it at the API gateway,
return 429 when the budget is exceeded, and pick from four classic algorithms that trade burst
tolerance against memory and accuracy.
QPS (Queries Per Second)
Requests processed by a server or database each second — the unit you size capacity in.
Token Bucket
Refills tokens at a steady rate r up to capacity b; allows short bursts up to b. The industry default (Stripe, AWS).
Where it sits
Place the limiter at the API gateway — the edge proxy every request already crosses — so rejected
traffic never reaches expensive backends. In a distributed fleet, all gateway nodes must share
counters (typically in Redis) or a client can dodge the limit by spreading requests across nodes.
ClientAPI gateway · rate limiter
API gateway
under budget→Backend
over budget→429 Too Many Requests
Shared counters live in Redis, so every gateway node enforces one budget.
Choosing an algorithm
Token bucket allows bursts up to bucket size and is the common default. Fixed-window counters are
cheapest but let traffic spike to 2× the limit at window edges. Sliding-window logs are exact but
store a timestamp per request in a Redis sorted set. Pick based on how much burst you can tolerate
versus how much memory you’ll spend.
Check yourself
1A client is being rejected by the limiter. What status code does it get?
429 signals the client exceeded its budget and may retry later — not 503 (server overloaded) or 403 (never allowed).
2You must tolerate short bursts up to a fixed size but hold a steady average rate. Which algorithm?
Token bucket refills at rate r up to capacity b, so it permits bursts up to b while bounding the long-run rate.
3Why must gateway nodes in a fleet share limiter state?
With per-node counters a client hitting N nodes gets N× the budget. Shared state gives every node one view.