Rate Limiter Architecture: Redis, Token Bucket & Atomic Quotas

The limiter's public surface is a single question — may this request proceed? — and the answer has to carry enough structure for the gateway to respond correctly, for operators to audit the decision, and for a retry to be safe. Everything in the rest of this page is an implementation of that one call.

A word on the example before the details: Northstar API, tenants Atlas and Birch, API key K1, user U-17, gateways A and B, Redis primary R with replica R2, and regions EU and US are all fictional teaching inputs. Every capacity, rate and latency figure below is a hypothetical assumption chosen so the arithmetic is easy to follow; none of them is a measurement or an industry statistic.

Where the decision runs

There are three common placements. An in-process library inside each gateway holds the policy snapshot and talks straight to the quota store, which costs one network hop. A sidecar moves that logic into a neighbouring process so the gateway stays language-agnostic. A central limiter service exposes the decision over a network API such as gRPC or HTTP, which adds a hop and a service to operate but keeps scripts, policies and telemetry in one deployable. Envoy's global rate limiting is an example of the third shape: the proxy calls a gRPC rate-limit service for each request on routes that ask for it, and the project's reference service uses Redis behind that interface. The same page also describes pairing a local token-bucket limiter in front of the global one so that a large burst is absorbed locally before it reaches the shared service — a two-stage layout this design reuses.

The admission request

The gateway builds the request after authentication, never from raw client input. The requestId is what makes a retry idempotent — repeating the call with the same id has the same effect as making it once — which matters when a timeout leaves the outcome unknown. Time is deliberately absent: the store supplies the clock (see the token-bucket chapter), so a gateway with a skewed clock cannot influence refill.

The decision

The diagram above shows the boundary as the contract sees it. The fields that matter most for correctness are policyVersion and deniedScope: the first makes a decision attributable to one immutable policy snapshot, the second tells the client and the operator which rule limited the request, which matters once several rules apply to the same call. fallback exists so that telemetry can separate decisions made with the shared store from decisions made without it.

A rate-limit key is both an identity and a routing instruction. Its text decides which counters are separate, which keys can be touched by one atomic script, which shard owns them, and when the state disappears.

The annotated key and the lifetime diagram above show the two jobs a key does: it names the state and it places it. Redis Cluster computes a key's hash slot as CRC16 of the key modulo 16,384, and when the key contains a non-empty {...} section only that section is hashed as Redis Cluster defines it. That is why the tenant sits inside braces: rl:v3:{t:atlas}:u:…:read and rl:v3:{t:atlas}:tenant:atlas:all land in the same slot and can be read and written by one script. Two consequences follow immediately. First, the tag material must be sanitized: tenant ids come from the control plane and are restricted to a safe charset, because a tenant id containing } or : would let someone shape keys. Second, a tenant tag makes the tenant the unit of placement, so a very large tenant is a hot slot — a trade-off covered in the partitioning chapter.

Principal ids are keyed hashes, not raw values

The principal part is an HMAC of the identifier under a secret pepper, truncated for compactness. A plain hash of a small id space such as IPv4 addresses or sequential user ids can be reversed by enumeration, so a key dump from a debugging session would expose them; an HMAC cannot be enumerated without the pepper. Truncation to 64 bits keeps keys short while collisions stay negligible for tens of millions of principals — and because the tenant tag is outside the hashed part, a collision could only ever merge two principals inside the same tenant, never leak across tenants.

Anonymous identity: how wide is one address?

For anonymous traffic the principal is a network address, and the address family changes what one key means. An IPv4 address is a rough proxy for a household or office, though carrier-grade NAT can put thousands of people behind one. IPv6 gives one customer far more addresses: a /64 or larger delegation to a home connection is common, but delegations vary by network, so no prefix length is correct everywhere. Keying on the full address lets one host rotate through addresses it controls, each with a fresh bucket, and fills the keyspace; keying on a wide prefix lumps unrelated users together and refuses the innocent ones. Treat the prefix length as policy: choose it from the allocations you observe, make it configurable per rule (the HMAC input is then the truncated prefix, not the address), and where abuse is the concern add a second, broader prefix key as a ceiling over the narrow one. Anonymous limits are coarse by nature, which is why P-ANON is a fixed window; the u and k identities do not have this problem.

What the version segment means

v3 names the state shape: which fields exist and in which units (here, millitokens and epoch milliseconds). It is not bumped when a limit changes. Limits travel as script arguments on every call, and the stored token count is clamped to the current capacity, so a tightened policy takes effect on the next request rather than waiting for old buckets to expire. Bumping the version, by contrast, abandons all live state and every principal restarts with a full bucket — which is the right behavior for a format change and the wrong one for an emergency tightening. The policy snapshot number travels in the decision record instead.

TTL is part of the algorithm

Every write sets an expiry in the same script, so a key is never left without one. For a token bucket the expiry is the time to refill from empty plus a small slack: once that much idle time has passed the bucket would be full anyway, and deleting it is indistinguishable from keeping it. For P-READ (capacity 20, refill 2 per second) the full-refill time is 10 s, and with a 5 s slack the TTL is 15 s. For the tenant bucket of P-TENANT the full-refill time is 60 s and the TTL is 65 s. Expiry is what bounds memory: only principals active within roughly the last refill period hold state.

