Distributed Rate Limiter Interview Guide: Questions & Answers

Ask what a wrong decision costs. If admitting 5% too many requests only warms up a backend, you are building soft protection and can accept approximate counts, asynchronous state and a fail-open path. If the limit is a contractual quota that a customer pays for, you need one authority per quota, an audit trail and an honest answer about overshoot. That single question moves the architecture more than any algorithm choice. Four more matter almost as much. Scope: per anonymous IP, per user, per tenant, per route, fleet-wide, or several of these at once, because multiple rules that must all pass push you toward one shard and one script. Cost variance: if an export costs about ten times a catalog read, counting requests will not protect the backend, so you need weighted cost and a concurrency cap. Geography: one region lets a single Redis shard be the authority; two regions force a choice between a latency penalty and bounded overshoot. Failure behavior: what should /login do when the limiter is down, and what should GET /catalog do? For Northstar I would state the working assumptions aloud: 50,000 req/s baseline, 500,000 at a 10× surge, per-user and per-tenant rules, one strict-sounding quota for Atlas, and soft protection for everything else.

• What if the interviewer says 'just make it exact'? — Ask exact relative to what: one Redis shard, one region, or the planet. Within one shard's atomic script, exactness is achievable. Across regions it costs either WAN latency on every decision or lost availability during a partition. Naming that price is the answer; promising all three properties is the mistake.
• Which requirement would you push back on? — A request for a limit that is simultaneously exact, global, available during partitions and low latency. I would offer the three honest variants from the multi-region chapter and let the product owner choose.
• Do you ask about latency? — Yes, because it bounds the design. I would propose a p99 admission decision in the low single-digit milliseconds within a region as a goal to measure, not a promise, since it includes connection pool wait, serialization and the network hop.

Take Northstar with limit 20 requests per 10 s per IP and two gateways, A and B, behind a load balancer. The caller has used 19 requests, split roughly evenly, so A's counter reads 9 and B's reads 10. The next request arrives at A, which sees plenty of room, and so does the one after at B. In the worst case each gateway independently lets the caller reach 20, and the fleet admits up to 20 × the number of gateways. With 100 gateways and round-robin routing the effective limit is no longer a limit at all, and it changes whenever autoscaling adds an instance. Sticky routing by key rescues the idea: if the load balancer hashes the API key to a gateway, the local counter sees all of that key's traffic. It then fails in three ways: a gateway restart or a rebalance resets or splits the state, one hot tenant pins to one gateway, and tenant limits that span many identities are still scattered. Local counters are still useful in three places: a single-instance service, a coarse edge backstop that only needs to stop floods, and a bounded fallback when the shared store is unreachable. What they cannot do is serve as the authority for a limit that customers can see.

• Could gateways gossip their counters instead of using Redis? — You can, and some systems do, but gossip gives eventual agreement: at any instant each gateway holds an older view of the others, so overshoot is proportional to gossip delay × aggregate rate. That can be fine for soft limits. For a quota with a visible number I would pay for one atomic authority.
• Why not give every gateway limit ÷ N? — It works only if traffic spreads perfectly evenly. If the load balancer sends 60% of a tenant's traffic to A, A starts denying while the fleet total is far under the limit, and N changes during autoscaling. Splitting is the right idea at larger granularity: leased chunks that are renewed by demand, not a fixed division.
• When would you still choose local-only? — A single-instance internal service, a per-connection limit (for example requests per WebSocket), or a first filter at the edge that protects the shared limiter itself from being flooded.

Forty requests in 0.2 seconds, against a limit of twenty per ten seconds. That is the worst case, and it is easy to produce. A fixed window counts requests in aligned buckets, say epoch multiples of 10 s. A client sends 20 requests at t = 9.9 s, all admitted because window one has room. At t = 10.1 s window two starts with a fresh count and admits 20 more. In the 0.2 s straddling the boundary the backend saw 2 × L, and no rule was broken: each window individually stayed within 20. The excess is exactly a factor of two, and a client can repeat the trick at every boundary. Fixed windows are still attractive because the implementation is the cheapest available: an INCR on key:window-index plus an expiry, with the first-create expiry handled in the same atomic step. Aligned reset times are also easy for a client to predict, which helps honest clients and helps attackers align bursts. I use them for coarse anonymous rules such as 20 per 10 s per IP, where a 2× burst is tolerable. For authenticated routes I switch to a token bucket, which bounds the burst explicitly, or to a sliding approximation.

• How does a sliding window counter fix it, and how exactly? — It is an approximation. With W = 10 s, limit 20, previous window count 18, current count 5 and 2.5 s into the window, the estimate is 18 × (1 − 0.25) + 5 = 18.5. Admitting one more gives 19.5 ≤ 20, so allow. The estimate assumes the previous window's requests were spread uniformly, so a burst late in the previous window can be misjudged in either direction. It is far closer than a fixed window but never strictly exact.
• What does an exact sliding log cost? — Memory proportional to the requests inside the window. Atlas at 1,000 per minute holds up to 1,000 entries for that one key; 20,000 active users × 20 entries is 400,000 entries. Trimming and counting must happen in one atomic script, and entry IDs must be unique so requests with identical timestamps do not overwrite each other.
• Could you simply use shorter fixed windows? — That narrows the burst but multiplies keys and writes, and the 2× pattern still exists at every boundary. If the contract says 'no more than N in any 10 seconds', use a log or a counter with an explicit approximation error, not a smaller fixed window.

They are not equivalent, and the difference is the whole decision. A sliding window promises a ceiling on any interval of its length: never more than 20 in any 10 seconds. A token bucket promises two different things, a burst allowance equal to its capacity and a long-run average equal to its refill rate. With capacity 20 and refill 2 tokens/s, an idle bucket can admit 20 immediately and then 2 per second, so over a ten-second span it can admit up to 20 + 2 × 10 = 40, double what a strict 20 per 10 s window would allow. If you describe that as '20 per 10 seconds' you are misstating the contract. For Northstar's authenticated read API I choose the bucket deliberately: real clients are bursty (a page load makes a dozen calls), the bucket lets them burst up to a bound and then settles to a sustainable rate, and the state is two numbers per key regardless of traffic. The sliding window earns its extra cost where the promise itself is a ceiling in any window, for instance a downstream partner who bills or throttles on exactly that rule. If I need both, I enforce both: a bucket for smooth average and burst, plus a coarse window or log for the hard ceiling. Pushed on the weakness of the bucket, I would say it admits more in a short span than a window of equal numeric value would, and that is by design.

