GCRA vs Token Bucket Precision

Both algorithms admit the same traffic in the steady state, so the choice comes down to three practical differences: how exactly each can answer “when may I retry?”, how each accumulates error over millions of operations, and how much state each keeps per key. This comparison builds on the mechanics in the GCRA and virtual scheduling guide and the token bucket implementation page.

The problem in concrete numbers

Publish 600 requests per hour — one every 6 seconds. A client exhausts its allowance and asks how long to wait.

A token bucket stores tokens = 0.37 and a refill rate of 0.1667 tokens per second. The wait is (1 − 0.37) / 0.1667 = 3.78 s, rounded up to 4. That figure is only as accurate as the stored float, which has been through thousands of read-multiply-write cycles, each rounding at the seventeenth significant digit and each also rounding the elapsed milliseconds.

GCRA stores TAT = 1751899203780 — a millisecond timestamp. The wait is (TAT − τ) − now, an integer subtraction with no accumulated error at all. Over a year of continuous traffic the token bucket’s drift is small but real; GCRA’s is exactly zero because time, not a counter, is the state.

Decision matrix

The honest summary: GCRA wins on answer quality and state size; token bucket wins on familiarity and on fractional costs. For a public API where Retry-After correctness matters and keys number in the millions, GCRA is the better default. For an internal service with weighted operations and a team that already understands buckets, the difference is not worth a rewrite.

Where the two actually diverge

Run 100,000 requests at a limit of 10 per second through both implementations and the admitted counts match to within one. The divergence shows up in three places.

The reported wait. A token bucket’s Retry-After is computed from tokens, which is a float that has absorbed rounding from every previous refill. In practice the error is well under a second — but it is systematically biased, because implementations clamp with max(1, ceil(...)) and the ceiling always rounds against the client.

Fractional costs. Charging 0.25 units is trivial with tokens and clumsy with a schedule: you shift the theoretical arrival time by 0.25 × T, which works but produces a schedule where “one request” is no longer the unit of reasoning.

Remaining, as a header. Clients read X-RateLimit-Remaining and pace themselves against it. A token bucket has the number already; GCRA must derive it from the schedule gap. Compute it inside the same atomic script — deriving it from a second read produces a value that disagrees with the decision that was just made.

Step-by-step: choosing between them

• Write down whether your API publishes a Retry-After clients are expected to obey. If yes, weight the decision toward GCRA.
• Count the active keys. Above roughly one million, the single-field state is worth real money.
• Check whether any operation has a fractional or highly variable cost. If most do, prefer the token bucket.
• Test the denial path of whichever you pick: a retry loop must never extend its own wait.
• If you need X-RateLimit-Remaining, verify it comes from the same atomic call as the decision.
• Benchmark both against your store — the difference is usually noise next to the round trip.
• Do not migrate a working limiter for the arithmetic alone; migrate when the wrong retry advice is causing real client harm.

-- Same limit, both algorithms, so you can A/B them behind one interface.
-- Token bucket: two fields, float refill.
local function token_bucket(key, cap, rate, now, cost)
  local st = redis.call('HMGET', key, 'tokens', 'ts')
  local tokens = tonumber(st[1]) or cap
  local ts     = tonumber(st[2]) or now
  tokens = math.min(cap, tokens + (now - ts) / 1000 * rate)
  local allowed = tokens >= cost
  if allowed then tokens = tokens - cost end
  redis.call('HSET', key, 'tokens', tokens, 'ts', now)
  redis.call('PEXPIRE', key, math.ceil(cap / rate * 1000) + 1000)
  -- Retry estimate carries the float's rounding with it.
  local retry = allowed and 0 or math.ceil((cost - tokens) / rate * 1000)
  return { allowed and 1 or 0, math.floor(tokens), retry }
end

-- GCRA: one field, integer schedule.
local function gcra(key, T, tau, now, cost)
  local tat = tonumber(redis.call('GET', key)) or now
  local allow_at = tat - tau
  if now < allow_at then
    return { 0, 0, allow_at - now }             -- exact wait, TAT untouched
  end
  local new_tat = math.max(now, tat) + T * cost
  redis.call('SET', key, new_tat, 'PX', math.ceil(tau + T * cost))
  local remaining = math.floor((tau - (new_tat - now)) / T)
  return { 1, math.max(0, remaining), 0 }
end

Gotchas and edge cases

• Comparing admitted counts proves nothing. Both algorithms admit the same traffic; a benchmark that only counts accepts will show them as identical and hide the difference that matters.
• A token bucket with second-resolution timestamps is much worse than GCRA. Storing ts in whole seconds quantises the refill and can double the effective error. If you keep buckets, keep milliseconds.
• GCRA with a zero tolerance is not a token bucket with capacity 1. With τ = 0, two requests in the same millisecond always reject the second; a capacity-1 bucket behaves the same way, but teams often set τ = 0 by accident when they mean “no burst above the rate”.
• Deriving remaining from a second call. Whichever algorithm you pick, one atomic call must return decision, remaining, and wait together.
• Float comparison at the boundary. tokens >= cost with tokens = 0.9999999999 rejects a request that should pass. Compare with a small epsilon, or use GCRA and avoid the class of bug.
• Migrating live keys. The two state formats are not interchangeable; a rollout must either dual-write, or accept that every key starts fresh — which grants everyone one burst at cutover.

Verification and testing

# Run both algorithms over the same arrival trace and compare their answers.
import math, random

LIMIT, PERIOD_MS, BURST = 10, 1000, 10
T, TAU = PERIOD_MS / LIMIT, BURST * (PERIOD_MS / LIMIT)

def trace(n=100_000, seed=7):
    random.seed(seed); t = 0
    for _ in range(n):
        t += random.choice([5, 20, 100, 400])     # bursty, then idle
        yield t

tokens, ts, tat = float(LIMIT), 0, 0
tb_admitted = gcra_admitted = 0
tb_wait_err = 0.0

for now in trace():
    # token bucket
    tokens = min(LIMIT, tokens + (now - ts) / 1000 * (LIMIT / (PERIOD_MS / 1000)))
    ts = now
    if tokens >= 1:
        tokens -= 1; tb_admitted += 1
    else:
        advertised = math.ceil((1 - tokens) / (LIMIT / (PERIOD_MS / 1000)) * 1000)
        true_wait = (1 - tokens) / (LIMIT / (PERIOD_MS / 1000)) * 1000
        tb_wait_err += advertised - true_wait     # always >= 0: rounds against the client
    # gcra
    if now >= tat - TAU:
        tat = max(now, tat) + T; gcra_admitted += 1

print(tb_admitted, gcra_admitted)                 # within 1 of each other
print(round(tb_wait_err / 1000, 1), "seconds of over-advertised wait")

The two admitted counts land within one of each other; the accumulated over-advertised wait is the number worth looking at, because it is time your clients spent not sending requests they were entitled to send.

Frequently Asked Questions

Related

• GCRA & Virtual Scheduling — the parent guide with the full algorithm.
• Implementing GCRA in Redis Lua — the production script and its tests.
• Token Bucket Implementation — the algorithm on the other side of this comparison.
• Algorithm Tradeoff Analysis — the wider comparison across all five families.