Rate Limits Are a Contract: Algorithms, Keys, State, and the Fail-Open Question Nobody Wants to Own

The page came in at 03:41: login latency through the roof, error rate climbing. The Redis node backing the rate limiter had run out of memory and stopped answering. And here is the part that made it a war story instead of an incident: half the services treated the dead limiter as “allow everything” and half treated it as “allow nothing.” The login endpoint — the one actually being brute-forced that night, the reason Redis was melting in the first place — was in the allow-everything half. The health-check endpoint, which nobody has ever attacked, was in the allow-nothing half, so the load balancer marked every instance unhealthy and took the site down for everyone.

Nobody had decided any of this. Each service had inherited whatever its HTTP middleware did by default when the limiter’s backing store threw a connection error. The single most security-relevant property of the entire rate-limiting system — what happens when it can’t answer — had been chosen by a library author who had never seen the threat model.

That night is the thesis of this post. A rate limit is not an implementation detail and it is not a performance feature. It is a contract with three parties — your infrastructure, your legitimate clients, and your attackers — and like any contract, the interesting clauses are the ones about what happens when things go wrong. This post walks the whole design space: the algorithms and their burst math, the choice of keys, the state problem and the multi-replica trap, the fail-open/fail-closed decision argued properly as per-endpoint security policy, and the client-facing surface the IETF has been standardizing since RFC 6585 gave us status code 429 in 2012¹.

What a rate limit actually promises

Strip away the implementation and a rate limit is two promises:

1. To the operator: no single key will consume more than its share of capacity, so one abusive or broken client cannot degrade service for the rest.
2. To the client: if you stay under the advertised rate you will not be throttled, and if you are throttled you will be told honestly — with a status code that means “slow down” rather than “we are broken,” and ideally with enough metadata to know when to come back.

Both halves matter. Teams obsess over the first promise and forget the second, then wonder why every client in the ecosystem hammers them with immediate retries: because a 500 or an unexplained connection reset tells a well-behaved client retry now, while a 429 with Retry-After: 30 tells it retry in 30 seconds. The signal is part of the mechanism. A limiter that rejects correctly but signals badly recreates the very load spike it exists to prevent.

There is also a third, unadvertised clause: what the limiter does when it cannot decide. We will get there. First, the machinery.

The algorithms, with the burst math done honestly

Every rate-limiting algorithm answers the same question — “has this key exceeded N operations per window W?” — but they disagree about what “per window” means, and the disagreement is exactly the burst behavior. For all of the following, take a nominal limit of 100 requests per 60 seconds.

Fixed window counter

The simplest thing that works: bucket time into fixed windows (12:00:00–12:00:59, 12:01:00–12:01:59), keep one counter per key per window, reject when the counter passes N. One Redis INCR plus an EXPIRE — the pattern is literally in the Redis INCR documentation as the canonical example².

The problem is the boundary. A client can send 100 requests at 12:00:59 and 100 more at 12:01:00. That is 200 requests in roughly one second — twice the nominal limit, delivered in 1.7% of the window — and the limiter is perfectly happy, because each window’s counter individually stayed at 100. In general, a fixed window admits up to 2N requests in any interval that straddles a boundary, and an adversarial client can hit that bound deliberately every single window. If your capacity planning assumed 100/minute means “never more than ~2/second sustained,” fixed windows quietly void that assumption by a factor of a hundred.

Fixed windows are fine when the limit exists for coarse quota accounting (a million calls per day) where a 2× transient is irrelevant. They are wrong when the limit exists to protect capacity.

Sliding window log

The exact answer: store a timestamp for every request, and on each new request count the timestamps in (now − W, now]. Perfectly smooth — at no instant does any trailing 60-second interval contain more than 100 requests. The cost is memory and work proportional to the request rate per key: at the limit, 100 timestamps per key, trimmed and counted on every request (a Redis sorted set with ZREMRANGEBYSCORE + ZCARD is the standard build). For low limits on high-value endpoints this is entirely reasonable. For a CDN-scale limiter it is not.

Sliding window counter — the Cloudflare approximation

Cloudflare’s rate limiter, described in their 2017 engineering write-up, keeps just two counters per key — previous window and current window — and estimates the trailing-window rate by assuming requests in the previous window arrived uniformly³:

rate ≈ previous_count × (W − elapsed_in_current_window) / W  +  current_count