• How would you make the bucket match 20 per 10 s more closely? — Shrink the burst and the refill together. Capacity 5 with refill 2/s still admits up to 5 + 2 × 10 = 25 in a 10 s span, so it does not meet a hard ceiling of 20; capacity 5 with refill 1.5/s gives 5 + 15 = 20. The bucket can be tuned so its worst-case span equals the window's ceiling, but then the sustained rate is only 1.5/s and the two remain different shapes, so check the arithmetic against the contract rather than assuming equality.
• Where does the leaky bucket fit? — Strictly, a leaky bucket as a meter is mathematically close to a token bucket. GCRA is the compact formulation that stores a single timestamp, the theoretical arrival time. A leaky bucket as a queue is a different thing: it shapes output by delaying requests, which an API gateway rarely wants because delayed requests hold connections.
• Which has the cheaper state? — Both bucket and GCRA use constant state per key (two fields, or one timestamp for GCRA). The log is O(requests in window) and the counter holds two integers plus the window index.

Compute the wait until enough tokens exist, round up to whole seconds, and describe it to the client as a hint. For P-READ (capacity 20, refill 2/s, cost 1), a client that sends 20 requests at t = 0 empties the bucket, and the 21st is denied with retryAfter = ceil(1/2) = 1 s. For the weighted export with cost 10 when 3 tokens remain, the deficit is 7, 7 / 2 = 3.5 s, and Retry-After becomes 4: rounding down would invite a retry that is denied again. HTTP carries the value either as a count of seconds or as an HTTP date, so a sub-second need of 0.5 s is expressed as 1. Three caveats make it a hint rather than a reservation. Other requests may consume the refilled tokens before the client returns. The bucket state may have changed through failover. And a request whose cost exceeds capacity can never succeed, so there is no meaningful retry time, and the right response is a 4xx that explains the policy, not a 429 with a misleading number. Fixed windows give a simpler value: the remaining time until the next aligned window starts. In practice I would add a little server-side jitter to the hint, because if 10,000 clients receive Retry-After: 1 they all return in the same second, and that is a retry storm we created ourselves.

• What about refillPerSec equal to zero? — Then division is undefined, so reject such a policy at publication time. A bucket that never refills is a one-shot allowance, which is a quota and should be modelled as one with a reset rule, not as a bucket.
• Should the gateway honor its own Retry-After? — Yes. Cache the denial locally for the hinted time, with a short floor such as 250 ms, so a client that ignores the header does not generate a store call per attempt. That protects the shard from denial storms.
• Why integer millitokens? — Refill is fractional: 2 tokens per second over 300 ms is 0.6 tokens. Storing integer millitokens (600 here) avoids floating-point drift and keeps the script deterministic across platforms.

A weighted bucket charges each request a cost instead of a flat one. Northstar's backend comfortably serves 2,000 cheap reads per second, and an export costs roughly ten times a read, so POST /reports/export is charged 10 units while GET /catalog is charged 1. The check is the same atomic step as before: refill, test available ≥ cost, deduct. With a bucket of capacity 20 and refill 2/s, a tenant could fire two exports back-to-back and then sustain one export every five seconds, which is 2 ÷ 10 = 0.2 per second, or 12 per minute when it does nothing else. There are traps. A cost greater than capacity can never be satisfied, so the policy must be rejected at publication. Starvation: if cheap requests keep the bucket below 10, a heavy request never gets through; the fix is a dedicated bucket or budget for heavy routes, not a priority hack. And the real cost of some requests is known only afterwards. For those I charge an estimate up front and reconcile when the true cost arrives, accepting that reconciliation is a second write and can be lost. Weights solve how much a request costs on average; they do not bound how many run at once, which is why exports also need the in-flight cap in the next chapter.

• Where do the weights come from? — From measurement of backend cost per route, reviewed periodically. They are policy data, versioned like limits, and wrong weights show up as backends saturating while limits are unused.
• Could you charge after the request finishes instead? — Post-execution accounting is accurate for variable cost, but it cannot stop a burst that is already in flight. I would combine a modest up-front estimate with a reconciling debit, so the admission decision still protects the backend.
• Is cost per byte or per CPU-second realistic? — It is, for workloads like search or AI inference, where tokens or CPU time are the real resource. The mechanism is the same weighted bucket with a better cost function; the harder part is estimating cost before execution.

Lua itself is not what makes it atomic. Redis executes a script as one unit on one instance, and while it runs, other commands on that instance wait; the Redis documentation describes this blocking behavior as the basis of atomic execution. That is the property the limiter needs. Without it, the gateway would do GET tokens, compute, then SET: gateways A and B both read '1 token', both compute 'allowed', both write, and one token has been spent twice. A script moves the read, the arithmetic and the write into the one place that serialises them. The same fact tells you what you do not get. It is atomic relative to that instance, not across shards, so a script touching two keys in different cluster slots is rejected with CROSSSLOT. It is not durable: Redis replication is asynchronous by default, so an acknowledged update can vanish in a failover. It is not free: while your script runs nothing else on that shard does, so scripts must stay short and O(1)-ish; a log that trims thousands of entries is a latency risk for every other tenant on that primary. Two operational details matter in the design: the script cache can be lost, for example after a restart or failover, so clients that call a script by its SHA-1 digest (EVALSHA) need a fallback: on a NOSCRIPT error they load the script again and retry, and, since Redis 5, scripts replicate by their effects, which is what allows TIME to be called inside them. Reading the store's clock there also removes clock skew between gateways from the decision.

• Why not MULTI/EXEC with WATCH? — WATCH gives optimistic concurrency: if the key changed, EXEC aborts and the client retries. Under contention on a hot key that is a retry loop on top of a round trip each time. A script avoids both because the decision happens inside the single execution.
• Is a Redis Function different from EVAL? — Functions are stored server-side as named libraries and replicate and persist with the dataset, which fixes the lost-script-cache issue. The atomicity story is the same; the deployment story is better.
• What if a script runs too long? — Redis can flag a slow script and other clients start receiving BUSY errors. SCRIPT KILL works only for scripts that have not written. That is a production incident created by an unbounded loop, so I keep per-call work constant and reject logs that cannot be trimmed cheaply.

The request must pass every rule, and the rules must be debited together or not at all. Take Atlas with the tenant quota of 1,000 requests/min and user U-17's bucket of capacity 20 refilling 2/s. If I check the tenant first and debit it, then find that U-17's bucket is empty, the tenant has been charged for a request that was denied; with many denied users that leaks tenant budget. So the script first evaluates every rule (refill each bucket, test each against its cost), and only if all pass does it debit all of them. If any fails, nothing is written except possibly the refill timestamps, and the response names the rule that blocked, with Retry-After set to the longest wait among the failing rules because the client must wait for all of them. To make that possible all of Atlas's keys carry the same hash tag, rl:v3:{t:atlas}:u:U-17:read and rl:v3:{t:atlas}:tenant, so they land in one slot on one primary and one script call and one round trip cover five rules rather than five calls. The weakness is concentration: a hot tenant becomes a hot slot. That is the reason for the leasing discussion later. The alternative, sequential per-rule checks with a refund when a later rule fails, is simpler to scale and weaker to reason about: the refund is a second operation that can itself fail, and between debit and refund other requests see a budget that is too low.

