GCRA & Virtual Scheduling

The generic cell rate algorithm stores one number per client — a timestamp — and from it derives an exact answer to “may this request proceed, and if not, how long until it can?” It is the quiet workhorse behind several production limiters, including rate-limiter-flexible’s burstiest modes and Redis’s own throttle module, and it belongs in the algorithm vocabulary the Core Rate Limiting Algorithms & Theory reference establishes. Where a token bucket tracks a floating token count and a refill timestamp, GCRA tracks only a theoretical arrival time and compares it against now. Same shape of behaviour, half the state, and a retry delay that falls out of the arithmetic instead of being estimated.

GCRA comes from ATM network traffic shaping, where it policed cell arrivals against a contracted rate. The translation to APIs is direct: a cell is a request, the emission interval is the minimum spacing between requests at the contracted rate, and the delay variation tolerance is how much bunching you permit before rejecting.

Mechanism: theoretical arrival time

Define two constants from the limit you want to advertise:

• Emission interval T — the ideal spacing between requests. For 100 requests per 60 seconds, T = 600 ms.
• Tolerance τ (tau) — how far ahead of schedule a client may run, expressed as a duration. A burst allowance of B requests means τ = B × T. With B = 10 and T = 600 ms, τ = 6,000 ms.

The stored state is a single timestamp, the theoretical arrival time (TAT): the earliest moment at which the next request would be perfectly on schedule. The decision rule is two lines:

allow  if  now ≥ TAT − τ
then       TAT ← max(now, TAT) + T
deny   otherwise, with retry_after = (TAT − τ) − now

Three properties follow immediately. First, the state is O(1) — one integer per key, roughly 8 bytes plus key overhead, against the two fields a token bucket keeps. Second, the retry delay is exact rather than estimated: (TAT − τ) − now is precisely how long until the request would be admitted, so the Retry-After you emit is correct to the millisecond instead of rounded off a token count. Third, there is no floating-point refill accumulating rounding error over millions of operations, because time itself is the accumulator.

Walk one sequence at T = 600 ms, τ = 1,800 ms (burst of 3), starting from an idle key:

The burst of four at t = 0 is the tolerance working as designed: τ of 1,800 ms buys three requests of slack above the perfectly paced one. Notice the denied request does not advance TAT — denials are free, so a client hammering a closed door cannot push its own recovery further away. That single property is what makes GCRA behave sanely under retry storms, and it is the detail most hand-rolled implementations get wrong.

Configuration reference

Set key_ttl to at least τ + T. Expire earlier and a client’s burst allowance silently resets during a lull, which is usually harmless but makes the limiter’s behaviour non-reproducible in tests. Expire much later and you retain memory for keys that will never return, wasting store space exactly as an unbounded sliding log would.

Implementation walkthrough

The whole algorithm fits in a Redis script with one key and no read-modify-write race, because the comparison and the write happen inside the same atomic evaluation.

-- gcra.lua — GCRA admission control. One key, one integer of state.
-- KEYS[1] = tat key
-- ARGV[1] = emission interval T (ms)
-- ARGV[2] = tolerance tau (ms)
-- ARGV[3] = cost multiplier (1 for a normal request)
-- Returns { allowed, retry_after_ms, reset_after_ms }
local T    = tonumber(ARGV[1])
local tau  = tonumber(ARGV[2])
local cost = tonumber(ARGV[3]) or 1

-- Use the STORE clock so every application node agrees on "now".
local t   = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local tat = tonumber(redis.call('GET', KEYS[1])) or now
local increment = T * cost
local allow_at  = tat - tau

if now < allow_at then
  -- Denied: TAT is NOT advanced, so retries do not push the schedule out.
  return { 0, allow_at - now, tat - now }
end

local new_tat = math.max(now, tat) + increment
redis.call('SET', KEYS[1], new_tat, 'PX', math.ceil(tau + increment))
return { 1, 0, new_tat - now }

The application wrapper turns those three numbers into a decision and the response headers described in rate-limit response headers:

// GCRA limiter wrapper: exact Retry-After, no estimation.
import Redis from "ioredis";

const redis = new Redis(process.env.REDIS_URL!);
const script = redis.defineCommand("gcra", { numberOfKeys: 1, lua: GCRA_LUA });

interface Verdict { allowed: boolean; retryAfterMs: number; resetMs: number; }