Concretely: previous minute saw 84 requests, we are 15 seconds into the current minute with 36 so far. Estimated trailing-minute rate = 84 × (45/60) + 36 = 63 + 36 = 99 — just under the limit, next request rejected. The assumption of uniform arrivals in the previous window is false in general, but the error is bounded and small in practice; Cloudflare measured that across 400 million requests from 270,000 distinct sources, only 0.003% of requests were wrongly admitted or rejected relative to an exact sliding log, and no request was allowed at a true rate above the limit³. Two integers per key, one weighted multiply per decision, boundary-burst problem gone. This is the default choice for high-cardinality limiting and the reason “sliding window” won the mindshare war.

Token bucket

The token bucket flips the accounting from “count requests in a window” to “maintain a budget.” A bucket holds at most B tokens and refills at r tokens per second; each request spends one token; an empty bucket means reject (or queue). Two parameters instead of one, and that second parameter is the whole point: B is your burst policy, r is your sustained-rate policy, and they are decoupled.

The math: over any interval of length t, a token bucket admits at most B + r·t requests. Long-run average rate converges to r no matter what; instantaneous burst is capped at B. Set B = 100, r = 100/60 ≈ 1.67/s and you get behavior close to a sliding window. Set B = 20, r = 1.67/s and you get the same sustained rate but a much tighter lid on spikes. Set B = 500 and you are saying “we tolerate big bursts as long as the average holds” — which is what a payments API wants during a customer’s flash sale, and is exactly the property Stripe cites for building its request limiter on token buckets with a Redis backend⁴.

Implementation is lighter than it sounds: you do not simulate a drip. Store (tokens, last_refill_timestamp) per key, and on each request compute tokens = min(B, tokens + (now − last) × r) before spending. Lazy refill, two floats per key.

Leaky bucket and GCRA

The leaky bucket is the token bucket’s dual — requests queue in a bucket that drains at a constant rate — and is what nginx’s limit_req module implements, with its burst parameter as the bucket depth and nodelay controlling whether burst-admitted requests are served immediately or paced⁵. The Generic Cell Rate Algorithm (GCRA), inherited from ATM networks and nicely explained in Brandur Leach’s essay on the design of stripe-adjacent limiters, is the elegant O(1) formulation: store a single “theoretical arrival time” per key, advance it by the emission interval T = W/N per admitted request, and allow a configurable burst tolerance τ⁶. GCRA gives token-bucket semantics with one stored timestamp and no float drift, and also yields the exact earliest retry time for free — which, as we will see, is precisely what you want to put in Retry-After.

Which one

The honest summary: fixed windows are for accounting, sliding-window counters are for protection at scale, and token bucket/GCRA are for when you want to say something about bursts rather than merely tolerate them.

Per what? Keys, and why layers beat one global limit

An algorithm without a key is not a policy. “100 per minute” — per what? The key choice determines what the limiter actually defends, and the central lesson from production systems is that no single key is correct, because different keys defend against different failure modes. Stripe’s published architecture runs four limiters in series — a per-user request-rate limiter, a per-user concurrency limiter, a fleet-utilization load shedder, and a worker-utilization shedder — precisely because each catches abuse the others structurally cannot⁴.

Take a concrete endpoint: POST /otp/send, which sends a one-time code by SMS. Enumerate the failure modes:

• A script hammers one phone number (SMS-bombing harassment, or burning your SMS budget). Defense: per-recipient limit — say 3 sends per number per 15 minutes. No other key catches this: the attacker can rotate IPs and even tenants, but the victim’s phone number is the invariant.
• One tenant’s buggy retry loop sends 50,000 OTPs to 50,000 distinct numbers. Per-recipient never trips. Defense: per-tenant limit, which is also your fairness mechanism — tenant A’s incident must not consume tenant B’s capacity.
• Unauthenticated traffic from one box probes the endpoint. There is no tenant yet. Defense: per-IP (or per-ASN/prefix, since single-IP limits die to residential proxy pools — treat per-IP as a speed bump, not a wall).
• Aggregate demand exceeds what your SMS provider will accept. Every per-key limit can be individually satisfied while the sum kills you: 10,000 tenants each politely under their cap is still 10,000× the per-tenant rate. Defense: one global concurrency/rate guard sized to downstream capacity — a load shedder, not a fairness device.

Four keys, four limits, evaluated as a chain where the most specific limit trips first and its identity is reported to the client (“recipient rate exceeded” is actionable; “rate exceeded” is not — though be careful what you reveal on unauthenticated endpoints, a topic that deserves its own post). The inverse design — one global limit and nothing else — fails in both directions at once: it lets a single tenant starve everyone (no fairness) and it forces you to set the number high enough for aggregate legitimate traffic, which makes it useless against any individual abuser. A global limit is the last layer, never the only one.