A fixed window counts requests in consecutive, non-overlapping slices of time and resets to zero at each boundary. It is the cheapest algorithm to store and the easiest to explain, and its boundary behavior is the reason it is demoted to coarse jobs in this design.

With window length W and limit L, a request at time now belongs to window w = now − (now mod W), the largest multiple of W not after now. Windows are aligned to epoch multiples, so for P-ANON (20 requests per 10 s) every anonymous IP resets at the same wall-clock instants: :00, :10, :20 and so on. The request is admitted when the count in its window is below L.

The boundary burst

The diagram above makes the weakness visible. A client that sends 20 requests at t = 9.9 s uses up window one; at t = 10.1 s window two starts empty and admits another 20. That is 40 requests in 0.2 s, twice the limit, with both windows individually compliant. The same effect applies at every boundary, so the worst-case instantaneous rate is 2L per W-long interval straddling a boundary. For a coarse anonymous rule that figure is tolerable; for protecting an expensive backend it is not.

Atomic increment with expiry

The textbook form is INCR key, then EXPIRE key W when the reply is 1. Those are two commands, and the gap between them is the first-create expiry race. If the client or the gateway dies after the increment and before the expiry, the key exists with no TTL and keeps its count forever — the principal is locked out permanently, and the memory is never reclaimed. The reversed order has its own hole: SET key 0 PX … NX followed by INCR is safe only until the key expires between the two calls, at which point INCR recreates it with no TTL. Pipelining does not help; a pipeline sends commands together but does not make them one atomic unit.

A script closes the gap, because the read, the increment and the expiry run as one uninterrupted step on the shard. The version below stores the window start inside the value, which adds a second line of defense: even if a TTL were somehow lost, a stale w no longer matches the current window and the counter silently restarts at zero.

Mentally running the script on the boundary example: at now = 9,900 ms the window start is 0 and the 20th request leaves remaining 0; the 21st returns {0, 0, 100} — denied, with 100 ms until the window ends. At now = 10,100 ms the stored w is 0 but the current window start is 10,000, so the count restarts and 20 more requests are admitted. The boundary burst is therefore the algorithm's behavior, not a bug in the script.

The sliding log keeps one record per admitted request and, at decision time, counts how many fall inside the trailing window. It has no boundary artifact, and it pays for that with state that grows with traffic instead of staying constant.

In Redis the natural structure is a sorted set. The score is the admission time in milliseconds and the member is a unique request identifier. A decision is three steps: trim members whose score is at or before now − W, count what remains, and add the new member if the count is below the limit. Trimming first defines the window as the half-open interval (now − W, now], so a request admitted exactly W ago has just expired. The diagram above lays these three steps out on a timeline.

Uniqueness and ties

Two requests can be admitted in the same millisecond. If the member were the timestamp, the second ZADD would overwrite the first and the log would undercount, silently admitting extra traffic. The member must therefore be a unique identifier, and the request's decision id is a convenient choice: replaying the same id finds the existing member (the ZSCORE check above) and returns allowed without adding a second entry, which gives the log idempotent retries for free within its window.

Memory is the real constraint

State is O(number of requests inside the window), per key. A tenant limited to 1,000 requests per minute can hold up to 1,000 entries; 20,000 active users limited to 20 requests per window can hold 20,000 × 20 = 400,000 entries. That is manageable at those numbers and unmanageable for a 100,000-per-minute partner key or a window of hours, and a hot key also means a large sorted set trimmed and inspected on every call. Denied requests do not add entries, which at least keeps a flooding client from growing its own log past the limit.

Retry timing is exact for a unit-cost request: the oldest member leaves the window at oldestScore + W, so the hint is that value minus now — 10,000 ms in the test case where 20 entries were all admitted at t = 1,000 ms and the 21st arrives at the same instant. Weighted costs would need several entries or a cumulative scan, which is one reason the log suits low-volume, high-value limits such as audit-sensitive actions rather than the main per-user path.

The approximate counter keeps just two numbers per key, the count in the current window and the count in the previous one, and estimates the trailing window by weighting the previous count by how much of it still overlaps.

In the diagram, take the canonical case: W = 10 s, limit 20, previous window 18, current window 5, and elapsed 2.5 s. The previous window still overlaps 75 % of the trailing interval, so est = 18 × 0.75 + 5 = 18.5. Admitting one more would make the estimate 19.5, which is at most 20, so the request is allowed. The script below does the comparison in integers by multiplying through by W, which avoids floating-point rounding: the condition is prev × (W − elapsed) + cur × W + W ≤ limit × W, and here that is 135,000 + 50,000 + 10,000 = 195,000 ≤ 200,000.

What the approximation assumes

