Distributed rate limiting

Deep dive

How it works

Parts:

• Key builder — maps a request to keys (ip:<addr>, acct:<id>, acct:<id>:<endpoint>); spends only if all allow.
• Limiter policy — GCRA, token bucket or sliding-window counter per key.
• Decision site — central store (e.g. Redis), per-node state, or a lease holder.
• Coordinator — owns the global bucket, grants token batches (design 3).
• Response layer — 429 plus Retry-After, shadow mode, fail-open/closed switch per endpoint.

Designs, in order of falling cost and rising error:

1. Central counter. Each request runs one atomic update in the store: a Lua script (Redis runs a script atomically), a MULTI/INCR/EXPIRE fixed window, or one GCRA key (redis-cell: CL.THROTTLE key max_burst count period [quantity] returns allowed flag, limit, remaining, retry-after, reset). Exact; 1 call per request.
2. Static split. Node i enforces L/N with a local limiter; membership changes rescale L/N. 0 calls. A node that gets more than 1/N of the traffic rejects while others idle.
3. Leased budgets. A node asks the coordinator for k tokens when its local budget is empty and spends them locally. Leases expire after a TTL (leases) so a dead or idle node strands nothing. If the coordinator is empty, back off before asking again. Envoy's quota-based global limiting works this way: nodes request quota assignments from a quota service.
4. Gossip counters. Nodes broadcast local counts (gossip style) and limit on the estimated sum. No store; over-admission grows with gossip delay; soft limits only.
5. Route by key. The edge hashes the key with consistent hashing so one node sees all of a key's traffic and a local limiter is exact. Cost: hot keys cannot spread; failover resets that key's state.
6. Answer. Allowed: forward. Denied: 429 with Retry-After; in shadow mode log and forward.

 client ─► LB ─► node 0 ─┐          design 1: every request ──────────►┐
 client ─► LB ─► node 1 ─┼─ local limiter ─┐                            │
 client ─► LB ─► node N ─┘  design 2: L/N  │  design 3: k tokens / call ▼
                                           └──────────► coordinator / Redis (GCRA per key)

Code

8 nodes, 20,000 requests at 2,000/s against a 1,000/s limit (burst 96), balancer weights 40/20/10/10/5/5/5/5 %.

use std::collections::HashMap;
use std::sync::atomic::{AtomicU64, Ordering::Relaxed};
use std::sync::Mutex;
use std::time::Instant;

const MS: u64 = 1_000_000;
/// One limit: a cell every `t` ns on average, bursts of `b` cells.
#[derive(Clone, Copy)]
struct Limit { t: u64, b: u64 }

/// GCRA state: one number, the theoretical arrival time (ns).
#[derive(Default, Clone, Copy)]
struct Gcra { tat: u64 }
impl Gcra {
    /// Grant up to `n` cells at `now`; returns how many fit.
    fn grant(&mut self, n: u64, now: u64, l: Limit) -> u64 {
        let base = self.tat.max(now);
        let room = (l.b * l.t).saturating_sub(base - now) / l.t;
        let g = n.min(room);
        self.tat = base + g * l.t;
        g
    }
}

/// Central store: every call is one network round trip in a real system.
struct Central { m: Mutex<HashMap<u32, Gcra>>, calls: AtomicU64 }
impl Central {
    fn new() -> Self { Central { m: Mutex::new(HashMap::new()), calls: AtomicU64::new(0) } }
    fn take(&self, key: u32, n: u64, now: u64, l: Limit) -> u64 {
        self.calls.fetch_add(1, Relaxed);
        self.m.lock().unwrap().entry(key).or_default().grant(n, now, l)
    }
}

/// Local lease: tokens taken in a batch, void after `ttl` ns.
#[derive(Default)]
struct Lease { tokens: u64, exp: u64, blocked_until: u64 }

fn xorshift(s: &mut u64) -> u64 { *s ^= *s << 13; *s ^= *s >> 7; *s ^= *s << 17; *s }