Two practical notes on keys. First, key cardinality is a cost and an attack surface: per-recipient keys on a public endpoint let an attacker allocate limiter state for every phone number they invent, so bound the keyspace (hash into it, expire aggressively). Second, keys must be derived from authenticated identity wherever possible — a per-tenant limit keyed on a client-supplied header is a per-attacker-chosen-string limit.

Where the counters live: the multi-replica multiplication trap

Now the state question. Your API runs as k replicas behind a load balancer. Where does tokens live?

In-memory, per replica. Fastest possible (nanoseconds, no network hop), zero infrastructure, and it silently rewrites your policy: each replica enforces N independently, so the fleet enforces up to k·N. With k = 8, your “100 per minute” is 800 per minute. Worse, k is not a constant — it is your autoscaler’s output. Load rises, HPA scales you from 8 to 20 replicas, and your effective rate limit rises 2.5× exactly when you most need it enforced — the limiter loosens in proportion to the load it exists to shed. And because load balancing is approximately random per request, a client’s experience is nondeterministic: the same request rate trips the limiter on whichever replica its requests happened to concentrate. Teams discover this trap empirically, usually via an invoice from their SMS provider.

In-memory limiting is still the right tool in two places: as a local pre-filter with the limit set to N (not N/k — a pure circuit-breaker against pathological single-source floods before you pay the network hop), and as the degraded fallback discussed below.

Database-backed. Correct and durable, and almost always wrong: a row update with contention on your hottest keys, on the same database your actual application needs, in the request path of every call. A rate limiter’s whole job is to be cheaper than the work it protects. If your limiter costs a Postgres transaction, an attacker doesn’t need to exceed the limit to hurt you — the checking is the DoS. Databases are fine for slow-moving quota (monthly billing caps checked against a cache) and wrong for request-rate enforcement.

Shared low-latency store — Redis, in practice. The industry default, and what Stripe, GitHub-scale APIs, and every serious framework converge on⁴. One authoritative counter per key, sub-millisecond checks, TTLs for free. Two implementation rules keep it honest. First, the check must be atomic: a read-modify-write done as GET then SET from application code is a race that over-admits under exactly the concurrent load that matters; use a Lua script (or Redis functions) so refill-and-spend executes atomically server-side. Second, put a budget on the hop: the limiter adds latency to every request, so the Redis call needs a tight timeout (single-digit milliseconds) — which forces the question of what to do when that timeout fires, i.e., the fail-open question below.

Here is a compact, production-shaped GCRA-style token bucket as an atomic Redis Lua script, callable from any language:

-- KEYS[1] = bucket key
-- ARGV[1] = burst capacity B
-- ARGV[2] = refill rate r (tokens/sec)
-- ARGV[3] = now (seconds, float)
-- ARGV[4] = cost (tokens for this request)
-- returns {allowed (0/1), retry_after_seconds}
local b     = tonumber(ARGV[1])
local r     = tonumber(ARGV[2])
local now   = tonumber(ARGV[3])
local cost  = tonumber(ARGV[4])

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or b
local ts     = tonumber(state[2]) or now

-- lazy refill
tokens = math.min(b, tokens + (now - ts) * r)

if tokens >= cost then
  tokens = tokens - cost
  redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
  redis.call('EXPIRE', KEYS[1], math.ceil(b / r) + 1)
  return {1, 0}
else
  redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
  redis.call('EXPIRE', KEYS[1], math.ceil(b / r) + 1)
  -- exact earliest time the deficit is refilled
  return {0, math.ceil((cost - tokens) / r)}
end

Note the return value: on rejection the script computes the exact number of seconds until the bucket can afford the request. That number is your Retry-After. Honest math produces honest headers.

For very large fleets there is a fourth option — the two-tier design Envoy formalizes as local rate limiting in front of a global rate limit service⁷. Each node enforces a cheap local approximation and only consults the shared store for decisions near the boundary, trading a bounded over-admit for a large cut in hot-path load on the shared store. You earn the right to that complexity after Redis CPU becomes your bottleneck, not before.

Fail-open or fail-closed: a security decision wearing an ops costume

Back to 03:41. Redis is down, or timing out, or failing over. Every request now reaches the limiter middleware and gets an exception instead of a decision. What do you do?

