Rate limiter

Why limit at all

A rate limiter protects a shared resource from being monopolised — accidentally (a runaway retry loop) or deliberately (abuse, credential stuffing, scraping). Without one, a single client’s spike becomes everyone’s outage: the expensive endpoint saturates, the queueing curve goes vertical, and well-behaved clients eat the latency caused by one misbehaving one. Stripe describes exactly this — a user’s “misbehaving script accidentally sending a lot of requests” — and treats the request rate limiter as the single most important one to build first.

A limiter is a gate, not capacity. If clients genuinely need that throughput and spacing requests out changes their result (real-time events), a limiter is the wrong tool — you need more capacity or a different protocol. The limiter’s job is to reject the load you can’t serve cheaply, with a clear signal, before it costs you the expensive work.

Four algorithms, two behaviours

The algorithms split into two families: those that smooth bursts and those that count over a window.

Token bucket. A bucket holds up to B tokens and refills at R tokens/second. Each request takes one token; if the bucket is empty, reject. The bucket lets a client save up unused allowance and spend it in a burst up to B, then settle to the sustained rate R. This is the algorithm Stripe uses in production (a centralised bucket host, tokens dripping in). It is the default for APIs because it matches how real traffic behaves: bursty, but bounded.

Leaky bucket. Requests enter a queue (the bucket) and drain at a fixed rate, like water through a hole. Overflow is dropped. It produces a perfectly smooth output rate — good for protecting a downstream that hates bursts — but it adds queueing latency and, unlike token bucket, does not allow bursts through. Token bucket allows bursts up to B; leaky bucket flattens them.

Fixed window. Count requests per fixed clock interval (e.g. per minute); reset the counter at the boundary. Trivial — one integer per client — but it has a sharp flaw covered below.

Sliding window. Two cheaper-than-perfect variants fix the fixed-window flaw. The sliding log keeps a timestamp per request and counts those within the trailing window — exact, but stores every request. The sliding window counter blends the current and previous fixed-window counts by how far you are into the window — approximate, but O(1) memory. Cloudflare popularised the counter approximation precisely because storing a log per client doesn’t scale to millions of keys.

Where to enforce it

The limiter belongs as far out and as early as possible — ideally at the edge (CDN/WAF) or the API gateway, before the request consumes a connection slot, a worker, or a database query on the protected service. Enforcing inside the service still protects the database but wastes the cheap resources (the TLS handshake, the worker thread) on requests you’re going to reject anyway. The general rule: reject as close to the client as you can, so the rejection is as cheap as possible.

But the outermost layer often doesn’t have the context to limit by the right key (user ID, API key, tenant), so real systems layer limiters: a coarse per-IP limit at the edge to absorb floods, then a precise per-API-key limit at the gateway, then sometimes a concurrency limiter at the service for expensive endpoints. Stripe runs four kinds in concert for exactly this reason.

The distributed counter and the race

One server with one in-memory counter is easy. A fleet of fifty servers behind a load balancer is the real problem: each request for one API key can land on any server, so the count must be shared, or fifty servers each enforce “100/min” and the client actually gets 5,000/min. The standard answer is a shared store — usually Redis — holding one counter per key.

Now the race. The naïve sequence is read-modify-write:

n = GET key          # server A reads 99
n = GET key          # server B also reads 99 (concurrent)
if n < 100:          # both see 99 < 100
    SET key n+1      # both write 100 — one increment is LOST
    allow

Two concurrent requests both read 99, both decide they’re under the limit, both allow — the client got 101. Under high concurrency this leaks badly. The fix is atomicity: make the increment-and-check a single indivisible operation. INCR in Redis is atomic, so the common pattern is INCR then compare, or a small Lua script that does the whole token-bucket refill-and-decrement server-side in one round trip (Redis executes a script atomically). The race is the entire reason distributed rate limiting is harder than it looks — the algorithm is trivial; doing it correctly without a lost update is not.

Telling the client: 429 and Retry-After

When you reject, say so precisely. The standard is HTTP 429 Too Many Requests, with a Retry-After header telling the client how many seconds to wait before trying again (some APIs also send X-RateLimit-Remaining / -Reset so a well-behaved client can self-throttle before hitting the wall). This matters because the alternative — a bare error with no guidance — pushes clients into tight retry loops that add load exactly when you’re already overloaded, turning a brownout into an outage. A precise 429 with Retry-After lets a good client back off cleanly; combined with client-side exponential backoff and jitter, it’s what keeps a limited system stable instead of thrashing.