Skip to content

GCRA Rate Limiting with Redis

A shared rate limit across many async workers needs state in one place, usually Redis, and the choice of algorithm decides how much state that is. A sliding-window log stores every request in the window; the generic cell rate algorithm (GCRA) stores a single number per key — the theoretical arrival time of the next request — and derives both "allowed?" and "retry after how long?" from it. Measured with Redis 8.10 and redis-py's async client: for 10,000 keys each allowed 100 requests per minute and filled to the limit, GCRA used 0.9 MiB — 89–92 bytes per key — and a sliding-window log in a sorted set 35.0 MiB, 3,657–3,667 bytes per key. Each check took 80–83 µs for GCRA and 77–89 µs for the log, a round trip either way. With a limit of 10 per second and a burst of 5, twenty clients hammering for three seconds got 36 requests through — the 6-request burst plus 30 — spaced 100.0 ms apart on average. But clients that slept for the returned retry-after and tried again made 17 denied checks per allowed request, because they all woke together; a reservation variant that books the next slot and tells the client exactly when to go made 0 refused calls and one Redis call per request — 55 calls against 648. This guide implements both.

Prerequisites

1. Understand GCRA's one number

For a limit of limit requests per period, GCRA spaces requests one emission interval apart, interval = period / limit, and keeps a theoretical arrival time (TAT): when the next request would be due if traffic were perfectly even. A request at time now is allowed if now is no earlier than TAT − burst × interval, and each allowed request pushes TAT one interval further:

local interval = period_ms / limit
local tat = tonumber(redis.call('GET', key) or now)
if tat < now then tat = now end
local allow_at = tat - burst * interval
if now < allow_at then
  return {0, math.ceil(allow_at - now)}         -- denied; retry after this many ms
end
local new_tat = tat + interval
redis.call('SET', key, new_tat, 'PX', math.ceil(new_tat - now) + 1)
return {1, 0}

That is the whole state: one value, expiring on its own once traffic stops. The burst parameter lets burst + 1 requests through back to back after an idle period, then enforces the interval. Measured with 10 per second and a burst of 5: 36 requests passed in three seconds of saturation — 6 at once, then 30 more — and 7 within the first 100 ms (the burst plus the first refilled slot). Take now from redis.call('TIME') inside the script, so every client uses the same clock.

Verify: after an idle period, exactly burst + 1 requests pass immediately, and sustained traffic is spaced one interval apart.

2. Compare memory and speed with a sliding log

A sliding-window log is exact in a different sense — it counts the requests actually made in the last window — and stores each of them:

redis.call('ZREMRANGEBYSCORE', key, '-inf', now - window_ms)
if redis.call('ZCARD', key) >= limit then return {0, 0} end
redis.call('ZADD', key, now, member)

Measured for 10,000 keys at 100 requests per minute each: 35.0 MiB for the sorted sets against 0.9 MiB for GCRA — about 40 times more memory — with check times within a few microseconds of each other, since both are dominated by the network round trip. The log's memory grows with the limit: a key allowed 10,000 requests per hour holds 10,000 members at saturation, while GCRA's stays one number. For per-user or per-API-key limits across many keys, that difference decides whether the limiter fits comfortably in Redis.

Verify: Redis memory per limiter key is known for your limits and key count.

GCRA against a sliding-window log in Redis A grid of 5 rows by 3 columns. GCRA against a sliding-window log in Redis property GCRA sliding-window log state per key one timestamp one entry per request in the window memory, 10,000 keys at 100/min 0.9 MiB (89-92 B/key) 35.0 MiB (3,657-3,667 B/key) check latency 80-83 us 77-89 us retry-after exact, from TAT needs the oldest entry reservation (book a future slot) natural awkward Redis 8.10, redis-py asyncio, Lua scripts using Redis TIME.

3. Avoid retry stampedes from denied clients

A denied client gets a precise retry-after, but every other denied client gets nearly the same one. They all sleep, wake together, and all but one are denied again:

async def call_with_retry(limiter, fn):
    while True:
        allowed, retry_ms = await limiter(keys=["api"], args=[1000, 10, 5])
        if allowed:
            return await fn()
        await asyncio.sleep(retry_ms / 1000)          # 20 clients wake at the same moment

Measured with 20 clients sharing 10 requests per second: 36 requests went through and 612 checks were denied — 17 wasted Redis round trips per allowed request, each costing about 80 µs of Redis time and a wake-up on the client. Adding random jitter to the sleep spreads the wake-ups but cannot fix the arithmetic: twenty clients competing for one slot every 100 ms means nineteen denials per slot. The fix is to stop competing for slots and hand them out instead.

Verify: count denied checks per allowed request; a ratio near the number of competing clients means a stampede.

Redis calls to get requests through, 20 clients sharing 10/s 2 horizontal bars comparing retry after denial: 36 through with the others. Redis calls to get requests through, 20 clients sharing 10/s retry after denial: 36 through 648 calls reserve a slot: 55 through 55 calls Both kept requests 100.0 ms apart on average; reservation clients booked up to 2 s ahead. Booking slots removes the stampede of denied retries.