The two answers have names. Fail-open: on limiter error, admit the request — availability over enforcement. Fail-closed: on limiter error, reject — enforcement over availability. Most frameworks pick one as a global default, and that global default is the bug, because the correct answer is a property of what each endpoint’s limit is for, and a typical service has limits serving two entirely different masters:

Load-shedding limits exist to protect capacity — yours or a downstream’s. The global guard on /otp/send, the per-tenant fairness cap on /search. For these, fail-open is nearly self-evident: the limit is subordinate to the service, and a limiter that takes the service down when the limiter breaks has inverted its own purpose. There is one sharp caveat: the limiter’s store often dies because of the very overload it should be shedding — the incident that kills Redis is correlated with the traffic you needed Redis to stop. So “fail-open” for load-shedding limits should really be fail-degraded: fall through to the per-replica in-memory limiter with a conservative local bound (N/k using the last-known replica count, or simply a hard per-instance concurrency cap). You lose precision, not protection.

Abuse limits exist to make an attack uneconomical — the 5-attempts-per-account limit on /login, the per-recipient cap on OTP sends, the per-account cap on password-reset emails. Here the calculus reverses, and it is worth arguing properly rather than by slogan, because the fail-open case sounds plausible: “if the limiter is down, failing closed means an attacker who can kill Redis can lock everyone out of login — we’d be handing them a DoS.” True. Now weigh the other branch: failing open means an attacker who can kill Redis gets an unmetered credential-stuffing window against every account you hold, for the full duration of the outage, silently. Compare the two failure states:

• Fail-closed failure: logins rejected. Loud (error rates, support tickets, pagers), bounded (ends when you restore the store or flip to a fallback), recoverable (nobody’s password got validated).
• Fail-open failure: stuffing proceeds at line rate. Silent (success metrics look normal), unbounded in consequence (validated credentials are permanent attacker assets), unrecoverable (you cannot un-confirm a password).

A visible availability incident versus an invisible security incident is not a close call. Security controls fail closed; that is what makes them controls. OWASP’s guidance on brute-force defense treats the throttle as a security control in exactly this sense — it is the mechanism that makes online guessing uneconomical, not a courtesy⁸. And note the incentive structure fail-open creates: if crashing your limiter disables your brute-force defense, your limiter’s availability becomes part of your authentication attack surface, and an attacker now has a reason to aim load at it.

The synthesis that held up in our systems:

1. Classify every limit at creation as shedding or abuse. If a limit seems to be both (the login limit protects capacity too), it is an abuse limit — the security property dominates.
2. Shedding limits fail degraded (local in-memory approximation), never hard-closed.
3. Abuse limits fail closed, with a local in-memory limiter as the first fallback so a brief Redis blip does not reject anyone — a per-replica counter still bounds an attacker to k·N, which for a 5-per-15-minutes login limit on 8 replicas is 40 attempts, annoying but not catastrophic. Hard-closed is the floor beneath the fallback, not the first response.
4. Never share a failure domain between the two classes. The limiter cluster that shields /search from load will be at its sickest during a volumetric event; your login limiter should not be a casualty of that. Separate Redis (or at least separate timeout/fallback policy) for abuse limits.
5. Make the choice visible in code. RateLimit(key=..., limit=..., on_error=FAIL_CLOSED) — an explicit parameter that a security review can grep for. The 03:41 postmortem’s root cause was not the outage; it was that on_error didn’t exist as a concept anywhere in the codebase.

The client contract: 429, Retry-After, and not punishing the polite

Now the other side of the contract — what the client is owed. The vocabulary is small and standardized, and using it wrong actively damages your own ecosystem.

Status code. RFC 6585 (April 2012) defined 429 Too Many Requests for exactly this: “the user has sent too many requests in a given amount of time”¹. Use it for per-client limit rejections. Use 503 for the load-shedding case where you are the problem (fleet over capacity) rather than the client — the distinction matters because client retry policies legitimately differ between “I am being throttled” and “the server is degraded.” Never use 500: a 500 tells clients and their retry libraries that retrying immediately is reasonable.

Retry-After. Defined in HTTP’s core semantics (RFC 9110 §10.2.3) for 503 and redirects, and explicitly available on 429 per RFC 6585⁹¹. Either a delay in seconds or an HTTP date. Send it whenever you can compute it — and with token bucket or GCRA you always can, exactly (see the Lua script above). A correct Retry-After converts an angry retry storm into a scheduled, spread re-arrival; it is the single highest-leverage line in your 429 handler.