• What if a rule is in a different tenant's slot, like a global limit? — Do not colocate everything under one tag. Treat the global rule differently: give gateways leased chunks of the global budget, so the cross-slot check becomes a local one plus an occasional lease call. The tenant and user rules stay in one script.
• Which rule do you report when two deny? — The one with the longer retry time, optionally listing both internally. Telling the client the shorter wait would cause an immediate second denial.
• Does evaluation order matter? — For atomic same-slot scripts not for correctness, only for cost: evaluate cheap or likely-to-deny rules first so a denial exits early. For security, order matters earlier in the pipeline: the pre-authentication IP check runs before identity-based rules.

Only when every key lives in the same hash slot. Redis Cluster splits the keyspace into 16,384 slots spread across primaries, and a script or multi-key command is allowed only if all its keys are in one slot; otherwise the server returns a CROSSSLOT error. Hash tags are the sanctioned workaround: only the text between the first braces is hashed, so {t:atlas} forces all of Atlas's keys into one slot. Inside that slot the check is atomic with respect to its primary. Across slots there is no transaction, which means a design that debits a tenant key on shard 1 and a global key on shard 2 is two operations with a failure window between them. A crash after the first debit leaves tokens spent for a request that was never admitted. There are four honest responses. Colocate what must be atomic and accept the hot-slot trade. Turn the cross-shard rule into a local one with leased chunks. Sequence the calls, most restrictive first, and compensate with a refund, accepting that failed refunds leak a bounded amount that a token bucket recovers from through refill. Or split the check into a cheap pre-filter and an authoritative atomic one. What I would never say is 'Redis cluster transactions make it atomic'. Even the colocated case is atomic on one primary only, and failover can still lose acknowledged writes.

• Does a hot tag make things worse? — Yes. A tag spanning one tenant puts all that tenant's traffic on one slot, so Atlas's 75,000 req/s flood would land on one primary. Tags bound the blast radius to the tenant but do not remove the hot spot.
• Can you shard a single tenant across slots? — You can split a very large tenant's budget into sub-buckets by hash of the user, each with a share of the tenant quota. That reintroduces fixed partitioning and unfairness unless shares are rebalanced, so only do it when a tenant would otherwise not fit on one shard.
• What does the refund path look like? — Give the debit a request ID, store it with a short TTL, and make the refund idempotent by that ID. A lost refund costs the tenant some tokens until refill; a duplicated one cannot refund twice.

Rate counts arrivals over time; concurrency counts how many are executing right now. They fail differently, and Northstar's export endpoint shows it. A tenant sends only 0.15 exports per second, comfortably under any rate rule, but each export runs for 20 seconds, so by Little's law (average number in the system = arrival rate × time each spends in it) about 0.15 × 20 = 3 are running at once; a few more per second and the backend is holding dozens of heavy jobs. A request-rate limiter never noticed. So the policy has a separate mechanism: at most 3 in-flight exports per tenant. The implementation is a semaphore built from leases, not a counter: on admission, a script removes expired entries from a sorted set keyed by tenant (score = lease expiry), checks the cardinality is below 3, and adds this request's ID with an expiry. On completion the gateway removes the ID. Every acquired slot needs a TTL because a crashed worker never calls release, and without expiry the slot would be held forever and the tenant eventually locked out. The TTL creates a tension to state out loud: too short and a long export loses its slot and a fourth runs, too long and a crash blocks capacity for the TTL. Heartbeat renewals address it at the cost of more traffic. The denial also reads differently: 429 with a reason of concurrency, and a Retry-After that is only a guess, because the slot frees when a job ends, not on a clock.

• When would you queue instead of rejecting? — When the work can tolerate waiting and the caller expects asynchrony, such as export jobs. A queue turns a denial into delay and needs its own bound and an overload policy. Do not queue synchronous request-response traffic, which only holds connections open.
• Do concurrency leases need to be exact? — Slightly over-admitting for a moment is usually acceptable. Under failover a lost acquire or release makes the count wrong, which TTL expiry repairs. For strict resource guards such as licences, you need a stronger, durable authority.
• How is this different from a distributed lock? — A lock has one holder; a semaphore here has up to N holders. The failure issues are the same family: expiry, fencing, and a holder that believes it still owns a slot after expiry.

Two different retries are tangled here, and they get different treatment. The first is the client retrying a request it believes failed. To the limiter that is a new attempt, and charging it is correct: the limiter counts attempts to use capacity. The second is the gateway timing out on the limiter call, where the script may well have executed and debited a token before the reply was lost. If the gateway blindly repeats the call, the same request is debited twice. For cheap token-bucket decisions I accept that: it errs toward denying a little too much, the bucket refills, and the cost of correctness would exceed the cost of the error. For expensive or paid operations such as POST /checkout or an export, the decision should be idempotent. The caller supplies a stable request ID, the script records decision:{tenant}:{request-id} with a bounded TTL (say a minute) in the same slot, and a repeat of that ID returns the stored decision without touching the budget. That costs memory proportional to rate × TTL for the protected routes only, which is why I would not do it for every read. Two design limits: the ID must be scoped to the tenant so one customer cannot replay another's IDs, and the retention is finite, so a retry after the window is a fresh request. A gateway-side rule completes it: do not retry the limiter call on timeout; apply the route's fail mode instead, which stops a slow store from turning into multiplied traffic.

• Can a replay be used to dodge the limit? — If the stored result is the first decision, replaying a denied ID simply returns denied, and replaying an allowed one returns allowed without more cost. The risk is an attacker minting fresh IDs, which is already covered by normal limits, so IDs buy no extra capacity.
• Why not use an exactly-once guarantee from Redis? — Redis does not offer exactly-once delivery across a lost reply; idempotency by key is the mechanism, and it is bounded by retention and by failover durability.
• What about downstream retries after admission? — Those are separate. An admitted request that fails and is retried by the client costs a token each time, which is intended: retries are load.

