Rate Limiting

Rate limiting is used for three distinct reasons and the algorithm and key should follow from which one you have. Protection: a service can handle 5,000 requests/s and must reject the 6,000th rather than slow down for everyone — see Backpressure for the same idea inside a pipeline. Fairness: one tenant of a multi-tenant API should not consume the capacity paid for by the others, so the limit is keyed per tenant or API key. Cost and abuse: password attempts, SMS sends and LLM calls cost money or open attack surface, so the limit is keyed per user or per IP and set well below capacity. A notification system applies all three at once — a per-user limit so nobody receives 200 pushes, a per-provider limit because the SMS gateway allows 100 messages/s, and a global limit to protect the workers.

A fixed window counts requests in each calendar interval (key:2026-08-25T10:04) with a counter that expires. It is one INCR and one EXPIRE, and it has a boundary problem: a limit of 100/minute allows 100 requests at 10:04:59 and 100 more at 10:05:00 — 200 in two seconds. A sliding log stores every request timestamp and counts those within the last window; it is exact and it costs memory proportional to the limit per key — fine for 100/minute, not for 10,000/second. A sliding window counter approximates the log with two fixed-window counters weighted by how far into the current window you are: prev × (1 − elapsed/window) + curr; it is O(1) memory and within a few percent of exact. A token bucket holds up to capacity tokens, refills at rate per second, and each request takes one; a full bucket allows a burst of capacity, then a sustained rate. A leaky bucket is the same maths from the other side: requests enter a queue of bounded size that drains at a fixed rate, so output is perfectly smooth and the burst is absorbed as latency rather than passed through.

Token bucket is the usual default because "sustained rate plus a bounded burst" is what most APIs actually want to promise, and its state is two numbers per key. Leaky bucket is right when the *downstream* cannot take bursts at all — an SMS provider that drops anything over 100/s, or a pipeline that must be smoothed. The DSA transfer is direct: the sliding window is Sliding Window (Fixed Size) applied to timestamps, the leaky bucket is a bounded Queue with a metronome consumer, and every one of them keys its state in a Hash Map.

The bucket does not need a timer. It refills lazily: on each request, compute how many tokens have accrued since the last refill, cap at capacity, then try to take one. The whole state is tokens and last. In a single process this is the code below; in Redis it is the same code as a Lua script so the read-modify-write is atomic across gateway instances.

Enforce as early as the key allows. Per-IP and per-API-key limits belong in the API gateway or load balancer, where a rejected request costs microseconds and never reaches a service; see API Gateway. Per-tenant and per-operation limits often need context only a service has (plan tier, remaining quota), so they are enforced there. Limits on outbound calls to a provider belong in the client that calls the provider — a token bucket sized to the provider’s contract, shared across workers. Layer them: a gateway limit protects the platform, a service limit enforces the business rule, an outbound limit protects the dependency.

With more than one gateway instance the counter must be shared, and Redis is the usual store because INCR is atomic and keys can expire. The trap is doing it in two round trips: INCR then EXPIRE is a race in which a crash between them leaves a key that never expires and a client locked out forever. Either pipeline them in a MULTI block, or — better — run a small Lua script so the check, refill and decrement are one atomic operation on the server. Redis Cluster shards keys by hash slot, so a per-client key lands on one node and there is no cross-node coordination. Precision has a price: a few percent of over-admission from local, per-instance buckets is often acceptable and removes the Redis round trip from the hot path entirely.

A rejected request gets 429 Too Many Requests, a Retry-After header in seconds (from the bucket’s refill maths or the window’s TTL), and ideally the RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset headers on every response so a well-behaved client can pace itself before being rejected. The limiter should be cheap to hit: a 429 that costs the same as a served request has not protected anything, which is why it lives at the edge. Log and count rejections per key; a tenant hitting their limit continuously is either abusing the API or has outgrown their plan, and both are worth knowing.

The client’s obligations are the mirror image: honour Retry-After rather than retrying immediately, back off with jitter if the header is missing, and never treat 429 as a transient error to retry in a tight loop — that converts a polite rejection into a retry storm, which is the scenario in Circuit Breaker arriving from the other direction.