export async function gcra(
  key: string,
  { limit, periodMs, burst, cost = 1 }: { limit: number; periodMs: number; burst: number; cost?: number },
): Promise<Verdict> {
  const T = periodMs / limit;          // emission interval
  const tau = burst * T;               // tolerance
  const [allowed, retryAfterMs, resetMs] = (await (redis as any).gcra(
    `gcra:${key}`, Math.round(T), Math.round(tau), cost,
  )) as [number, number, number];
  return { allowed: allowed === 1, retryAfterMs, resetMs };
}

export function applyHeaders(res, v: Verdict, limit: number) {
  // Remaining is derived: how many whole intervals of slack are left.
  res.set("X-RateLimit-Limit", String(limit));
  res.set("X-RateLimit-Reset", String(Math.ceil(v.resetMs / 1000)));
  if (!v.allowed) {
    // Exact, not rounded off a token count — the headline GCRA benefit.
    res.set("Retry-After", String(Math.max(1, Math.ceil(v.retryAfterMs / 1000))));
    res.status(429).json({ error: "rate_limited", retry_after_ms: v.retryAfterMs });
  }
}

Deriving X-RateLimit-Remaining needs one extra step, because GCRA does not store a count. The equivalent quantity is floor((τ − (TAT − now)) / T) clamped to [0, burst] — the number of further requests that would still be inside tolerance. Compute it in the same script if you need the header; do not issue a second call to estimate it, or the header and the decision disagree the moment traffic is concurrent.

Distributed considerations

GCRA inherits the same distributed properties as any single-key algorithm: correctness depends on every node evaluating against the same clock and the same key. Because the state is a timestamp, clock choice matters more than it does for a counter. Two nodes whose local clocks differ by 400 ms will write TATs that differ by 400 ms, and the effective limit wobbles by that amount. Reading TIME inside the script, as above, sidesteps the problem entirely: the store becomes the single clock, which is the same mitigation the distributed algorithm sync guide recommends for window boundaries.

Under Redis Cluster, keep the whole decision on one node by hashing the key so all traffic for one identity lands on one slot — gcra:{acct_42}:search with the account in a hash tag. Cross-slot scripts are rejected, and a limiter split across slots is not a limiter.

Replication is the residual risk. A primary failover loses any TAT writes that had not replicated, which resets an identity’s schedule to “idle.” The blast radius is one burst per key, bounded by burst, which is usually acceptable — far smaller than the equivalent loss in a sliding log. If it is not acceptable for a billing-critical path, pair the limiter with the durable counter pattern described in billing-critical sliding log usage.

Failure modes and mitigations

• Advancing TAT on denial. Implementations that write the new TAT before checking admission turn every rejected retry into a longer wait, so a client with an aggressive retry loop locks itself out indefinitely. Return early on denial, as the script above does.
• Local clocks in a multi-node fleet. Passing Date.now() from the application into the script reintroduces skew. Read TIME inside Redis.
• Second-resolution timestamps. Storing TAT in whole seconds quantises T to one second, which silently caps your maximum rate at one request per second per key. Use milliseconds, and integers.
• Burst set to zero. τ = 0 means strictly paced traffic: two requests in the same millisecond always reject the second, and browsers open six connections at once. Give every public limit a burst of at least a few emission intervals.
• TTL shorter than the tolerance. An expiry below τ + T resets the schedule during quiet periods, making load tests non-reproducible and letting a periodic client exceed the advertised rate.
• Cross-slot keys in a cluster. A key without a hash tag can land anywhere; two keys for the same identity means two limiters. Hash-tag the identity.

Worked example: sizing GCRA for a public API

Suppose you publish “1,000 requests per hour” for a free tier. Naively that is T = 3,600,000 / 1,000 = 3,600 ms — one request every 3.6 seconds — which is unusable for a browser dashboard that fires eight requests when a page loads. The advertised number is a budget, and the burst tolerance is what makes the budget spendable in a realistic pattern.

Set burst = 60. Then τ = 60 × 3,600 ms = 216,000 ms, or 3.6 minutes of schedule slack. A client arriving idle can fire 60 requests immediately, then settles into one every 3.6 seconds. A dashboard that loads eight resources per page view can render 7 pages back to back before pacing kicks in, and a client that idles for an hour regains the full 60-request cushion. Compare that with a fixed window, where the same budget lets a client spend all 1,000 in the first second of each hour and then wait 59 minutes — a pattern that is worse for both parties.

