← Back to blog2026-08-21

Rate limiting is three questions

Is this caller too fast? Has this account used its allowance? Is this box full? The third question cannot be built out of per-caller counters, and it is the one about survival. How we closed that gap in Rust and axum: shed instead of queue, limit the thing that actually costs money, replace fixed-window boundary doubling with GCRA, and choose each limiter's failure direction on purpose.

Most services answer one question and call it three

We audited every limiter in our Rust backend last week. On paper it looked well defended: twenty-five endpoints with per-IP caps, per-account throttles on login and password reset, daily quotas on the expensive AI features, a semaphore in front of the solver. On paper.

Then we asked a different question — what happens when the box is simply full? — and found the answer was: nothing. It gets slower. Forever. There was no request timeout, no in-flight bound, no cap on live WebSockets, no cap on live game tables, and no load shedding anywhere. Overload had no representation in the system at all.

That gap has a shape worth naming, because it is not specific to us:

Question	Keyed on	Typical mechanism	Do you have it?
Is this caller going too fast?	IP / account / session	token bucket, GCRA	almost certainly
Has this account used its allowance?	user, per day	a counter in the database	if you sell tiers
Is this box full?	nothing — it is global	admission control + shed	usually not

The first two are about fairness and billing. Only the third is about survival, and it is the one that cannot be built out of per-caller counters: a hundred honest users making their first request each pass every per-caller check ever written. If the only limits you have are keyed on somebody, you have no capacity control.

Rule 1: shed, do not queue

The instinct when a server is busy is to make callers wait. Queueing feels polite. It is usually the wrong choice, and you can decide which case you are in with one question: does the client have a deadline you cannot see?

Ours does. A poker action clock runs for 15 seconds; our web client gives up reconnecting after a 30-second budget. A player who waits eight seconds for a CALL to register has already had a worse experience than one who is told “table full, try again in a moment” — and the queued player is also still holding the capacity that made everyone else slow. Queueing under overload does not reduce the damage, it spreads it to the people who were already playing fine.

So every bound we added refuses instead of waiting. The one exception is deliberate: a short bounded wait for the CPU permit, because ordinary contention resolves in milliseconds and shedding those would be silly. Past the deadline it sheds too:

pub async fn cpu_permit_or_shed(max_wait: Duration) -> Option<OwnedSemaphorePermit> {
    match tokio::time::timeout(max_wait, cpu_admission::acquire()).await {
        Ok(permit) => Some(permit),
        Err(_) => None,   // caller answers 503 + Retry-After
    }
}

“Wait a little, then refuse” is almost always better than either extreme. Unbounded queueing turns overload into mystery latency; refusing instantly turns a two-millisecond hiccup into an error page.

Rule 2: limit the thing that actually costs money

The natural unit for a limit is the one you can see — requests, connections, users. The right unit is the one that consumes the resource, and they are often different.

On our service the expensive object is a table: one long-lived task per game holding the state machine, timers, bot decisions and fan-out. Six friends at one six-max table are one table. Six people each practising against bots are six tables. Identical “concurrent users,” six times the cost. A cap expressed in connections is therefore either too tight for the cheap population or too loose for the expensive one — the one thing it can never be is correct for both.

So the primary bound counts live game tasks, and it refuses at exactly one place:

pub fn table_capacity_refusal(live_tables: usize) -> Option<Response<Body>> {
    let cfg = global_admission_config();
    if cfg.max_live_tables == 0 || live_tables < cfg.max_live_tables {
        return None;
    }
    Some(refusal(SERVICE_UNAVAILABLE, "server_full", cfg.retry_after_sec,
        "The server is at capacity and cannot open a new table right now. \
         Joining an existing table still works."))
}

Note what it refuses. Create, never join. The marginal cost of one more seat at a table that already exists is nearly zero, and turning away someone who was invited to a game already in progress is the worst possible way to spend a capacity limit. When you cap a resource, work out which operations actually allocate it and let the rest through.

