Rate Limiting
Token buckets, leaky buckets and sliding windows: how an API says 429 to one noisy client so that everyone else still gets served, and where that decision lives.
An interactive System Design lesson: 23 steps, about 30 minutes, on a live simulation in your browser.
Two customers call one API. client-a and client-b each send 160 requests a second through the gateway to api. The gateway can limit traffic, but right now it lets everything through.
The api works on 4 requests at a time for 10 ms each, and up to 16 more may wait in its queue. That is about 400 requests a second of capacity. The two customers together send 320, so every request succeeds and the p99 is 22 ms: 10 ms of work plus the network.
What you will learn
One noisy client
- An API with no limit: Capacity is a budget in requests per second. When the traffic stays inside it nobody waits; everything in this lesson is about what happens when it does not.
- One client floods the API: Without a limit, the heaviest client sets the service level for everyone: overload does not stay with the client that caused it.
Saying no: 429
- A limit at the gateway: A rate limit turns overload into refusals: a cheap, fast, explicit 429 at the door instead of slow 503s from deep inside the system.
- One refusal, hop by hop: 429 means you are over your allowance and should come back later; 503 means the server is in trouble. Retry-After says when.
Token bucket
- A bucket of tokens: A token bucket allows a burst up to its size, then the refill rate: bucket size is the burst, refill rate is the average.
- How much of a burst gets through
- Quiet time earns a burst: Idle time turns into burst allowance, up to the bucket size and no further.
- Drill: token-bucket arithmetic
Leaky bucket
- A leaky bucket queues the burst: A leaky bucket trades latency for smoothness: the service behind it sees a constant rate, and the client pays for its burst in waiting time.
- Leaky bucket under a flood
Counting in windows
- Fixed window: a counter per second
- Across the window edge: A fixed window forgets everything at the edge, so a client can get twice the limit in a moment by bursting on both sides of it.
- Sliding log: exact, and costly: A sliding log is exact because it remembers every request, and it costs memory in proportion to the limit.
- Sliding window counter: A sliding window counter is two counters and one multiplication: nearly the accuracy of the log at the cost of a fixed window.
Whose limit
- Who pays under a global limit: A global limit protects the service, not the customers: the noisy client still takes the victim's share.
- One bucket per client: Fairness needs a key: a limit per API key or user gives each customer their own budget, so one customer's flood is their problem alone.
Where the limit lives
- The limit in nginx
- Two gateways, one limit: A limit enforced on several machines is only as tight as the counter they share, and that counter must be updated atomically.
- Drill: the nginx zone
- What a well-behaved client does: A good client treats 429 as a schedule: wait as long as Retry-After says, otherwise back off exponentially with random jitter, then give up.
- Drill: pick the algorithm
Recap & playground
- Cheat sheet
- Playground