The formula assumes the previous window's requests were spread uniformly. When they are not, the estimate is wrong in both directions. Suppose all 18 requests of the previous window arrived in its last 2.5 s: at elapsed = 2.5 s the true trailing-window count is 18 plus the current count, but the estimate has discounted the 18 to 13.5. Requests keep being admitted until the estimate would exceed the limit, so the current window can grow to 6 and the true trailing count reaches 18 + 6 = 24 against a limit of 20, which is 20 % over. If instead the 18 had arrived at the very start of the previous window, the estimate overstates and the limiter denies traffic the true window would allow. The error is bounded by the size of the previous window's count, which is why the method is described as approximate and never as exactly enforcing the limit.

A token bucket holds up to capacity tokens, receives refill tokens per period, and spends cost tokens per request. It is the primary algorithm of this design because it models what operators usually mean — a sustained rate plus a bounded burst — in constant space and with a precise retry time.

Units: millitokens and milliseconds

Fractional tokens are real: 300 ms at 2 tokens/s is 0.6 tokens. Floating-point state would work in a single process but is awkward to compare, serialize and reason about across replicas. The design stores tokens as an integer count of millitokens and time as integer epoch milliseconds, so 1 token = 1,000 millitokens, capacity 20 is 20,000, and 2 tokens/s is expressed as 2,000 millitokens per 1,000 ms. Writing the rate as a pair (refill amount, period in ms) rather than a single per-second value keeps awkward rates exact: P-TENANT is 1,000,000 millitokens per 60,000 ms, which is 16.67 tokens/s that has no clean decimal form per second.

The P-READ timeline

The diagram above plots the same timeline. The final row matters for memory as well as arithmetic: after 10 s without requests the bucket is exactly as if it had just been created, which is why the key can expire at that point.

Burst is part of the contract

Over any span of T seconds a bucket can admit up to capacity + refillRate × T: for P-READ, 20 + 2 × 10 = 40 requests in 10 s, twice what a strict "20 per 10 seconds" window would allow. This is the intended burst behavior, and it is also the reason a token bucket is not a sliding window with the same numbers (invariant I4). If a downstream dependency really cannot tolerate that burst, the capacity should be lowered, or a second, stricter rule added.

Weighted cost and retry time

An export carries cost 10 against a bucket with the same 20-and-2 shape (for illustration). If 3 tokens remain, the deficit is 7, and 7 / 2 = 3.5 s, so the hint is 3,500 ms and the HTTP header is Retry-After: 4, rounded up to an integer number of seconds. Rounding up is deliberate: a client that returns at 3 s would be denied again. A cost larger than capacity can never succeed, no matter how long the client waits; that case is reported separately (retry −1) instead of producing an ever-growing hint.

Validation, overflow and clock behavior

"Leaky bucket" names two different things, and mixing them up is the commonest way to design the wrong component. One smooths output by queueing; the other only decides admit or reject.

A leaky bucket as a queue accepts requests into a finite buffer and releases them at a constant rate. Output is perfectly smooth, and the cost is latency, queue memory and a worker that drains the buffer: it is traffic *shaping*. A leaky bucket as a meter keeps only a level that rises with each request and drains at a constant rate; a request is rejected when adding it would exceed the bucket depth. That is *policing*, and it is mathematically the mirror image of a token bucket: level = capacity − tokens. This module's limiter polices; it never holds requests. Delaying or queueing is a separate design with its own capacity and timeout questions. The diagram below lines the three policing formulations up against the shaping queue.

GCRA, the same meter with one number

The Generic Cell Rate Algorithm stores a single timestamp, the theoretical arrival time (TAT): the moment at which the bucket would be completely drained if no more requests came. With emission interval T = period / refill (500 ms for 2 tokens/s) and burst depth B = capacity × T (10,000 ms for 20 tokens), a request of cost c is admitted when max(TAT, now) + c × T − now ≤ B, and then TAT becomes max(TAT, now) + c × T.

Run it on P-READ with the bucket fresh (tat = now): requests 1 to 20 give newTat − now = 500, 1,000, …, 10,000, all within B; the 21st gives 10,500 > 10,000 and is denied with a hint of 500 ms — the same answer the token bucket produced. After 5 s of idle on a bucket whose TAT stands 10,000 ms ahead, the next request has newTat − now = 10,500 − 5,000 = 5,500, which is admitted; the equivalent token count before it was (10,000 − 5,000) / 500 = 10, matching the bucket.

A rate-limit decision is a read, a computation and a write. If another request can run between the read and the write, two gateways can both spend the same last token. The cure is to put the whole sequence inside one operation that the store executes without interleaving.

The conceptual reference

This is a teaching model, not an implementation. read and storeAtomically are two separate operations, so the function as written is *not* atomic across callers: gateways A and B can both read one remaining token and both store a decrement. It also leaves several things open that a real system must settle: now is passed in by the caller, so the time source is whatever each gateway's clock says; refillPerSec = 0 divides by zero in the retry computation; assert is a process crash rather than a decision a caller can act on; fractional refill is floating point; it writes the bucket even on denial, which is a choice rather than a necessity; and the retry hint comes out in seconds while the rest of the system works in milliseconds.

Why one script solves the race