The tuning question is always “what does one unit of user intent cost?” Measure it: if a single page view costs eight requests and your users open at most five pages in quick succession, burst = 40 covers the real pattern with headroom. Setting burst from a round number rather than a measured interaction pattern is how limits end up simultaneously too tight for legitimate users and too loose for scripts.

Comparing with library implementations

Several widely used limiters implement GCRA or something near it, and the differences are worth knowing before you write your own. rate-limiter-flexible’s RateLimiterRedis in its burst-friendly configuration behaves like a token bucket with a stored count; its RLWrapperBlackAndWhite and queue helpers add pacing on top. Redis’s redis-cell module (CL.THROTTLE) is a direct GCRA implementation in Rust, returning [limited, limit, remaining, retry_after, reset_after] — exactly the fields the script above computes — and it is the least error-prone option when you are allowed to load a module. Go’s golang.org/x/time/rate is a token bucket with a reservation API that gives you the same exact-delay property from the other direction: Reserve() returns how long to wait rather than rejecting.

If you adopt a library, verify two behaviours before trusting it in production: that denials do not advance the schedule, and that the clock source is the shared store rather than the calling process. Both are two-line tests, and both are the difference between a limiter that degrades gracefully under a retry storm and one that amplifies it.

When to prefer GCRA

• You need an exact Retry-After and a smooth queue-free pacing story → GCRA, whose denial answer is a duration by construction.
• You need fractional or weighted costs with a large capacity and infrequent bursts → token bucket, whose token count expresses partial credit more naturally.
• You need exact request counts for billing → neither; use a durable counter or a sliding log alongside the limiter.
• You need the smallest possible state per key across tens of millions of keys → GCRA, at one integer per key.
• You are integrating with a library that already implements one → use theirs, and verify its denial semantics against the retry-loop test above.

Operating a GCRA limiter

Day-to-day operation differs from a counter-based limiter in three ways worth knowing before you are debugging one at midnight.

Inspecting state is trivial and useful. GET gcra:acct_42 returns a single millisecond timestamp. Subtract now and you know instantly whether the key is ahead of schedule (positive) or idle (at or below now). Subtract τ as well and you have the exact moment the next request will be admitted. A one-line debug endpoint that returns those three numbers removes most of the guesswork from support tickets, because you can answer “when will this customer be unblocked?” with a timestamp rather than an estimate.

Changing the limit takes effect immediately, and asymmetrically. Raising the rate shortens T, so stored TATs that were computed with the old, larger T sit further in the future than the new schedule implies — clients experience a brief period of stricter-than-configured pacing that resolves within τ. Lowering the rate has the opposite effect: existing TATs are closer than the new schedule wants, so a client gets a small windfall. Neither needs intervention, but both are worth knowing before somebody concludes the deploy broke the limiter.

Metrics come from the returned durations, not from a count. Record retry_after_ms as a histogram rather than counting denials alone: a limiter denying 2% of requests with a median wait of 40 ms is healthy pacing, while the same 2% with a median wait of 25 seconds means clients are far over budget and your support queue is about to fill. The same distinction is invisible in a plain rejection counter, which is why the metrics instrumentation guide recommends histograms for exactly this signal.

Capacity planning is simpler than for counter algorithms: one key per active identity, one integer of state, plus key overhead — roughly 90 bytes per key in Redis including the key name. Ten million active identities cost under a gigabyte, and idle keys evict themselves via the TTL. Compare that with a sliding log at the same cardinality, where per-key memory scales with request volume and the same fleet can need two orders of magnitude more RAM.

In this section

• GCRA vs Token Bucket Precision — where the two disagree and which numbers each rounds.
• Implementing GCRA in Redis Lua — the production script, headers, and tests.
• Burst Tolerance Tuning with GCRA — choosing τ from real client behaviour.

Related

• Core Rate Limiting Algorithms & Theory — the parent reference and the algorithm comparison table.
• Token Bucket Implementation — the closest relative, and the usual alternative.
• Leaky Bucket Mechanics — the queue-based cousin GCRA replaces without a queue.
• Distributed Algorithm Sync — clock and replication concerns for timestamp state.
• Algorithm Tradeoff Analysis — how GCRA scores on memory, precision, and burst tolerance.