Rate Limiting

The big picture#

Everything below expands on these points. Read the core sections top to bottom for the full mental model; the collapsible "Go deeper" box on distributed limiting holds the advanced internals (Redis data structures, GCRA, Lua) you can skip on a first pass.

Start here: why count requests at all?#

A server has finite CPU, memory, and downstream capacity (a database, a third-party API). Without a limit, one misbehaving client — a retry loop, a scraper, a bug — can starve everyone else. This is the noisy-neighbor problem, and retry storms make it worse: a downstream blip makes every client retry at once, and those retries pile onto the very system that's already struggling. Rate limiting caps each client (by API key, IP, or user id) to a budget, and rejects requests over budget so the rest of the fleet stays healthy.

Token bucket: a budget that refills continuously#

A bucket holds up to `capacity` tokens. Tokens refill continuously at `refillRate` tokens/second (not in discrete steps). Every request costs one token: if the bucket has at least one, it's allowed and a token is removed; otherwise the request is denied. Because refill is continuous, a client that's been idle accumulates tokens up to the cap and can spend them all in a single burst — that burst tolerance is the defining trait of a token bucket.

1. On each request, compute elapsed time since the last refill and add elapsed × refillRate tokens, capped at capacity.
2. If tokens ≥ 1, subtract 1 and allow.
3. Otherwise deny — and tell the client roughly how long until the next token (1/refillRate seconds away from a full token).

Notice there's no background timer adding tokens on a schedule. Refill is computed lazily, on demand, from the elapsed time since the last touch — so the entire state for a client is just two numbers: a token count and a last-updated timestamp. That O(1) footprint is why token bucket scales to millions of keys.

Leaky bucket: smoothing into a steady output rate#

Where a token bucket controls the input rate (how fast you can spend tokens), a leaky bucket controls the output rate: requests fill a fixed-size queue, which drains at a constant `leakRate`. If the queue isn't full, the request is queued (allowed) and the level rises by one; if it's full, the request overflows (denied). The level falls continuously between requests as the queue drains.

The practical difference from a token bucket: a token bucket lets a client who's been idle spend a full burst instantly. A leaky bucket forces every request through at (at most) the leak rate, queue or no — it actively smooths bursts into a steady trickle, which is exactly what you want in front of a downstream system that can't handle spikes at all.

Fixed window counter: the simplest implementation, with a real flaw#

Divide time into fixed windows of `windowMs` (e.g. one window per second). Keep one counter per window: increment on each request, reset to 0 whenever the clock crosses into a new window. Allow while the counter is under `limit`. That's the entire algorithm — one integer, one comparison.

Sliding window log: exact, at the cost of memory#

Keep a timestamp for every request, instead of just a count. On each new request, drop every timestamp older than `now - windowMs`, then allow only if fewer than `limit` timestamps remain — and if allowed, record the new timestamp. Because the window is checked relative to *now*, not a fixed grid, there's no boundary to burst across: the count over any trailing windowMs-wide span is always exact.

The cost is storage: O(limit) timestamps per client instead of a single integer, plus the work of pruning on every request. For a client with a small limit this is fine; for millions of clients with high limits it adds up.

Sliding window counter: approximating the log with two integers#

A compromise: keep two fixed-window counters — the current window's count and the immediately previous window's count — instead of every timestamp. Estimate the trailing-window count as `prevCount × overlapWeight + currCount`, where `overlapWeight` is how much of the previous window still falls inside the trailing windowMs-wide span (1.0 right at the window boundary, decaying to 0 by the next boundary).

This assumes requests are spread evenly across the previous window, which isn't always true — so it's an approximation, not exact like the log. In exchange it costs O(1) state per client (two counters) instead of O(limit), which is why it's the choice production rate limiters (e.g. Cloudflare's) actually ship. Cloudflare reported that on 400 million requests from 270,000 distinct sources, only about 0.003% were wrongly allowed or limited versus an exact sliding log — a tiny error for a huge memory saving.

The cost that decides everything: per-client state#

A rate limiter doesn't keep one number — it 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?