Redis executes a Lua script or function as one uninterrupted unit on a single instance: while it runs, other clients' commands wait, so the script's effects either have not happened yet or have already happened. That is exactly the read-compute-write isolation the pseudocode needs. The same documentation notes that scripts replicate to replicas by their *effects* — the resulting write commands — which has been the default since Redis 5.0 and the only mode since 7.0, and that with effects replication the older restriction on non-deterministic commands is lifted, so calling TIME inside a script is legitimate. Redis's own rate-limiter guides take the same approach and read the server clock inside the script, which removes disagreement between application servers about what time it is.

The cost of this isolation is that nothing else runs on that instance while the script does. A script must therefore be short and bounded: no loops over unbounded data, a capped number of rules, and no commands whose cost grows with the key's size. Redis lets a script run until the busy-reply threshold (five seconds by default), after which other clients start receiving BUSY errors — a limiter script should be a very short operation by design, and its real execution time is something to measure on your own hardware rather than assume.

The production form

A walk through P-READ confirms the units. Arguments: capacity 20,000, refill 2,000, period 1,000, cost 1,000, slack 5,000. For a fresh key, tokens = 20,000 and ts = now. full_ms = ceil(20,000 × 1,000 / 2,000) = 10,000. Twenty calls in the same millisecond each find delta = 0, subtract 1,000 and return {1, remaining, 0}; the last returns 0 remaining. The 21st call finds 0 tokens, retry = ceil(1,000 × 1,000 / 2,000) = 500 and returns {0, 0, 500} without writing — so the denied request changes nothing. Five seconds later with no consumption, delta = 5,000, refill = floor(5,000 × 2,000 / 1,000) = 10,000 millitokens. A cost-10,000 request against 3,000 millitokens returns {0, 3000, 3500}; the gateway turns 3,500 ms into Retry-After: 4. After every allowed call the key expires in full_ms + slack = 15,000 ms.

Choices the script makes, stated out loud

• Denied requests do not consume. A deny returns before any write, so a flooding client cannot drain its own bucket below what honest retry timing would give it, and a denied request costs no replication traffic. The alternative — charging attempts to discourage hammering — is a legitimate policy, but it needs its own rule and its own counter.
• Only the store's clock is used. ts is never taken from the caller, and ts = max(ts, now) keeps the stored timestamp from moving backwards.
• Keys and arguments are separated. The bucket key is passed in KEYS, limits in ARGV; the script computes no key names, so it stays valid under Redis Cluster.
• TTL is set in the same write. No code path can store state without an expiry.
• Parameter errors surface as errors. A malformed policy yields an error reply the client classifies as a policy fault, distinct from a store outage.

Atomic is not durable

The diagram above shows the sequence. Atomicity is a property of one instance at one moment. Redis replication is asynchronous by default: the primary acknowledges the write before every replica has it. If R fails and R2 is promoted before it has applied the last few decisions, those debits are gone, and the promoted instance admits as though they never happened. Redis Cluster's design acknowledges this window plainly, and Redis replication adds that WAIT can make the loss much less likely by blocking until replicas acknowledge, yet writes can still be lost in a failover depending on configuration — it narrows the window; it does not make the system strongly consistent. The bound for a limiter is small and finite: a lost bucket state can make at most that bucket's consumed budget reappear — at most its capacity, 20 for a P-READ user bucket and 1,000 for Atlas's tenant bucket. Restoring from an RDB or AOF snapshot and key eviction under maxmemory have the same shape: an older state or a missing key means a fuller bucket. Evicting counters silently resets enforcement, so the limiter store should use noeviction, or an eviction policy only over keys that are truly disposable, and rely on TTLs for cleanup.

A single request rarely faces one limit. It may need the per-user bucket, the tenant quota and a route budget all to agree, and the interesting question is whether those checks happen as one atomic step or as a sequence that can be left half-done.

All rules or none

The rule is conjunctive: every applicable limit must permit the request. Evaluated sequentially against separate stores, a denial by the second rule leaves the first rule already debited — a *partial debit*: the user bucket lost a token for a request the tenant rule refused. Undoing it needs a refund, and a refund after an ambiguous failure is how quotas get double-refunded. The better design avoids the question by evaluating all rules in one script that reads every bucket, decides, and writes only if every rule allows. A denial anywhere debits nothing.

In Redis Cluster this is only possible when all the keys live in one hash slot; multi-key operations over keys in different slots fail with a CROSSSLOT error Hash tags are the tool: {t:atlas} in every key of tenant Atlas puts the user bucket, the tenant bucket, the route budget and the decision record on one slot, as the diagram above shows. Without the tag the user and tenant keys would hash independently and, on a multi-shard cluster, the combined script would be rejected.