The remaining-quota headers. For a decade the ecosystem improvised X-RateLimit-Limit / X-RateLimit-Remaining / X-RateLimit-Reset in mutually incompatible dialects — GitHub’s REST API alone documents both primary and “secondary” limits with x-ratelimit-* headers and its own reset semantics¹⁰. The IETF HTTPAPI working group has been converging this zoo into two structured fields, RateLimit and RateLimit-Policy; as of the version-11 draft (May 2026, Polli, Martínez Ruiz, and Miller), the shape is¹¹:

RateLimit-Policy: "burst";q=100;w=60, "daily";q=1000;w=86400
RateLimit: "burst";r=12;t=31

RateLimit-Policy advertises the standing policy (quota q per window w seconds, optionally a quota unit qu and a partition key pk); RateLimit reports live state for a named policy (remaining quota r, seconds until reset t). The named-policy design finally lets a server express layered limits — the burst cap and the daily cap — in one machine-readable place, which is exactly the layered-keys reality described above. It is still an Internet-Draft, so ship it alongside whatever legacy X-RateLimit-* your clients already parse, but the direction of travel is clear, and designing your internal limiter to produce (policy_name, remaining, reset) tuples now costs nothing.

The draft’s security considerations are worth internalizing even if you never emit the headers: quota metadata is an information channel, and a RateLimit header on an unauthenticated endpoint tells an attacker precisely how fast to probe without tripping you¹¹. Advertise generously to authenticated first parties; be terse with strangers.

And the client’s half of the bargain: honor Retry-After, back off exponentially when you get 429 without one, and jitter your retries. The canonical demonstration is Marc Brooker’s 2015 AWS Architecture Blog analysis showing that exponential backoff without jitter leaves retrying clients synchronized in waves, and that “full jitter” (sleep a uniform random amount up to the backoff ceiling) dramatically reduces both total work and time-to-recovery¹². A rate-limit contract only works if both sides perform; publishing an SDK that implements the polite-client half is how API providers in practice make that happen.

Numbers, shadows, and the operational afterlife

Three habits separate limiters that work from limiters that ambush their own users.

Derive the numbers, don’t vibe them. Load-shedding limits come from measured capacity: max concurrent requests before p99 degrades, downstream provider’s contractual rate, SMS budget divided by expected distribution. Abuse limits come from the threat arithmetic: a 5-per-15-minutes per-account login limit caps online guessing at 480 attempts/day/account — against even a weak password distribution that is a decades-long attack, which is the point. If you cannot say what a limit’s number defends, you cannot say what its fail mode should be either; the two ignorances travel together.

Shadow before you enforce. Run every new limit in log-only mode against production traffic first. The distribution of would-be rejections tells you immediately whether the limit is placed where you think: when we shadowed a per-tenant limit sized from median usage, the would-block list was headed not by abusers but by our two largest customers’ perfectly legitimate batch jobs. Enforcement without shadowing is how rate limits become outages with extra steps.

Alert on the limiter, not just with it. Rejection-rate per policy per key-class is a first-order product metric (a spike in per-recipient OTP rejections is an attack report). But also instrument the limiter’s own health: error rate to the backing store, fallback activations, fail-closed rejections. The 03:41 incident produced its first useful signal from a dashboard nobody had built yet.

The contract, restated

The engineering content of rate limiting is genuinely pleasant — GCRA is a beautiful algorithm, the Cloudflare two-counter trick is the kind of approximation you show juniors to teach them what “good enough, provably” means, and the whole field fits in a page of arithmetic about B + r·t. But none of that arithmetic is where limiters fail in production. They fail at the seams: the boundary burst nobody computed, the replica count silently multiplying the policy, the global limit that was really no limit, the 500 where a 429 belonged, and above all the unexamined default when the backing store stops answering.

So treat the limit as the contract it is, and write all the clauses down. Per endpoint: what the limit protects (capacity or abuse), what key it binds, what algorithm and therefore what burst it admits, what the client is told (status, Retry-After, quota headers), and — in writing, greppable, reviewed by whoever owns your threat model — whether it fails open, degraded, or closed. RFC 6585 gave us the vocabulary fourteen years ago; the RateLimit header fields draft is finishing the machine-readable half now¹¹¹. The standards have done their part.

The judgment this post exists to land: fail mode is not an ops setting, it is the security clause of the contract, and any limiter whose fail mode you cannot state from memory is a limiter you have not actually designed. The night you find out is always 03:41.

References