Implementing GCRA in Redis Lua

-- gcra.lua  — production GCRA. KEYS[1] = the identity's schedule key.
-- ARGV[1] = emission interval T in ms (integer)
-- ARGV[2] = tolerance tau in ms (integer)
-- ARGV[3] = cost multiplier (>= 1)
-- Returns { allowed, remaining, retry_after_ms, reset_after_ms }
local T    = tonumber(ARGV[1])
local tau  = tonumber(ARGV[2])
local cost = tonumber(ARGV[3]) or 1

-- (1) One clock for the whole fleet: the store's own.
local t   = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

-- An unseen key behaves as a client that is perfectly on schedule right now.
local tat      = tonumber(redis.call('GET', KEYS[1])) or now
local increase = T * cost
local allow_at = tat - tau

-- (2) Denial returns FIRST: the schedule is never advanced by a rejected request,
--     so a client retrying in a tight loop cannot push its own recovery away.
if now < allow_at then
  local remaining = math.floor((tau - (tat - now)) / T)
  return { 0, math.max(0, remaining), allow_at - now, tat - now }
end

local new_tat = math.max(now, tat) + increase
-- (3) TTL covers the whole tolerance window, so an idle key expires only once the
--     client would have regained its full burst anyway.
redis.call('SET', KEYS[1], new_tat, 'PX', tau + increase)

-- (4) Remaining is derived from the same state that produced the verdict.
local remaining = math.floor((tau - (new_tat - now)) / T)
return { 1, math.max(0, remaining), 0, new_tat - now }

// gcra.ts — load once, call by SHA, degrade explicitly.
import Redis from "ioredis";
import { readFileSync } from "node:fs";

const redis = new Redis(process.env.REDIS_URL!, { commandTimeout: 50 });
const SRC = readFileSync(new URL("./gcra.lua", import.meta.url), "utf8");
let sha: string | null = null;

export interface Limit { limit: number; periodMs: number; burst: number; }
export interface Verdict { allowed: boolean; remaining: number; retryAfterMs: number; resetMs: number; }

async function evalGcra(key: string, args: (string | number)[]): Promise<number[]> {
  if (!sha) sha = await redis.script("LOAD", SRC) as string;
  try {
    return await redis.evalsha(sha, 1, key, ...args) as number[];
  } catch (err: any) {
    if (String(err.message).includes("NOSCRIPT")) {          // failover flushed the cache
      sha = await redis.script("LOAD", SRC) as string;
      return await redis.evalsha(sha, 1, key, ...args) as number[];
    }
    throw err;
  }
}

export async function check(identity: string, route: string, l: Limit, cost = 1): Promise<Verdict> {
  const T = Math.max(1, Math.round(l.periodMs / l.limit));   // integer ms, never zero
  const tau = Math.round(l.burst * T);
  // Hash tag keeps every key for this identity in one cluster slot.
  const key = `gcra:{${identity}}:${route}`;
  try {
    const [allowed, remaining, retryAfterMs, resetMs] = await evalGcra(key, [T, tau, cost]);
    return { allowed: allowed === 1, remaining, retryAfterMs, resetMs };
  } catch {
    // Explicit degradation: read paths fail open, and the caller records the metric.
    return { allowed: true, remaining: 0, retryAfterMs: 0, resetMs: 0 };
  }
}

// gcra.test.js — the four invariants worth pinning.
import { describe, it, expect, beforeEach } from "vitest";
import { check } from "./gcra.js";

const L = { limit: 10, periodMs: 1000, burst: 5 };   // T = 100 ms, tau = 500 ms
let id;
beforeEach(() => { id = `t_${crypto.randomUUID()}`; });

it("admits the burst from idle, then denies", async () => {
  const v = [];
  for (let i = 0; i < 7; i += 1) v.push(await check(id, "r", L));
  expect(v.filter((x) => x.allowed).length).toBe(6);   // burst 5 + the on-schedule one
  expect(v[6].allowed).toBe(false);
});

it("reports a wait that actually works", async () => {
  for (let i = 0; i < 7; i += 1) await check(id, "r", L);
  const denied = await check(id, "r", L);
  await new Promise((r) => setTimeout(r, denied.retryAfterMs + 5));
  expect((await check(id, "r", L)).allowed).toBe(true);
});

it("does not extend the wait when hammered", async () => {
  for (let i = 0; i < 7; i += 1) await check(id, "r", L);
  const first = (await check(id, "r", L)).retryAfterMs;
  for (let i = 0; i < 20; i += 1) await check(id, "r", L);     // tight retry loop
  const later = (await check(id, "r", L)).retryAfterMs;
  expect(later).toBeLessThanOrEqual(first);                    // fails if TAT advanced on deny
});

it("expires the key once the tolerance has passed", async () => {
  await check(id, "r", L);
  const ttl = await redis.pttl(`gcra:{${id}}:r`);
  expect(ttl).toBeGreaterThan(0);
  expect(ttl).toBeLessThanOrEqual(600);                        // tau + T
});