Walk-through for U-17 on GET /catalog: rules are the user bucket (capacity 20,000, refill 2,000 per 1,000 ms) and the tenant bucket (capacity 1,000,000, refill 1,000,000 per 60,000 ms), each with cost 1,000. When U-17 has 1,000 left and the tenant has 639,000, the call returns {1, 0, 0, 0, 638000}: allowed, no denying rule, no retry, remaining 0 and 638,000 millitokens. If the user bucket is already empty the call returns {0, 1, 500, 0, 639000}: denied by rule 1, retry 500 ms, and the tenant bucket still holds 639,000 — nothing was debited. If the tenant bucket instead holds only 3,000 millitokens and the request costs 10,000, the call returns {0, 2, 420, …} — retry = ceil(7,000 × 60,000 / 1,000,000) = 420 ms — and the user bucket stays untouched. With several denying rules the hint is the maximum, since all must be satisfiable, and denied_by names the first denying rule in evaluation order.

• Listing the same key twice in KEYS: both entries would read the same stale state and the second write would overwrite the first. The control plane must reject duplicate keys.
• Unbounded rule lists: script time grows with the number of rules. Cap them (a handful per request) and validate at publish time.
• Evaluating any rule that needs a different slot inside this script. Those rules need leases or an explicit sequence, below.

Which rule rejects first, and what is exposed

Evaluation order affects reporting, not enforcement: all rules are always checked, and the first denying rule is the one named in deniedScope. Put the most specific, least sensitive rule first (user, then route, then tenant), so the client is told about its own limit before it learns anything about a shared one. For a caller without permission to see tenant-wide capacity, the response should name only the scope the caller can act on.

What cannot be atomic across shards

The fleet-wide P-GLOBAL budget (40,000 requests/s on GET /catalog) lives in its own key and its own slot; it cannot share a script with Atlas's keys without forcing all traffic onto one shard. Two ways exist to combine it with per-tenant rules. Sequential checks with compensation: debit global, then debit the tenant script, and if the tenant script denies, release the global debit. That works only if the compensation is idempotent, which a token refund is not. Alternatively, leasing: the gateway holds a locally spendable chunk of the global budget (chapter on hot keys) and consults the global store only to renew it, so the per-request path stays single-shard. This design uses leasing for P-GLOBAL and treats the global budget as approximate by exactly the size of the parked chunks.

Weighted cost is not concurrency

The diagram above separates the two gates. P-EXPORT combines two mechanisms, deliberately. Weighted cost — 10 units per export against the rate bucket — controls how much capacity exports consume per unit time, so ten cheap reads and one export are accounted fairly. Concurrency — at most 3 in-flight exports per tenant — controls how many run at the same time, which a request-rate bucket cannot: a tenant can issue an export per second with minute-long runtimes and pile sixty jobs onto the backend while staying inside any plausible request rate. The concurrency check is a semaphore, a different state machine: acquire a lease with an expiry, release it when the export finishes, and let expiry reclaim leases whose holder crashed.

The release is ZREM key leaseId, which is idempotent by construction — releasing twice, or releasing a lease that already expired, changes nothing. This is the property that makes compensation safe here: if the lease is taken and then the rate bucket denies, the gateway releases the lease and nothing is double-refunded. The ordering is therefore lease first, token debit second, with an idempotent release on denial. Both operations are keyed under the tenant tag and could be merged into one script if the extra round trip matters. A denial from the concurrency rule has no time-based retry hint, because it clears when an export finishes, not at a computable instant; the 429 uses a policy-chosen Retry-After instead, and long exports should renew their lease with a heartbeat shorter than its TTL.

The limiter is on the critical path of every request, so it has to fail in a way that is chosen in advance. The hardest failure is not an error; it is a timeout, because after one the gateway does not know whether the script ran.

Budgets and bounds

Every wait has a bound (invariant I10). The decision gets a single deadline, taken from a monotonic clock, shorter than the request's own budget — for illustration a few milliseconds for the cheap read path. The connection pool is small and bounded, acquisition waits at most about a millisecond, and a request that cannot get a connection degrades immediately instead of queueing behind others; unbounded queues turn a slow store into a slow gateway. A circuit breaker per shard counts timeouts and errors, opens when they exceed a threshold, and lets a limited number of probe calls through when half-open. The usual hazard to avoid is a retry multiplier: three attempts from 100 gateways against a struggling shard triples its load exactly when it can least afford it.

Two kinds of failure

The scripting documentation recommends calling EVALSHA and handling NOSCRIPT by loading the script, because the script cache is volatile across restarts and failovers; the gateway must therefore be ready to re-load on the new primary after a failover.

policy.idempotent is true for rules whose script call carries a decision record (the decision_ttl_ms argument of the multi-rule script is non-zero): exports, lease grants and other expensive or hard-to-undo spends. On a retry the script finds the record under the same decision id and returns the stored result without debiting again, so a lost reply cannot cause a double debit. The retention is bounded — long enough to cover the call's deadline and retries (tens of seconds in the example), short enough that the records stay cheap. At a hypothetical 100 exports/s with 30 s retention that is 3,000 records. Applying the same record to every cheap read would be 500,000/s × 30 s = 15 million records at peak, many times more keys than the limiter itself, which is why cheap reads do not use it. A retry after retention expires would debit again; that residual risk is bounded to one operation. The decision id must be minted by the gateway, scoped to the tenant, and generated with enough randomness that two different requests cannot collide.

