Rate limiting

Token buckets, sliding windows, and enforcing them across many servers.

System design conceptQueues, streams and batch1 Nov 2026

01The intuition

The problem it solves

A library lets each student borrow at most five books a week. Without the rule, one student could take every book on the shelf and the rest of the class gets nothing. The rule protects the shared thing from any one user, whether that user is greedy or just has a bug.

An API is the shelf. One client with a loop that forgot to sleep can send 10,000 requests a second, which is more than the service can handle for everyone else. A rate limiter enforces "at most N requests per key per time period", where the key is a user, an API token or an IP address, and answers the over-limit requests with a fast 429 instead of letting them in.

The hard part is not the rule. It is enforcing it across 200 servers that each see a slice of the traffic, within a millisecond, without a central bottleneck that becomes the thing that falls over.

Build it one piece at a time

Step 1: a counter per key per window. Keep a counter named user17:10:03 (user 17, the minute starting 10:03). Each request increments it; if the result exceeds 100, reject. This is a fixed window. Its flaw: a user can send 100 requests at 10:03:59 and 100 more at 10:04:00, 200 in two seconds, and never be stopped.

Step 2: the token bucket. Each key owns a bucket that holds up to B tokens and refills at r tokens a second. A request takes one token; if the bucket is empty, it is rejected. Store only two numbers per key: tokens and the time of the last refill. On each request, add r × elapsed seconds (capped at B), then subtract one.

Time	Tokens before refill	Refill (r = 10/s, B = 20)	After request	Decision
0.0 s	20	+0	19	allow
0.1 s	19	+1	19	allow
burst of 25 at 0.1 s	19	+0	0 after 19 allowed	6 rejected
2.1 s	0	+20 (capped)	19	allow

The bucket allows a short burst up to B and a long-run average of r, which is what most APIs want.

Step 3: the sliding log, when exactness matters. Store the timestamps of a key's recent requests, drop those older than the window, and count what is left. Exact, but memory grows with the limit; fine for "10 password attempts per hour", wasteful for "10,000 reads per minute".

Step 4: share the state. Two hundred servers must see one bucket per key. Put the buckets in a fast shared store (Redis) and do the refill-and-take in a single atomic script so two servers cannot both take the last token. Route each key to one shard by hashing, so a key's bucket lives in one place and the store scales by adding shards.

Step 5: cut the round trip. A shared-store call costs about a millisecond on every request. Give each server a local bucket with a slice of the quota, say 1/200 of r, and let it sync with the shared store every 100 ms. The limit becomes approximate by a few percent, and the hot path touches no network.

Why it works, with the numbers

The token bucket's promise: in any interval of length t seconds, at most

allowed(t) ≤ B + r × t

requests pass. At r = 100 a second and B = 200, a minute admits at most 6,200, and a 10-second burst at most 1,200. Memory is two numbers per active key: 10 million keys cost about 200 MB. The failure modes: a shared store that is down (decide to fail open and let traffic through, or fail closed and block everyone; most choose open for ordinary APIs and closed for login), clocks that differ between servers (use the store's clock), and a key choice that is too coarse, where one shared office IP counts as one user.

The trade-off you must say out loud

Accuracy against latency and cost. A central store is exact and adds a round trip; local buckets are fast and slightly over-admit. Say the key you limit on, the limits and burst, what the client receives (429 with Retry-After and the remaining quota in headers), and what happens when the limiter itself fails. The follow-up is "how does the client know its quota", and the answer is the response headers.

Where it shows up in the 100 Google problems

Distributed rate limiter: this design in full, with the atomic script and the local-bucket optimisation as deep dives.
API gateway: limiting happens at the door, per token and per route.
Web crawler: a bucket per host so the crawler stays polite to small sites.
Authentication platform: strict sliding-log limits on login attempts per account and per IP.
Notification system: per-user limits so one app cannot buzz a phone a hundred times an hour.