Every Gateway Thought There Was Room

My last post compared rate limiters as if one machine saw every request. Real APIs sit behind several gateways, and "100 requests per minute per key" has to be enforced across all of them. The usual answer is a shared counter in something like Redis that each gateway syncs with every so often, because asking the store on every request is slow. That post ended by saying I hadn't measured what the gap between syncs costs. This one does.

The short version: a shared counter synced every Δ seconds lets through the limit plus about (K−1)/K of whatever an attacker sends during one Δ, where K is the number of gateways, until it hits K times the limit. With 8 gateways syncing every second, a flood at 100 times the limit gets 2.4 times the limit, and a flood at 1,000 times gets 7.3 times. So the safe sync interval depends on how fast the attacker is, not on the limit. A gateway that assumes the others are doing what it's doing stays under 1.7 times the limit at any flood rate, but it starts rejecting honest clients when traffic is unevenly spread and syncs are slow. Leases never over-admit, but on a low-rate key they either strand most of the budget or turn into a store round trip on nearly every request.

The setup

One key, a limit of 100 per 60-second sliding window, K gateways from 2 to 32. Each request lands on one gateway. Every gateway syncs with a central store every Δ seconds (0.1, 0.3, 1, 3 or 10), at its own random offset. I made the store generous: it keeps the exact timestamp of every admitted request, and a sync is instant. The only error left is that a gateway doesn't know what the others admitted since they last pushed. Six designs:

• Central log: every request asks the store. Exact, and the baseline for everything below.
• Split: no sharing; each gateway allows 100/K on its own.
• Shared counter: admit if what the store said at the last sync, plus what this gateway admitted since, is under 100.
• Assume the others did what I did: the same, but count this gateway's admits since its last sync K times over.
• Track my share: like the previous one, but use this gateway's measured share of recent traffic instead of 1/K.
• Leases: at each sync a gateway hands back unused slots and asks for 1.5 times its recent arrivals per interval (plus one). The store counts outstanding grants as used, so it never grants past 100. A gateway admits only within its grant. A second version, leases + ask when empty, asks for nothing when it's been idle and goes to the store immediately when it runs out, at the cost of a round trip for that request. If the store says no, it waits for its next sync.

Honest traffic was a steady client at 50%, 80% or 100% of the limit, or page loads (bursts of about 10 requests within a second) at 50% or 80%, with requests spread evenly over the gateways or unevenly (gateway i gets a share proportional to 1/i, so the busiest of 8 gets 37% and the busiest of 32 gets 25%). Floods were steady random traffic at 1.5 to 1,000 times the limit, spread evenly. That's 2,815 runs: 5 seeds of 300 minutes each for honest traffic, 3 seeds of 20 to 60 minutes for floods, and a set of honest runs with a limit of 10,000 to see what changes for a busy key.

Checks before trusting it: with one gateway, the shared counter and both extrapolating designs made exactly the central log's decisions. The central log served 99.61% of a steady client at 80%, which matches the Erlang loss formula, as in the last post. With all gateways syncing at the same instants and a fixed-window counter, a heavy flood gets exactly K × 100 per window (4.000 with four gateways), which is what you'd work out by hand. And across all 2,815 runs no lease design ever had more than 100 admitted in any 60 seconds.

Floods: the allowance is one sync interval

Admitted per minute, as a multiple of the limit, with 8 gateways syncing every second:

The shared counter's numbers collapse onto one variable: x, the attack traffic arriving in one sync interval, measured in units of the limit. A 100× flood is 167 requests a second, so with Δ = 1 s, x = 1.67. With syncs of 1 s or faster, all 60 combinations of gateway count, sync interval and flood rate with x up to 2 land within 4% of 1 + (K−1)/K × x. With 2 gateways and x = 0.5 that predicts 1.25 and the simulation gave 1.24; with 8 gateways and x = 0.17, 1.146 against 1.135 to 1.146; with 32 gateways and x = 1.67, 2.61 against 2.61. The formula overestimates by up to 15% at Δ = 10 s, where an interval is a sixth of the window (2.18 against 2.46 with 8 gateways at x = 1.67). Past x ≈ 2 it bends over and approaches K, because no gateway will admit more than 100 of its own requests in a window: 32 gateways at Δ = 10 s and a 1,000× flood got 30.7×.

