System designCore12 min
Rate limiting algorithms
Cap how fast each client can call you, so one noisy caller, buggy script or attack can't take the service from everyone else. Five ways to count, the one most APIs choose, and how to keep one count across many servers.
An API that serves every caller
Every client calls the service with its own API token, and the service answers whatever arrives.
1 · The problem
One buggy script can take the service from everyone
A shop's orders API serves the apps its sellers build. Each app calls with its own API token. The orders service can answer 5,000 requests a second, and on a normal afternoon about 3,500 arrive from 2,000 sellers.
Then one seller ships a sync script with a bug: when a call fails, it calls again at once, in a loop. It sends 3,000 requests a second. Now 6,500 arrive for 5,000 places, and the extra 1,500 a second pile up in a queue (Throughput, utilization & queueing has the arithmetic). Within seconds every seller's request is slow, and soon every one times out.
3,500 + 3,000 = 6,500 a second against room for 5,000. One client out of 2,000 sends almost half the traffic, and everyone pays for it.
Nothing in the path asks who is calling or how often. A rate limiter does: it counts each client's requests and refuses the ones over that client's limit, before any real work is done. The buggy script gets refusals; everyone else gets their usual answers.
What to count by is the first decision, the key:
- An API token or account is the fairest key: it names the customer who agreed to the limit.
- A signed-in user works for apps where people, not programs, call.
- An IP address is the fallback for anonymous traffic. It is rough: thousands of people behind one office or mobile network share an address, and an attacker can rotate through many.
2 · The answer
A limiter refuses early, cheaply, and says when to come back
Limits usually run at the edge, in the API gateway (Reverse proxies & API gateways), so a refused request costs a counter check and nothing else. The refusal itself is standard HTTP:
- 429 Too Many Requests means this client sent too many in a given time. Caches must not store it.
- Retry-After says when to try again, as seconds (
Retry-After: 1) or as a date. - Many APIs also send the remaining quota on every answer, so a well-behaved client slows down before it is refused.
The service never sees the 101st request. The app learns how much room it had left, and how long to wait once it ran out.
There is no single standard for the quota headers yet. GitHub's REST API, for example, sends x-ratelimit-limit, x-ratelimit-remaining and x-ratelimit-reset (when the window resets, in Unix seconds). An IETF draft from 2025 proposes standard RateLimit and RateLimit-Policy fields, such as RateLimit: "default";r=50;t=30: 50 left, more in 30 seconds.
Use 429, not 503. A 503 Service Unavailable says the service itself is overloaded, which is a different problem with its own fixes. Rate limiting is about one client, and the rest of the service is fine. Some tools default to 503 anyway; NGINX's limiter does until you set limit_req_status 429.
A refused client should wait as told, then back off with jitter if it is refused again (Timeouts, retries, backoff & jitter). A client that retries a 429 at once only adds to the count against it.
3 · Counting by the clock
A fixed window lets twice the limit through at each reset
The simplest count is a fixed window: one counter per key for each second (or minute), reset when the clock ticks over. With a limit of 100 a second it is one number per key, and one comparison per request. It has a gap at every reset.
- Sent by one client
- The limit
100 requests at 0.99 s and 100 more at 1.01 s. Each window's counter sees 100 and allows all of them, yet any one-second stretch from 1.01 s to 1.99 s holds 200: double the limit.
Two ways to close the gap:
- A sliding log keeps the time of every request and counts those in the last second. It is exact, but it stores one timestamp per request: up to 100 × 8 bytes = 800 bytes per key here, against 16 bytes for two counters, and it grows with the limit.
- A sliding window counter keeps only this window's count and the last one's, and assumes the last window's requests were spread evenly. It adds the share of the last window that still falls inside the past second.
Time | Last second, this second | Estimate | Room left |
|---|---|---|---|
1.01 s | 100, then 0 | 100 × 0.99 + 0 = 99 | 1 |
1.50 s | 100, then 1 | 100 × 0.50 + 1 = 51 | 49 |
1.90 s | 100, then 50 | 100 × 0.10 + 50 = 60 | 40 |
Just after the reset, nearly all of the first burst still counts, so the second burst is refused. Half a second later, half of it still counts. The estimate is not exact, because real requests are not spread evenly, but it is close: one large CDN measured 0.003% of 400 million requests wrongly allowed or refused with this method.
4 · The usual choice
A token bucket allows a steady rate and short bursts
Real clients are bursty: an app opens and makes twenty calls at once, then nothing for a while. A token bucket allows exactly that, with two numbers per key:
- The bucket holds up to b tokens
For example 20, and it starts full.
- Tokens drip in at rate r
For example 10 a second, never beyond b.
- Each request takes one token
No token left: refuse with 429.
- So bursts pass, averages don't
A quiet client can send 20 at once, but over time cannot average more than 10 a second.
Follow one idle key with b = 20 and r = 10 a second:
Time | Tokens | Requests arriving | Result |
|---|---|---|---|
0 s | 20 (full) | 30 at once | 20 allowed, 10 refused; 0 left |
0.5 s | 5 (dripped in) | 8 | 5 allowed, 3 refused; 0 left |
1.0 s | 5 | 2 | 2 allowed; 3 left |
3.0 s | 20 (3 + 20, capped at 20) | none | 20 waiting for the next burst |
No timer needed: refill lazily on each request
function allow(b: { tokens: number; at: number }, rate: number, size: number, now: number) {
b.tokens = Math.min(size, b.tokens + ((now - b.at) / 1000) * rate);
b.at = now;
if (b.tokens < 1) return false;
b.tokens -= 1;
return true;
}Nothing ticks in the background: each request first adds the tokens earned since the last one, so a million idle keys cost nothing but their two stored numbers. This is the algorithm behind many public APIs. Amazon API Gateway, for example, throttles with a token bucket and calls its two numbers the rate and the burst.
The catch is that the burst is allowed by design. If the service behind the limit cannot take 20 requests from every client at the same moment, size b for the service, not only for the client.
5 · Smoothing instead
A leaky bucket makes bursts wait instead of passing them
Leaky bucket names two different things, so check which one a tool means:
- As a meter, it is the token bucket in a mirror: each request pours water in, the water leaks out at the rate, and a full bucket refuses. The decisions are the same. A precise form of it, the generic cell rate algorithm (GCRA), stores just one timestamp per key.
- As a queue, requests wait in a bounded queue that drains at a fixed rate. Bursts are not refused at once and not passed at once: they wait, and only an overflowing queue refuses.
A rate of 1 a second with room for 5 waiting. Of a burst of 8, the first goes through at once, 5 wait their turn a second apart, and 2 are refused.
NGINX's request limiter works this way: with rate=1r/s and burst=5, the first request of a burst goes through at once, up to 5 more wait their turn, and the rest are refused. Adding nodelay passes the burst at once instead, which behaves like a token bucket. The queue suits a backend that must see an even pace; it is a poor fit for an API whose callers would rather get a fast 429 than a slow answer.
Algorithm | How it counts | Memory per key | Catch |
|---|---|---|---|
Fixed window | One counter per window, reset on the clock | One number | Twice the limit across a reset |
Sliding log | A timestamp per request | One entry per request | Exact, but memory grows with the limit |
Sliding window counter | This window plus a weighted share of the last | Two numbers | Close to exact, not exact |
Token bucket | Tokens drip in; each request takes one | Two numbers | Bursts up to the bucket size, by design |
Leaky bucket queue | Requests wait and drain at a fixed rate | A queue | Smooth, but bursts wait instead of passing |
6 · Across many servers
Ten gateways need one count, or a fair share each
One gateway is rarely enough, so there are ten behind a load balancer. If each counts only what it receives, a client spread across all ten gets 100 a second from each: 1,000 a second, ten times its limit. Three ways out:
Approach | How | Trade-off |
|---|---|---|
Shared counters | Every gateway updates the key's counter in a shared store, such as Redis, in one atomic step | Exact; costs a store call per request, and refusals hit the store too |
Split the limit | Each of N gateways allows the limit ÷ N on its own | No extra call; unfair when a client's traffic is uneven |
Local buckets, settled on a timer | Each gateway counts in memory and syncs with the store every 100 ms or so | Off the request path; a client may be refused a little early |
A shared counter must be updated in one step. Redis's documented pattern is INCR on a key per client per second, with an EXPIRE so old keys disappear. Sent as two separate commands, a gateway that crashes between them leaves a counter that never expires. Send both in one MULTI/EXEC transaction, or in one Lua script.
Then decide what happens when the counter store is down:
- Fail open: let requests through unlimited for a while. Many limiters choose this; Envoy's rate limit filter, for example, allows requests by default when its rate limit service errors.
- Fail closed: refuse everything. The limiter then turns a counter outage into a full outage.
Either way, start a new limit in log-only mode, recording what it would have refused, before it refuses anything.
The rate limiter design later on this path takes the third row: gateways count locally and settle with the store every 100 ms, so the store is never on a request's path.
7 · In a real system
Watch one client flood a rate-limited API
Rate Limiter System Design
One client goes from 2,000 to 20,000 requests a second
Run the flood scenario: one client's traffic jumps tenfold. Its own bucket runs dry and it gets 429s, while every other client's answers stay as fast as before.
Check yourself
5 questions
Takeaways
Remember this
- Limit per key at the edge, and refuse with 429 and Retry-After before any real work is done.
- A fixed window lets twice the limit through around each reset; a sliding window counter fixes that with two numbers per key.
- A token bucket allows a steady rate with bursts up to its size, and refills lazily on each request.
- A leaky bucket as a queue smooths bursts by making them wait; as a meter it decides like a token bucket.
- Across many gateways, share the counter atomically, split the limit, or count locally and settle on a timer, and decide whether to fail open.