Rule 3: know which way each limiter fails

Every limiter has a failure mode and you have to choose it deliberately, because the choices are opposite for different layers.

Our per-caller limiter keeps one entry per key in memory. That map has to be bounded — an unbounded map inside a defence against resource exhaustion is a denial of service wearing a defence’s clothing. But when it is full, what should it do?

The per-caller limiter never evicts a live bucket, and never admits a caller unmetered. If every bucket is still in use it refuses the unknown caller instead. Reaching that state takes tens of thousands of distinct callers active at once — an attack, not a busy Tuesday — and during an attack turning away a stranger is the right failure.
The global capacity rail fails closed. That one is the last thing standing between a busy box and a dead one.

We got that first one wrong twice before it was right, and both wrong answers are instructive. Admitting new keys untracked when the map filled up meant anyone who could fill it could switch the limiter off for everyone arriving afterwards. Evicting the “least indebted” bucket to make room sounded better and was still wrong: the scan is a bounded sample, so an over-budget bucket can be the victim — which hands an attacker a way to clear their own refusal. The rule we landed on is the one whose property can be stated rather than estimated, and that is the actual lesson: if you cannot say in one sentence what your fallback guarantees, you do not have a fallback, you have a hope.

The same thinking produces the exemption list, which is where a naive global limiter does the most damage:

Health and readiness probes are exempt. A busy box that fails its health check gets rolled back or restarted by the deploy system — you have converted a recoverable overload into an outage. This is the single most important line in our implementation, and it is a one-line matches!.
Static bundles are exempt. One cold page load fetches dozens of hashed assets at once over HTTP/2. Counting those against a bound sized for dynamic work sheds real users at a handful of simultaneous page loads — the limiter attacking the site it protects.
The WebSocket upgrade is deliberately NOT exempt, which surprised us. The instinct is that a socket living for an hour should not be counted against a budget sized for 20-millisecond requests — but the handler authenticates the session (a database read) before the socket-specific caps can run, so exempting the path leaves that work outside every bound. It is safe to count because the in-flight slot is released when the 101 response is produced: the framework hands the socket to a separate task, so a live connection holds no request slot. That is a load-bearing framework detail, so it is pinned by a test that opens a real socket and asserts the slot came back.

Rule 4: fixed windows leak double at the boundary

The most common rate-limiter in the wild counts requests into wall-clock windows: now / 60 as the bucket key, reset the counter when the bucket changes. It is four lines and it is wrong in a specific, exploitable way.

A caller with a 60-per-minute cap can spend all sixty at t = 59.9 s and another sixty at t = 60.1 s: 120 requests in 200 milliseconds, entirely within the rules, every minute, on every endpoint you protect that way. If your cap exists because 60 is what the endpoint can survive, the fixed window quietly doubles it at the worst possible moment.

The fix is not a sliding log (one timestamp per request, unbounded memory). It is GCRA — the leaky bucket expressed as a virtual scheduling deadline. One Instant per key, no counters, no resets, and an exact retry time instead of “wait for the window”:

let interval  = window / limit;          // average spacing the quota implies
let tolerance = interval * (limit - 1);  // exactly one full quota of burst

let tat      = *entry;                            // theoretical arrival time
let earliest = tat.checked_sub(tolerance).unwrap_or(now);
if earliest > now {
    return Decision::denied(retry_after: earliest - now);
}
*entry = max(tat, now) + interval;                // admit, advance the deadline

Same memory as the fixed window (better, actually — one timestamp instead of a counter plus a window id), no boundary to game, and the refusal can tell the client exactly how long to wait. Every 429 we emit now carries a real Retry-After derived from that arithmetic rather than a guess.

Rule 5: your limiter runs before authentication, so any key the caller controls is a key they can rotate

Per-IP is the default because it needs no auth. It is also the key that punishes exactly the users you least want to punish: carrier NAT can put thousands of mobile users behind one address, and they share one budget.