The reading I'd give it: when the window fills, every other gateway is working from a count that's up to one interval old, and each keeps admitting its share of the flood until it next hears from the store. That costs (K−1)/K of one interval's worth of attack traffic per window.

Two things I expected to help didn't. A sliding window doesn't save the shared counter: the sliding and fixed-window versions were within 5% of each other at every flood rate from 10× up with syncs of 1 s or faster, and within 15% at 10 s. A fixed window frees the whole budget at once at the minute boundary, so every gateway sees room at the same moment. A sliding window frees it gradually, but the over-admitted requests come in clumps, and when a clump ages out all the gateways see the same hole together and fill it again. And shorter syncs only help in proportion: Δ = 0.1 s against a 1,000× flood is x = 1.67 again, and 32 gateways admitted 2.63×.

Extrapolating local counts is a real fix for floods. "Assume the others did what I did" stayed at or under 1.24× with 2 gateways and 1.68× with 32 at every flood rate, because when traffic is spread evenly each gateway's count times K is a decent estimate of the total. Tracking each gateway's actual share was worse (up to 3.0× with 32 gateways): in a flood, admissions are near zero most of the time, so the measured shares are noisy, and a gateway that thinks its share is large lets in too much.

What it costs honest clients

Rejected requests for a steady honest client at 80% of the limit, uneven routing, syncing every second; the central log rejects 0.4%. Brackets show the worst 60 seconds over all runs, as a multiple of the limit:

Splitting the limit is the clear loser. With uneven routing the busy gateway runs out while the quiet ones sit on unused quota: 39% rejected with 32 gateways at a load where the central log rejects 0.4%. Even with perfectly even routing it rejected 15% at 32 gateways, since random routing makes each gateway's share fluctuate.

The shared counter is almost free for honest clients. It rejects no more than the central log, and slightly less as syncs get slower, because the slack it gives attackers it also gives everyone else. With Δ = 10 s the honest client's worst minute reached 1.15× the limit, and page-load bursts reached 1.9×.

Extrapolating has a cost that grows with the sync interval and with uneven routing. A gateway that gets 25% of the traffic and multiplies its own count by 32 thinks the key is eight times busier than it is. At Δ = 1 s that's 4.9% rejected with 32 gateways; at Δ = 10 s it's 16.4%. With even routing at Δ = 10 s it was 5.4%. Tracking the share fixes most of the uneven-routing cost (1.5% at 32 gateways, 4.5% at Δ = 10 s), which is the trade against its weaker flood cap.

Plain leases strand budget. With 32 gateways each asking for at least two slots per interval, up to 64 of the 100 slots are parked on gateways that may not use them, and the client loses 36%. Asking when empty fixes that completely, but for this key it's just the central log with extra steps: a store round trip on 98% of requests, because each gateway sees well under one request per interval.

A busy key changes the lease picture. With a limit of 10,000 a minute and the client at the limit with even routing, leases + ask when empty went to the store on 1 to 6% of requests and never went over the limit, though with Δ = 10 s it rejected 4 to 6% against the central log's 0.8%. Splitting is still bad there with uneven routing (37% rejected at 32 gateways and 80% load). So leases are for keys that each gateway sees many times per interval; for the long tail of quiet keys, a lease is a round trip.

What I'd take from it

• If you run a shared counter with a sync interval, budget for the limit plus (K−1)/K of what an attacker can send in one interval, up to K times the limit. Kong's Rate Limiting Advanced plugin, for example, exposes this as a sync_rate setting, and its docs say the shared counters are accurate only when syncing on every request.
• If floods matter, scale your local count by K before comparing it to the limit. It caps the damage at well under 2× for any flood rate, at the price of rejecting some honest traffic when routing is uneven and syncs are slow. Keep the sync interval short if you do.
• Don't split the limit evenly across gateways unless routing is sticky and even. It has no attack risk and the worst honest cost of anything here.
• Leases (Google's Doorman is the well-known example, though it leases rates rather than slots) give an exact guarantee and are cheap for busy keys. For quiet keys, either accept a round trip per request or accept stranded budget.

Caveats: one key, floods spread evenly over the gateways (an attacker who can pick a gateway changes the extrapolating rule's numbers), an idealized store with exact timestamps and instant syncs, no network delay, and one simple lease-sizing policy. Real gateways with slower or lossy syncs would over-admit more, not less.