GCRA: The Generic Cell Rate Algorithm

GCRA (from ATM networks) implements token-bucket behavior with a single timestamp per key: the "theoretical arrival time" (TAT). A request is allowed if now ≥ TAT − burst_tolerance; then TAT = max(TAT, now) + emission_interval. It's precise, needs one value per key, and naturally yields Retry-After. Libraries: redis-cell (CL.THROTTLE), throttled (Go), and many gateway plugins.

Token bucket vs GCRA

Python (GCRA with Redis)

GCRA = '''
local tat = tonumber(redis.call('GET', KEYS[1]) or ARGV[1])
local now, interval, tolerance = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
tat = math.max(tat, now)
if now < tat - tolerance then
  return {0, tat - tolerance - now}          -- denied, retry after (ms)
end
local new_tat = tat + interval
redis.call('SET', KEYS[1], new_tat, 'PX', math.ceil(new_tat - now + tolerance))
return {1, 0}
'''

def gcra_allow(redis, key: str, rate_per_sec: float, burst: int) -> tuple[bool, int]:
    interval = 1000 / rate_per_sec                     # ms between requests
    tolerance = interval * burst
    now = redis.time()                                 # single clock: Redis server time
    now_ms = now[0] * 1000 + now[1] // 1000
    allowed, retry_ms = redis.eval(GCRA, 1, key, now_ms, interval, tolerance)
    return bool(allowed), int(retry_ms)

Common pitfalls

• Mixing clocks from many app servers.
• Forgetting key expiry (memory growth).
• Off-by-one burst semantics (document burst carefully).

Key points

• One timestamp per key
• Token-bucket semantics
• Natural Retry-After

Further reading: Brandur: Rate limiting with GCRA