Three rate limiters, and the millisecond where each one changes its mind

I kept reaching for express-rate-limit without knowing what it did, and every explanation I found stopped at "fixed window can burst at the boundary" without showing the code. So I wrote the three common algorithms myself to find out where they actually differ. They differ in about four places, and all four are interesting.

One interface, three behaviours

interface RateLimiter {
  /** Counts the request when it returns true. Call once per request. */
  isAllowed(key: string): boolean;
  remaining(key: string): number;
  reset(key: string): void;
  clear(): void;
}

isAllowed counting the request is the one API decision worth arguing about. The alternative is a separate consume(), which is more honest and which everybody then forgets to call. Coupling the check to the count makes the common path correct by default and the unusual path, checking without spending, impossible. I would make the same trade again, and it is the first thing I document.

Fixed window, and the 2x burst

One counter per key per window, windows aligned to the clock. Cheapest of the three: one small object per key no matter how much traffic arrives. The catch is what happens at the edge.

A client with a budget of 100 per minute can spend all 100 at 00:00:59.998 and all 100 again at 00:01:00.001. That is 200 requests in three milliseconds, against a limit that says 100 per minute, and it is not a bug. It is what clock-aligned windows mean. There is a test that asserts it, named for what it is:

it("lets a burst across the boundary through at 2x the limit", () => {
  const limiter = new FixedWindowLimiter(5, 1000);

  // Spend the whole budget at the very end of the window.
  jest.setSystemTime(999);
  for (let i = 0; i < 5; i++) expect(limiter.isAllowed("k")).toBe(true);
  expect(limiter.isAllowed("k")).toBe(false);

  // New window, full budget again, 2ms later.
  jest.setSystemTime(1001);
  for (let i = 0; i < 5; i++) expect(limiter.isAllowed("k")).toBe(true);
});

Sliding window log, and what it costs

Store a timestamp per request and count how many fall inside the trailing window. No boundary trick works, because there is no boundary; the window moves with the caller. You pay in memory: up to limit timestamps per key.

The subtlety is that expired entries have to be pruned on read. Skip it and the array grows without bound, and worse, the count never drops below the limit, so the key is permanently blocked. A limiter whose failure mode is locking someone out forever is worse than no limiter.

Token bucket, and the bug I shipped

Buckets start full, each request spends a token, tokens return at a fixed rate. Refill is lazy: nothing runs on a timer, it just works out how much time has passed since the last call. Constant memory per key like fixed window, smooth like sliding window, which is why it is the default I reach for.

I got it wrong the first time, and the way I got it wrong is instructive. I floored the token count on every refill:

const elapsed = (now - bucket.last) / 1000;
bucket.tokens = Math.floor(
  Math.min(this.capacity, bucket.tokens + elapsed * this.refillPerSecond)
);
bucket.last = now;

With a refill of 5 per second, 100ms of elapsed time earns 0.5 tokens. Floor it and you earn nothing. A client polling every 100ms therefore discards half a token on every call and never earns one back, so it stays blocked forever while the maths says it should be allowed through at 5 per second.

const elapsed = (now - bucket.last) / 1000;
bucket.tokens = Math.min(
  this.capacity,
  bucket.tokens + elapsed * this.refillPerSecond,
);
bucket.last = now;

// The bucket holds a float; the decision is integral.
if (bucket.tokens >= 1) {
  bucket.tokens -= 1;
  return true;
}
return false;

The general shape of this bug is worth remembering: rounding inside an accumulator rather than at the point of use. It is invisible when calls are far apart and total starvation when they are close together, which means the failure only appears under the traffic pattern a rate limiter exists to handle.

Choosing between them

Token bucket unless you have a reason. Sliding window when a boundary burst would genuinely hurt the thing behind the limiter. Fixed window when the resource is cheap and the volume is large enough that per-key memory matters.

Known limits

All three are in-memory and per-process, so two instances behind a load balancer enforce the limit twice, once each. That is fine for a single-node service and it is exactly why production deployments put the counter in Redis. Nothing evicts keys either: key on something unbounded like client IPs on a public endpoint and the map grows for the life of the process. Both are stated in the README rather than discovered.