/// (arrival ns, node) pairs: 2000 req/s for 10 s, skewed balancer.
fn trace(n_req: usize) -> Vec<(u64, usize)> {
    let w = [40u64, 20, 10, 10, 5, 5, 5, 5]; // percent of traffic per node
    let mut s = 0x9E3779B97F4A7C15;
    (0..n_req).map(|i| {
        let mut r = xorshift(&mut s) % 100;
        let node = w.iter().position(|&x| { if r < x { true } else { r -= x; false } }).unwrap();
        (i as u64 * 500_000, node)
    }).collect()
}

/// Run `f` over the trace; returns (admitted, worst admitted count in an aligned 100 ms bin).
fn run(tr: &[(u64, usize)], mut f: impl FnMut(usize, u64) -> bool) -> (u64, u64) {
    let mut bins = vec![0u64; (tr.last().unwrap().0 / (100 * MS)) as usize + 1];
    let mut ok = 0;
    for &(t, node) in tr { if f(node, t) { ok += 1; bins[(t / (100 * MS)) as usize] += 1; } }
    (ok, *bins.iter().max().unwrap())
}

fn main() {
    const N: usize = 8;
    let tr = trace(20_000);
    let end = tr.last().unwrap().0;
    let lim = Limit { t: MS, b: 96 }; // 1000/s, burst 96
    let bound = lim.b + end / lim.t; // most any GCRA can admit by time `end`
    let mut rows: Vec<(&str, u64, u64, f64, f64)> = vec![];
    for variant in 0..3 {
        let reps = 50;
        let (mut res, mut calls, t0) = ((0, 0), 0, Instant::now());
        for _ in 0..reps {
            let c = Central::new();
            let mut stat: Vec<Gcra> = vec![Gcra::default(); N];
            let mut lease: Vec<Lease> = (0..N).map(|_| Lease::default()).collect();
            let split = Limit { t: lim.t * N as u64, b: lim.b / N as u64 }; // L/N each
            res = run(&tr, |node, now| match variant {
                0 => c.take(0, 1, now, lim) == 1,                      // central: 1 call per request
                1 => stat[node].grant(1, now, split) == 1,              // static split: 0 calls
                _ => {                                                  // leases: batch 20, ttl 50 ms
                    let l = &mut lease[node];
                    if now >= l.exp { l.tokens = 0; }
                    if l.tokens == 0 && now >= l.blocked_until {
                        let g = c.take(0, 20, now, lim);
                        if g > 0 { l.tokens = g; l.exp = now + 50 * MS } else { l.blocked_until = now + 5 * MS }
                    }
                    if l.tokens > 0 { l.tokens -= 1; true } else { false }
                }
            });
            calls = c.calls.load(Relaxed);
        }
        let dt = t0.elapsed().as_secs_f64();
        rows.push((["central", "static L/N", "lease x20"][variant], res.0, res.1,
                   calls as f64 / tr.len() as f64, reps as f64 * tr.len() as f64 / dt / 1e6));
    }
    assert!(rows[0].1 <= bound, "central must never exceed the exact bound");
    println!("limit bound {bound} of {} offered; central worst 100ms bin {}", tr.len(), rows[0].2);
    for (name, ok, worst, calls, mdps) in &rows {
        println!("{name:<11} admitted {ok:>5} ({:+.1}% vs bound) worst100ms {worst:>3} calls/req {calls:.3} {mdps:.1} M decisions/s",
                 (*ok as f64 / bound as f64 - 1.0) * 100.0);
    }
}

Output, measured on this Mac (Apple M4 Pro), release build, single thread; "calls" are coordinator calls per offered request, with no network in the model:

limit bound 10095 of 20000 offered
central     admitted 10095 (+0.0%) calls/req 1.000 105.4 M decisions/s
static L/N  admitted  8997 (-10.9%) calls/req 0.000 510.6 M decisions/s
lease x20   admitted 10058 (-0.4%) calls/req 0.566 124.3 M decisions/s

"Bound" is the most a burst-96, 1,000/s GCRA can admit in this trace. Leased tokens are debited at the coordinator, so the total never exceeds it; the error is timing (spent up to a TTL late) and expiry. Calls/req is high because at 2x overload an empty coordinator is re-asked every 5 ms; at normal load it is about 1/k per admit (by construction, not measured).