Start from the number: 500,000 admission calls a second at a 10× surge on a 50,000 baseline. If one primary can run about 40,000 of these scripts per second (an assumption I would replace with a load test), then 500,000 ÷ 40,000 = 12.5, so at least 13 shards. I would plan 20, which puts the average at 25,000 per shard, 62.5% of that budget, leaving room for uneven hashing and for the catch-up work after a failover or a slot move. The multiplication I care about most is the one I avoid: if five hierarchical checks (global, tenant, user, route, concurrency) hit five different stores the fleet does 5 × 500,000 = 2.5M interactions a second, but when the rules for a tenant share a hash tag and run as one script, it is 500,000 script calls. That is the reason for colocation. Memory is the easier axis: 2M active keys at an assumed 200 bytes is 400 MB, double it for allocator and replication overhead, so about 800 MB per copy and 1.6 GB with a replica, comfortably small. After the shards, reduce the calls themselves. Gateways cache denials for the retryAfter hint so refusals cost nothing at the store. Leased token chunks take admit-heavy keys off the hot path. Idle keys expire by TTL. A cheap local pre-filter drops obvious floods before they reach the limiter. The uniform hashing assumption is the one I would stress next, because real tenants are not uniform.

• What breaks the 20-shard plan first? — Skew. One tenant's keys share a slot, so a tenant with a large share of traffic overloads its primary while the other nineteen idle. Capacity planning has to be per-hot-key as well as per-fleet.
• How do you add shards without breaking enforcement? — In Redis Cluster, resharding moves slots between primaries and migrates each existing key with its contents and TTL, so a bucket that already exists keeps its state across the move. The exposure is a bucket that does not exist yet at the moment its slot moves, or one that is lost on a failure mid-move: it is re-created full, a brief over-admission bounded by its capacity. I would schedule moves outside peak and rehearse them under load, because the migration itself adds latency to the keys involved.
• Why not a database with conditional updates? — A relational row with UPDATE ... WHERE tokens >= cost is atomic and durable, which is attractive for low-volume, high-value quotas. At 25,000 decisions per second per shard the write amplification and commit latency make an in-memory store the better fit.

First separate two loads, because the limiter's work is attempts, not admissions. Take Atlas flooding at 75,000 attempts per second on one key set, which is 15% of a 500,000 peak. That lands on a single shard with a 40,000 budget, so the shard is overloaded even though Atlas may be admitted for only a trickle. This case is deny-heavy, and the cure is not at the store: after a denial the gateway keeps a short local negative cache for the hinted retry time (with a floor of about 250 ms), so repeated attempts are answered locally and never reach Redis. The second case is admit-heavy: the fleet-wide protection of GET /catalog allows 40,000 requests per second across 100 gateways, so every admit touches the same key. There I lease chunks. A gateway asks the store for 100 tokens at a time and spends them locally, so store traffic falls from 40,000 to about 400 operations a second. The price is that up to 100 gateways × 100 tokens = 10,000 tokens can sit unspent in gateways, equal to 0.25 s of the global rate, and that number is the staleness and overshoot bound of the technique. I would then watch for it: per-shard operations per second against the budget, the top keys by call count (sampled in the gateways so as not to add load to Redis), and the negative-cache hit ratio. A third tool is to shed at the edge when a tenant is plainly abusive, but that is a different layer. When leasing and caching are still not enough for a single tenant, you split its budget into sub-buckets and accept some unfairness.

• Is the negative cache safe? — It can only over-deny, never over-admit, and only for the hinted interval. The cost is that a legitimate request arriving just after the true refill, inside the cached window, is refused slightly early; that is why the interval is short and bounded.
• Why not shard hot keys randomly? — Splitting one bucket into k sub-buckets divides capacity, so a client that lands on one sub-bucket may be denied while the others hold tokens. You need rebalancing or sampling to keep it fair; leasing handles it more gracefully.
• How do you detect a hot key at runtime? — Per-shard command rate skew, gateway-side sampled counters per key prefix, and the deny ratio per tenant. Redis can also report hot keys with some configurations, but I would not depend on that during an incident.

Walk the timeline. Gateways A and B send decisions to primary R, which acknowledges them and streams the changes to replica R2 asynchronously. At some instant R dies. Whatever R acknowledged but had not yet shipped is gone; R2 is promoted from the state it had. The Redis cluster specification is explicit that asynchronous replication means acknowledged writes can be lost in a failover, and WAIT can narrow the window by waiting for replica acknowledgements but does not turn the system into a strongly consistent one. For a limiter the loss has a specific direction: counters roll back to an older value, so some tokens that were spent are available again, and keys created in the lost window start from scratch (a new bucket is full). The over-admission is bounded by the work inside the replication lag. With a hypothetical lag of 100 ms, a shard running at 25,000 decisions per second could lose roughly 2,500 recent writes, but they are spread over many keys: a per-user bucket of capacity 20 can regain at most 20 tokens, and Atlas's tenant bucket at most the tokens spent in those 100 ms, a handful at a 1,000 per minute quota. That is acceptable for rate limiting, whose purpose is protecting capacity, and unacceptable for anything that behaves like a ledger, so billing quotas need a database or a stronger mechanism. Practical consequences: clients must recover from a lost script cache (NOSCRIPT), the failover period itself is governed by the route's fail mode, and after promotion I watch deny rates for a bump, since the limiter forgets recent debts and then re-learns. A restore from an old persistence file (an RDB snapshot or the AOF append-only log) causes the same rollback, only larger.

• Would you use WAIT on every decision? — It adds a replica round trip to the hot path and still does not make the failover safe in every case. I would reserve it for rare, high-value operations such as a plan-quota consumption, not for per-request decisions.
• How do you tell users nothing happened? — I would not, except through operations: a failover event is an annotation on the dashboards, and the deny-rate bump is expected. The user-visible effect is a handful of extra admits, not an error.
• Would you pick synchronous replication instead? — Redis's model is asynchronous by default; a store with synchronous consensus gives stronger durability at the price of latency on every decision. For soft limits the asynchronous model wins; for hard financial quotas I would choose the stronger store and pay for it.

By asking which is worse for this route: the abuse that gets through while the limiter is blind, or the outage the customer sees if I refuse. There is no global answer. POST /login fails closed, because without throttling an outage window is an open invitation to credential guessing, and a few minutes of refused logins costs less than a successful account takeover. POST /reports/export also fails closed, since one flooding tenant can exhaust the backend in seconds. POST /checkout is the hardest call: refusing it loses revenue, but an unmetered fallback exposes the payment backend, so it fails closed too, and the mitigation is to make the outage short and visible, with idempotency keys so clients can retry safely afterwards. POST /search and GET /catalog are cheap and cacheable, so they use a bounded local fallback: a conservative per-gateway cap that keeps the front page up while the over-admission stays a number I can state. I record this as a field in the policy, failMode: closed | bounded-local | open, reviewed by the owner of each route, not hard-coded in the gateway. Fail open does not preserve the limit; it suspends enforcement. Fail closed does not preserve availability; it converts a limiter outage into a customer-visible one. Saying that plainly is what makes the choice defensible. A circuit breaker around the store call makes the switch fast and automatic, with alerts whenever any route is in a non-normal mode.

