GCRA

Deep dive

How it works

In: key, cost, now (monotonic ns) · Out: allow or deny, retry_after, remaining · State: one theoretical arrival time (TAT) per key, 8 bytes · Cost: O(1); one atomic load + one CAS.

Parameters: emission interval T = 1 s / rate, burst b (max requests at once), so the tolerance window is L = b · T.

1. Load tat (0 for a new key).
2. new_tat = max(tat, now) + cost · T.
3. If new_tat − now > L: deny; retry_after = new_tat − L − now.
4. Else store new_tat (CAS) and allow; remaining = (now + L − new_tat) / T.

time ─────────────────────────────────────────►
 now                                 now + L (= b·T)
  │◄────── allowed region for new_tat ──────►│
  └─ tat after k quick requests = now + k·T  → the (b+1)-th exceeds now+L → deny

Code

use std::sync::atomic::{AtomicU64, Ordering};
use std::time::{Duration, Instant};

pub struct Gcra {
    tat: AtomicU64,   // theoretical arrival time, ns since `base`
    t_ns: u64,        // emission interval
    limit_ns: u64,    // burst * emission interval
    base: Instant,
}

#[derive(Debug, PartialEq)]
pub enum Decision { Allow { remaining: u64 }, Deny { retry_after: Duration } }

impl Gcra {
    pub fn new(per_second: u64, burst: u64, base: Instant) -> Self {
        assert!(per_second > 0 && burst > 0);
        let t_ns = 1_000_000_000 / per_second;
        Gcra { tat: AtomicU64::new(0), t_ns, limit_ns: t_ns * burst, base }
    }

    pub fn check(&self, now: Instant, cost: u64) -> Decision {
        let now_ns = now.saturating_duration_since(self.base).as_nanos() as u64;
        let inc = self.t_ns * cost;
        let mut tat = self.tat.load(Ordering::Relaxed);
        loop {
            let new_tat = tat.max(now_ns) + inc;
            if new_tat > now_ns + self.limit_ns {
                return Decision::Deny { retry_after: Duration::from_nanos(new_tat - self.limit_ns - now_ns) };
            }
            // Relaxed is enough: TAT protects no other memory, only itself.
            match self.tat.compare_exchange_weak(tat, new_tat, Ordering::Relaxed, Ordering::Relaxed) {
                Ok(_) => return Decision::Allow { remaining: (now_ns + self.limit_ns - new_tat) / self.t_ns },
                Err(cur) => tat = cur,
            }
        }
    }
}

fn main() {
    let t0 = Instant::now();
    let g = Gcra::new(100, 10, t0);                       // 100 req/s, burst 10
    let allowed = (0..15).filter(|_| matches!(g.check(t0, 1), Decision::Allow { .. })).count();
    assert_eq!(allowed, 10);
    assert_eq!(g.check(t0, 1), Decision::Deny { retry_after: Duration::from_millis(10) });
    assert!(matches!(g.check(t0 + Duration::from_millis(10), 1), Decision::Allow { remaining: 0 }));
}

Shared limit in Redis. The same arithmetic runs server-side as a script (EVAL, or the redis-cell module's CL.THROTTLE), so read-compute-write is atomic without a client round trip per step: GET the TAT (missing = now), compute new_tat = max(tat, now) + cost·T, deny with retry-after new_tat − limit − now if new_tat − now > limit, else SET key new_tat PX ceil(new_tat − now). The expiry equals the time until the key is back to idle, so idle clients cost no memory. Take now from Redis TIME (or one trusted clock) rather than from each caller.

Complexity and constants

• In process: one atomic load + one CAS; order of 5-20 ns uncontended. Under heavy contention on one key, CAS retries rise; shard hot keys or batch costs.
• Memory: 8 bytes per key (plus map overhead). The key can expire as soon as tat ≤ now: an idle key carries no information.
• Redis: one GET + one SET in a script per check; the TTL drops idle keys automatically.
• Resolution: integer ns makes T exact for rates dividing 10⁹; for others the rounding error is < 1 ns per request.

Efficiency

• Cost: In process one atomic load and one CAS: order of 5-20 ns uncontended, 8 bytes per key. The Redis form is one GET and one SET inside one script, a round trip of order of 0.1-1 ms. The bound is contention on one key's cache line in process, and the network round trip when shared.
• Levers:
  • One timestamp instead of (tokens, last) — 16 → 8 bytes per key, a CAS instead of a lock — many keys.
  • Reserve several units per CAS (batch cost) — fewer CAS retries — hot keys.
  • Expire the key once tat ≤ now (Redis PX) — idle keys cost 0 bytes — huge key spaces.
  • Server-side script or CL.THROTTLE — 1 round trip instead of 3 — limits shared across servers.
• Naive → standard → state of the art:
  • Mutex around (tokens, last) with a refill timer per key · a lock and a timer per key.
  • Lazy-refill token bucket with a shard mutex · about 16 B per key, order of 10-30 ns.
  • GCRA, AtomicU64 per key (governor), or redis-cell in Redis · 8 B per key, lock-free, order of 5-20 ns.

Implementation notes

• per_second above ~10⁹ gives t_ns = 0; for very high rates, count in units of cost or use a token bucket with fixed-point tokens.
• Keyed limiters: a sharded map of AtomicU64 (or a concurrent map like dashmap), with periodic sweep of keys where tat < now.
• Use one now per batch of checks to amortize the clock read.
• Multiple limits (per second and per day): run two GCRAs; allow only if both allow, and roll back the first if the second denies (or accept small overspend).
• Send Retry-After directly from retry_after; clients that honor it remove most retry pressure.
• Remaining quota for headers: (now + limit − tat) / T tokens, the exact token-bucket count; with matching parameters GCRA and a token bucket admit the same requests (mind off-by-one in how each counts burst).
• The CAS loop retries only when another thread updated the same key in between; under heavy contention on one key, batch costs per thread (reserve 10 at once) to cut retries.

Pitfalls

• Using wall-clock time across machines in the Redis variant without a single time source: skewed callers grant extra or deny wrongly. Use the server's TIME or one clock per region.
• Forgetting max(tat, now): idle time then accumulates as unlimited credit.
• cost > burst can never succeed: reject it up front with a clear error instead of an endless retry-after.
• Integer overflow on t_ns * cost with large costs; use checked or saturating math.

Variants and alternatives

In production

governor (Rust, keyed and direct GCRA limiters), redis-cell (CL.THROTTLE), throttled (Go), ATM switches (the original use: cell rate policing).

Implementations

Sources

• ITU-T Recommendation I.371, Traffic Control and Congestion Control in B-ISDN. spec
• The ATM Forum, Traffic Management Specification Version 4.0, 1996.
• governor, Rust GCRA rate limiter. code
• Brandur Leach, redis-cell, Redis module implementing GCRA. code