Complexity and constants

• O(1) per decision; state 8-16 bytes per key plus map overhead.
• Cost drivers: round trips per request (1, 1/k or 0), key cardinality, hot keys, store replication.
• Over-admission: central 0; static L/N none but under-admits under skew; leases at most N·k tokens above policy in a window; gossip grows with delay.

Efficiency

• Cost: The central decision itself is ~10 ns (measured above, uncontended, no network). A real check is one round trip, order of 0.1-1 ms, and one Redis core serves order of 10⁵ script calls/s (see Token bucket). Bound: network latency and the single-key core, not CPU.
• Levers:
  • Lease k tokens per call — calls drop to about 1/k (measured: 0.566/req under overload, ≤ 1/k when not) — high request rates per node.
  • Local bucket in front of the global check — absorbs bursts, fewer global calls (Envoy docs recommend local plus global) — bursty clients.
  • Route by key — 0 calls, exact — when the balancer can hash on the key.
  • One script call per check — 1 round trip instead of 3 — multi-key checks.
  • Cache "denied until t" locally — no store call for abusers — attack traffic.
• Naive → standard → state of the art:
  • Read, compare, write back (racy) · 2 round trips, over-admits.
  • Atomic GCRA/script per request in Redis · 1 round trip, exact.
  • Local bucket plus leased global quota · ~1/k calls, bounded over-admission.

Implementation notes

• Failure of the store: choose per endpoint. Fail open for ordinary reads (Stripe fails open so a Redis outage does not break the API); fail closed for login, SMS and payment, or fall back to a local L/N limiter.
• Give the store call a tight timeout; a slow store is worse than a down one. Wrap it in a circuit breaker.
• Clock skew: take now from one source (the store's TIME) for window algorithms; leases use each node's monotonic clock and a TTL.
• Keys: aggregate IPv6 by /64 (common practice: one subscriber usually holds a /64); carrier-grade NAT (shared space 100.64.0.0/10, RFC 6598) puts many users behind one IPv4 address, so give IP limits headroom and prefer account limits after login. Expire idle keys.
• 429 Too Many Requests is RFC 6585 (Proposed Standard, 2012): it may carry Retry-After, defined in HTTP semantics (RFC 9110). Return the computed wait, add jitter on the client (backoff).
• "RateLimit header fields for HTTP" (draft-ietf-httpapi-ratelimit-headers-11, 2026-05-23) is still an Internet-Draft, not an RFC; it defines RateLimit-Policy and RateLimit.
• Shadow mode first: Stripe dark-launches each limiter to see what it would block, and keeps feature-flag kill switches.

Pitfalls

• N local buckets at rate L each: N × L admitted.
• Fixed-window INCR doubles the burst at window edges; use GCRA or a sliding window.
• INCR then EXPIRE as two calls leaks a key if the client dies between them (the Redis docs warn about this); use MULTI/Lua.
• Store failover loses recent counts (replication is asynchronous): brief over-admission, usually acceptable.
• Limiting only by IP blocks a whole school or mobile carrier.
• Leases without TTL: a crashed node strands its tokens.

Variants and alternatives

In production

Stripe's request-rate and concurrency limiters on Redis; Envoy global rate limiting via a gRPC rate limit service (envoyproxy/ratelimit, Redis) and its quota-based mode.

Implementations

Sources

• M. Nottingham, R. Fielding, Additional HTTP Status Codes, RFC 6585, 2012. RFC
• R. Fielding et al., HTTP Semantics, RFC 9110, 2022 (Retry-After). RFC
• RateLimit header fields for HTTP, Internet-Draft draft-ietf-httpapi-ratelimit-headers-11, 2026. draft
• J. Weil et al., IANA-Reserved IPv4 Prefix for Shared Address Space, RFC 6598, 2012. RFC
• Stripe Engineering, Scaling your API with rate limiters, Stripe blog, 2017. post
• Redis docs, INCR (rate limiter pattern) and Scripting with Lua. INCR · Lua
• Envoy docs, Global rate limiting. docs