Per-account is fairer, but a rate limiter that has to look up an account before it can decide is a database query in front of every route, paid on every request, to save a few tokens.

So we reached for a third option that costs nothing: key on a hash of the session cookie. The cookie is already a random token; hashing it gives a stable per-session identity with no lookup, no PII in the map, and nothing recoverable in the logs.

Our cross-vendor reviewer killed it in one sentence. The limiter runs before authentication — that is the whole point of a middleware — so it cannot tell a real session cookie from an invented one. Any anonymous caller could send session=<random>, get a brand-new budget, and repeat that per request. We had not built a rate limiter. We had built a rate limiter with a documented bypass, and the documentation was a comment explaining how nice the key was.

The fix is to charge two buckets and make the un-forgeable one mandatory:

let addr = check(class, keys.address, ADDRESS_QUOTA_MULTIPLIER);  // always
if !addr.allowed { return addr }
match keys.session {
    Some(s) => check(class, s, 1),   // extra fairness when a cookie exists
    None    => addr,
}

Now rotating cookies buys exactly one thing: the wider address budget, which exists so a NAT full of honest users is not throttled as one person. The escape is bounded by a multiplier instead of being unbounded — and the address bucket is charged even for requests the session bucket then refuses, because a refused caller is still a caller making requests.

The reusable rule is not “don’t key on cookies.” It is: write down which of your keys the caller can choose, and make sure at least one key they cannot choose is always charged. Every keying scheme leaks somewhere. Pick the leak you can live with, bound it, and say so in the comment.

The tower layer, and the one line everyone gets wrong

In axum/tower, a global bound is a Layer wrapping the whole router. The shape is unremarkable except for one detail that bites everybody:

fn call(&mut self, req: Request<Body>) -> Self::Future {
    // `call` may be invoked on a CLONE whose `poll_ready` was never driven.
    // Swap in the ready instance and keep the clone for next time.
    let clone = self.inner.clone();
    let mut inner = std::mem::replace(&mut self.inner, clone);

    Box::pin(async move {
        let _guard = match admission.try_enter() {
            Some(g) => g,                       // RAII: released on EVERY exit
            None => return Ok(refusal(503, "server_busy", retry_after, "...")),
        };
        match tokio::time::timeout(deadline, inner.call(req)).await {
            Ok(res) => res,
            Err(_)  => Ok(refusal(503, "request_timeout", retry_after, "...")),
        }
    })
}

Two things to copy. The mem::replace is the documented tower workaround for the readiness contract; skip it and you get intermittent panics under load, which is a delightful way to discover your capacity layer. And the guard must be a drop guard, not a manual decrement — a client that disconnects mid-request drops the future, and a slot that is only released on the success path leaks one unit of capacity every time that happens. The same rule applies to the WebSocket guard, which we move into the upgraded future so it lives exactly as long as the socket.

Where the numbers come from

A limit you cannot defend gets raised the first time someone complains, which means it may as well not exist. Ours come from a ladder run against the real production box: the service held 150 concurrent tables inside its latency budget, was over budget at 200, and fell off a cliff by 300 — and the operating point was set at 80 % of the measured ceiling, because the ceiling was measured against a fleet that was already connected and warmed up, and real traffic arrives in bursts on top of whatever is already there.

Two properties matter as much as the numbers:

Every bound is an environment variable. When the box changes, the limits move without a code change — and re-measuring is the only honest way to move them, because the binding constraint was never CPU and does not scale with cores.
Every bound is counted. In-flight, peak, shed total, timeout total, rejections by reason. A capacity limit that never reports how often it fired is indistinguishable from one that is misconfigured to never fire, and you will find out which at the worst possible time.

If you take one thing: go and ask your own service what happens when it is full. Not what happens when one caller is rude — what happens when everyone is polite and there are simply too many of them. If the answer is “it gets slower,” you have per-caller rate limiting and no capacity control, and those are not the same product.