Rate Limiter Architecture, in depth: GCRA in one Redis key, composite limits, local token leasing, failure policy and client signalling

The contract

Every limit is a key, a rate and a burst. The key is built from request attributes, called descriptors: tenant, user, API key, route, or a combination. The rate is the sustained allowance, such as 100 requests per second. The burst is how many requests may arrive at once after a quiet period.

The limiter exposes one function: decide(descriptors, cost) -> (allowed, retry_after, remaining). Cost lets one call count as more than one unit, which matters for expensive endpoints or token-metered LLM APIs. Everything else in the architecture exists to make that function fast, correct enough, and safe when its dependencies fail.

GCRA: a token bucket in one number

A token bucket stores two numbers per key: tokens and last refill time. GCRA stores one, the theoretical arrival time (TAT): the time at which the key would be fully rested if requests arrived exactly at the allowed rate. With emission interval T, the period divided by the rate, and burst B, each admitted request pushes TAT forward by T, and a request is allowed if the new TAT is no more than B intervals ahead of now.

One number means one small Redis string per key, one atomic read-modify-write, and an exact retry-after for free: the time until the request would have been allowed. It is equivalent to a token bucket with capacity B and refill rate 1/T.

-- GCRA: one key per limit, time from the Redis server.
-- KEYS[1] = limit key; ARGV = emission interval T (us), burst B, cost
local T    = tonumber(ARGV[1])
local B    = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local t    = redis.call('TIME')
local now  = tonumber(t[1]) * 1000000 + tonumber(t[2])

local tat = tonumber(redis.call('GET', KEYS[1])) or now
if tat < now then tat = now end
local new_tat  = tat + T * cost
local allow_at = new_tat - B * T

if allow_at > now then
  return {0, allow_at - now, 0}              -- denied, retry after (us)
end
redis.call('SET', KEYS[1], new_tat, 'PX', math.ceil((new_tat - now) / 1000) + 1)
return {1, 0, math.floor((now - allow_at) / T)}   -- allowed, remaining

Three details make this production-grade. Time comes from Redis TIME, not from the gateways, so clock skew between pods cannot grant extra requests; calling it before writes relies on effect replication, the default since Redis 5. The key expires when TAT falls into the past, because an expired key and a rested key behave identically, so idle keys cost no memory. And the whole decision is one script, so concurrent requests on the same key cannot both pass on a stale read.

Tracing it by hand

Take 5 requests per second with burst 3, so T = 200,000 microseconds and B = 3. Four requests arrive at time 0. The first finds no key, so TAT is 0; new TAT is 200,000 and allow_at is 200,000 minus 600,000, far in the past: allowed, with 2 remaining. The second moves TAT to 400,000 with allow_at at minus 200,000: allowed, 1 remaining. The third moves it to 600,000 with allow_at at 0, which is not after now: allowed, 0 remaining.

The fourth would move TAT to 800,000, putting allow_at at 200,000, after now: denied, retry after 200 ms, and nothing is written. At 250 ms a new request finds TAT at 600,000, computes new TAT 800,000 and allow_at 200,000, which is before 250,000: allowed. Another at the same instant would need allow_at 400,000, so it is denied with a 150 ms retry. That is exactly a burst of three followed by one request per 200 ms.

Composite limits in Redis Cluster

Real policies stack limits: 1,000 per second per tenant and 50 per second per user within it. Checking them in two calls creates a race in which the first call consumes quota and the second denies, so quota leaks. Checking them in one script needs all keys in one cluster slot, which Redis Cluster allows through hash tags: keys rl:{tenant42}:all and rl:{tenant42}:user:7 hash only the braced part, so they share a slot.

The composite script computes every limit's new TAT first, denies if any limit denies, returning the largest retry-after, and writes all TATs only if all allow. The cost is that one busy tenant's keys all live on one shard. That is usually right, since limits are per tenant anyway, but watch per-shard load for your largest tenants.

Scaling the hot path with local leases

A Redis call per request adds a network round trip and puts Redis on every request's critical path. A Redis shard handles a large but finite number of script calls per second, and one huge tenant lands on one shard. The fix is to let each gateway pod take a lease: consume several units from the global GCRA in one call, then serve that many decisions from memory.

import threading, time

class LeasedLimiter:
    """Serve most decisions from a local lease; refill it from the global GCRA."""
    def __init__(self, redis_script, key, interval_us, burst, lease=10, ttl=1.0):
        self.script, self.key = redis_script, key
        self.T, self.B, self.lease, self.ttl = interval_us, burst, lease, ttl
        self.tokens, self.expires = 0, 0.0
        self.lock = threading.Lock()

    def allow(self):
        with self.lock:
            now = time.monotonic()
            if self.tokens > 0 and now < self.expires:
                self.tokens -= 1
                return True, 0
            ok, retry_us, _ = self.script(keys=[self.key],
                                          args=[self.T, self.B, self.lease])
            if not ok:                        # a full lease is not available
                ok, retry_us, _ = self.script(keys=[self.key],
                                              args=[self.T, self.B, 1])
                return bool(ok), retry_us
            self.tokens, self.expires = self.lease - 1, now + self.ttl
            return True, 0

