Distributed Rate Limiter Failures: Races, Outages & Overshoot

Thirty-five failures of a distributed rate limiter, grouped by what actually goes wrong: counts that disagree, state that leaks, a store that fails over, a hot tenant, an identity that can't be trusted, a policy that is stale, a region that cannot be reached.

Every incident on this page is a hypothetical scenario built on the fictional Northstar API (tenants Atlas and Birch, key K1, user U-17, gateways A and B, Redis primary R with replica R2, regions EU and US). No incident describes a real outage at a real company, and every number is a teaching input or planning figure — not a benchmark, not a statistic. The design that these failures stress is the one from Complete Design: a token bucket per principal as the primary algorithm, one atomic store authority per key, a semaphore for concurrency, and weighted cost for expensive routes.

Each incident follows the same arc: what set it off, how it unfolded in time, what a caller or operator saw, the mechanism underneath, how you would detect it, what to do in the first minutes, how to recover, how to prevent it, what correctness still holds, and what the fix costs. A compact table closes every incident with nine of those elements (everything except the timeline) so they are easy to find; the prose around it carries the timeline and the arithmetic, and varies because the failures do.

Allowance failures versus telemetry failures

Two kinds of failure get confused constantly. An allowance failure means the limiter admitted or denied something the policy says it should not have: F01, F03, F10 and F21 are examples. A telemetry failure means the limiter decided correctly but the record of what it decided is wrong: F30 is the only pure case on this page. The distinction matters operationally because the responses are opposite. If you see an allowance failure, you change enforcement. If you see a telemetry failure, you must not touch enforcement; you repair the evidence. Treating a dashboard gap as an over-admission can lead to needless tightening, and treating a real over-admission as 'probably just metrics' lets it continue.

What 'availability' means when the limiter is strict

Fail-closed is easy to say and easy to misunderstand. When the store is unreachable and a route is strict, the gateway refuses requests it could have served. For the user that is unavailability of that feature, expressed as a 503 (service or dependency unavailable) rather than a 429 (you exceeded your quota); the two should not be interchangeable, because a client's correct reaction differs. The reason to accept it is that the alternative on an expensive route is an unmetered path to a backend that serves everyone. So availability, for Northstar, is defined per route: catalog reads keep working under a bounded local fallback, exports pause. Which route gets which mode is a product-and-risk decision recorded in policy, and F20 walks through it with numbers.

Failure map: all 35 incidents

The first class of failure is arithmetic: the limiter counts correctly by its own rules, but those rules or the way they are executed don't match the promise made to the customer.

Fixed windows, process-local counters and multi-step Redis logic each leave a gap in which more traffic passes than intended. The remedy is mostly structural (one authority, one atomic step, one time source), which is why Architecture Deep Dive spends its time on the script rather than on tuning. The Redis scripting documentation describes a script as executing atomically, with other server activity blocked while it runs; that property is what closes F03 and F07, and it is also why scripts must stay short.

F01 — Fixed-window boundary double burst

Take P-ANON — 20 requests per 10 s, fixed windows aligned to epoch multiples of 10 s — and a scraper behind one Northstar-facing IP that knows it. At t = 9.9 s it sends 20 requests; the counter for window 1 reaches 20 and every request passes. At t = 10.1 s the window id flips, a fresh counter starts at 0, and another 20 pass. That is 40 admissions in 0.2 s, exactly 2×L, while each window individually obeyed the rule. Nothing is broken in the sense of a bug: the policy simply never promised anything about intervals that straddle a boundary.

The damage comes from multiplication. If 500 coordinated IPs all do this, 500 × 40 = 20,000 requests arrive inside 0.2 s, an instantaneous rate of 100,000 req/s against a catalog backend that comfortably handles 2,000. Averaged over 20 s the same IPs look like 500 × 2/s = 1,000 req/s, which is why per-minute dashboards stay green. An attacker finds the boundary by probing: the first 429 marks the end of one window and the next admit marks the start of the next. A sliding-window counter estimates the second burst against a weighted share of the first and curbs it (still approximately), and a token bucket bounds the pair differently: it can admit up to 20 + 2T tokens in any T seconds, so 40 in 10 s but not 40 in 0.2 s. That is why Northstar keeps fixed windows only for coarse anonymous rules and uses buckets where burst shape matters.

F02 — Two gateways each allow the last slot

Gateway A and gateway B each keep an in-process counter for the P-ANON rule on one IP. The fleet-wide intent is 20 per 10 s. At t = 4 s the IP has made 19 requests, and by an unlucky load-balancer spread, 10 of them went through A and 9 through B. A's local counter reads 10, B's reads 9 — neither is near 20. Both continue to admit, and both are correct about their own memory.

Formally, with N gateways each enforcing L locally the fleet admits up to N × L. With the 100 gateways of the P-GLOBAL example and a per-gateway limit of 20, that is 2,000 per 10 s for one IP, 100× the intent. Dividing the limit by N does not rescue it: 20 / 100 = 0.2 requests per gateway is not representable, and a load balancer that lands six requests in a row on one instance rejects a customer who is nowhere near the fleet limit. Sticky routing narrows the error but couples limit accuracy to LB behavior and breaks on every deploy or failover. The only fix that preserves the count is one shared authority per key — the move Complete Design makes in the Visual Design Journey scenes 8–10 — with a locally cached deny path to keep it cheap.

F03 — Naive Redis GET/SET check-then-write race

Northstar's first shared-store version reads the counter with GET, compares in the gateway, and writes back with SET. It looks right in a single-threaded test. In production, A and B each execute GET rl:ip:203.0.113.9 within the same millisecond and both see 19; both decide 19 < 20, both SET 20. The store holds 20, and both requests have been allowed — one slot was spent, two requests used it.

The loss scales with concurrency and round-trip time. If a key sees 5,000 req/s and the read-compute-write gap is 1 ms, about five requests are in that gap at any instant, and each overlapping group can admit several requests while recording a single increment. A flood amplifies this: the busier the key, the more it under-counts. Atomic increments (INCR) solve plain counting; a token bucket needs read, refill arithmetic, comparison and write as one unit, which is what a Lua script or function provides — the Redis scripting docs describe a script as running atomically, blocking other activity on that instance while it runs. That atomicity is per instance; the durable story is F10.

