Rate limiting algorithms
Rules for deciding whether a request is within a client's allowance: token bucket, leaky bucket, and fixed or sliding window counters. A strong answer says how you handle bursts, share counts across servers, and answer the rejected client.
What it is
A rate limiter decides, request by request, whether a client is still within its allowance over some stretch of time, and what to do with the excess: reject it, hold it until it fits, or let it through marked as over the limit. The allowance is attached to a key. In HTTP APIs the key is typically the client's IP address, and it can be the user or the application when requests are authenticated or carry a cookie. The IETF's RateLimit header draft describes the same shape in its own terms: a quota, measured in units such as requests or bytes, over a time window, scoped to a partition such as one user.
Token bucket. Picture a bucket that holds at most B tokens. Tokens are added at a fixed rate, and any token that arrives when the bucket is full is thrown away. A request checks the bucket: if a token is there, it removes one and passes; if the bucket is empty, nothing changes and the request does not conform. The long-run rate is bounded by the refill rate, and the depth of the bucket sets how large a burst can pass at once, which is why a client that has been quiet for a while can spend its saved-up tokens in one go. A practical implementation stores the token count and the time of the last refill, and on each request adds the tokens earned since then, capped at the capacity, before taking one. Stripe describes its per-user request limiter as exactly this: a central bucket host, one bucket per user, tokens dripping in slowly, a request removing one and being rejected when none are left, with the state kept in Redis.
Leaky bucket. Two different algorithms share this name. As a meter, a conforming request pours a fixed amount of water into a bucket that drains at a constant rate, and a request that would overflow it is rejected; it mirrors the token bucket, and with matching parameters it accepts and rejects the same requests. As a queue, requests sit in the bucket and leave at a steady rate, so the output has essentially no bursts; it shapes traffic rather than policing it, and the cost is waiting time. nginx's limit_req module works this way: excess requests are delayed so that they are processed at the configured rate, up to a burst count; beyond that they are refused, with a 503 status by default (configurable since version 1.3.15). The nodelay option passes the burst at once instead of pacing it, and delay (version 1.15.7) sets how many excess requests go through before pacing starts.
Window counters. A fixed window divides time into intervals that don't overlap and keeps one counter per key per interval, with the interval number in the key, for example user:42:minute:28871280. Each request increments the counter, and once the count passes the limit the request is denied. It costs one counter key that expires on its own, but the boundaries are fixed in time rather than relative to the client: a client that sends its whole allowance at the end of one interval and again at the start of the next has pushed twice the limit through in a moment. A sliding window log stores the timestamp of each request in a sorted set, drops the ones older than the window, and counts what is left; the count is exact over a true rolling window, and the memory grows with the number of requests per key. A sliding window counter keeps the current and previous fixed-window counts and estimates the rolling total as the current count plus the previous count weighted by how much of the current window is still ahead. It stores two counter keys and is an estimate that can land a little above or below the exact count, while smoothing the boundary spike of a plain fixed window.
What the rejected client gets. A 429 Too Many Requests response says the client has sent too much in a given time, and a Retry-After header can say how long to wait before trying again. The RateLimit header draft (draft 12, November 2026, still a work in progress) adds RateLimit-Policy, which advertises each policy's quota and, optionally, its window, and RateLimit, which carries the quota remaining right now and, optionally, the window it applies to; it warns clients that a positive remaining quota is not a promise that the next request will be served. Choose deliberately between 429 and 503 for each situation, and make the error message something the caller can act on.
HTTP/1.1 429 Too Many Requests
Retry-After: 12
RateLimit-Policy: "per-minute";q=100;w=60
RateLimit: "per-minute";a=0;w=12
Content-Type: application/problem+json
{"title": "Rate limit exceeded", "detail": "100 requests per minute per API key. Retry in 12 seconds."}When to use it
Add a limiter when clients can slow down without changing the result of their work: a batch job, a sync script, a dashboard polling for updates. Stripe reports that its per-request rate limiter had rejected millions of requests in the month its post covers, with a notable share from test-mode scripts that had got out of hand, and recommends a request rate limiter as the first one to build. Pick the token bucket when some bursts are legitimate, such as a flash sale where a real client briefly needs more than its usual cap; a fixed per-second ceiling would refuse it, while a bucket sized for the spike lets it through and still holds the average.
Limit something other than the request count when the request count is not what hurts. A concurrent requests limiter caps how many of a client's requests may be in flight at once. It suits CPU-heavy endpoints where slow responses lead callers to retry, and the retries add load to the resource that was already struggling. A quota can be counted in requests, in content bytes or in concurrent requests, and the header fields above can advertise which one applies.
Where the count lives decides what the limit means. A counter in each server's memory limits that server's share of the traffic; a shared store such as Redis limits the client as a whole. If you promise a customer a per-user limit, we'd count across the whole fleet, which means a shared store. That store then becomes a dependency on the request path, so decide up front what happens when it is slow or unreachable. The practice we'd follow: fail open, catching failures in the limiter and letting requests through rather than taking the API down; keep a switch to turn each limiter off; and run each new limit in a watch-only mode first to see what it would have blocked before it blocks anything. nginx offers that watch-only idea as limit_req_dry_run (version 1.17.1), which counts excess requests without delaying or refusing them. The choice between letting traffic through and refusing it has its own page: Failing open or failing closed.
When not to
A limiter is the wrong tool when callers can't space their requests out, which is common for real-time events; the fix there is usually more capacity, not a tighter limit. It is also the wrong tool for an overload that comes from the system itself, a slow database or a lost availability zone: a per-client limit sees each caller as fine while the whole service is drowning. That calls for load shedding, which decides from the state of the system rather than from who is asking, for example by reserving a share of capacity for the most important operations and refusing lower-priority ones when the rest is used up. See Backpressure and load shedding for that side of the problem.
The exact algorithms can be more than the job needs. A fixed window is the right choice for a daily or monthly quota tied to billing: a burst at the window boundary is a cost you can bound and state, and the counter costs one key per client per window. A sliding window log is worth its memory for a small number of high-value keys, such as login attempts per account, and a poor fit for high-volume traffic across a very large number of keys, because its memory grows with each request it remembers. A leaky-bucket queue is right in front of a backend that wants a steady pace and wrong for an interactive API, where the waiting it adds shows up as latency for the caller. And a per-server counter with no shared store is fine when the limit protects that one server's resources, such as a connection pool, rather than enforcing a promise made to a customer.
Compared
| Algorithm | Bursts | State per key | Pick it when | The weaker option is right when |
|---|---|---|---|---|
Token bucket | Up to the bucket size, then the refill rate | A token count and a last-refill time | Clients have legitimate spikes and you want a clear average rate | A strict ceiling per interval matters more than smoothness: use a window counter |
Leaky bucket (queue) | None; output is paced at a constant rate | A queue of waiting requests | The backend wants a steady stream and callers can wait | Callers are interactive and waiting is worse than a refusal: use a token bucket |
Fixed window | Up to twice the limit across a boundary | One counter key with an expiry | Long quotas (a day, a month) or cheap first-pass protection | A per-minute limit must hold at any instant: use a sliding window |
Sliding window log | Bounded by the limit in any rolling window; the count is exact | A sorted set with one timestamp per request in the window | Few keys, high stakes, exact counts required | Keys are many and traffic is high: memory per request is too much, use the counter |
Sliding window counter | Near the limit; the estimate can run slightly over or under | Two counter keys, current and previous window | Rolling limits at scale with little memory | Exactness is required, for instance a contractual limit: use the log |
In a picture
How to say it in an interview
The common mistake
Quiz
Questions that use this
Related
Sources
- Wikipedia: Token bucket
- Redis documentation: Token bucket rate limiter with Redis and Node.js
- nginx documentation: Module ngx_http_limit_req_module
- Stripe Engineering Blog: Scaling your API with rate limiters
- MDN: 429 Too Many Requests
- IETF Internet-Draft: RateLimit header fields for HTTP (draft-ietf-httpapi-ratelimit-headers-12)