• Who decides the mode? — The service owner, with security input for authentication routes. The default for new routes should be the conservative one: closed or bounded, so a forgotten setting never becomes an open door.
• Is there a middle path for strict routes? — Yes: bounded local fallback. Each gateway keeps a small local allowance, for instance a fraction of the limit divided by gateway count, and the total admitted during an outage is bounded by that allowance × gateways × duration.
• How long can fail-open last? — Only as long as the alert is unacknowledged. It should page, and the maximum exposure should be an explicit number the owner signed off on, not an open-ended default.

The first move is to stop it from taking the gateways down with it. At 500,000 decisions per second, a slow Redis that holds each request for a 500 ms timeout would exhaust connection pools and threads within moments, turning a limiter fault into a total outage. So the call has a short timeout budget in milliseconds, a bounded connection pool, and a circuit breaker that trips after a threshold of failures; when open, the gateway does not call the store at all and applies the route's fail mode directly. Then comes the question of what to apply. Strict routes return 503 (the dependency is unavailable, which is not the same statement as 'you exceeded your quota'), or a bounded local fallback may answer 429 under an explicit local rule. Cheap routes continue with local counters. Two correctness points deserve attention. A timeout is ambiguous: the store may have executed the debit, so do not retry the call; see the earlier question on double charging. And recovery is not instant: when the store returns, many keys may be missing or reset, and half-open breaker probes should ramp traffic up gradually so that the first moments do not become a second overload. During the incident the useful signals are breaker state, time spent in each fail mode, and the volume admitted by fallback, which is also the overshoot estimate.

• Why 503 and not 429? — 429 tells a caller that it exceeded its limit and should slow down. If the limiter is broken the caller did nothing wrong, and 503 states that the service cannot decide right now. Treating them as the same would mislead clients and dashboards.
• What should the local fallback count? — Per-gateway token buckets with small capacity, keyed by the same identity. Totals are approximate because traffic is uneven across gateways, so the fallback is a cap on damage, not a replica of the policy.
• Is it ever right to retry the store call? — Once, on a connection-level failure before the request was sent, if the budget allows. After an ambiguous timeout, no.

Treat each shard as a primary and at least one replica in a different availability zone, with automatic promotion, and spread the primaries across zones. If the 20 shards are placed so that each zone holds about a third of the primaries, losing a zone means roughly a third of the shards fail over together and the rest keep deciding; with all primaries in one zone, the same event stops every decision at once. Gateways run in all zones and talk to the primary wherever it is, so some decisions pay a cross-zone round trip, typically a fraction of a millisecond to a couple of milliseconds in many clouds (hypothetical; measure it), which is worth paying to keep the authority single. Replication stays asynchronous, so the failover caveats from the earlier question apply per shard: promotion takes time, recent writes can be lost, and during the gap the route's fail mode governs. Capacity needs headroom for the failure case too: a failover moves the work to the promoted replica, redundancy is gone until a new replica is built, and that resynchronisation uses CPU and network on the new primary. Running shards at 62.5% of the budget leaves room for it, and I would rehearse it rather than assume it. The remaining design item is the client side: topology refresh after promotion, bounded connection pools to avoid a reconnect storm, and jittered reconnect backoff.

• Why not a multi-primary store? — Multi-primary systems resolve conflicts after the fact, which for a counter means lost increments or overshoot. For one region I prefer a single authority per key with a fast failover.
• Do you place the replica in the same AZ for latency? — No. Replication lag is already the durability risk, and a same-zone replica gives no protection against zone loss.
• How do you test it? — Fail a zone in a staging environment under replayed load, and measure the time gateways spend in fallback, the deny-rate bump after promotion and any error spikes from stale topology.

Often they cannot, and the claim is only true under an assumption nobody states. Suppose EU and US each run the full policy of 1,000 per minute for Atlas using their own regional Redis. Each region is internally correct and atomic, and Atlas, sending traffic to both, can have 1,000 admitted in each: up to 2,000 per minute, which is 2× the contracted limit. Nothing malfunctioned; the limit simply was never a single number anywhere. There are three real designs. Central authority: one region holds the quota and the other asks it for each decision; the limit is exact within that authority's atomicity, but every request in the remote region pays a WAN round trip (I would illustrate 80–120 ms, hypothetically) and the remote region loses admission when the link is down, which is the price of strictness. Regional leases: an allocator holds the pool and each region obtains budget chunks it can spend locally; decisions stay fast and the overshoot is bounded and computable. Independent regions with reconciliation after the fact: simple and fast, but the overshoot is unbounded in principle and only suitable for soft limits. A fourth hybrid, a strict home region for the tenant's writes and a lease for the other region, is possible but more to operate. My default for a plan quota would be leases with the bound stated in the contract, and a strict home region only if the customer requires zero overshoot and accepts the latency and partition cost.

• Why not synchronize the regional counters constantly? — Constant sync is a distributed counter with a WAN delay; each region still decides on stale information, so the overshoot is proportional to delay × rate. It is a continuous version of leasing without the explicit bound.
• Which regions need to be in the design? — Only those where a tenant has traffic. A tenant seen in one region needs no cross-region mechanism, so I would pin quota authority to the region where the tenant is active and add leasing only on demand.
• How do you explain this to a product manager? — Offer three plain choices: exact but slower and unavailable when partitioned; fast with a bounded, published overshoot such as 'up to 20% above plan'; or fast and approximate with reconciliation.

Picture Atlas's minute window starting at 12:00:00 with the allocator's pool at 1,000. EU gets busy and asks for a chunk; the allocator grants 100 tokens, now pool = 900, and stamps the lease with a 15-second TTL clamped so it never outlives the window (a lease granted at 12:00:50 expires at 12:01:00, not 12:01:05). EU spends those 100 tokens through its own atomic regional bucket with no WAN call per request. When EU is down to a low-water mark, it asks for another chunk before it runs dry, so users do not stall. The allocator grants only what remains at the instant of the grant, never more; if the pool is at 60 the grant is 60. Unspent tokens at expiry go back or are forgotten, which is a design choice: returning them avoids waste but needs a reliable return path, while forgetting them is simple and means some capacity is stranded. US follows the same loop. Each grant has an ID so that a retried request returns the original grant instead of a fresh one, which prevents duplicate grants after a timeout. Two failure modes need handling. Depletion unfairness: with a static 50/50 split, if EU's demand is 900 and US's is 100, EU is denied 400 while US leaves 400 unused. Demand-weighted chunk renewal solves that, because the busy region keeps asking and the quiet one stops. And a partition: a region cut off from the allocator can only spend what it already holds until the TTL ends, and gets nothing new.