F06 — Token bucket clock moves backward or forward

P-READ is a bucket with capacity 20 and refill 2/s, and the gateways supply now from their own clocks. Gateway A's clock is 30 s ahead. A's request stores updatedAt = t + 30. B, correctly timed, then runs the formula with now = t: max(0, now − updatedAt) = 0, so no refill arrives until B's clock catches the stored value. Thirty seconds at 2 tokens/s would have refilled 60 tokens, so U-17 stays at whatever she had — the bucket appears frozen and legitimate users see 429.

The opposite direction is the quieter one. A clock that jumps forward 60 s makes delta = 60, refill 120 tokens, clamped at 20: an exhausted bucket becomes full instantly, handing out an unplanned 20-request burst per key to every principal that touches that gateway. The cure is a single time source for the decision: read the store's clock inside the script (the script sees the same now for every gateway), persist an integer millitoken balance, and clamp so updatedAt never moves backward. Reading TIME inside a write script is allowed because of effects replication: the scripting docs say it became the default in Redis 5.0 and the only mode in 7.0, and that with it enabled non-deterministic commands such as TIME can be used freely. On a version older than 5.0 that is not the default, so check yours.

F07 — Concurrent weighted reservations exceed the budget

A weighted export costs 10 units under P-EXPORT. Birch's export bucket holds 15 tokens. Two exports arrive from different gateways at the same moment. With separate read and debit steps both read 15 ≥ 10, both proceed to debit, and the bucket either goes to −5 (if the debit is unconditional) or to 5 with 20 units spent (if the second write overwrites the first). The weight multiplies the damage of F03: a one-token race loses one request, a ten-token race loses ten.

Done atomically the sequence is deterministic. The first script sees 15, admits, stores 5. The second sees 5 against cost 10, deficit 5, and returns retryAfter = ceil(5 / 2) = 3 s. Two further traps belong here. First, a reservation made at admission is a prediction: an export that will actually scan a large range costs more than the nominal 10, so either charge a worst-case estimate and refund the difference after execution, or accept the estimate as a bounded error. Second, the refund itself is a write that can be duplicated by retries; it needs a stable request id, otherwise the same 'refund 4' applied twice mints tokens.

Limiter state is cheap per key and expensive in aggregate, and the interesting failures happen at the edges of its lifecycle: creation without expiry, growth without bound, deletion without notice, and restoration to the wrong moment.

The planning figure used throughout: 2M active keys × an assumed 200 B per key is 400 MB, about 800 MB per copy with 2× headroom, and about 1.6 GB for a primary plus one replica. The 200 B is an assumption to be replaced with a MEMORY USAGE measurement on real keys; the headroom is there for allocator overhead and replication buffers. The key model rl:v3:{t:atlas}:u:U-17:read has a TTL equal to time-to-full-refill plus slack, written in the same script as the update. Each incident below is what happens when one part of that sentence stops being true.

F04 — INCR without TTL after a crash or a bad key lifecycle

The fixed-window counter is created with INCR, and the EXPIRE is a second command issued by the gateway afterwards. At 02:14 a gateway process is killed between the two. The key exists with no expiry. If the key name embeds the window index the leak is a stray string; if an engineer 'simplified' the key to rl:v3:ip:203.0.113.9 the counter never resets, and from that moment that IP is permanently blocked after its twentieth request.

The slow version of the same bug is a leak. Suppose crashes or bad deploys strand 1,000 keys a minute: 1,000 × 1,440 = 1.44M keys a day, and at an assumed 200 B each (measure your own with MEMORY USAGE) that is 288 MB every day that never expires. The fix is structural: set the TTL in the same script as the write, so there is no instant at which the key exists without one. A cheap audit looks for keys whose remaining TTL is −1; I'd sample with SCAN, never KEYS, on a primary under load. The docs note that overwriting commands such as SET clear a key's timeout, so any code path that rewrites a counter must re-apply it.

F05 — Sliding log memory growth on a hot key

The sliding-log algorithm stores one entry per admitted request so it can count exactly. For Atlas at 1,000 requests/min that is up to 1,000 sorted-set members on the tenant key, and for 20,000 active users × 20 entries it is 400,000 members in total — workable. The incident starts with a design shortcut: the team also logs denied attempts 'for audit'. When Atlas floods at 75,000 attempts/s, the tenant log would take 75,000 × 60 = 4.5M entries inside a single minute, all on one key and therefore one shard.

At an assumed 50 B per sorted-set member (hypothetical; measure it), that single key is about 225 MB, and every trim, count or delete over it is O(log N + M) work inside one blocking command. Latency on every other key sharing that primary rises while the script walks the set. The fix is a design decision, not tuning: store only admitted requests (so the key is bounded by the limit itself, 1,000 here), or move to a counter-based approximation when exactness is not worth the memory. The sliding log keeps its place for low-limit, high-value rules where exactness is cheap and a flood cannot grow the set.

F14 — High-cardinality bogus principals exhaust memory

Plan the keyspace first. Two million active keys at an assumed 200 B each is 400 MB; with 2× headroom for allocator overhead and replication buffers that is about 800 MB per copy, so a primary plus one replica needs ≈ 1.6 GB. Now an attacker sends 50,000 requests/s, each with a never-seen principal id (random API key strings, or random user ids in a login form). If the limiter creates a bucket for every distinct principal, 50,000 new keys/s with a 60 s idle TTL means a steady state of 3M extra keys: 3M × 200 B = 600 MB, doubled to 1.2 GB — half as much again as the 800 MB planned per copy, reached in about a minute.

A longer TTL is worse. An idle TTL of one hour keeps 50,000 × 3,600 = 180M keys alive, 36 GB at the same assumed size. Whichever limit the memory hits (maxmemory, F15) the defender loses: evictions erase honest users' state, or writes begin failing. The defense is to refuse to allocate per-principal state for identities that have not earned it: verify the credential cheaply first (F35), bucket unauthenticated traffic by a bounded coarse key such as client prefix, set TTL to the refill horizon (for P-READ, 20 / 2 = 10 s plus slack), and alarm on key-creation rate, not just key count.

F15 — Key eviction silently resets enforcement