For non-idempotent cheap calls, an ambiguous timeout is accepted as a possible single extra debit of one unit (1 token of 20) and the request follows the degraded policy. What must not happen is a compensating refund (INCR back): if the debit never ran, the refund creates a free token, and if a retry then also refunds, the bucket gains tokens it never lost.

Degraded decisions by route class

The diagram above shows the other half of resilience, which is in the client. If 10,000 clients are told Retry-After: 1, all return in the same second and recreate the spike; with jitter spread over roughly one second the same 10,000 arrive at about 10,000 per second on average instead of all in the same instant. Gateways also keep a short negative cache for a denied key — deny locally for up to the returned hint, capped at 250 ms in this example — so a flood against an exhausted key is absorbed at the gateway instead of reaching the shard. See retry with backoff, circuit breaker and load shedding for the general patterns.

The HTTP response is where a correct decision becomes either a usable signal or a new source of load. Status code, ordering relative to authentication, and the retry hint each have one correct place in the pipeline.

Order of checks

The two quotas answer different questions and are not substitutes. The IP check protects the front door from callers who have not proved who they are, including a flood of bogus credentials that would otherwise cost authentication CPU and could create unbounded per-key state. The principal check protects shared backend capacity from callers who have. A design that runs only the second lets unauthenticated traffic through to the expensive part; one that runs only the first lets an authenticated partner behind a shared NAT (network address translation: many users appearing as one public IP) or a rotating pool of IPs through unchecked.

Status semantics

429 Too Many Requests is the status defined in RFC 6585 for a user sending too many requests in a given time; the specification permits a Retry-After header to say how long to wait. 503 Service Unavailable says the service cannot handle the request now. They are not interchangeable: a quota violation by a valid caller is the caller's to fix by slowing down, a limiter outage is the operator's problem, and clients, retry libraries and SLO dashboards treat them differently. When a policy deliberately degrades to a local fallback and that local bucket is empty, the response is 429 because a defined limit rejected it; when the policy fails closed because the store is unreachable, the response is 503.

Not every 429 a client sees comes from this limiter. An upstream CDN, a partner gateway, or the backend itself can each answer 429 for their own reasons, and a request this limiter admitted can still be rejected downstream. Telemetry should tag the originating layer (decision.source) so incident reviews do not attribute every 429 to one component.

Retry-After

RFC 9110 defines Retry-After as either an HTTP-date or a non-negative integer number of seconds. This design emits integer seconds: it cannot be misread because of client or server clock skew, and it is trivial to compute. The conversion from the script's millisecond hint is max(1, ceil(retryAfterMs / 1000)). A 500 ms hint (the 21st request on a drained P-READ bucket) becomes Retry-After: 1; the 3,500 ms export hint becomes Retry-After: 4. Rounding up is deliberate, as a client that returns early is denied again.

The value is a hint, not a reservation (I5). Between the denial and the retry, other requests from the same principal, other gateways, or a policy change can consume the capacity the hint expected to be free. The server may also add random jitter to the hint so that clients denied in the same instant do not return in the same instant, which, combined with jittered exponential backoff in the client, prevents the synchronized retry spike that the retry storm module analyses.

RateLimit header fields: status as checked

Informing clients of their quota proactively is the aim of the IETF HTTPAPI working group's Internet-Draft draft-ietf-httpapi-ratelimit-headers, which defines a RateLimit-Policy field (the quota policies a server applies) and a RateLimit field (the quota currently available). As checked on 6 November 2026, it is still an Internet-Draft, not an RFC: the working group's repository carries revision tag -11 and its source still shows the placeholder RFC number. Check the IETF datatracker for its current state, and the parameter syntax has changed between revisions, so treat the example below as illustrative of the latest draft source and re-check before shipping. The older X-RateLimit-* headers are a de facto convention that different services use with differing meanings; they are not standardized.

Three points from the draft matter in practice. The draft states that when Retry-After and RateLimit appear together, Retry-After takes precedence. It states that the fields convey hints, so clients must not treat remaining quota as a service-level agreement. And it warns, among its security considerations, that servers should not disclose capacity information to untrusted parties, and that counting error responses such as 401 or 403 against quota could let a malicious client probe for traffic information. A token bucket does not have a single window, so advertising q;w is an approximation; if the approximation would mislead, send Retry-After alone.

• Send RateLimit-Policy and RateLimit only to authenticated callers, for the scope they own: their user or key limit, not Atlas's tenant-wide remaining quota to a user who is not an Atlas administrator.
• To unauthenticated callers (stage 1), send 429 with Retry-After and a generic body. Do not include policy names, tenant identifiers, limits or remaining counts.
• Return the same response for an unknown API key and for a wrong secret, so rate-limit behavior does not reveal which identities exist.
• Apply jitter to retry hints and document jittered exponential backoff for clients.

Atomicity is per instance, so capacity comes from spreading keys over shards. Two forces pull against each other: colocation makes multi-rule decisions atomic, and spreading makes load even. The skew that colocation creates is where the limiter fails first.

Sizing from the workload

