I Argued With an Interviewer About Global Rate Limiting. Neither of Us Were Right

Global rate limiting has a conservation law. Once you see it, most of the architectural debate disappears. TL;DR Per-request broadcast is as bad as it sounds — roughly 20,000× more messages than the alternative. That objection was correct. But "broadcast" in rate limiting almost never means per-request. It means periodic aggregate sync, whose cost is decoupled from QPS — it scales with active key count and sync frequency, not traffic. The real weakness of a static per-region limiter isn't coordination cost. It's traffic skew: when an account's traffic concentrates in one region, a static split under-admits by up to factor of number of regions(R). There's a conservation law: coordination rate × worst-case overshoot = arrival rate × region count. You choose a point on that curve. You cannot beat the product. Practical design: leases, not counters. Key-owned, not broadcast. Adaptively sized, so you only pay coordination cost for hot accounts. Widening the limit window is free accuracy. "1,000 per minute" is 60× cheaper to enforce globally than "17 per second." The disagreement In a system design interview, I proposed a rate limiter with a per-region limiter per account. Each region enforces locally, decisions are made in-process, no network call in the request path. Rate limit decisions sit in front of everything, so they have to be fast — and a central global counter means a cross-region round trip on every request. That's tens of milliseconds added to every call to save a few microseconds of arithmetic. Obviously wrong. The interviewer suggested a broadcast mechanism to share counts between regions. I pushed back. It sounded over-engineered for rate limiting: a lot of network traffic and a lot of moving parts to solve a problem that mostly doesn't need solving exactly. Rate limiting is approximate by nature. Why build a distributed consensus problem into it? I've since done the arithmetic I should have done in the room. The short version: my objection was right about the thing I was objecting to, and wrong about the thing being proposed. And the interesting part is that neither of us named the actual weakness in my design. Where the objection holds up If "broadcast" means every region tells every other region about every request, the objection is not just right, it's overwhelming. Take five regions(R) and one million requests per second: messages/sec = QPS × (R − 1) = 1,000,000 × 4 = 4,000,000 messages/sec Four million cross-region messages per second, to coordinate a counter. And the bandwidth isn't even the problem — four million small packets per second is a packet-rate problem, which is much harder to engineer around than throughput. You would be running a larger distributed system to police your service than the service itself.So: if that's the proposal, no. Where the objection falls apart But that isn't what anybody builds, and it isn't what the interviewer meant. Periodic aggregate sync works differently. Each region keeps local counters. Every sync period — call it 100ms — it ships one message containing the deltas for accounts that were active in that window. The cost model changes completely: messages/sec = R × (R − 1) / T bytes/sec = A × B × R × (R − 1) / T where A is active accounts per window, B is bytes per entry, T is the sync period and R is number of regions . Note what's not in that formula: QPS.Same five regions, 100ms sync, 10,000 active accounts per window, 16 bytes per entry (a hashed account ID and a count): Per-request broadcast Periodic aggregate sync Messages/sec 4,000,000 200 Payload ~200 MB/s (at 50 B/msg) ~32 MB/s Scales with request rate active keys ÷ sync period Two hundred messages per second. Against a data plane already moving a gigabyte per second, the sync traffic is about 3% of bandwidth and a rounding error in packet rate. I was off by four orders of magnitude on the thing I objected to — not because the arithmetic is hard, but because I answered the naive version of the proposal instead of asking which version was meant. That's the actual interview lesson, and it's not a technical one. There's a deeper reason this works, which is worth naming because it turns a hack into a principle: rate limit counters are CRDTs. Each region owns its own slot in a per-region vector, and merging is just summing slots. No two regions ever write the same slot, so there are no conflicts, no consensus, and no ordering requirement. Gossip isn't a shortcut here. It's the theoretically correct tool, because the data structure was designed to be merged. The flaw neither of us named Here's what I actually got wrong, and it has nothing to do with broadcast. A static per-region split gives each region L/R — with a global limit of 1,000/sec across five regions, each region allows 200/sec. That's exactly right if traffic is evenly distributed across regions. It almost never is. Accounts are geographically sticky. A customer in Frankfurt sends nearly all their traffic to your European region. GeoDNS, anycast, and latency-based routing all work hard to make traffic regionally concentrated — that's their job. So consider an account whose traffic is 100% in one region: Region needs: 1,000/sec Region allows: 200/sec Effective limit: 200/sec → 5× too strict You promised the customer 1,000 requests per second. You are delivering 200 and rejecting the rest with a 429. Your utilization of the limit you sold is 1/R. That's not a tuning problem or an accuracy trade-off. That's a product bug, and it's systematic rather than occasional. And it gets worse the more regions you add, which is the opposite of how infrastructure is supposed to behave. This is what the interviewer was fishing for. They weren't asking me to build gossip because gossip is delightful. They were asking whether I'd noticed that a static split breaks under skew — and coordination was the hint toward the real question. I argued against the hint instead of hearing the question. The conservation law Once you accept that regions need to share something, the question becomes how much and how often. This is where the problem gets clean. Stop thinking about sharing counters. Think about leases. A coordinator hands a region permission to admit S requests. The region spends that locally, at zero network cost, and comes back when it runs low. Two quantities matter. Coordination load — how often anyone has to talk: coordinator RPCs/sec = Λ / S (Λ = total arrival rate) Worst-case overshoot — how far past the global limit you can go, when every region happens to spend its outstanding lease at once: overshoot ≤ R × S Now multiply them: (Λ / S) × (R × S) = Λ × R The S cancels. Coordination rate × worst-case overshoot = arrival rate × region count. It's a constant. Bigger leases buy you less chatter and more overshoot, in exact proportion. Smaller leases buy accuracy and cost you RPCs, in exact proportion. There is no lease size that gets you both, and no clever protocol that beats the product — only a different point on the same hyperbola. This is why the argument I was having was unwinnable in both directions. I wanted accuracy for free; the interviewer's framing sounded like it wanted coordination for free. Neither exists. The only real question is which end of the curve your use case belongs on, and that's answerable. A worked example, to show the curve is friendlier than it sounds. At one million requests per second with a lease size of 1,000: Coordinator sees 1,000 RPCs/sec — a single modest server. Worst-case overshoot is 5,000 requests — 0.5% of a one-second budget. You reduced coordination by 1,000× and gave up half a percent of precision. That is an excellent trade, and it's available to anyone who does the multiplication. A useful corollary: relative error is a ratio of two timescales For the counter-sync design rather than leases, the same idea shows up as: relative overshoot ≈ T / W sync period over limit window. Which produces a table worth memorizing: Limit Window Sync period Overshoot 1,000/sec 1 s 100 ms ~10% 10,000/min 60 s 1 s ~1.7% 1M/day 24 h 60 s ~0.07% And now the part that belongs in a product conversation rather than an engineering one. "1,000 per minute" and "17 per second" describe nearly the same rate. But the minute-long window is 60× cheaper to enforce globally at the same accuracy, because you're comparing the sync period against a window 60 times longer. Widening your limit window is free accuracy. It costs nothing, requires no new infrastructure, and is usually invisible to customers — most people reading your API docs cannot tell you whether they'd rather have 17/sec or 1,000/min. If your rate limits are specified per-second and you're struggling to enforce them globally, the cheapest available fix isn't in your architecture. It's in your API documentation. The design that falls out Four decisions, in the order they matter. 1. Leases, not counters. Counter sync tells regions what already happened. Leases tell them what they're allowed to do. Leases bound your error by construction — overshoot can't exceed what you handed out — whereas counter sync bounds it only statistically, by staleness. Same conservation law, but with a knob you can actually turn. 2. Own each key, don't broadcast it. Hash the account to a home region that owns its global budget. Other regions lease from that owner. This kills the R × (R−1) fan-out and replaces it with point-to-point traffic: broadcast: O(A × R(R−1) / T) key-owned: O(A / T) At five regions that's a 20× reduction, and unlike broadcast it doesn't get worse quadratically as you add regions. It also makes the failure story concrete: if a home region is unreachable, everyone else falls back to the static L/R split. Degraded and too strict, but bounded and predictable — which is the correct failure mode for a limiter. 3. Size leases adaptively. Rate limit traffic is a power law: roughly 1% of accounts generate most of the volume. Give a hot account a large lease and refresh it often; give a dormant account one small lease that lasts all day. Consumption rate is the only input you need, so this tunes itself. This is the direct answer to "too much network traffic" — you only pay coordination cost for the hot set, and the hot set is small. 4. Make the hierarchy explicit. Three tiers, each an order of magnitude slower and more accurate than the last: Tier Latency Holds In-process nanoseconds this host's slice of the lease Regional aggregator sub-millisecond this region's lease Cross-region coordinator tens of ms, off the hot path the global budget The request path only ever touches tier one. Everything else is background reconciliation. That was the correct instinct in my original answer, and it survives intact — it just needed the other three decisions underneath it. One implementation note worth having: use a token bucket, and store it as a timestamp rather than a count. The entire state of a token bucket is one number — the time at which the bucket would have been empty — and the current balance is derived from elapsed time on read. That makes it a single 8-byte value per key, trivially cheap to replicate, and lazily refilled with no background timer. Pick your tier by the cost of being wrong The conservation law says you must choose. This is how: Use case Cost of overshooting Design Coordination DDoS / abuse prevention ≈ zero static split, local only none API fairness / free tier mild annoyance leases, key-owned seconds Paid quota revenue leakage small leases sub-second Hard safety or contractual cap breach central counter, eat the latency synchronous Most rate limiting is in the first two rows. If you're protecting a service from being overwhelmed, admitting 1,050 requests instead of 1,000 harms nobody — the whole point is to stop the 100,000-request case. Engineering precision into that is spending real money to solve an imaginary problem, which was the legitimate instinct behind my original objection even though I applied it to the wrong target. The bottom row is the one people get wrong in the other direction. If a limit is contractual or safety-critical, approximate enforcement isn't a trade-off, it's a defect, and that's the rare case where a synchronous central counter is the right answer despite the latency. Low-QPS, high-value limits can afford a round trip. What I'd say now The answer I'd give today, in about the same time I had: Local decisions in the request path, always — a rate limiter that adds a cross-region round trip has failed at its job. But don't statically split the limit, because traffic is regionally skewed and a static split silently under-delivers by up to the number of regions you have. Instead give each region a lease against a key-owned global budget, sized by how fast that account is actually consuming. Pick the lease size from the conservation law: coordination rate times overshoot is fixed, so decide which one you care about and buy the other. And check whether the limit window can be widened, because that's free. The interviewer and I were arguing about a point on a curve. Neither of us had drawn the curve. That's the part I'd want back — not the answer, the move. When someone suggests an approach that sounds wrong, the useful question isn't "why is that wrong?" It's "what do you know about this problem that makes that sound right to you?" References Doorman — distributed client-side rate limiting with capacity leases: github.com/youtube/doorman/blob/master/doc/design.md Envoy global rate limiting architecture: envoyproxy.io — architecture overview, global rate limiting Envoy Gateway "rate limiting with cost" — the reservation/reconciliation pattern for variable-cost requests Apigee LLMTokenQuota and Azure API Management llm-token-limit — production token-based LLM rate limit policies