When the store reaches maxmemory, the configured policy decides what happens. With noeviction Redis returns errors for writes that would grow memory, which the limiter sees as store failures and routes through its fail mode. With an allkeys-* policy Redis instead silently deletes keys, and a deleted limiter key means a missing key — and a missing token bucket is treated as full. At 02:10, memory pressure under the F14 attack evicts the bucket for K1 while Atlas is flooding; the next request finds no key, creates a full bucket of 20 and admits 20 immediately.

Eviction looks harmless when the evicted bucket would have refilled anyway: after 10 s idle every P-READ bucket is full, so losing it changes nothing. It is harmful for recently depleted buckets, for fixed-window counters, and for any long-horizon quota whose accrued consumption exists only in this key. The volatile-* policies only consider keys with a TTL and, per the docs, behave like noeviction when no key has one, so mixing limiter keys with cache keys in one instance makes the policy hard to reason about. My preference: a dedicated limiter instance sized with headroom, TTL on every key, and an alert on any non-zero eviction counter rather than a policy that quietly self-heals into over-admission.

F33 — Persistence restore resets counters unexpectedly

After a host failure, Redis R is restarted from its last RDB snapshot, taken every five minutes in this example. Snapshots are point-in-time copies; the docs are explicit that this style can lose the writes since the last save point, while AOF with an everysec policy bounds the loss to roughly a second. The restored keys reflect state from up to five minutes ago. Short-horizon limits barely notice: a P-READ bucket refills fully in 10 s, so a five-minute-old bucket plus elapsed time is nearly full either way.

Long-horizon quotas are where it hurts. Suppose Atlas also has a hypothetical daily plan quota of 100,000 requests, consumed at 1,000/min. A five-minute rollback forgets 5,000 requests, 5% of the day's quota, handed back for free; a restore from last night's backup forgets far more. Restoring is also where staleness stacks with F10: if the restored node is promoted, replicas may disagree with it. The practical rule is to match durability to the horizon. Rate buckets are disposable, and a restore is fine. Quotas that carry legal or billing meaning belong in a durable ledger (I12), with Redis as a fast admission cache over it.

A store with atomic scripts gives you a correct decision on one instance. It does not give you correctness across a failover, across slots, or while it's down.

The Redis documentation is consistent on the limits. Replication is asynchronous by default, and WAIT reduces but does not eliminate the chance of losing an acknowledged write during failover; Sentinel's deployment notes say a Sentinel plus Redis system does not guarantee that acknowledged writes are retained. For Redis Cluster, multi-key operations require all keys to hash to the same slot, and scripts must receive every key they touch as declared key arguments; hash tags such as {t:atlas} force colocation. These sources were read in the official redis/docs repository on 6–7 Nov 2026 (see the ledger in the last chapter); the design below leans only on what they say.

F09 — Redis Cluster cross-slot atomicity assumption breaks

A hierarchical check for U-17 touches three keys: the user bucket, the Atlas tenant bucket, and a fleet-wide GET /catalog protection key. On the single-node staging Redis the three-key script works. In production the data lives on a cluster, where each key hashes to one of 16,384 slots and a multi-key operation requires every key to be in the same slot; the cluster spec says multi-key operations are only available when all keys hash to the same slot, and the scripting docs add that all keys a script touches must be passed as declared key arguments. The user and tenant keys carry the tag {t:atlas} and colocate; the global key has no tag and lives on another node. The script is rejected (in practice with a CROSSSLOT-style cross-slot error; the exact error text is not quoted in the sources checked for this page).

What the gateway does with that error decides the incident. Under fail-open, every request is 'a limiter error' and passes: a deploy that looked like a harmless refactor disables all enforcement. Under fail-closed, every request on that rule is denied: a self-inflicted outage. Neither is a rate-limiting decision; both are a missing capability being treated as an answer. The repair is to stop pretending: keep rules that must be atomic together under one hash tag (tenant-scoped rules), and evaluate the cross-tenant global rule as a separate, explicitly non-atomic step that may admit slightly more than the global limit or be handled by token leasing (F13). A staging environment with the same cluster topology would have caught this.

F10 — Primary failover loses recently acknowledged counter writes

Redis replication is asynchronous by default: the primary acknowledges a write before the replica has necessarily received it. Primary R serves the shard that holds Atlas's keys; R2 trails by up to 200 ms during a busy moment. At t = 0 R dies. A failover promotes R2, whose state is whatever had been replicated. Every script effect in the unreplicated tail — the debits that clients were told succeeded — is gone. The Redis docs are plain about it: WAIT makes it harder to lose a write but does not turn Redis into a strongly consistent system, and acknowledged writes can still be lost during failover.