Leasing never admits more than the global limit, because every leased unit was counted by the script. Its error runs the other way: units leased by a pod that then gets no traffic are stranded until they expire. With P pods and lease size L, up to P times L units can be stranded, so a quiet period at the wrong moment can deny requests the global limit would have allowed. The script's fallback to a single-unit request when a full lease is unavailable limits that loss near the edge of the quota.

Choose L from the per-pod rate: a lease should last a fraction of a second, since longer leases save little and strand more. Keys with low limits should not be leased at all.

When the limiter's dependencies fail

Whatever the policy, put a tight timeout on the Redis call, a few milliseconds, and a circuit breaker around it, so a slow Redis does not add its latency to every request. Emit a metric whenever a decision is made in fallback mode; silent fail-open looks exactly like healthy traffic.

Telling clients what happened

Deny with HTTP 429 Too Many Requests, defined in RFC 6585, and a Retry-After header, defined in RFC 9110, in whole seconds rounded up from the script's retry value. The IETF HTTP API working group has a draft defining RateLimit and RateLimit-Policy fields that advertise quota and remaining units; it is still a draft whose syntax has changed between revisions, so pin to a specific revision if you emit it.

Keep rate limiting separate from overload. A 429 says this caller exceeded its allowance. When the service itself is overloaded, shed load with 503 regardless of caller; that is covered in load shedding and backpressure. A rate limiter that is also asked to protect capacity ends up with limits set so low that they hurt well-behaved tenants.

Multi-region budgets

A single global Redis across regions puts a cross-region round trip on the hot path. The common alternatives are: give each region its own limiter with a fixed share of the budget, which under-admits when traffic is skewed; give each region the full budget, which can admit up to N times the limit across N regions; or rebalance shares every few seconds from observed regional traffic. For most APIs, per-region shares rebalanced periodically are accurate enough, and a per-tenant home region is simpler still when tenants are geographic.

The policy plane

Limits change more often than code. Keep them in a versioned policy store that gateways load and cache, with defaults per tier and overrides per tenant. Every new or tightened limit ships first in shadow mode: the decision is computed and logged as would-deny but not enforced. A day of shadow data shows exactly which callers a limit would hit before any of them see a 429. Record metrics per limit, not per key, to keep cardinality bounded, and log denied keys separately.

Worked example: a public API tier

A SaaS API gives each tenant 1,000 requests per second with a burst of 200, and each user 50 per second with a burst of 20. Forty gateway pods serve 30,000 requests per second at peak. Per tenant, T is 1,000 microseconds and B is 200; per user, T is 20,000 and B is 20.

Without leasing, peak load is 30,000 composite script calls per second. Leasing the composite check would be wrong: a lease of 10 would take half of one user's burst, and splitting the checks brings back the quota leak. So interactive traffic keeps the single composite script, with tenants spread across shards by their hash tags and the cluster sized for the full call rate. Leasing applies only to machine API keys, which carry a tenant limit and no per-user limit, about 60 percent of traffic. Leases of 10 cut those calls from 18,000 to about 1,800 per second. The worst-case stranded quota for one tenant is 40 times 10, or 400 units, under half a second of its allowance, and the one-second lease lifetime bounds how long it stays stranded.

They fail open for the capacity limits with a local fallback of 25 per second per tenant per pod, and fail closed for the login endpoint. Shadow mode found three integration partners bursting to 600 at the top of each minute; they raised those partners' burst before enforcing.

Testing it

Run the same algorithm in pure Python with an injected clock and test the traced sequence, then run the Lua script against a real Redis in CI with a loop of concurrent callers and check that admitted counts never exceed B plus elapsed time divided by T.

def gcra(state, now, T, B, cost=1):
    """Pure-Python twin of the Lua script, for tests with a fake clock."""
    tat = max(state.get("tat", now), now)
    new_tat = tat + T * cost
    allow_at = new_tat - B * T
    if allow_at > now:
        return False, allow_at - now
    state["tat"] = new_tat
    return True, 0

def test_burst_then_steady():
    s, T, B = {}, 200_000, 3                 # 5 per second, burst 3
    assert [gcra(s, 0, T, B)[0] for _ in range(4)] == [True, True, True, False]
    assert gcra(s, 0, T, B) == (False, 200_000)
    assert gcra(s, 250_000, T, B)[0] is True
    assert gcra(s, 250_000, T, B)[0] is False

Failure modes

What to do next

1. Write down every limit you enforce as key, rate, burst, and what it protects: capacity, spend or security.
2. Implement GCRA as one Redis script with server time, and test it with a fake clock and with concurrent callers.
3. Put composite limits in one slot with hash tags and write all keys only when all allow.
4. Choose fail-open or fail-closed per limit, add a timeout and circuit breaker, and alert on fallback decisions.
5. Return 429 with Retry-After, and use load shedding, not the rate limiter, for overload.
6. Add leases only when Redis load or latency demands it, and measure stranded quota.
7. Ship every new limit in shadow mode first.