Rate Limiting Algorithms

// Read-then-write in two commands has a race. One Lua script does not.
const TOKEN_BUCKET = `
local key       = KEYS[1]
local capacity  = tonumber(ARGV[1])
local refill    = tonumber(ARGV[2])   -- tokens per second
local now       = tonumber(ARGV[3])   -- caller-supplied, ms
local cost      = tonumber(ARGV[4])

local state   = redis.call('HMGET', key, 'tokens', 'ts')
local tokens  = tonumber(state[1])
local last    = tonumber(state[2])

if tokens == nil then
  tokens = capacity
  last = now
end

-- Refill for the elapsed time, capped at capacity
local elapsed = math.max(0, now - last) / 1000
tokens = math.min(capacity, tokens + elapsed * refill)

local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end

redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', key, math.ceil((capacity / refill) * 1000 * 2))

-- seconds until enough tokens exist for another request of this cost
local retry = 0
if allowed == 0 then retry = math.ceil((cost - tokens) / refill) end

return { allowed, math.floor(tokens), retry }
`;

const sha = await redis.script('LOAD', TOKEN_BUCKET);

export async function consume(key, { capacity, refillPerSecond, cost = 1 }) {
  const [allowed, remaining, retryAfter] = await redis.evalsha(
    sha, 1, key, capacity, refillPerSecond, Date.now(), cost);
  return { allowed: allowed === 1, remaining, retryAfter };
}

// Cost-weight by how expensive the endpoint actually is.
const COST = {
  'GET /api/health': 0,
  'GET /api/invoices': 1,
  'POST /api/invoices': 2,
  'POST /api/reports': 25,        // a report is not one request's worth of work
  'POST /api/exports': 50,
};

export function rateLimit({ capacity = 100, refillPerSecond = 2 } = {}) {
  return async (req, res, next) => {
    const key = `rl:${req.user?.id ?? req.ip}`;
    const cost = COST[`${req.method} ${req.route?.path ?? req.path}`] ?? 1;
    if (cost === 0) return next();

    const { allowed, remaining, retryAfter } =
      await consume(key, { capacity, refillPerSecond, cost })
        .catch(() => ({ allowed: null }));

    // Store unavailable → degrade to a local limiter, never to "allow all".
    if (allowed === null) {
      metrics.increment('ratelimit.store_error');
      return localFallback.allow(key) ? next()
        : res.status(429).json({ error: 'rate_limited' });
    }

    res.set('RateLimit-Limit', String(capacity));
    res.set('RateLimit-Remaining', String(Math.max(0, remaining)));
    res.set('RateLimit-Policy', `${capacity};w=${capacity / refillPerSecond}`);

    if (!allowed) {
      res.set('Retry-After', String(retryAfter));
      return res.status(429).json({ error: 'rate_limited', retryAfter });
    }
    next();
  };
}

// ── 1. Fixed window: one counter, boundary burst ─────────────────────
async function fixedWindow(key, limit, windowS) {
  const bucket = `${key}:${Math.floor(Date.now() / 1000 / windowS)}`;
  const count = await redis.incr(bucket);
  if (count === 1) await redis.expire(bucket, windowS);
  return count <= limit;
}
// ✅ one command  ❌ up to 2x the limit across a boundary

// ── 2. Sliding window log: exact, memory-hungry ──────────────────────
async function slidingLog(key, limit, windowMs) {
  const now = Date.now();
  const [, , count] = await redis.multi()
    .zremrangebyscore(key, 0, now - windowMs)      // drop what fell out
    .zadd(key, now, `${now}-${Math.random()}`)
    .zcard(key)
    .pexpire(key, windowMs)
    .exec();
  return count[1] <= limit;
}
// ✅ exact  ❌ one member per request — costly at high limits

// ── 3. Sliding window counter: the usual production choice ───────────
async function slidingCounter(key, limit, windowS) {
  const now = Date.now() / 1000;
  const current = Math.floor(now / windowS);
  const elapsed = (now % windowS) / windowS;        // 0..1 through this window

  const [prev, curr] = await redis.mget(`${key}:${current - 1}`, `${key}:${current}`);
  // Weight the previous window by how much of it still overlaps.
  const estimate = (Number(prev) || 0) * (1 - elapsed) + (Number(curr) || 0);

  if (estimate >= limit) return false;

  await redis.multi()
    .incr(`${key}:${current}`)
    .expire(`${key}:${current}`, windowS * 2)
    .exec();
  return true;
}
// ✅ two keys, cheap  ⚠️ approximate (typically within a few percent)

// ── 4. Leaky bucket: smooths completely ──────────────────────────────
// Requests queue and drain at a fixed rate. Use when the DOWNSTREAM system
// cannot absorb bursts at all — a legacy database, a paid third-party API.
// Implemented as a token bucket with capacity == 1 refill interval, or as a
// real queue with a fixed-rate worker.

// ── Choosing ─────────────────────────────────────────────────────────
//   general API traffic        → token bucket (bursts are normal)
//   strict contractual rate    → sliding window counter
//   protecting a fragile dep   → leaky bucket / queue
//   internal, low stakes       → fixed window

// A single key is always wrong for something. Layer them.
export function layeredRateLimit(req) {
  const layers = [];

  // 1. Per authenticated principal — the most meaningful identity
  if (req.user) {
    layers.push({ key: `u:${req.user.id}`, capacity: 300, refill: 5 });
  }

  // 2. Per tenant — one customer must not starve another
  if (req.user?.tenant) {
    layers.push({ key: `t:${req.user.tenant}`, capacity: 3000, refill: 50 });
  }

  // 3. Per IP — catches unauthenticated traffic and one noisy machine
  layers.push({ key: `ip:${req.ip}`, capacity: 100, refill: 2 });

  // 4. Per API key, if that is the credential
  if (req.client?.apiKeyId) {
    layers.push({ key: `k:${req.client.apiKeyId}`, capacity: 1000, refill: 20 });
  }

  // 5. Global, per endpoint — a circuit breaker for a broad campaign
  layers.push({ key: `ep:${req.method}:${req.route?.path}`,
                capacity: 10_000, refill: 200 });

  return layers;
}

export function rateLimitAll() {
  return async (req, res, next) => {
    for (const layer of layeredRateLimit(req)) {
      const { allowed, retryAfter } = await consume(`rl:${layer.key}`, {
        capacity: layer.capacity, refillPerSecond: layer.refill,
      });
      if (!allowed) {
        // Log WHICH layer fired — otherwise 429s are undiagnosable.
        logger.info({ layer: layer.key, path: req.path }, 'rate limited');
        res.set('Retry-After', String(retryAfter));
        return res.status(429).json({ error: 'rate_limited', retryAfter });
      }
    }
    next();
  };
}

// ⚠️ Getting the IP right is a prerequisite. Behind a proxy without
//    `trust proxy` configured, req.ip is the load balancer, every request
//    shares one bucket, and the limiter either blocks everyone or nobody.
app.set('trust proxy', 1);

// ⚠️ And never `trust proxy: true` on a public app — the client then prepends
//    its own X-Forwarded-For and gets a fresh bucket per request.