Quantify the loss with the planning numbers. A shard averaging 25,000 script calls/s with a 200 ms tail has 25,000 × 0.2 = 5,000 effects missing. For a single key the bound is the debits it took in that tail: Atlas at its 1,000/min cap admits about 16.7/s, so a 1 s lag could lose roughly 17 tokens (~1.7% of the minute's quota); a user bucket regains at most the tokens it spent in the tail, ≤ 20. The loss is leniency, not strictness (a stale replica has more tokens than reality), it is silent, and it is a one-shot over-admission bounded by the unreplicated tail. A worse variant exists: Sentinel docs warn that a client partitioned with an old primary can keep writing to it until it learns of the failover, and those writes are discarded. For P-READ and P-ANON that is acceptable and cheaper than WAIT on every call. For quotas where it is not, use a durable ledger or an allocator that accepts the cost of synchronous replication.

F20 — Redis outage: strict route fails closed, low-risk route falls back locally

At 14:02 the whole limiter store becomes unreachable for four minutes (power event on R's rack; R2 is also down). Every gateway's script call times out at its 5 ms budget. Northstar had chosen the fail mode per route in advance. POST /reports/export — ten units and an expensive backend — fails closed: the gateway returns 503 (not 429, because the caller did nothing wrong) with a small Retry-After hint. GET /catalog falls back to a per-gateway local bucket. P-GLOBAL is 40,000 req/s over 100 gateways, so each gateway's fair share is 400 req/s; with 100 gateways each enforcing exactly that, the worst case fleet-wide admission is 40,000 req/s again — the fallback preserves the global ceiling only if LB spread is even and gateways don't allow more than 1/100th.

If an operator sets each fallback to 800 req/s 'to be safe for customers', the bound becomes 80,000 req/s, 2×. The honest framing of availability is per route: during the outage, catalog readers keep working with approximate limits, while exporters get a clear refusal. A strict-safety stance means some legitimate users are rejected: that is the intended behavior, because an unmetered export route is a way to topple the backend that serves everyone else. What users experience must be told as 503 with guidance, not a vague timeout, and the circuit breaker on the limiter client keeps the 5 ms budget from turning into 5 ms of queueing for every request.

Capacity failures come in two shapes: the limiter itself becomes the bottleneck, or the limiter is fine and the thing behind it is not.

The limiter's load is made of attempts. At the 50,000 req/s baseline a ten-times surge is 500,000 admission calls/s; with a hypothetical 40,000 script executions/s budget per primary, that is 500,000 / 40,000 = 12.5, so at least 13 shards, and Northstar plans 20 (25,000/s each, 62.5% of budget). That assumes uniform hashing, an assumption that hot tenants break (F13). Five hierarchical checks in five stores would be 2.5M interactions/s; the same rules in one same-shard script are 500,000 script calls. The patterns load shedding, bulkhead and circuit breaker apply directly here, and cascading failure describes the way an overloaded limiter propagates into the API.

F12 — The limiter itself overloads at peak; pool exhaustion

Peak is 500,000 admission calls/s across 20 shards: 25,000/s per shard, 62.5% of a hypothetical 40,000/s budget. Now a shard pauses for 50 ms (a rewrite, a big-key delete). Each gateway handles 500,000 / 100 = 5,000 req/s, and by Little's law concurrent in-flight store calls ≈ rate × latency: at 2 ms that is 10; at 50 ms it is 250. A pool of 64 connections is saturated once latency exceeds 64 / 5,000 = 12.8 ms. Callers queue for a connection, the queue grows, and requests wait long enough that the client times out and retries, adding load.

So the limiter, whose job is to protect the backend, has become the thing every request waits on. Three bounds fix this and all three must be finite (I10): a small pool with a short acquire timeout; a total deadline (say 5 ms) after which the fail mode applies; and a breaker that stops calling a struggling shard so it can recover. Latency from one shard must not queue behind requests for healthy shards, so pools are per shard (a bulkhead). If that shard's pool is empty the right answer is the route's fail mode immediately, not waiting.

F13 — One hot tenant saturates a single shard

Atlas floods at 75,000 attempts/s, 15% of the 500,000 req/s peak, and all of its keys carry the tag {t:atlas} so one hierarchical script can touch them. Everything lands on one shard whose budget is 40,000 script executions/s. The shard sees 75,000 / 40,000 = 187.5% of its capacity from Atlas alone; add the ordinary 25,000/s average that shard would serve anyway and the load is 100,000 / 40,000 = 250%. Birch lives on the same slot range by hash luck and now gets slow decisions, though Birch has done nothing.

The important detail is that the limiter's load is attempts, not admits. Atlas's actual admits are capped at 1,000/min (≈16.7/s); the other ≈74,983/s are denials, and each denial still costs a script run. Two different mitigations apply to two different shapes. For deny-heavy keys, the gateway honours the store's retryAfter with a short negative cache (a floor of 250 ms): once a gateway hears 'denied, retry in 0.8 s' it denies locally for that long. 100 gateways making at most 4 calls/s each means 400 store calls/s instead of 75,000, a 99.5% reduction; staleness costs at most 250 ms × 16.7 tokens/s ≈ 4 tokens of Atlas's tenant budget, about 0.4% of its minute. For admit-heavy keys (P-GLOBAL at 40,000/s) the answer is token leasing: chunks of 100 tokens across 100 gateways cut store operations from 40,000/s to 400/s, with up to 100 × 100 = 10,000 tokens parked in gateways, 0.25 s of global capacity, as the explicit staleness bound.

F27 — Expensive export hits the concurrency cap despite low RPS

Atlas runs a nightly job that starts one export every 10 s, 0.1 req/s — nowhere near any rate rule. Each export runs for 90 s. By Little's law the in-flight count is arrival rate × duration = 0.1 × 90 = 9, but P-EXPORT allows only 3 in flight per tenant. The sustained ceiling is 3 / 90 = 0.033/s, i.e. 2 exports per minute, against 6 arriving per minute: four of every six exports (two in three) are refused, and the 9 in-flight the job wanted can never materialize. The job's owner reads 'rate limit exceeded', checks the 1,000/min policy and is baffled: the rate was fine; the semaphore was not.

Concurrency and rate are different mechanisms with different failure modes. A rate bucket needs only elapsed time; a semaphore needs acquire and release, and release can fail. If a worker crashes holding one of Atlas's three permits, it stays held. The lease must therefore expire (TTL longer than the longest legitimate export, with a renewing heartbeat); but too short a TTL lets a slow job lose its lease and a fourth run start. The response should say which limit refused the request, with a Retry-After that is only a hint (I5), and releases must be idempotent so a retry doesn't free someone else's permit.

F28 — Backend overload persists although every client is within quota

Northstar's catalog backend comfortably serves 2,000 req/s per cell (a cell is one independently scaled copy of the backend with its own capacity). Each user is within P-READ's 2/s sustained refill, but 1,500 users all at their ceiling produce 1,500 × 2 = 3,000 req/s, 150% of that cell, with no individual violating anything. P-GLOBAL's 40,000/s protects the fleet because it is sized for 20 such cells (20 × 2,000); it says nothing about whether one cell's traffic is unevenly distributed to a single backend.

Per-client limits bound each client, not the sum. The sum is determined by how many clients show up, and a launch, a mobile push or a cache expiry can bring thousands at once. The response is a layered one rather than a larger counter: an aggregate admission cap near the backend (sized to measured capacity), load shedding that prefers cheap reads over exports when the backend's latency climbs, and bulkheads so a surge on one route doesn't consume capacity for another. When shedding, deny the least valuable work first and be explicit that those are 503s from overload protection, not 429s attributed to a customer.

A limit is only as fair as the key it counts, and a key is only as trustworthy as the process that derived it.

The same limiter code can be too strict (people sharing an address), too weak (an attacker minting addresses) or irrelevant (an attacker aiming at an account rather than a source). The identity question precedes the counting question: the invariant I3 requires each decision to be attributed to a trusted principal scope, not to whatever string the request supplied. The ordering rule used here is cheap edge limits keyed by network source first, verification of the credential second, and principal-scoped limits third, so unauthenticated callers never create expensive state and never learn another tenant's quota.

F16 — NATed mobile users unfairly share one public IP

A mobile carrier places 500 handsets behind a single public address. P-ANON counts 20 requests per 10 s for that IP. When a marketing push opens the Northstar app on all of them at once, the first 20 requests succeed and the remaining 480 of 500 (96%) are denied. Each user, individually, made one request. The limiter's view — one noisy source — is the NAT's doing, not theirs.

The inverse is the abuser who hides behind the same sharing, which is why simply raising the IP limit is a poor reflex: 500 × 20 = 10,000 requests per 10 s through that address is enough to hurt. A better structure is two-tiered. Unauthenticated routes (a first GET /catalog) keep a generous, coarse IP rule sized for known carrier-grade NATs. As soon as a request carries a verified identity (a signed token, an API key tied to a tenant), the limit moves to that principal, where each handset has its own P-READ bucket. Device tokens issued after a first challenge can narrow anonymous keys a step further. Whichever signal is used, the denial response should say that the limit applies to the network address, so support can recognize the pattern.

F17 — Untrusted forwarded-for header evades IP policy

Northstar's gateways derive the client IP from the leftmost entry of X-Forwarded-For. That header is plain text and a client can send it. An attacker running a single machine at 5,000 req/s changes the header on every request: 5,000 different 'IPs' per second, each with a fresh P-ANON window of 20. Every request is admitted, and the limiter has created 5,000 new keys per second to remember them (the F14 shape).

The fix is about trust, not parsing. Only append-style proxy headers set by infrastructure you control can be believed, and the correct entry is the one added by your own outermost proxy. The standard approach is to take the address of the connection from the last trusted hop (the edge load balancer sets or overwrites the header; gateways discard any value coming from outside it, and count hops from the right). I3 also forbids attributing decisions to an unverified header, so the decision log must record which hop supplied the address. Where the edge is a CDN, use its connecting-IP field rather than the generic header. IPv6 adds another detail: one customer can control a /64 or more, so keys should aggregate to a prefix rather than treat each address as a person.

F19 — Anonymous login attack bypasses authenticated-user quotas

POST /login happens before anyone is authenticated, so none of the per-user quotas exist yet. A botnet of 2,000 IPs each sends 2 attempts/s, inside P-ANON's 20 per 10 s, aimed at the one account U-17 and at a long list of other usernames. That is 4,000 guesses per second, 345.6 million per day (4,000 × 86,400). Each IP is entirely polite; the target is not.

Another key is needed: the targeted account, hashed so the raw username isn't stored in key names. A bucket of, for example, 10 failed attempts per 10 minutes per account bounds guesses at U-17 to 1/min = 1,440 per day instead of the botnet's 345.6M. But this key can itself be weaponised. An attacker who can send failures for U-17 would lock the real owner out; so the account key throttles (slows, requires a challenge, sends the owner a notice) instead of hard-locking, and successful logins from known devices bypass the failure count. The limiter provides the counting; credential-stuffing detection, WAF challenge and breached-password checks are separate controls (I9).

F35 — Malicious traffic consumes limiter state before authentication

Northstar decides to rate limit by API key, so the limiter runs first and the key is whatever the request header says. A scanner floods 100,000 req/s with random strings in the API-key header. Every request creates a bucket, 100,000 new keys/s. With a 60 s idle TTL that is 6M live keys × 200 B = 1.2 GB (the whole planned fleet footprint for two million keys is 400 MB), and the script executions alone are 100,000 / 800,000 = 12.5% of the 20-shard budget before a single real request is served. Birch, calling with a valid key, now competes with this noise for the same shards.

The ordering of checks is the defense. A cheap local signature or key-format validation can reject syntactically bad credentials at the gateway without touching the store. Before that, a coarse in-process limiter on the source address (no network call, bounded memory, approximate by design) absorbs volume. Only after a request is attributable should per-principal state be created. That order doesn't leak quota information either: unauthenticated callers receive the same generic denial and no remaining-quota headers, and a 401 for a bad key is not a 429. The cost is that a very large distributed flood still lands on the CPUs of the gateways; the limiter is not a DDoS service (I9).

Hierarchies of limits are where careful designs break: which rule denied, which rules were charged, and whose key was it anyway.

Northstar's semantics are simple on paper. A request must pass every applicable rule — user bucket, tenant quota, route cost, concurrency cap, fleet protection — and the effective limit is the most restrictive. Three things go wrong in practice: partial charges when one rule denies (F08), precedence that doesn't match the operator's mental model (F18), and keys that don't isolate what they claim to (F29). All three are specification failures, not Redis failures.

F08 — Multi-key partial debit when one rule denies

A request must pass two rules: U-17's P-READ bucket and the Atlas tenant quota of 1,000/min. The implementation is sequential: debit the user's bucket, then check the tenant's. The tenant is at its cap, so the request is denied, but U-17's token is already gone. The denied user is charged for service they never received.

With the tenant exhausted for 30 s and a client retrying at 5 req/s, U-17 spends five tokens a second and refills two: net loss 3 tokens/s, so a full 20-token bucket empties in 20 / 3 ≈ 6.7 s. When the tenant window resets she is still locked out by her own empty bucket — a failure that the tenant's denial caused but that outlasts it. Two correct designs exist. If the keys share a hash slot (tag {t:atlas}), one script checks every rule first and debits only if all pass: all-or-nothing, I2's condition. If the rules sit on different shards, no single transaction exists; you must either refund the first debit when the second rule denies (with idempotency, or the refund can duplicate), or reorder to check the scarcest rule first and accept a bounded inconsistency.

F18 — Tenant/user limit conflict and wrong rule precedence

Atlas asks for a higher per-key limit for K1, and an operator adds an override of 100 reads/s. Atlas's tenant plan is 1,000/min = 16.7/s. The system's semantics are 'every applicable limit must permit the request', so the override only raises one link of the chain: the tenant's sustained ceiling stays 16.7/s (and a user-level bucket such as P-READ still refills at 2/s). Because the tenant budget is a minute-sized allowance, though, K1 can spend it as a burst: at 100/s for 10 s it consumes the whole 1,000-per-minute budget, and every other Atlas user is denied until the window ends.

The incident has two readings. In the first, the semantics are right and the expectation is wrong: nobody showed the operator the effective limit. In the second, an implementation uses 'most specific rule wins' without a tenant cap: K1 then runs at 100/s = 6,000/min, six times the tenant plan (6,000 / 1,000 = 6), starving others. The design answer is to make precedence explicit (all must pass), compute and display the effective limit when a rule is authored, lint overrides that exceed their parent, and name the denying rule in the response so the customer sees 'tenant quota' rather than 'your key'.

F29 — Counter key collision contaminates tenants

A refactor drops the tenant from the user key: rl:v3:u:U-17:read. Atlas's U-17 and Birch's U-17 — two unrelated people whose ids both came from small per-tenant sequences — now share one bucket of 20. During an Atlas flood on that user id, Birch's U-17 receives 429 on a first request. Another variant, concatenating fields without a delimiter, makes tenant 'ab' + user 'c1' the same string as tenant 'a' + user 'bc1'.

Contamination is silent: every individual decision is internally consistent, and both parties are told 'rate limited' by an honest-looking system. The fix is a key builder used everywhere: tenant first, mandatory, inside the hash tag; fields length-prefixed or encoded; principals hashed for privacy (also keeping raw ids out of logs); version and namespace as fixed prefixes. A unit test creates identical principal ids in two tenants and asserts distinct keys, and a canary request from Birch with Atlas's flood running checks isolation end to end. I3 asks the same of every decision log: the scope that produced the decision must be recorded.

Across regions, no design is both strictly exact and fully available during a partition (I8). The honest choice is which bound to advertise and which cost to pay.

For Atlas's global quota G = 1,000 requests/min, three designs sit on one axis. Independent regional enforcement is fully available and unbounded in overshoot (up to n × G). A home-region authority has zero overshoot but makes the remote region pay a WAN round trip (80–120 ms in this illustration) and deny during a partition. Regional leases sit between them with a stated bound.

F21 — Regional partition: independent regions overshoot the global quota

Atlas's global P-TENANT quota is G = 1,000 requests/min across regions EU and US. During a network partition between the regions (or between each region and the allocator) a design that enforces the full limit independently in each region admits up to 1,000 in EU and up to 1,000 in US: 2,000/min = 2× G. With n regions the worst case is n×G. The naive design isn't wrong to be available during a partition; it is wrong to advertise a global limit it can't keep.

A leased design gives each region only a share to spend. The allocator holds the pool for the minute; regions ask for chunks of 100 tokens with a 15 s TTL, clamped to the window end; grants never exceed the remaining pool. If the US holds 200 unspent tokens when the partition starts, it can admit at most those 200 until they expire and gets nothing new: overshoot is 0, the cost is up to 200 tokens (20% of G) stranded and requests denied. The general bound for admitted traffic in a window is G + carry-over of unclamped leases across the boundary + local fallback allowances + grant records lost in an allocator failover. With two regions, carry-over ≤ 100 each gives +200 (+20%), and a bounded fallback of 100 each adds another +200, so the worst case is 1,400 = 1.4 × G if both are permitted. A strict home-region variant yields zero overshoot but forces the remote region to pay a WAN round trip (80–120 ms in this illustration) and to deny during partition: there's no zero-overshoot, fully-available option (I8).

F22 — Regional lease exhaustion despite globally unused tokens

Atlas's pool of 1,000/min is split statically 50/50. EU demand in the minute is 900 and US demand is 100. EU spends its 500 and is denied 400 requests; US serves its 100 and leaves 400 unused. The tenant observes 600 successful requests out of 1,000 allowed (60% utilization) while the allocator shows 400 tokens untouched — the quota is available, just parked in the wrong place.

Demand-weighted renewal repairs it: regions renew in 100-token chunks as local remaining falls under a threshold, and the allocator grants from the shared pool in the order of requests. EU asks nine times and US once, so the full 1,000 are used (900 + 100) at the cost of renewal round trips (80–120 ms each in this example, taken before the chunk runs out so the request path never waits). Unspent tokens at lease expiry return to the pool where the window allows. Granularity matters: what can be stranded in a partition is whatever a region holds at that moment. With two 100-token chunks parked in the US, as in F21, that is 200 tokens (20% of G); smaller chunks lower the bound but cost more renewals.

F23 — Lost or duplicated lease grant after retries; fencing and idempotency

The US asks the allocator for a 100-token lease; the allocator grants and debits the pool; the response is lost; the US retries. If the allocator treats the retry as a new request, it debits the pool a second time — 100 tokens are consumed from G and the region only knows of one lease (a 10% waste of G). If the US instead applies both grants while the pool only counted one (a bug in the dedupe path), the region holds 200 against a 100 debit: a 100-token overshoot, 10%.

Two mechanisms close it. Leases are identified by region plus a sequence number: the allocator stores the grant keyed by that id and returns the same lease on a replay (idempotency, with a retention window longer than the longest retry). Each lease also carries an epoch (a fencing token) so that after an allocator failover or a region restart, leases from an older epoch are refused at reconcile. The allocator's own state faces F10: if its grant records are replicated asynchronously, a failover can forget grants made in the unreplicated tail. With a lag window that saw at most k = 2 chunk grants, up to 200 tokens (+20% of G) could be granted again. Hence the bound's last term, 'grant records lost in allocator failover'.

F32 — Clock, time-zone and reset assumptions create inconsistent policy application

Fixed windows for P-ANON align to epoch multiples of 10 s, which is the same instant everywhere. But a hypothetical daily plan quota for Atlas was implemented as 'reset at local midnight', each region using its own zone. EU resets at 00:00 CET, US at 00:00 PST, 9 hours apart (UTC+1 vs UTC−8). Atlas sees EU capacity return at 23:00 UTC and US capacity at 08:00 UTC, and the global daily total is no longer one day: in a 24-hour slice that straddles one region's reset but not the other's, the combined admits can exceed the daily quota.

Daylight-saving shifts make it worse: a 'day' is 23 or 25 hours twice a year, and zones switch on different dates, so for a few weeks each year the 9-hour offset becomes 8. The remedy is to define every window as a UTC epoch interval, publish reset to clients as an absolute epoch time or a delay-seconds value, and let the customer's billing timezone live only in the control plane, which translates it to a UTC boundary once. Key-expiry clock semantics were not checked for this page, so the safe design is to give every window its own explicit boundary (a window id derived from UTC epoch time) and use TTL only for cleanup.

Policies are data, and distributing data takes time; the limiter has to decide what to enforce while that time elapses.

There are three clocks at work: how fast a new policy reaches gateways, how long a gateway will keep using one it can't refresh, and how long a rolling deploy leaves two behaviors in production at once. The separation of stale policy from stale counters (I13, I3) is useful here: the counter store might be perfectly consistent while the rules applied to it are an older version. Feature flags face the same propagation problem, and the feature flag system design shows the same pattern from a different angle.

F24 — Stale policy after emergency tightening

At 10:00:00 an operator cuts Atlas's P-TENANT from 1,000/min to 200/min to stop a flood. Gateways poll the control plane every 30 s and cache the snapshot. Until each gateway refreshes, it enforces the old numbers. If Atlas sends traffic at the old limit, the extra admitted in a 30 s staleness window is 1,000/60 × 30 = 500 versus 200/60 × 30 = 100 permitted, i.e. 400 extra requests. A gateway that lost its connection to the control plane can remain stale indefinitely unless a maximum age forces a safe default.

Two separate states are in play: policy (rules) and counters. Stale policy means the right counter is consulted with the wrong parameters; stale counters means the right parameters apply to the wrong state. This incident is the first. A related trap: if the policy version is part of the key (rl:v3:... becomes rl:v4:...), activating the new version also swaps in a fresh, full bucket, handing every principal a one-time allowance; parameters that change in place avoid that. I13 says it plainly: there's no instantaneous global revocation; there is a bound, and the bound is poll interval + jitter + max-age. For a real emergency, use a push channel plus a hard edge-side deny rule, since policy propagation is the wrong tool for a flood happening now.

F25 — Rollback of a bad policy and out-of-order snapshots

Policy v41 ships with a unit mix-up: Atlas's tenant limit becomes 10/min instead of 1,000. Within a minute, deny rates on Atlas jump to 99%. The operator 'rolls back' by re-publishing v40, and gateways ignore it, because they accept only versions greater than the one they hold (v41). Separately, consider a delayed v41 message that reaches a gateway after it has already accepted a later good version (say v42): without ordering checks it overwrites the good config with the bad one.

Rollback must be forward-moving: publish v42 with the contents of v40, and let gateways accept only strictly increasing versions (reject a lower or equal version), with each snapshot immutable and checksummed. The rollout should limit damage before anyone rolls back: a 5-gateway canary of 100 is 5% of traffic, enough to see the Atlas denial rate move from ~1% to 99% and halt the publish automatically. The deny-rate-by-policy-version signal is what turns a bad number into a five-percent incident; a full-fleet instant push turns it into a hundred-percent one.

F34 — Rolling deploy changes algorithm or policy version and reshuffles eligibility

Release 4 changes P-ANON from a fixed-window counter (string keys) to a token bucket (hash keys) and bumps the key namespace from rl:v3 to rl:v4. The rollout replaces 100 gateways in 10 batches, two minutes apart: for about 20 minutes both versions run. A client load-balanced across them is judged by two independent sets of keys: up to 20 per 10 s under v3 on the old pods plus a fresh full bucket of 20 under v4 on the new ones. In the worst case the client gets 2× during the mixed period, and each flip hands out a fresh full bucket once.

If, instead, the new code reused the old key names, it would find string values where it expects hashes and the store would return a wrong-type error (standard Redis behavior for commands applied to a key of another type; not re-checked against the docs for this page), which looks like a limiter outage on the new pods. Expand–contract migrations avoid both: ship code that can read both formats first, run the new algorithm in shadow mode (compute the decision, don't enforce, compare), switch enforcement through the control plane rather than through code deployment, and let old keys age out by TTL. Because TTL = time-to-refill plus slack, the old namespace disappears within minutes.

Clients are part of the system: their retries decide whether a denial lowers load or multiplies it.

A 429 (RFC 6585) is a statement about the caller's quota; Retry-After (RFC 9110, a delay in seconds or an HTTP date) is a hint about when trying again is likely to be useful, not a reservation (I5). A 503 means the service or its dependency is unavailable and shouldn't be used as a synonym for 429. The RateLimit header fields are an IETF Internet-Draft, not a published RFC: the working group's source repository still labels the document an Internet-Draft (checked 7 Nov 2026), although the datatracker page itself could not be opened from the authoring environment, so treat the status as 'draft, check before citing'. The practices for clients are in retry and backoff, and the retry storm module shows the production pattern.

F11 — Quota-store timeout: ambiguous write and a double-check on retry

The gateway sends the token-bucket script for U-17, the store executes it (one token debited), and the response is lost on the network; the gateway times out at 20 ms. The gateway cannot tell whether the debit happened. A naive client library retries automatically; the second execution debits again. U-17 paid two tokens for one request, or, if the gateway treats the timeout as fail-open, was admitted while also being charged. Ambiguity is intrinsic: a timeout means 'unknown', not 'did not happen'.

There are two defensible policies. First: do not retry debit scripts at all. A single attempt with a deadline, then the route's fail mode, bounds the error to at most one extra debit per timeout. Second: make the debit idempotent with a stable logical request id. The script records the id with a short TTL and returns the stored decision on replay. The cost: 25,000 script calls/s per shard with a 15 s id TTL is at most 375,000 live ids; at an assumed 60 B each that is 22.5 MB per shard, plus the collision and replay rules (ids scoped per tenant, TTL longer than the retry window, shorter than the bucket's purpose). Pick the first unless the route's retries are unavoidable.

F26 — Aggressive retry storm from synchronized Retry-After

Atlas's 10,000 clients are told Retry-After: 1. They all sleep exactly one second and retry at the same instant. At t = 1.000 s, 10,000 requests hit the gateways within a few milliseconds — 100 per gateway — and the tenant's shard. If the planning budget is 40,000 script executions/s, each execution is on average 1 / 40,000 = 25 µs of shard time, so 10,000 simultaneous calls represent 10,000 × 25 µs = 0.25 s of one shard's single-threaded work. A shard is blocked for a quarter of a second, and everything else on it queues.

Denied again, the clients retry again at t = 2.000 s: a heartbeat of synchronized spikes, a pattern that persists until demand falls. With jitter, say uniform over 1–2 s, the same 10,000 clients spread to ≈ 10,000 per second average, a spike that is 25% of one shard's budget rather than a quarter-second stall; with jittered exponential backoff (delay chosen uniformly up to base × 2^attempt) later waves spread wider still. Since Retry-After is a hint rather than a reservation (I5), the server can add jitter to the hint itself so even naive clients desynchronize, and gateways can negative-cache (F13) so repeated denials stay out of the store.

The last two incidents are about the edges of the limiter's authority: what it only reports, and what it does not see.

A decision log, a metric and a usage report are views of what the limiter did; they are not the limiter. A bypass is the opposite: a path that avoids the limiter and therefore avoids its views. Both are dangerous for the same reason, which is that the dashboards stay calm. The correctness invariants I12 and I14 are the guardrails: metrics are not a ledger, and privileged routes are narrow, authenticated, audited and capped.

F30 — Allowed telemetry is lost or duplicated; observability is not the authority

Every decision is also published to an event pipeline for dashboards and usage reports. At 15% loss in the pipeline the dashboard shows Atlas at 850 admitted in a minute when the store actually admitted 1,000; at-least-once redelivery on another day shows 1,300. Neither number says anything about what the limiter allowed: the script on the store decided, atomically, before any event was emitted. Counting events is accounting; the decision is enforcement.

Confusing the two causes real harm in both directions. If enforcement read the lossy metric, then with a 15% undercount the limit of 1,000 would fire only after about 1,000 / 0.85 ≈ 1,176 true admits, an overshoot of 17.6% caused by telemetry. If the usage report feeds billing (I12), undercounts lose revenue and duplicates over-bill. The remedy is separation: the store-side script maintains the authoritative window counter and emits a monotonic per-window total; the pipeline carries per-decision events with ids for dedup, and a reconciler compares the sums and raises a discrepancy rather than correcting enforcement. An alert named 'telemetry gap' is a different page from one named 'limit exceeded'.

F31 — Internal bypass or privileged route floods the backend

To keep health checks and an internal reindex job from being throttled, someone adds a rule: if a request has X-Internal: true, skip the limiter. The reindex job runs away at 5,000 req/s against a backend that handles 2,000 comfortably (250%). Nobody counted it, and Birch's catalog calls slow to a crawl. Worse, the header is a header: once it is known, an attacker can add it.

A bypass is a different route, not a skipped check. Internal callers authenticate with a service identity (mTLS or signed tokens), pass through a narrow route with its own small cap (for instance 200 req/s, 10% of the backend's 2,000), and every use is audited with the identity and reason. Health probes get an even smaller allowance on a path that exposes nothing else. The alert is on the privileged route's usage, so the cap's own saturation is visible. I14 sums it up: exemption with accounting, not exemption from accounting.

The incidents reduce to a small set of signals, a few drills and a handful of standing rules. If those exist before the first incident, most of the 35 become short events rather than long ones.

Signals worth paging on, and signals worth a ticket

Service-level objectives for the limiter are best written about its decisions, not its uptime: the fraction of admission calls answered within the p99 goal (a low single-digit-millisecond target in the same region, a goal to measure rather than a benchmark), the fraction answered by the authority rather than by a fail mode, and the over-admission ratio (admitted ÷ allowed) for each strict policy. A limiter that answers 100% of calls from a fail mode is 'available' and worthless; the second measure makes that visible.

Game days that exercise the failures

• Kill primary R during a load test at peak ratio and measure the over-admission tail against replication lag (F10), then confirm routes follow their fail modes (F20).
• Run a hot-tenant flood of 75,000 attempts/s at one tenant and confirm Birch's p99 stays inside target and the negative cache cuts store calls by well over 90% (F13).
• Replay a synchronized 10,000-client retry wave with and without server-side jitter (F26).
• Create 50,000 bogus principals/s against pre-auth routes and watch memory, evictions and script rate (F14, F15, F35).
• Partition EU from US and the allocator; check that admitted ≤ the documented bound for the lease design (F21–F23).
• Publish a deliberately bad policy to the canary only; confirm auto-halt, then roll forward with a higher version (F24, F25).
• Run a rolling deploy that changes the key namespace in shadow mode and diff decisions (F34).
• Corrupt the telemetry pipeline on purpose and confirm enforcement and billing totals are unchanged (F30).
• Restore a snapshot from five minutes ago in staging and measure which limits notice (F33).

• Retrying a debit script after a timeout without an idempotency key (F11).
• Defaulting unknown errors or a missing key to 'allow' or to 'block' without a recorded decision (F09, F15).
• Using telemetry as enforcement or as the quota ledger (F30).
• Creating per-principal state before the credential is verified (F35).
• Header-based bypass of the limiter (F31).
• Calendar-local windows in a multi-region quota (F32).
• Advertising a global limit without stating the overshoot bound and the partition behavior (F21).

Verification ledger and open items

Redis behaviors were checked on 6–7 Nov 2026 against the official documentation sources (the redis/docs repository that publishes redis.io): atomic script execution and blocking, effects replication as the default since Redis 5.0 and the only mode since 7.0, with TIME usable inside scripts under it (scripting intro); asynchronous replication and the limits of WAIT (replication page); no-guarantee-of-retained-acknowledged-writes under Sentinel (Sentinel page); same-slot requirement and hash tags (cluster specification); declared key arguments for scripts (scripting intro); eviction policy list, noeviction and volatile-* behavior (eviction page); RDB snapshots vs. AOF everysec loss window (persistence page); SET-style commands clearing key timeouts (EXPIRE page); script maximum execution time (programmability overview). Not re-verified: the exact CROSSSLOT error text, wrong-type behavior in F34, the evicted-keys counter name, key-expiry clock semantics, and the HTTP/IETF specifications (RFC 6585, RFC 9110), which could not be reopened from the authoring environment; the RateLimit header draft's status was checked only through the working group's source repository. All numbers on this page are hypothetical teaching inputs.