Hypothetical inputs: 50,000 admission calls/s at baseline and a 10× surge to 500,000/s. If each call is a single script on one shard, and a planning budget of 40,000 script executions/s per primary is assumed (a placeholder to replace with your own load test, not a benchmark), the minimum is 500,000 / 40,000 = 12.5, so at least 13 shards. Planning 20 shards gives 25,000 calls/s on average, 62.5 % of the budget, which leaves room for imperfect hashing and headroom for failover. Combining five hierarchical rules into one same-shard script keeps it at 500,000 script calls/s, one round trip each; the same five checks against five stores would be 5 × 500,000 = 2.5 million store interactions/s.

Memory scales with active keys, not request rate: 2 million active keys at the assumed 200 B/key is 400 MB, about 800 MB per copy with headroom, about 1.6 GB for a primary and one replica. At 20 shards that is roughly 20 MB of live key data per shard (about 40 MB with the headroom) — memory is rarely the first constraint; per-shard CPU and the hottest key are.

A hot key is a load problem on attempts

With the tenant hash tag, all of Atlas's keys sit in one slot and so on one shard. If an Atlas flood attempts 75,000 requests/s (15 % of the 500,000 peak) against one key set, that shard sees 75,000 script calls per second, more than its 40,000 budget — even though Atlas is mostly being *denied*. The limiter's load is determined by attempts, not by admitted requests. Adding shards does not help, since the traffic belongs to one slot. Two mitigations apply, and they fix different problems.

Near the limit, a bucket holding 60 tokens cannot satisfy a 100-token request even though 60 are available. A production lease handles the tail by retrying with a smaller chunk after a denial, or by granting partial chunks. Unspent tokens expire with the lease; refunding them to the store would reintroduce the double-refund problem of an ambiguous retry.

Other levers

• Dedicated or smaller placement for very large tenants. If Atlas alone is a large share of traffic, give its keys a tag with a bucket suffix such as {t:atlas:3} and split its tenant budget into k sub-buckets, accepting that each request then sees a share of the tenant limit (approximate, with slack proportional to the split) in exchange for spreading load over k slots.
• Approximate local counters for coarse protective rules, reconciled periodically, when exactness is not required.
• Pipelining independent decisions from different keys on the same connection to amortise round trips; it improves throughput but provides no atomicity between the commands.
• Cardinality controls: cap new-key creation per source before authentication, so bogus identities cannot grow the key set (see the security chapter).

Across regions, the physics changes: a coordinated decision costs a wide-area round trip, and during a partition independent regions cannot both stay available and enforce one exact global number. Each option below buys one property and sacrifices another.

Take Atlas's P-TENANT quota with a global limit G = 1,000 requests/min, served from regions EU and US. If each region enforces the full limit independently, each admits up to 1,000 in the minute: the tenant can legitimately consume 2,000/min, twice the contract. That is the baseline failure every multi-region design has to avoid.

Leases in detail

The allocator holds the pool for the current minute window: 1,000 tokens. A region asks for a chunk of 100, gets a lease with a TTL of 15 s clamped to the window end, and admits locally from it. Grants never exceed the remaining pool at grant time. Clamping matters: a lease granted at 0:50 would expire at 1:05 if unclamped; clamped, it dies at 1:00, so tokens from one minute cannot be spent in the next — the carry-over term in the bound below disappears when clamping is applied.

Two failure modes of leases need their own defense. A lost or duplicated grant after a retry is why the grant is idempotent by lease id. An allocator failover that loses recent grant records can re-grant tokens that regions already hold, which becomes an overshoot term. The state of the allocator is itself a small quota store whose own replication is asynchronous unless it is built on a consensus-backed store.

Depletion and fairness

Splitting the global limit statically — 500 per region — turns demand imbalance into denial: if EU demand is 900 and US demand is 100, EU is denied 400 requests while US leaves 400 tokens unused. Demand-weighted chunk renewal fixes this: regions renew when they run low, so EU draws more chunks from the shared pool while US draws few. The unfairness left is whatever sits in leases at any instant, bounded by the chunk size times the number of regions.

The overshoot bound

The partition diagram earlier in this chapter shows these quantities for the cut-off case. Admitted traffic in a window is bounded by G plus the terms that each design choice adds: admitted ≤ G + Σ(unclamped lease carry-over across the window boundary) + Σ(local fallback allowances) + (grant records lost by asynchronous allocator failover). With clamped leases the first term is zero. Without clamping and with 2 regions, each carrying up to a 100-token chunk over the boundary, it is up to 200 (+20 % of G = 1,000). A bounded local fallback of 100 tokens per region during a partition adds up to 200. In a partition where US holds 200 unspent tokens and is cut off from the allocator, it can admit at most those 200 before the leases expire, and gets nothing new; with clamping and grants never exceeding the pool, the overshoot is zero, and the cost is that up to 200 tokens (20 % of G) are stranded and the tenant's US users are denied once they run out. The bound is therefore a *design output* that can be tuned with chunk size, TTL and fallback, and stated in the contract.

The data plane makes millions of decisions per second against a policy that changes a few times a day. Keeping the two separate lets policy be audited, validated and rolled back without touching the request path, and it gives every decision a policy version to be explained by.