• Why 15 seconds and 100 tokens? — They are illustrative. A shorter TTL reduces stranded tokens and overshoot but increases allocator traffic and raises sensitivity to allocator hiccups; larger chunks reduce traffic but increase the maximum stranded amount. The right pair comes from the contract and measurement.
• Where does the allocator live and what if it fails? — Typically in a home region on a replicated store. If it fails, regions run on their remaining leases and then apply the route's fail mode. Because replication is asynchronous, a failover can lose recent grant records, and I count that in the overshoot bound.
• What happens at the window boundary? — Leases are clamped to the window end so unspent grants do not carry into the next window; otherwise a region could spend an old grant plus the new window's budget, which is the carry-over term in the bound.

Write down everything that can let a request in beyond G and add it up. For a window with global limit G, the admitted count is at most G + (lease carry-over across the window boundary, summed over regions) + (local fallback allowances, summed over regions) + (grant records lost when the allocator fails over asynchronously). Now plug in Atlas: G = 1,000 per minute and two regions. If leases are not clamped to the window, each region could carry up to 100 tokens across a boundary (assuming at most one outstanding chunk per region at that moment; with two outstanding chunks the term doubles), so the carry-over term is up to 2 × 100 = 200, which is +20%. If each region may fall back to a bounded local allowance of 100 tokens when it cannot reach the allocator, that is another 2 × 100 = 200, another +20%. With a design that clamps leases to the window, never grants more than the remaining pool, and has no local fallback on that policy, the first two terms are zero and overshoot depends only on lost grant records. Take the partition case: US holds 200 unspent tokens when it loses the allocator. It can admit at most 200 more until the lease expires, nothing new arrives, and when the lease is clamped there is no overshoot at all; the cost is that up to 200 tokens (20% of G) are stranded or denied. That trade, no overshoot against some stranded capacity, is the most useful sentence to offer an interviewer. If pushed, I say what the bound does not cover: it assumes bounded clock error in clamping the lease and a correct allocator, so I would add monitoring that compares the sum of regional admits per window against G.

• What if the interviewer wants zero overshoot and zero stranded tokens? — That means a single synchronous authority, which gives up either latency or partition availability. The trade-off between stranding and overshoot is inherent to partitioned budgets.
• How do you reduce stranded tokens? — Shorter TTLs, smaller chunks, return of unspent tokens on a healthy path, and demand-weighted renewal. Each costs allocator traffic.
• How do you verify the bound in production? — Sum admitted counts per tenant across regions per window from decision telemetry and compare with G. Because telemetry is not a ledger, treat the result as an alerting signal, not proof.

First ask what 'exact' protects. If the figure is a billing commitment, the answer is usually metering with a ledger and reconciliation, not a request-time gate, because the limiter is the wrong tool for exact accounting. If it protects a shared downstream that can take only 1,000 per minute, the customer needs a hard guarantee and I would present the price list honestly. Option one: a single home authority for Atlas, say in EU. Every US request pays the WAN round trip, which I would illustrate at 80–120 ms (hypothetical), and US admission stops during a partition. That is exact relative to that authority's atomicity, and still subject to asynchronous failover of its primary. Option two: leases with strict rules, clamped to the window, grants never beyond the remaining pool and no local fallback. Overshoot is zero within the stated assumptions and the cost is stranded tokens, perhaps up to 200 (20%) during a partition, plus allocator calls. Option three: leases with a published bound, for example up to +20%, cheaper and more available. I would recommend option two for a hard downstream limit, option three for a plan quota, and I would define the window precisely (fixed or rolling, which clock, which timezone) because 'per minute' is ambiguous. The sentence I would avoid is 'globally consistent with no overshoot', which says nothing about authority, partitions or failover.

• What if they refuse any stranded capacity? — Then they are asking for a single synchronous authority with fast, reliable links, and they should accept the latency cost for the remote region or lose availability during partitions. There is no design that removes both.
• Is a consensus store a way out? — A consensus-based store gives linearizable counters across a quorum, but each decision then costs cross-region quorum latency; it is the central-authority option with better durability, not a free upgrade.
• Should the limiter be the billing system? — No. Billing needs durable, auditable, idempotent accounting. Use the limiter for protection and a ledger for money.

