Loom Rate Limiting

Rate Limiting

Overview

Control the request rate a client can make: protect from abuse, enforce fair usage, shed load. Two decisions dominate correctness: which algorithm (burst tolerance vs accuracy vs memory) and how to make the counter atomic in a distributed setting. Everything else is headers and policy.

Algorithm Selection

⚠ Fixed-window boundary burst is the classic footgun: with limit=100/min, a client can send 100 at 00:59.9 and 100 at 01:00.1 — 200 requests in ~0.2s while never violating either window. If bursts matter, use sliding-window or token-bucket.

⚠ Token bucket ≈ leaky bucket (as a meter) ≈ GCRA — mathematically equivalent rate meters differing in burst allowance and storage. Don't reimplement all three; pick token bucket for app code, GCRA for a single-value distributed limiter.

Token Bucket

Allows bursts up to capacity, refills at refillRate tokens/sec. Refill is computed lazily on access (no background timer needed).

class TokenBucket {
  private tokens: number;
  private lastRefill = Date.now();
  constructor(private capacity: number, private refillRate: number) {
    this.tokens = capacity;
  }
  consume(n = 1): boolean {
    const now = Date.now();
    this.tokens = Math.min(this.capacity, this.tokens + ((now - this.lastRefill) / 1000) * this.refillRate);
    this.lastRefill = now;
    if (this.tokens >= n) { this.tokens -= n; return true; }
    return false;
  }
}
// 100 req/min sustained, burst of 10:
const bucket = new TokenBucket(10, 100 / 60);

• capacity = max burst; refillRate = sustained rate. These are independent knobs — that's the point.
• In-process instance is per-node only. For multi-node, store {tokens, lastRefill} in Redis and refill inside a Lua script (below).

Sliding Window Log vs Counter

Log keeps every timestamp in the window — exact, but memory grows with the limit and it's the heaviest to store/GC. Counter keeps the current + previous window counts and interpolates:

// weighted = prevCount * (1 - elapsedIntoCurrentWindow) + currentCount
const weighted = prev * (1 - progress) + curr;
if (weighted < limit) { curr++; /* allow */ }

The counter is the pragmatic distributed default: 2 integers/key, no boundary burst, ~99% accurate. Use the log only when the limit is small and exactness is required (auth attempts, payment retries).

Leaky Bucket

Queue requests, drain at a fixed rate; reject when the queue is full. Use to shape traffic into a fragile downstream, not to meter clients. Downside: adds latency (requests wait in queue) and needs a real queue/worker — don't reach for it unless constant output rate is the actual requirement.

Distributed Rate Limiting (the hard part)

The naive distributed limiter is broken by a race:

const count = await redis.incr(key);   // node A and B both read/return 1... 100
if (count === 1) await redis.expire(key, 60);  // ⚠ two problems below

⚠ Two real bugs in the INCR-then-EXPIRE pattern:

1. Lost TTL — if the process crashes (or the connection drops) between INCR and EXPIRE, the key is created with no expiry and the client is rate-limited forever. Always set expiry atomically.
2. TTL reset / sliding drift — calling EXPIRE on every request (not just count===1) turns a fixed window into an accidental sliding one and can let counts never expire under sustained load.

Fix: do it in one atomic Lua script. Redis executes scripts atomically, eliminating the read-modify-write race across nodes.

// Sliding-window-log limiter, atomic. Returns [allowed, remaining, resetAtMs].
const LUA = `
  local key = KEYS[1]
  local now, window_start, limit, window_s = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
  redis.call('ZREMRANGEBYSCORE', key, '-inf', window_start)
  local count = redis.call('ZCARD', key)
  if count < limit then
    redis.call('ZADD', key, now, now .. '-' .. math.random())
    redis.call('EXPIRE', key, window_s)
    return {1, limit - count - 1}
  end
  local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
  local reset = oldest[2] and (oldest[2] + window_s * 1000) or (now + window_s * 1000)
  return {0, 0, reset}
`;
const [allowed, remaining, resetAt] = await redis.eval(
  LUA, 1, `ratelimit:${id}`, Date.now(), Date.now() - windowS * 1000, limit, windowS,
);

⚠ Sorted-set log gotcha: now .. '-' .. math.random() is the member; two requests in the same millisecond need distinct members or one silently overwrites the other. Prefer a monotonic counter or a request UUID over math.random() for high concurrency.

GCRA (Generic Cell Rate Algorithm) is the storage-cheapest exact limiter: store a single theoretical arrival time (TAT) per key, updated atomically. This is what redis-cell (the CL.THROTTLE module command) and many library limiters implement — reach for it at high key cardinality where storing timestamp sets is too expensive.

Redis Cluster

Multi-key operations (including a Lua script touching >1 key) must resolve to one slot. Use hash tags — the substring in {...} is what's hashed:

const key = `{ratelimit:${userId}}:counter`; // all keys for this user → same slot

Without the tag, EVAL across a user's minute+hour keys throws CROSSSLOT.

Fail-open vs Fail-closed

When the limiter backend (Redis) is down, you must choose:

• Fail-open (allow) — availability over protection. Correct for most public APIs: a limiter outage shouldn't take down the whole API. Risk: no protection during the outage.
• Fail-closed (deny) — protection over availability. Correct for abuse-critical or cost-critical paths (login, payment, expensive LLM calls) where an unmetered flood is worse than downtime.

Decide per endpoint, log every fallback, and add a local in-process fallback limiter so fail-open still has some ceiling. console.error the Redis failure — a silent catch that always next()s is an unmonitored open door.

Quotas (multi-window)

Tiered plans typically enforce several windows at once (per-minute burst + per-day quota). Check the coarsest/cheapest first isn't right — check the one most likely to reject first, but always increment all atomically to avoid partial counting:

// Per-tier: enforce minute AND day. Increment both, then evaluate.
const p = redis.pipeline();
p.incr(minKey); p.expire(minKey, 60);
p.incr(dayKey); p.expire(dayKey, 86400);
const [[, min], , [, day]] = await p.exec();
if (min > tier.perMinute || day > tier.perDay) return { allowed: false };

⚠ Pipeline is not atomic (commands can interleave with other clients). For strict multi-window correctness use one Lua script; a pipeline is usually fine for quotas where small over-count is acceptable.

Per-key layering (IP + user)

Check IP limits first (DDoS / pre-auth abuse), then user/anonymous limits. An unauthenticated flood should die at the IP gate before touching per-user logic. Key hierarchy: ip → api-key → user → global. Apply the most restrictive that matches.

The 429 Contract

Return 429 Too Many Requests with headers so clients can self-throttle. There are two header families — emit both during the migration period:

res.setHeader("RateLimit-Limit", limit);          // draft IETF (draft-ietf-httpapi-ratelimit-headers)
res.setHeader("RateLimit-Remaining", remaining);
res.setHeader("RateLimit-Reset", secondsUntilReset); // delta-seconds in the draft
res.setHeader("X-RateLimit-Limit", limit);        // de-facto legacy (many clients still read these)
res.setHeader("X-RateLimit-Remaining", remaining);
res.setHeader("X-RateLimit-Reset", unixTimestamp); // legacy uses absolute unix ts
res.setHeader("Retry-After", secondsUntilReset);  // ⚠ REQUIRED on 429; seconds or HTTP-date

⚠ Reset ambiguity: the IETF draft uses delta-seconds; the legacy X-RateLimit-Reset convention often uses an absolute Unix timestamp. Clients get this wrong constantly — document which you emit and be consistent. Retry-After is the unambiguous, standardized one; always send it on a 429.

⚠ Set rate-limit headers on successful responses too (so clients see Remaining drop and back off before hitting 429), not only on the 429.

Express middleware shape

function rateLimiter(opts: { windowMs: number; max: number; keyGen?: (r) => string; skip?: (r) => boolean }) {
  return async (req, res, next) => {
    if (opts.skip?.(req)) return next();
    const key = opts.keyGen?.(req) ?? req.ip;
    let r;
    try { r = await limiter.isAllowed(key, opts.max, opts.windowMs / 1000); }
    catch (e) { console.error("ratelimit backend down", e); return next(); } // fail-open, logged
    res.setHeader("RateLimit-Limit", opts.max);
    res.setHeader("RateLimit-Remaining", r.remaining);
    res.setHeader("RateLimit-Reset", Math.ceil((r.resetAt - Date.now()) / 1000));
    if (!r.allowed) {
      res.setHeader("Retry-After", Math.ceil((r.resetAt - Date.now()) / 1000));
      return res.status(429).json({ error: "RATE_LIMIT_EXCEEDED", retryAfter: ... });
    }
    next();
  };
}

⚠ req.ip behind a proxy/LB is the proxy's IP unless you set app.set('trust proxy', ...) correctly. Get this wrong and you either rate-limit the whole world as one IP, or trust a spoofable X-Forwarded-For. Trust only your own proxy hops.

Client-Side Handling

• On 429, honor Retry-After exactly; do not immediately retry (that's the abuse the server is defending against).
• For non-429 errors use exponential backoff with jitter (base * 2^n * random()) — synchronized retries from many clients recreate the thundering herd.
• Track RateLimit-Remaining and pre-emptively slow down before hitting 0.

Gateway/Infra Options

Prefer offloading to the edge when a gateway already fronts your services:

• Nginx — limit_req_zone + limit_req ... burst=N nodelay. burst without nodelay queues (leaky-bucket-like, adds latency); with nodelay allows the burst immediately then enforces rate. Per-node only unless fronted by shared state.
• Kong — rate-limiting plugin, policy: redis for cluster-wide counting; fault_tolerant: true = fail-open.
• Envoy — global RLS via external gRPC ratelimit service; failure_mode_deny: false = fail-open.
• AWS API Gateway — account/stage throttlingRateLimit+throttlingBurstLimit (token bucket) and per-key usage plans with quota (month/week/day). Note the account-level default (10k rps) can throttle before your per-method limits.

Edge limiting stops abuse before it costs you app compute; app-level limiting gives per-user/business-logic granularity. Real systems use both.

Advanced Patterns

• Adaptive limiting — adjust the limit from observed success rate (AIMD: multiplicatively decrease on errors, additively/slowly increase when healthy). Backpressure that reacts to actual downstream health.
• Priority shedding — under high load, reject low-priority classes first (batch/background) while protecting critical (health, auth). Combine with a per-class token bucket.
• Circuit breaker — orthogonal to rate limiting: opens on downstream failures (not client rate) to stop hammering a broken dependency. Compose them; don't conflate them.

Gotchas Checklist

• Limiter is atomic (Lua/GCRA), not read-then-write across nodes — no lost-TTL, no cross-node race
• Chosen algorithm matches burst policy (fixed-window boundary burst understood/accepted)
• Fail-open vs fail-closed decided per endpoint, backend failures logged, not silently swallowed
• Retry-After sent on every 429; RateLimit-* sent on success responses too
• Reset semantics (delta-seconds vs absolute) documented and consistent
• trust proxy configured; client IP is the real client, not the LB, and X-Forwarded-For isn't blindly trusted
• Redis keys have TTLs; Cluster deployments use hash tags for multi-key/Lua ops
• Client retries use Retry-After + jittered backoff, not tight-loop retry
• Multi-window quotas incremented together (Lua) or accept small over-count (pipeline)
• Limits load-tested at the window boundary and at Redis-down (both failure modes exercised)