Only the sliding log scales with the limit itself. Picture 10 million keys, each limited to 1,000 requests/minute. The four O(1) algorithms need a couple of words per key — call it ~16 bytes, ~160 MB total, comfortably in RAM. The sliding log can hold up to 1,000 timestamps per key — gigabytes, plus the pruning cost on every single request. That memory cliff is the whole reason the approximate sliding-window counter exists, and why exact limiting at scale is rare.

Distributed rate limiting: one limit across many servers#

Everything so far 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 the problem is hard, because per-node limits don't compose.

Two families of fixes, and the choice is the recurring theme of this page — exactness versus latency:

• 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 gossips or syncs totals (e.g. divides the global budget and rebalances). No per-request round-trip, but the global count lags, so the limit is approximate near boundaries.
• Sticky routing: route each client consistently to the same node (by hashing the key at the LB), so its counter lives in exactly one place and a plain in-memory limiter is globally correct for that client. Simple and fast, but it fights load balancing and breaks when nodes are added, removed, or fail.

Failure modes: what breaks at the edges#

• Boundary burst (fixed window): up to 2× the limit across a window boundary, covered above — the reason sliding windows exist.
• Thundering herd at window reset: with a fixed window, every client's budget refreshes at the same instant (e.g. the top of the minute). Clients that were throttled all retry together the moment the window flips, producing a synchronized spike. Token bucket and GCRA avoid this because each client's budget refills on its own continuous schedule, not a shared grid.
• Clock skew across nodes: window and timestamp math depends on time. If two nodes disagree on 'now' by even tens of milliseconds, they'll prune and bucket differently, and a request can be double-counted or missed. Centralize time at the store (use Redis's clock, or its TIME command) rather than each node's local clock.
• Limiter store down: if Redis is unreachable, every request is suddenly undecidable — and you must have chosen a policy in advance.

The trade-offs, in one place#

Three axes run through every decision on this page. Pick where you sit on each and the algorithm mostly falls out.

• 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 (approximate) vs. central (exact): 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 / GCRA force a steady rate. Choose by what's downstream — a cache-friendly API can absorb bursts, a fragile legacy backend cannot.

The five algorithms side by side#

Where rate limiting runs in the wild#

• Stripe — token bucket as the core, with four layered strategies (a request-rate limiter, a concurrent-request limiter, 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 (e.g. 5,000 req/hour authenticated) advertised via X-RateLimit-Limit / -Remaining / -Reset headers and a 403 (primary limit) or 429 (secondary limit) with Retry-After when exhausted.
• Cloudflare — the approximate sliding-window counter described above, running at the edge across millions of domains; chosen for O(1) memory and ~0.003% error over a pure sliding log.
• nginx limit_req — the classic leaky bucket (its docs say so explicitly): 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 stage/route, returning 429 on exceed; Envoy offers both a local token-bucket filter and a global gRPC rate-limit service backed by a shared store.
• Redis cell / GCRA — redis-cell's CL.THROTTLE brings exact, single-key GCRA limiting to anything that can talk to Redis, a common building block for homegrown limiters.

Common questions & gotchas#

In an interview#

Lead with the trade-off, not the list: every algorithm here is trading accuracy against memory. Fixed window is O(1) but bursts at boundaries; the sliding log is exact but O(limit); the sliding counter approximates the log in O(1) by assuming even distribution within a window. Token bucket and leaky bucket are a different axis entirely — they shape *when* a budget can be spent (all at once vs. smoothed) rather than just how it's measured.

Be ready to say which one you'd pick and why: token bucket for a public API that should tolerate bursts, leaky bucket in front of something that genuinely can't handle spikes, sliding window counter when you need window-boundary correctness at scale. Then expect the follow-up that separates juniors from seniors: 'now make it work across 50 servers.' Answer with the shared-store-vs-local trade, name Redis (INCR+EXPIRE, ZSET log, or GCRA/redis-cell), and bring up fail-open vs. fail-closed when that store is down.

Then try it in the simulator: pick fixed window, BURST past the limit right before a window boundary, ADVANCE_TIME just past it, and BURST again — watch the count momentarily allow close to 2× the limit. Switch to sliding window log or counter and repeat the same sequence to see the boundary burst close up.

References & further reading#