Different layers, different keys, chosen by what can be trusted at that point in the request. Before authentication the only stable handle is network-level, so a coarse per-IP rule (Northstar's 20 requests per 10 s) guards the front door. After authentication the identity is a verified principal: the API key K1 or user U-17, inside a tenant, so Atlas's per-user bucket is separate from Birch's. Above that sits the tenant key, the plan-level 1,000 per minute that spans every identity, and beside it the route group, so an expensive export does not share a bucket with catalog reads. A final fleet-wide key protects shared backends. A concrete name such as rl:v3:{t:atlas}:u:U-17:read shows the parts: namespace, a version that marks the meaning of the stored state, the tenant in a hash tag so a tenant's rules colocate, the principal type and ID (hashed if it is personal data), and the route group. Three rules keep the keyspace honest. Derive keys from verified claims or headers set by a proxy you control, never from a client-supplied value. Give every key a TTL equal to the time to full refill plus slack, set in the same script as the write, so abandoned keys expire. And bound cardinality: an attacker inventing identities should never create unlimited keys, which is why pre-authentication counters use IP keys and short TTLs, and identity keys are created only after verification.

• Why include a version in the key? — When a change alters what the stored value means, such as moving from request counts to millitokens, the new code must not read old data. A new version segment starts fresh state; the price is a momentary reset, which I schedule and announce.
• Should the IP be part of the authenticated key? — Usually not; a user's quota should follow the user across networks. IP can be an additional, looser rule for anomaly signals.
• What about hashing for privacy? — Hash personal identifiers in keys and logs with a keyed hash so raw keys and IPs never appear in Redis dumps or dashboards. The trade-off is that debugging requires a lookup path.

Move the limit off the IP wherever you can, and where you cannot, make the IP rule generous and treat it as a backstop. A university network or a mobile carrier's NAT can put hundreds of people behind one address. Under Northstar's anonymous policy of 20 per 10 s per IP, one person hammering refresh can lock out everyone else behind that address, which is both unfair and an easy denial-of-service against a target's coworkers. The primary fix is identity: authenticate early, and count the authenticated principal, so each user has their own bucket regardless of address. For endpoints that must stay anonymous (login, signup, catalog browsing) the IP limit is set high enough that a plausible shared network is not routinely hit, and I add a second, more specific key when one is available: a signed device or session cookie issued earlier, or the targeted account name for login. IPv6 needs thought because one user may control a whole /64, so aggregate at a prefix, not per address. Spoofing is the opposite failure: if you trust X-Forwarded-For as sent by the client, an attacker rotates the header and evades the rule, so take the client address only from a header appended by a proxy you operate, at a known position in the chain. The honest limit of IP-based fairness is that it is a heuristic. A response to a suspicious IP can be a challenge or a slower service instead of a hard 429, which treats a shared network more gently.

• What if marketing wants a higher limit for a known office? — An allowlisted range with a higher cap is reasonable, stored as versioned policy and reviewed, so it does not decay into a permanent hole.
• Do you penalize failed attempts differently? — For login yes: count failures against the account and the IP separately, with a lower threshold than for successful traffic.
• How do you measure unfairness? — Track the deny rate per key class and look for a single IP with many distinct sessions or users being denied together. A high deny rate across many authenticated users from one IP is the signature of NAT trouble.

Accept that you cannot count by user yet, so layer three cheap controls and be careful about two traps. The first control is a per-IP limit at the edge, a fixed window such as 20 per 10 s being enough, checked with local counters or a cheap shared store before any expensive work, so that password hashing and database lookups are not reachable at attacker speed. The second is a per-target-account limit, keyed on a hash of the submitted username, which stops a distributed attacker from hammering one account from many addresses; once a threshold is crossed I add delay or a challenge rather than a hard lockout. The third is a global ceiling on failed logins, so a credential-stuffing wave that spreads below every per-IP and per-account threshold still trips an alarm. Trap one is the lockout weapon: if three bad attempts lock an account for an hour, an attacker can lock out any victim on purpose, so use progressive delay, step-up verification or per-IP weighting. Trap two is leakage: the responses and timing must be the same whether or not the account exists, and 429 must not reveal which accounts are being watched or give predictable reset times. State creation needs a guard too: counters for bogus usernames are an attacker-controlled keyspace, so I use short TTLs and a cap on keys per IP prefix. For the failure case this endpoint fails closed with a 503, because an unthrottled login is exactly what a credential-guessing attacker wants during an outage. I also state the boundary: a botnet with ten thousand addresses, each trying a few passwords, passes through all these rules, and that needs bot detection and multi-factor authentication, which are separate products.

• Should the limiter run before or after authentication? — Both, in layers. The cheap pre-auth rule goes first so brute force cannot bypass it, and the principal rules run after authentication, so unauthenticated traffic cannot create or read authenticated quota state.
• Would you return 401 or 429 first? — If the pre-auth limit is exceeded, 429 without evaluating credentials. Otherwise normal authentication results apply, and failed attempts feed the counters.
• What about attackers who vary the username every request? — Per-account keys then protect nothing, and the per-IP and global failed-login ceilings carry the load, with the key count bounded by TTL and by an IP-prefix cap.

It does not solve volumetric attacks, because those fill the network link or exhaust the proxy before the request ever reaches limiter logic, and it does not catch distributed attacks that stay below each individual threshold. Do the arithmetic for Northstar. Anonymous clients may send 20 requests per 10 s, which is 2 per second. A botnet of 100,000 addresses each sending 1 request per second is under every per-IP limit and still produces 100,000 requests per second, 50 times the 2,000 req/s that the backend comfortably serves for cheap reads. No per-key rule fires because no key misbehaves; the aggregate is the attack. Worse, the limiter becomes part of the load: each request still costs TLS, parsing, an identity lookup and a store call, and at hundreds of thousands per second the limiter store is itself a victim, which is why I keep the first filters local and cheap. Defense is layered: network-level scrubbing and anycast absorption at the edge (the same address announced from many sites, so attack traffic is spread across them), WAF and bot-detection signals, global load shedding and a circuit breaker to keep the origin alive, and then the per-identity limits for fairness among legitimate tenants. The limiter's honest role is to enforce a contract between you and your customers and to blunt one noisy client. Calling it DDoS protection both overstates it and risks that a real outage will be blamed on the wrong layer.

• Can per-IP limits at the edge help? — They cut off the simple floods and noisy scanners with local counters, at no store cost, but they do nothing against a distributed attack and risk NAT collateral. Use them as a layer, not as the defense.
• What adds protection beyond limits? — Load shedding by priority when the backend saturates, circuit breakers on dependencies, and capacity headroom; those protect the aggregate rather than any key.
• Does your design resist a flood of unique keys? — Cardinality caps and TTLs, with identity keys created only after authentication, keep the keyspace from being attacker-controlled.

Keep two things apart: stale policy (gateways hold an old rule) and stale counters (the store holds an old state). The control plane stores policies as versioned, immutable snapshots: validated at publication (no refill of zero, no cost above capacity, no duplicate precedence), audited, and rolled out in stages by tenant or percentage. Gateways pull or are pushed the snapshot, and apply it atomically so no request sees half a ruleset. Each decision records the policy version it used, so a disputed denial can be traced. For ordinary tuning of numbers, gateways pass the current limits to the script as arguments, so an existing bucket picks up a new capacity or refill at its next call. When the meaning of the stored state changes, the key version changes and the state starts fresh, which is a reset I would plan. Emergency tightening is the hard case. A push channel delivers it in seconds, but a gateway that cannot reach the control plane keeps its last-known snapshot, so there is no instantaneous global revocation under disconnection, and I say that explicitly. The mitigations are a bounded staleness rule (alert and optionally go conservative when the snapshot age exceeds a threshold) and monotonic versions, so an old snapshot arriving late cannot replace a newer one. Rollback is a new, higher version carrying the previous content, never a lower one, so every node converges in one direction.

• What if the control plane is down? — Data-plane decisions continue with the last snapshot. That is the right default, because the control plane's job is change, not per-request service; alerts fire on snapshot age.
• How do you test a policy before enforcement? — Shadow mode: evaluate the new policy, record would-deny decisions with their version, and compare against the current one before switching it on.
• Who may change a policy? — Role-based access with per-tenant scoping, four-eyes approval for global rules, and an audit trail. A broken limit can take down a tenant or open the system to abuse, so it deserves the same care as a code deploy.

I would begin with the signals that say which guarantee is currently in force, since a dashboard full of request rates cannot answer that. First, fail-mode activations: per route, how long the gateways have been in bounded-local or fail-open mode, because those periods are when limits are weaker than advertised. Second, store health: p99 decision latency against the single-digit-millisecond goal, timeouts, connection pool wait, shard command rate against the 40,000 budget, memory and above all the eviction count, because an evicted counter silently resets enforcement. Third, replication lag and failover events, which explain a sudden bump in admits. Fourth, hot-key and cardinality indicators: per-shard skew, top tenant share of calls, growth in key count. Fifth, policy state: the snapshot age per gateway and the version in force per region. Sixth, regional leases: grants per minute, exhaustion events and stranded tokens, plus the sum of admits per window compared with G as an overshoot estimate. Seventh, client behavior: what fraction of retries arrive before the Retry-After hint, which warns of storms. Paging alerts go to the things that remove protection or availability: non-zero evictions, fail-open on a strict route, snapshot age beyond bound, a shard above budget. Deny-rate swings per tenant are tickets, and usually a customer conversation, not an incident. Keep metric labels at tenant and route level, not per user, for cost and privacy; sample per-decision logs with hashed identifiers. And be clear that these metrics are not an authoritative ledger: telemetry can be lost or duplicated, so billing needs its own accounting.

• How do you debug 'why was I denied'? — Return a decision ID in the response and store a sampled decision record with policy version, rule, tokens before and after, and the shard. Support can look up the ID without exposing raw identifiers.
• What is the single best leading indicator? — Shard command rate against its budget plus the deny ratio by tenant; the first predicts overload, the second shows who is driving it.
• How would you notice overshoot? — Compare admitted counts from the gateway logs or downstream with the policy per window. Because it relies on telemetry, I would use it to alert, not to prove compliance.

Because a 429 is a message, not a defense. Picture 10,000 clients that all receive Retry-After: 1. If they honor it exactly, 10,000 requests return in the same second, a synchronized wave that we caused, and the limiter and backend feel it as a spike. If they ignore it, the requests continue immediately. Either way the denied request already consumed a connection, TLS work, parsing, an identity lookup and usually a store call, so the cost was not avoided, only reduced. The server therefore needs its own measures: gateways cache denials for the hinted period so repeats are cheap, the edge drops floods before the limiter, load shedding protects the backend when aggregate traffic exceeds capacity even though no single key breaks its limit, and concurrency caps guard the expensive routes. The client side needs a contract: documented behavior, SDKs that implement jittered exponential backoff, and a retry budget so a client cannot amplify failures. With jitter spreading the 10,000 retries over one to two seconds, the load is about 10,000 per second on average instead of a single spike. One more point: not every 429 a client sees comes from this limiter. A downstream service, a CDN or a partner API can emit its own, and an admitted request can still fail with 429 or 503 behind the gateway, so the response body should say which policy denied, and clients should not interpret admission as a guarantee of success.

• How do you implement jitter on the server side? — Randomise the hint within a small range, for example the computed wait plus a random fraction of it. Clients that add their own jitter on top gain further spreading.
• What if clients abuse Retry-After by retrying early? — Early retries count as attempts and are denied; repeated early retries are visible as a client class and can be penalised, for example by escalating the hint.
• Does 429 replace 503 under overload? — No. 429 is addressed to one caller who exceeded a policy. 503 reports that the service cannot handle the request at present, which is the correct status when shedding aggregate load.

Use 429 Too Many Requests, defined in RFC 6585, when a valid caller exceeds a policy, with a Retry-After header; RFC 9110 defines Retry-After as either a number of seconds or an HTTP date, and a hint about when a retry might succeed, not a reservation. A 503 means the limiter or the service is unavailable, which is a different statement and should not be mixed with 429. Authentication failures keep their 401 or 403, but the cheap pre-auth IP check runs before expensive credential work, and principal quotas are applied after authentication. For quota visibility there are two conventions. The legacy X-RateLimit-Limit/Remaining/Reset headers are a de-facto convention without a single specification, so semantics vary between providers. The RateLimit and RateLimit-Policy fields are described by an IETF HTTPAPI working-group document that is still an Internet-Draft, not an RFC; as checked on 6 November 2026 the working group's repository still carries it as a draft in progress, so I would offer the fields as optional and say they may change. The body should carry a stable machine-readable reason and the decision ID. On exposure: show limit and remaining only to authenticated callers on their own principal, and do not give unauthenticated callers a precise tenant quota or a predictable reset instant, which helps attackers time their bursts. State plainly that Retry-After is computed from current state and other callers can change the outcome.

• Should remaining quota be returned on every response? — For authenticated API clients it is useful and cuts blind retries, but it costs a computation and may reveal usage patterns. Allow tenants to opt in, and omit it on anonymous routes.
• What about an HTTP date versus seconds? — Seconds are simpler and avoid clock-skew issues between client and server; dates are acceptable but need accurate clocks on both ends.
• Is it fine to adopt the draft headers now? — It is a judgment call. If you use them, version your policy descriptions and keep the legacy headers while the draft changes, and document that the format may evolve.

For a product with a few gateways and perhaps a thousand requests per second, I would build exactly one thing: a single Redis instance with one short atomic script that implements a token bucket per API key, called by the gateway on each request. The script reads the store's clock, refills in integer millitokens, decides, writes and sets an expiry in one step, as in the sketch below. The gateway answers 429 with Retry-After when denied, and applies one global fail mode to the whole service (fail open for a cheap product, closed for a sensitive one), plus a small in-process cap as a safety net. A single replica gives restart safety at the price of the asynchronous failover caveat. There is no hierarchy, no hash tags, no leases, no regions, no control plane beyond a policy file in version control. This is correct for the stated scope: one authority, one atomic step, bounded state. At a thousand decisions per second one primary is nowhere near its budget, and a single round trip per request is affordable. I would name the triggers for growth in advance, because each one corresponds to a section of this guide. Several rules per request that must be debited together lead to hash-tagged keys and a multi-rule script. One tenant dominating the load leads to negative caching and leased chunks. Expensive routes lead to weighted cost and a concurrency cap. A second region leads to the lease-or-home-authority decision. A paying customer who needs an exact quota leads to a stronger store. The main risk in the simple design is that it becomes complicated in an unplanned way, so keep policy as data, keep the key schema versioned, and keep the limiter behind an interface so the implementation can change.

• Why not rate limit at the load balancer or CDN instead? — For coarse IP-level limits that is the cheapest and most scalable place. It cannot express per-tenant or weighted policy, which needs application identity, so the two combine rather than compete.
• What would you cut if it were just one gateway? — Remove Redis: an in-process token bucket is exact for one instance. Add Redis when the second gateway appears.
• What is the first thing you would measure? — Decision latency at p99 and the deny ratio per tenant, together with Redis memory and evictions. Those three expose almost every early problem.