Start here: why count requests at all?#
TL;DRthe 30-second version
- A rate limiter decides per request, accept or reject. It caps each client (by API key, IP, or user id) to a budget so one bad actor can't starve everyone. Over-budget requests get a fast HTTP 429.
- Five classic algorithms trade accuracy against cost. Token bucket and leaky bucket are O(1) per client. Fixed window is one counter but bursts at boundaries. Sliding-window log is exact but O(limit) memory. Sliding-window counter is approximate and O(1), and it's what Cloudflare ships.
- Token and leaky bucket shape when a budget is spent (all at once, or smoothed). The window algorithms measure how much was spent over a span. Interviewers like it when you separate those two axes.
- The hard part is many servers. Per-node limits don't add up to a global limit, so production limiters keep counters in a shared store (usually Redis) and choose between exact-but-central and approximate-but-local.
A server has finite CPU, memory, and downstream capacity. Without a limit, one misbehaving client can starve everyone else: a retry loop, a scraper, a bug. Retry storms make it worse, because a downstream blip makes every client retry at once, and those retries pile onto the system that's already struggling. Rate limiting caps each client to a budget and rejects the rest, so the fleet stays healthy for everyone else.
Token bucket first, then the window counters#
A token bucket holds up to `capacity` tokens. Tokens refill continuously at `refillRate` tokens per second. Every request costs one token: if the bucket has one, the request is allowed and a token is removed; otherwise it's denied. Because refill is continuous, a client that's been idle banks tokens up to the cap and can spend them all in one burst. That burst tolerance is the defining trait of a token bucket.
- On each request, compute the time since the last refill and add elapsed × refillRate tokens, capped at capacity.
- If tokens ≥ 1, subtract 1 and allow.
- Otherwise deny, and tell the client roughly how long until the next token (1/refillRate seconds).
capacity = 5 tokens · refill = 1 token / second · ★ = a token, · = empty slot
There's no background timer adding tokens. Refill is computed lazily, from the time since the last touch. So the whole state for a client is two numbers: a token count and a timestamp. That O(1) footprint is why token bucket scales to millions of keys.
A leaky bucket flips the control to the output side. Requests fill a fixed-size queue that drains at a constant `leakRate`. If the queue has room, the request is queued and allowed. If it's full, the request overflows and is denied. Where a token bucket lets an idle client burst, a leaky bucket forces every request through at the leak rate. That smoothing is what you want in front of a downstream system that can't handle spikes at all.
A fixed window counter is the simplest thing that works. Divide time into windows of `windowMs`, say one per minute. Keep one counter per window: increment on each request, reset to zero when the clock crosses into a new window, allow while the counter is under `limit`. One integer, one comparison. It has a real flaw.
PredictLimit is 100 requests per minute with a fixed window. A client fires 100 requests at 11:00:59 and 100 more at 11:01:00. Did the limiter do its job?
Hint: Count per fixed window vs. count over any trailing 60 seconds.
Each burst lands in a separate window, so the fixed-window limiter allows both. That's 200 requests in about one second, double the intended rate. This boundary burst is the whole reason sliding windows exist.
A sliding window log closes that gap exactly. Keep a timestamp for every request instead of a count. On each new request, drop every timestamp older than `now - windowMs`, then allow only if fewer than `limit` remain. The window is measured from now, not from a fixed grid, so there's no boundary to burst across. The cost is memory: O(limit) timestamps per client instead of one integer, plus the pruning work on every request.
A sliding window counter approximates the log with two integers: the current window's count and the previous window's count. It estimates the trailing-window count as `prevCount × overlapWeight + currCount`, where `overlapWeight` is how much of the previous window still falls inside the trailing span.
limit = 100 / 60s · now = 15s into the current window
This assumes requests were spread evenly across the previous window, so it's an approximation. In exchange it costs O(1) per client. Cloudflare measured it on 400 million requests from 270,000 sources: only about 0.003% were wrongly allowed or limited versus an exact log. That's why it's the one production limiters at scale actually ship.
The cost that decides everything: per-client state#
A rate limiter keeps state for every active key, and there can be millions of them: one per API key, per IP, per user, sometimes per route. So the question that picks the algorithm in practice is how many bytes, and how much work, per key per request.
| Algorithm | State per key | Work per request |
|---|---|---|
| Token bucket | O(1) — count + timestamp | O(1) |
| Leaky bucket | O(1) — level + timestamp | O(1) |
| Fixed window | O(1) — one counter (+ window id) | O(1) |
| Sliding window counter | O(1) — two counters | O(1) |
| Sliding window log | O(limit) — a timestamp per request in window | O(limit) to prune |
Only the sliding log grows with the limit itself. Picture 10 million keys, each limited to 1,000 requests a minute. The four O(1) algorithms need a couple of words per key, about 16 bytes, so around 160 MB in total, which fits in RAM. The sliding log can hold up to 1,000 timestamps per key: gigabytes, plus pruning on every request. That memory cliff is why the approximate counter exists and why exact limiting at scale is rare.
One limit across many servers, and the trade-offs it forces
Everything above assumed a single process holding the counter. Real APIs run behind a load balancer across dozens or hundreds of nodes, and any node might handle any client's request. Now it's hard, because per-node limits don't compose.
- Shared store (central, exact): every node reads and updates one counter in a fast shared store, almost always Redis. Exact global enforcement, at the cost of a network round-trip per request and a dependency that must stay up.
- Local + async reconciliation (distributed, approximate): each node keeps a local counter and periodically syncs totals. No per-request round-trip, but the global count lags, so the limit is approximate near the edge.
- Sticky routing: hash each client to the same node at the load balancer, so its counter lives in one place and a plain in-memory limiter is correct for that client. Simple and fast, but it fights load balancing and breaks when nodes are added, removed, or fail.
In Redis, a fixed window is INCR on the window's key plus EXPIRE on the first increment. An exact sliding log is a sorted set per key: ZREMRANGEBYSCORE to prune, ZCARD to count, ZADD to record. A token bucket is a small Lua script that reads {tokens, lastRefill}, refills, and decrements atomically, so two nodes can't both spend the last token. GCRA stores one value instead, the Theoretical Arrival Time: the earliest instant the next request is allowed. Compare now to it, push it forward on success, and the gap to it is exactly the Retry-After. The redis-cell module ships GCRA as one atomic command, CL.THROTTLE.
- Accuracy vs. memory: the sliding log is exact but O(limit) per key; the sliding counter is approximate but O(1). At millions of keys, approximate almost always wins.
- Local vs. central: a per-node in-memory limiter is fast and has no dependency but can't enforce a global limit; a shared Redis counter is globally exact but adds a round-trip and a hard dependency on every request.
- Burst tolerance vs. smoothness: token bucket forgives idle clients a burst; leaky bucket and GCRA force a steady rate. Choose by what's downstream.
The five algorithms side by side
| Algorithm | Accuracy | Memory / key | Burst behavior | Best for |
|---|---|---|---|---|
| Token bucket | Good | O(1) | Allows bursts up to capacity | Public APIs, burst-friendly clients |
| Leaky bucket | Good | O(1) | Smooths to a steady output rate | Protecting a spike-intolerant backend |
| Fixed window | Poor (boundary burst) | O(1) | Up to 2× at boundaries | Simple internal limits, coarse caps |
| Sliding window log | Exact | O(limit) | No boundary burst | Low-volume, high-stakes limits |
| Sliding window counter | Near-exact (~0.003% err) | O(1) | No meaningful boundary burst | High-scale limiting (Cloudflare) |
Where rate limiting runs in the wild
- Stripe — token bucket as the core, with four layered strategies (request rate, concurrent requests, a fleet-usage load shedder, and a worker-utilization limiter) so one customer's surge can't take down a payments API.
- GitHub — token-bucket-shaped REST limits (5,000 req/hour authenticated), advertised via X-RateLimit-Limit / -Remaining / -Reset headers, with Retry-After when exhausted.
- Cloudflare — the approximate sliding-window counter, running at the edge across millions of domains, chosen for O(1) memory and ~0.003% error.
- nginx limit_req — a leaky bucket: requests queue and drain at a fixed rate, with an optional burst parameter and nodelay mode.
- AWS API Gateway — token bucket with a steady rate and a burst capacity per route, returning 429 on exceed. Envoy offers both a local token-bucket filter and a global rate-limit service backed by a shared store.
What breaks at the edges
- Thundering herd at window reset: with a fixed window, every client's budget refreshes at the same instant, so every throttled client retries together the moment the window flips. Token bucket and GCRA avoid this because each client refills on its own continuous schedule.
- Clock skew across nodes: window and timestamp math depends on time. If two nodes disagree on 'now' by tens of milliseconds, a request can be double-counted or missed. Use the store's clock (Redis TIME) rather than each node's.
- INCR then EXPIRE as two commands: if the process dies between them the key never expires and leaks. Do both atomically, in a MULTI transaction or a Lua script.
- Several Redis commands per decision without a Lua script or MULTI: two nodes can interleave the read-modify-write and both spend the last token.
- Giving 10 nodes 10 identical local counters of 100/min: round-robin lets one client through at roughly 1,000/min, and a window reset can nearly double that again.
In an interview
Lead with the trade-off, not the list. Every window algorithm trades accuracy against memory. Token bucket and leaky bucket are a different axis: they shape when a budget can be spent. Say which you'd pick and why, then expect the follow-up that separates juniors from seniors: 'now make it work across 50 servers.'
Token bucket or leaky bucket, which one allows bursts?
Token bucket. A client that's been idle banks tokens up to the cap and can spend them at once. A leaky bucket drains at a fixed rate no matter what, so it smooths bursts into a steady trickle. Use it in front of something that can't handle spikes.
Why reject over-budget requests instead of queuing them?
An unbounded queue hides the overload: latency climbs until the system falls over. A fast 429 fails cheaply and hands the decision back to the client, which backs off and retries later. Limiting and queuing are different tools.
Which algorithm would you pick?
Token bucket for a public API that should tolerate bursts. Leaky bucket in front of something that can't handle spikes. Sliding window counter when you need window-boundary correctness at scale. Sliding log only for low-volume, high-stakes limits like login attempts.
How do you rate-limit across many servers?
Per-node counters can't see the global total. Keep the counter in a shared store, usually Redis: INCR+EXPIRE for a fixed window, a sorted set for an exact sliding log, or GCRA via redis-cell, wrapped in Lua so the read-modify-write is atomic. High-scale systems often go approximate instead: local counters with periodic reconciliation, or sticky routing. Then say what happens when Redis is down: fail open to a local limit, or fail closed for login and payments.
What does the client get back?
HTTP 429 Too Many Requests, with a Retry-After header saying how long to wait, and increasingly the standardized RateLimit headers describing remaining quota so clients can slow down before being rejected.
References & further reading
- Cloudflare — How we built rate limiting capable of scaling to millions of domains — the approximate sliding-window counter, and the 0.003% error analysis
- Stripe — Scaling your API with rate limiters — token bucket plus four layered strategies in a payments API
- Brandur Leach — Rate Limiting, Cells, and GCRA — the clearest walkthrough of GCRA and the Theoretical Arrival Time
- IETF — RateLimit header fields for HTTP (draft-ietf-httpapi-ratelimit-headers) — standardizing RateLimit / RateLimit-Policy signaling