What validation has to catch

• cost ≤ capacity and refill > 0 for every token-bucket rule (the script's guards are the last line, not the first)
• all numeric fields within the integer bounds, and units consistent (millitokens, milliseconds)
• rule sets for one request map to the same hash tag, are at most a handful long, and contain no duplicate keys
• a fail mode is explicit for each rule; a rule without one does not publish
• exemption rules carry their own caps and an owner; a rule that matches everything or has no cap is rejected

Rollout and distribution

A bundle is an immutable snapshot with a monotonically increasing version and a checksum. The control plane stages it: validate, replay recent traffic samples against it offline to estimate the denial rate by rule, release to a small slice of gateways or a canary tenant, observe the deny rate and fallback metrics, then release to everyone. Gateways keep the previous bundle while they fetch the new one and switch atomically per snapshot; one request is evaluated against one bundle from start to finish, and the version number is written into the decision.

Two sources of staleness are separate and should be reasoned about separately: stale policy (a gateway still evaluating bundle 41) and stale counter (store state that does not reflect recent decisions, from replication lag or restore). Tightening a limit propagates in the time of the slowest distribution path, typically a push plus a poll interval; a gateway that is disconnected from the control plane keeps evaluating its last bundle indefinitely unless it is told to expire it (I13). If instant revocation matters for a rule, give snapshots an explicit maximum age and a conservative behavior after it.

Rollback is not decrementing the version number. A rollback publishes a *new* bundle whose content equals an older one, with a higher version. Gateways accept only versions greater than the one they hold, so a delayed old snapshot arriving late cannot overwrite a newer one. Because limits ride as script arguments and stored tokens are clamped to the capacity in force, a rollback or tightening takes effect on the next call for existing buckets, with no key migration.

An operator needs to answer, in order: is the limiter itself healthy, is it deciding the way the policy says, and is anyone being treated unfairly. The metrics that answer each question are different, and none of them is the ledger of record.

Overshoot cannot be read from the store, which only knows its own authority's view. It is estimated offline: take sampled decision logs from all regions, group by rule and by true window, and compare admitted counts with the limit plus the documented bound of the chosen design. A consistent excess above the bound is a bug in the design or the implementation.

Cardinality has to be budgeted like any other resource. Tenant, rule and route group are bounded and safe dimensions; raw user ids, API keys and IP addresses are not safe as metric labels or in logs. Log the keyed principal hash and a decision id, and keep the sampling rate for allowed decisions low and for denials and fallbacks high.

A rate limiter makes a decision about someone, so the first question is who: and the identity it keys on must come from something the caller cannot choose. Most limiter bypasses come from trusting an identity or a header the caller can forge.

Before and after authentication

Pre-authentication limiting exists to keep the front door from being used as a cheap way to create state or burn CPU. It keys on IP, uses a small, TTL-bound state (the fixed window of P-ANON), and caps new keys per source. Failed authentication attempts count against that IP budget, not against the tenant the attacker claims, so a stranger who guesses Atlas's key id cannot drain Atlas's quota. Post-authentication limits key on verified principals. A request that fails authentication never touches a tenant bucket, which is also why attackers cannot use fake credentials to consume the state of real tenants. The cost to be honest about: IP-only limits are not a fairness mechanism, since many users behind one carrier-grade NAT share an address and a determined attacker rotates addresses cheaply. They defend the front door and nothing else.

Least privilege and privacy

• Give the gateways a Redis identity that can run only the commands the limiter scripts need, on the limiter's key namespace, and nothing administrative; use authenticated, encrypted connections between gateways and stores.
• Store only keyed hashes of principals in keys, logs and metrics. Raw API keys, user ids and IP addresses never appear in key names or log lines.
• Treat the pepper used for key hashing as a secret with rotation: rotating it re-keys all state, so schedule rotation as a version change.
• Run the privileged-operations and health-probe path as a separate route with its own authentication, its own small cap and its own audit log (I14); a bypass that is unmetered is a flood channel.

Each guarantee in this design holds under named conditions. The table states them so that a claim such as "no double admission" is never read as broader than the mechanism behind it.

Two assumptions underlie several rows and deserve a name. The first is a single, correctly operated store authority per key set: one primary per shard, with failover that may lose a bounded tail of acknowledged writes. The second is bounded clock misbehaviour on that authority: wall-clock steps are possible but not unbounded, which is what the clamps in the script absorb.

A worked trace ties the earlier chapters together. All values are hypothetical: policy bundle 42, epoch milliseconds are shown as offsets from T₀, and the Atlas tenant bucket is assumed to hold 640,000 millitokens at the start.

Reading the trace against the invariants: step 7 is I1 in action — one authority serialises the two contenders — and step 8 shows that the losing request consumed nothing; step 11 is I6, the bounded-retention decision id preventing a double debit; step 12 is the reason concurrency is a distinct mechanism; and step 13 is I8 and I10 in miniature, with explicit bounds instead of an unlimited fall-open. The diagrams on this page cover the parts that are easiest to get wrong, and the Complete Design page shows the same components assembled step by step.