Rate limiting: token buckets, windows, and the distributed catch

An unprotected endpoint trusts every caller to be reasonable, and callers are not reasonable. A buggy client retries in a tight loop. An attacker brute-forces a login or scrapes your data. One enterprise tenant fires ten thousand requests a second and starves everyone else. A downstream you pay per-call gets hammered and hands you a surprise invoice. Rate limiting is the seatbelt for all of these: a cap on how many requests a given client may make in a given window, with the excess rejected — conventionally with HTTP 429 Too Many Requests and a Retry-After header telling the client when to come back.

It's a small idea with a surprising amount of depth, because how you count matters, what you count per matters, and the whole thing quietly breaks the day you run more than one server.

Why and where

The motivations are worth separating because they change what you limit and how hard:

• Abuse and security — throttle brute-force logins, credential stuffing, scraping. These want strict, per-identity limits on sensitive endpoints.
• Fairness — stop one client from monopolizing a shared resource, so all tenants get a slice. Per-tenant limits.
• Stability — cap total load so a traffic spike (or a retry storm) can't exhaust the service. This overlaps with load-shedding.
• Cost control — bound calls to a metered downstream (an SMS gateway, a maps API, an LLM) so usage can't run away.

A limiter can live at the edge (the load balancer, API gateway, or CDN — cheap, before the request costs you anything) or in the application (a middleware/guard that knows the authenticated user and per-route rules). Serious systems often run both: a crude high ceiling at the edge, precise per-user/per-route limits in the app.

The four algorithms

This is the heart of it. All four answer "has this client exceeded its allowance?" — they differ in accuracy, memory, and how they treat bursts.

Fixed window. Keep one counter per client per clock window ("requests this minute"). Increment on each request; if it exceeds the limit, reject; reset the counter when the window rolls over. Dead simple, one integer per client, trivially cheap. Its flaw is the boundary burst: because the counter resets at the window edge, a client can spend its entire allowance in the last second of one window and its entire allowance in the first second of the next — 2× the limit in a two-second span, straddling the reset. For many uses that's tolerable; for strict limits it's a real hole.

Sliding window log. Store a timestamp for every request, and to check the limit, count how many timestamps fall in the trailing window (e.g. "the last 60 seconds," continuously). Perfectly accurate, no boundary artifact — but memory grows with request volume (one entry per request), which is expensive at scale.

Sliding window counter. The practical compromise: keep per-window counts and approximate the sliding window by weighting the previous window's count by how much it still overlaps the current moment. Almost as smooth as the log, almost as cheap as fixed window — a common production default.

Token bucket. A bucket holds up to N tokens and refills at a steady r tokens/second. Each request removes a token; an empty bucket means reject. The elegance is that it separates burst capacity from sustained rate: the bucket size N is how big a burst you tolerate, and the refill rate r is the long-run average you allow. A client that's been quiet accumulates a full bucket and can burst N requests, then is throttled to r/second. This models real traffic ("mostly quiet, occasionally bursty") better than a flat window, which is why it's the most widely used algorithm.

Try the token bucket. Let it refill to full, then hit Burst ×10 — the quiet client spends its whole bucket at once, then gets throttled to the refill rate until tokens build back up. Lower the rate and the throttling bites sooner.

Leaky bucket. Requests enter a queue that drains at a fixed rate; if the queue overflows, reject. Where token bucket allows bursts through, leaky bucket smooths them out — output is a constant trickle regardless of how bursty the input was. Use it when the thing you're protecting needs a steady, even flow (a downstream that dislikes bursts) rather than "bursts are fine, just cap the average."

The one-line way to hold the two bucket algorithms apart: token bucket caps the average and permits bursts; leaky bucket forces a smooth rate and absorbs bursts into a queue.

What to key on

A limit is always per something, and the choice has sharp edges:

• Per IP — works for anonymous traffic, but it's crude: many users behind one office NAT or mobile carrier gateway share an IP, so limiting per IP can throttle a whole building for one bad actor — and a determined attacker just rotates IPs and sails through. Necessary for unauthenticated endpoints, imperfect everywhere.
• Per user / per API key — the right key once you know who's calling: precise, fair, and immune to IP games. This is what you want for authenticated routes.
• Per endpoint — limits should differ by route: a login or password-reset endpoint deserves a far stricter limit than a read. One global limit is almost always wrong.

Whatever the key, the rejection should be a 429 with Retry-After, and well-behaved clients should back off — ideally exponential backoff with jitter, so a thundering herd of rejected clients doesn't all retry in the same instant and re-create the spike.