4. Reserve slots instead of retrying

GCRA's state makes reservation natural: rather than refusing a request that is early, book it the next free slot — push TAT forward — and tell the client how long to wait before going. Refuse only when the wait would exceed what the caller accepts:

local wait = tat - burst * interval - now
if wait < 0 then wait = 0 end
if wait > max_wait then
  return {0, math.ceil(wait)}                -- too far out: refuse, book nothing
end
redis.call('SET', key, tat + interval, 'PX', math.ceil(tat + interval - now) + 1)
return {1, math.ceil(wait)}                  -- booked: sleep wait ms, then go

async def acquire_slot(reserve, key: str, max_wait_ms: int = 2000) -> None:
    booked, wait_ms = await reserve(keys=[key], args=[1000, 10, 5, max_wait_ms])
    if not booked:
        raise RateLimited(retry_after=wait_ms / 1000)
    await asyncio.sleep(wait_ms / 1000)

Measured with the same 20 clients and a 2-second maximum wait: 55 requests went through with 0 refusals and exactly 55 Redis calls, still spaced 100.0 ms apart (minimum 99.1 ms). Clients queue in Redis in the order they asked, so the result is also first-come, first-served across processes. A booked client that is cancelled while sleeping leaves its slot unused, which only makes the limiter slightly conservative. Choose max_wait from the caller's deadline, so no request books a slot it cannot use, as in propagating deadlines with contextvars.

Verify: under contention, each request costs one Redis call, and booked requests start at their slot times.

Two clients reserving slots A sequence of 4 messages between 3 participants. Two clients reserving slots client A Redis (TAT) client B reserve: wait 0, TAT += 100 ms reserve: wait 100 ms, TAT += 100 ms go now sleep 100 ms, then go One call per request; order is preserved across processes.

5. Key, expire and fail safely

Use one GCRA key per limited subject — API key, tenant, route — and let the PX expiry clean up idle keys; GCRA's key lives only as long as its TAT is in the future. Decide in advance what the service does when Redis is unavailable:

async def allowed(limiter, key: str) -> bool:
    try:
        ok, _ = await asyncio.wait_for(limiter(keys=[key], args=[60_000, 100, 10]), 0.05)
        return bool(ok)
    except (redis.ConnectionError, TimeoutError):
        LIMITER_UNAVAILABLE.inc()
        return LOCAL_FALLBACK.try_acquire(key)          # a per-process limit at limit / instances

Failing open loses the limit during an outage; failing closed turns a Redis outage into a full one; a per-process fallback at a fraction of the global limit keeps a rough bound. The same choice is discussed for sliding windows in sliding window rate limiting with Redis and asyncio. Several limits on one request — per second and per day — need checking together before any is consumed, as in enforcing multiple rate limits at once.

Verify: limiter keys expire after idle periods, and a Redis outage produces the behaviour you chose, under a tight timeout.

Which Redis rate limiter? A decision on What does the limit need with 4 outcomes. Which Redis rate limiter? What does the limit need? many keys or large limits GCRA ~90 bytes per key many clients competing GCRA reservation 1 call per request exact count of last-window requests sliding-window log ~3.7 KB per key here Redis down decided fallback + tight timeout open, closed or local Use Redis TIME inside the script so all clients share one clock.

Verification

A GCRA limiter in Redis is correct when:

  • Bursts and spacing match the configuration: burst + 1 immediately, then one interval apart.
  • State is one key per subject, expiring when idle, with memory measured.
  • Competing clients reserve slots rather than retrying, costing one call per request.
  • The Redis-failure behaviour is defined and protected by a timeout.

Diagnostic Hook: export allowed, denied and booked-wait times per limiter key. A rising booked wait is the queue in front of the limit growing — demand above the configured rate — and shows up long before requests start being refused at max_wait.

Pitfalls & edge cases

  • Retrying denied clients. Measured: 17 denied checks per allowed request.
  • Sliding logs for many keys. Measured: about 40 times GCRA's memory.
  • Client clocks in the script. Use redis.call('TIME').
  • Booking slots beyond the caller's deadline. Set max_wait from it.

Frequently Asked Questions

What is GCRA rate limiting?

The generic cell rate algorithm stores one value per key — the theoretical arrival time of the next request — and allows a request if it is no more than the burst allowance early. It used about 90 bytes per key in Redis in testing.

Is GCRA better than a sliding window in Redis?

For memory, by far: 0.9 MiB against 35 MiB for 10,000 keys at 100 requests per minute, at the same 80 µs per check. A sliding log counts exact requests in the window, if you need that.

How do I stop rate-limited clients from retrying in a stampede?

Use GCRA in reservation mode: each call books the next slot and returns the wait. With 20 clients, Redis calls fell from 648 to 55 with no refusals.

How is burst handled in GCRA?

A burst of b lets b + 1 requests through at once after idleness; with 10/s and burst 5, 36 requests passed in 3 seconds of saturation.