Rate Limiting Algorithms Compared

A policy such as “100 requests per minute” sounds complete until two clients send at a boundary, one request costs 50 times more than another, or the wall clock moves backward. The useful question is not which limiter is universally best. It is which approximation of time and capacity matches the traffic contract.

This comparison keeps the state local and explicit. Distributed ownership, Redis scripts, and cross-region coordination are separate architecture problems. Here the focus is the algorithm itself: what it admits, how much burst it permits, what state it retains, and how to prove those properties with a virtual clock.

Define the contract before choosing an algorithm #

Let L be permitted units in interval W, c the cost of one request, and A(t) the admitted cost in a time range. A strict rolling-window policy requires:

The interval is half-open: an event at exactly t - W has expired. Writing this boundary rule down prevents production and tests from disagreeing by one millisecond. It also exposes why a fixed window is different: it constrains aligned buckets, not every rolling interval.

A limiter should answer more than a boolean:

export type Decision = {
  allowed: boolean;
  remaining: number;
  retryAfterMs: number;
};

function requireCost(cost: number): void {
  if (!Number.isFinite(cost) || cost <= 0) {
    throw new RangeError('cost must be finite and positive');
  }
}

remaining is measured in policy units, not necessarily requests. An inexpensive cache hit might cost 1, an export cost 20, and an LLM operation cost estimated tokens. Costs need not be integers, but fractional accounting should use consistent rounding when exposed in HTTP headers.

Three burst quantities are easy to confuse:

• Boundary burst: extra traffic admitted because accounting resets at an aligned boundary.
• Burst capacity: intentionally saved credit, as in a token bucket.
• Queue burst: work admitted now but delayed by a shaper.

Fairness is also scoped. A FIFO leaky-bucket queue preserves arrival order, but a heavy request can block small ones. Independent per-client buckets isolate clients, but do not make several clients sharing a downstream dependency fair. The algorithm cannot repair a keying policy that groups the wrong actors.

Window algorithms: simple, exact, or approximate #

A fixed window stores one bucket identifier and a used count. It is constant-memory and easy to explain, but a client can spend L just before a boundary and another L just after it. That is up to 2L in an arbitrarily short span.

export class FixedWindow {
  #windowId = Number.NaN;
  #used = 0;
  #lastMs = 0;

