Rate Limiting

// Two counters per key instead of a timestamp per request. Cloudflare's
// approximation: assume the previous window's traffic was evenly spread, and
// count the fraction of it that overlaps the sliding window ending now.
async function slidingWindow(redis, key, { limit, periodMs }) {
  const now = Date.now();
  const windowStart = Math.floor(now / periodMs) * periodMs;
  const elapsed = now - windowStart;

  const curKey = `sw:${key}:${windowStart}`;
  const prevKey = `sw:${key}:${windowStart - periodMs}`;

  const [current, previous] = (await redis.mget(curKey, prevKey)).map((v) => Number(v) || 0);

  // rate = prev * ((period - elapsed) / period) + current
  const rate = previous * ((periodMs - elapsed) / periodMs) + current;
  if (rate >= limit) {
    return { allowed: false, rate, retryAfter: Math.ceil((periodMs - elapsed) / 1000) };
  }

  // Keep the counter for two periods: the next window needs to read it.
  await redis.multi().incr(curKey).pexpire(curKey, periodMs * 2).exec();
  return { allowed: true, rate: rate + 1 };
}

// The worked example from Cloudflare's write-up: limit 50/minute, 42 requests
// in the previous minute, 18 in the first 15 seconds of this one.
//   42 * ((60 - 15) / 60) + 18  =  42 * 0.75 + 18  =  49.5   -> still allowed
// A fixed window would have seen 18 and allowed 32 more; a sliding log would
// have been exact but stored 60 timestamps instead of two integers.

// The decision nobody writes down until the limiter causes the outage:
// does an unreachable counter mean allow or deny?
function rateLimit({ rate, capacity, failOpen }) {
  return async (req, res, next) => {
    // Key on the authenticated principal, then the IP. Keying only on IP puts
    // a whole office NAT or mobile carrier behind one bucket.
    const key = req.apiKeyId ? `key:${req.apiKeyId}` : `ip:${req.ip}`;

    let decision;
    try {
      decision = await consume(redis, key, { rate, capacity, cost: costOf(req) });
    } catch (err) {
      limiterErrors.inc();
      // Fail open for a limiter whose job is fairness between tenants: a
      // Redis blip should not be a total outage. Fail CLOSED when the limiter
      // is the only thing protecting a resource that cannot survive the load.
      if (failOpen) return next();
      return res.set('Retry-After', '1').status(503).json({ error: 'limiter unavailable' });
    }

    // X-RateLimit-* is convention, not standard. The IETF RateLimit fields
    // are still a draft; send these because that is what clients parse.
    res.set('X-RateLimit-Limit', String(capacity));
    res.set('X-RateLimit-Remaining', String(Math.max(0, decision.remaining)));

    if (!decision.allowed) {
      res.set('Retry-After', String(Math.max(1, decision.retryAfter)));
      // 429 means "you are over YOUR limit"; 503 means "the server is over
      // capacity". Clients and SDKs back off differently on each.
      return res.status(429).json({ error: 'rate_limit_exceeded' });
    }
    next();
  };
}

// Weight by cost, not by request count: one report export is not one GET.
const costOf = (req) =>
  req.path.startsWith('/exports') ? 25 : req.method === 'GET' ? 1 : 3;

app.use('/v1', rateLimit({ rate: 10, capacity: 50, failOpen: true }));

// Shared Redis is correct but adds a round trip to every request. The usual
// production shape is a two-layer limiter: a local bucket that absorbs the
// common case, and the shared one as the authority.
class TieredLimiter {
  constructor(redis, { rate, capacity, instances }) {
    this.redis = redis;
    this.rate = rate;
    this.capacity = capacity;
    this.instances = Math.max(1, instances);
    // Each instance may spend its own share WITHOUT asking Redis. Traffic is
    // never perfectly even, so this leaks some of the limit by design.
    this.localShare = Math.max(1, Math.floor(capacity / this.instances));
    this.local = { tokens: this.localShare, ts: Date.now() };
  }

  refillLocal() {
    const now = Date.now();
    // Refill at this instance's SHARE of the rate. Refilling at the whole
    // global rate would let every instance sustain the full limit on its own,
    // so 20 pods would allow 20x the limit without ever asking Redis.
    const gained = ((now - this.local.ts) / 1000) * (this.rate / this.instances);
    this.local.tokens = Math.min(this.localShare, this.local.tokens + gained);
    this.local.ts = now;
  }

  async allow(key, cost = 1) {
    this.refillLocal();
    // Fast path: spend locally, no network. Correct only up to localShare.
    if (this.local.tokens >= cost) {
      this.local.tokens -= cost;
      return { allowed: true, authority: 'local' };
    }
    // Slow path: this caller is pushing hard enough to matter, so pay the
    // round trip and get the real answer.
    const decision = await consume(this.redis, key, {
      rate: this.rate, capacity: this.capacity, cost,
    });
    return { ...decision, authority: 'shared' };
  }
}

// Instance count comes from service discovery, not a constant: after a scale
// out to 20 pods, a hardcoded 10 doubles the effective limit silently.
const limiter = new TieredLimiter(redis, {
  rate: 1000, capacity: 5000, instances: await discovery.replicaCount('api'),
});