  constructor(
    readonly limit: number,
    readonly windowMs: number,
  ) {}

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    nowMs = Math.max(nowMs, this.#lastMs);
    this.#lastMs = nowMs;
    const windowId = Math.floor(nowMs / this.windowMs);
    if (windowId !== this.#windowId) {
      this.#windowId = windowId;
      this.#used = 0;
    }

    if (cost > this.limit) {
      return { allowed: false, remaining: this.limit - this.#used, retryAfterMs: Infinity };
    }
    const allowed = this.#used + cost <= this.limit;
    if (allowed) this.#used += cost;
    return {
      allowed,
      remaining: Math.max(0, this.limit - this.#used),
      retryAfterMs: allowed
        ? 0
        : (windowId + 1) * this.windowMs - nowMs,
    };
  }
}

A sliding log records every admitted event. Pruning at <= nowMs - windowMs implements the half-open interval exactly. For weighted events, the retry time is when enough oldest cost has expired, not merely when the first event expires.

type Event = { at: number; cost: number };

export class SlidingLog {
  readonly #events: Event[] = [];
  #used = 0;
  #lastMs = 0;

  constructor(
    readonly limit: number,
    readonly windowMs: number,
  ) {}

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    nowMs = Math.max(nowMs, this.#lastMs);
    this.#lastMs = nowMs;
    while (this.#events[0]?.at <= nowMs - this.windowMs) {
      this.#used -= this.#events.shift()!.cost;
    }

    if (cost > this.limit) {
      return { allowed: false, remaining: this.limit - this.#used, retryAfterMs: Infinity };
    }
    if (this.#used + cost <= this.limit) {
      this.#events.push({ at: nowMs, cost });
      this.#used += cost;
      return { allowed: true, remaining: this.limit - this.#used, retryAfterMs: 0 };
    }

    const mustExpire = this.#used + cost - this.limit;
    let expired = 0;
    for (const event of this.#events) {
      expired += event.cost;
      if (expired >= mustExpire) {
        return {
          allowed: false,
          remaining: Math.max(0, this.limit - this.#used),
          retryAfterMs: Math.max(0, event.at + this.windowMs - nowMs),
        };
      }
    }
    throw new Error('unreachable');
  }
}

An array with shift() is readable demonstration code; a production log should use a deque or an array plus a head index to avoid repeated compaction. Memory is O(n) in admitted events per key, which is exact but dangerous when L is large.

A sliding counter keeps the current and previous fixed buckets, then weights the previous bucket by the overlap fraction. With e elapsed milliseconds in the current window:

export class SlidingCounter {
  #start = Number.NaN;
  #current = 0;
  #previous = 0;
  #lastMs = 0;

  constructor(
    readonly limit: number,
    readonly windowMs: number,
  ) {}

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    nowMs = Math.max(nowMs, this.#lastMs);
    this.#lastMs = nowMs;
    this.#advance(nowMs);
    const estimated = this.#estimate(nowMs);
    if (cost > this.limit) {
      return { allowed: false, remaining: Math.max(0, this.limit - estimated), retryAfterMs: Infinity };
    }
    if (estimated + cost <= this.limit) {
      this.#current += cost;
      return { allowed: true, remaining: Math.max(0, this.limit - estimated - cost), retryAfterMs: 0 };
    }
    return {
      allowed: false,
      remaining: Math.max(0, this.limit - estimated),
      retryAfterMs: Math.ceil(this.#timeUntil(cost, nowMs)),
    };
  }

  #advance(nowMs: number): void {
    const start = Math.floor(nowMs / this.windowMs) * this.windowMs;
    if (Number.isNaN(this.#start)) this.#start = start;
    if (start === this.#start) return;
    this.#previous = start === this.#start + this.windowMs ? this.#current : 0;
    this.#current = 0;
    this.#start = start;
  }

  #estimate(nowMs: number): number {
    const elapsed = nowMs - this.#start;
    return this.#current + this.#previous * (1 - elapsed / this.windowMs);
  }

  #timeUntil(cost: number, nowMs: number): number {
    const target = this.limit - cost;
    if (this.#previous > 0 && target >= this.#current) {
      const at = this.#start + this.windowMs *
        (1 - (target - this.#current) / this.#previous);
      return Math.max(0, at - nowMs);
    }
    const nextStart = this.#start + this.windowMs;
    if (this.#current === 0) return Math.max(0, nextStart - nowMs);
    const at = nextStart + this.windowMs * (1 - target / this.#current);
    return Math.max(0, at - nowMs);
  }
}

The estimate is smooth and constant-memory, but it assumes events in the previous bucket were uniformly distributed. A burst concentrated at one edge can be over- or under-counted. Use it when bounded error is acceptable and an exact log is too expensive.

Token bucket, leaky bucket, and GCRA #

A token bucket refills continuously at rate r units per millisecond up to capacity B. A request spends c tokens:

export class TokenBucket {
  #tokens: number;
  #lastMs: number;

  constructor(
    readonly capacity: number,
    readonly refillPerMs: number,
    nowMs = 0,
  ) {
    this.#tokens = capacity;
    this.#lastMs = nowMs;
  }

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    const safeNow = Math.max(nowMs, this.#lastMs);
    this.#tokens = Math.min(
      this.capacity,
      this.#tokens + (safeNow - this.#lastMs) * this.refillPerMs,
    );
    this.#lastMs = safeNow;
    if (cost > this.capacity) {
      return { allowed: false, remaining: this.#tokens, retryAfterMs: Infinity };
    }
    const allowed = cost <= this.#tokens;
    if (allowed) this.#tokens -= cost;
    const deficit = Math.max(0, cost - this.#tokens);
    return {
      allowed,
      remaining: Math.max(0, this.#tokens),
      retryAfterMs: allowed ? 0 : deficit / this.refillPerMs,
    };
  }
}

Token bucket permits an idle client to accumulate a deliberate burst of B, then continue at average rate r. It is often the best match for interactive APIs because short bursts complete immediately.

A leaky bucket is frequently described ambiguously. As a meter it mirrors token bucket. As a shaper, implemented below, it queues accepted work and emits it at a steady rate. readyAtMs is the completion time assigned by a FIFO schedule.

export type ShapingDecision = Decision & { readyAtMs: number };

export class LeakyBucketShaper {
  #nextAvailableMs = 0;

  constructor(
    readonly capacity: number,
    readonly leakPerMs: number,
  ) {}

  schedule(cost: number, nowMs: number): ShapingDecision {
    requireCost(cost);
    const queued = Math.max(0, this.#nextAvailableMs - nowMs) * this.leakPerMs;
    if (cost > this.capacity || queued + cost > this.capacity) {
      const deficit = Math.max(0, queued + cost - this.capacity);
      return {
        allowed: false,
        remaining: Math.max(0, this.capacity - queued),
        retryAfterMs: cost > this.capacity ? Infinity : deficit / this.leakPerMs,
        readyAtMs: nowMs,
      };
    }

    const start = Math.max(nowMs, this.#nextAvailableMs);
    this.#nextAvailableMs = start + cost / this.leakPerMs;
    return {
      allowed: true,
      remaining: Math.max(0, this.capacity - queued - cost),
      retryAfterMs: 0,
      readyAtMs: this.#nextAvailableMs,
    };
  }
}

Shaping improves downstream smoothness but adds latency and head-of-line blocking. Capacity must include the newly admitted cost, and a cost larger than capacity can never fit.

GCRA, the Generic Cell Rate Algorithm, stores one theoretical arrival time (TAT). Let T = 1 / r be time per unit and B be burst units. A weighted request is conforming when its candidate TAT stays within the burst horizon:

export class Gcra {
  #tatMs = 0;
  readonly #timePerUnitMs: number;

  constructor(
    readonly burstUnits: number,
    unitsPerMs: number,
  ) {
    this.#timePerUnitMs = 1 / unitsPerMs;
  }

  allow(cost: number, nowMs: number): Decision {
    requireCost(cost);
    const candidate = Math.max(nowMs, this.#tatMs) + cost * this.#timePerUnitMs;
    const horizon = nowMs + this.burstUnits * this.#timePerUnitMs;
    const allowed = cost <= this.burstUnits && candidate <= horizon;
    if (allowed) this.#tatMs = candidate;
    const debtUnits = Math.max(0, (this.#tatMs - nowMs) / this.#timePerUnitMs);
    return {
      allowed,
      remaining: Math.max(0, this.burstUnits - debtUnits),
      retryAfterMs: allowed ? 0 : Math.max(0, candidate - horizon),
    };
  }
}

GCRA gives token-bucket-like behavior with one timestamp and no continuously updated floating token balance. For unit requests, the traditional tolerance is tau = (B - 1) * T. The weighted candidate form above also prevents one request larger than the entire burst budget from passing on an empty limiter.

Compare and select by traffic shape #

The same public endpoint may need more than one policy: a token bucket for short client bursts plus a longer fixed quota for daily cost. Compose limiters only when each rule has an independent product meaning. Stacking several near-identical limits makes rejection and Retry-After hard to explain.

Clocks, weighted costs, and HTTP behavior #

All examples accept nowMs instead of reading a global clock. In Node.js, use performance.now() or a process.hrtime.bigint() adapter for in-process elapsed time. Clamp negative deltas, as TokenBucket does, even with a monotonic source: restored snapshots, bad mocks, and numeric conversions still happen. Periodically rebasing floating state avoids precision loss in processes that run for months.

Weighted requests require admission before expensive work, so derive cost from trusted, cheap attributes: authenticated plan, declared batch size with a hard maximum, route class, or validated content length. Never trust an arbitrary client-supplied cost. Decide whether rejected requests consume units; the implementations above do not. Charging malformed or abusive attempts can be a separate limiter.

For HTTP, return 429 Too Many Requests only when this client or policy is rate-limited; use 503 when shared capacity is unavailable regardless of client budget. Retry-After is integer seconds or an HTTP date, so round milliseconds up:

const retryAfterSeconds = Math.max(1, Math.ceil(decision.retryAfterMs / 1000));
response.setHeader('Retry-After', String(retryAfterSeconds));

RateLimit-Limit, RateLimit-Remaining, and RateLimit-Reset from RFC 9333 can describe the active quota. For weighted policies, document that remaining means units. For token bucket and GCRA, distinguish “time until this request cost fits” from “time until the bucket is completely full.” If several policies apply, report the one that most constrained the response or use the RFC’s multiple-policy syntax. Headers are advisory snapshots; concurrent requests can spend the advertised remainder before the client uses it.

Do not sleep inside an ordinary API rate limiter. Reject promptly and let the client schedule retry. Sleep belongs in an explicit shaper with bounded queue length, cancellation, deadlines, and metrics. Otherwise waiting requests consume sockets and memory while appearing harmless.

Simulation and boundary-focused tests #

Virtual time turns rate-limit tests into table-driven arithmetic instead of flaky sleeps. A tiny harness can replay weighted arrivals:

type Limiter = { allow(cost: number, nowMs: number): Decision };
type Arrival = { at: number; cost: number; allowed: boolean };

export function verify(limiter: Limiter, arrivals: Arrival[]): void {
  for (const arrival of arrivals) {
    const actual = limiter.allow(arrival.cost, arrival.at);
    if (actual.allowed !== arrival.allowed) {
      throw new Error(
        `at=${arrival.at} cost=${arrival.cost}: expected ${arrival.allowed}, got ${actual.allowed}`,
      );
    }
  }
}

verify(new TokenBucket(4, 1 / 1000), [
  { at: 0, cost: 4, allowed: true },
  { at: 1500, cost: 2, allowed: false },
  { at: 2000, cost: 2, allowed: true },
]);

Use vectors that attack the contract, not only evenly spaced happy paths:

Add property tests: admitted cost in every exact rolling window never exceeds L; token balance stays in [0, B]; accepted leaky-bucket work never exceeds queue capacity; and delaying an otherwise identical request cannot make it less eligible when no intervening request arrives. Compare GCRA and token bucket over randomized unit-cost traces with equivalent B and r; their decisions should match within floating-point tolerance.

Finally simulate realistic traces: synchronized clients at the second boundary, one heavy request among small requests, idle-then-burst traffic, and sustained traffic just above r. Record accept ratio, maximum consecutive rejection, queue delay, and retry accuracy. Average throughput alone will not reveal unfair bursts or pathological tail latency.

Takeaways #

• Fixed windows minimize state but deliberately tolerate reset spikes.
• Sliding logs enforce the literal rolling-window contract; sliding counters trade exactness for constant memory.
• Token buckets reward idle time with immediate bursts; leaky-bucket shapers exchange latency for smooth output.
• GCRA expresses continuous conformance with one timestamp and maps cleanly to burst plus sustained rate.
• Make boundaries, weighted units, clock behavior, and rejection headers part of the contract.
• Prove the contract with virtual-time vectors around expiry, rollback, fractional cost, and overload before optimizing storage.