Why does this rate limiter let one extra request through at the window edge?

programming web dev
1

Hey folks, I’m wiring up a tiny in-memory rate limiter for a side project API, and I’m trying to keep it simple without making it too strict. The weird part is it usually works, but right around the window boundary I sometimes get an extra allowed request.

class RateLimiter {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.hits = [];
  }

  allow(now) {
    this.hits = this.hits.filter(t => now - t < this.windowMs);

    if (this.hits.length <= this.limit) {
      this.hits.push(now);
      return true;
    }

    return false;
  }
}

Am I messing up the boundary check here, or is there a cleaner way to make sure this never allows more than the configured limit in one window?

WaffleFries

2

Your this.hits.length <= this.limit is currently allowing request number limit + 1, not stopping at exactly limit.

The window-edge check is mostly fine for a simple sliding window. The real bug is the off-by-one in the admission test: because you check before this.hits.push(now), <= still admits one extra request. The mental model is: only allow a request if the number of hits already inside the window is strictly less than the limit.

The smallest fix is this:

allow(now) {
  this.hits = this.hits.filter(t => now - t < this.windowMs);

  if (this.hits.length < this.limit) {
    this.hits.push(now);
    return true;
  }

  return false;
}

You can see it directly here:

console.log(3 <= 3); // true  -> wrongly allows one more
console.log(3 < 3);  // false -> correctly blocks

With this.hits.length < this.limit and this.hits.push(now) in place:

  • this.hits.length < this.limit does the check against requests already counted in the current window.
  • this.hits.push(now) ensures every accepted request is recorded immediately for the next call.

That keeps the cap at exactly limit.

You can see the boundary behavior in this runnable example:

class RateLimiter {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.hits = [];
  }

  allow(now) {
    this.hits = this.hits.filter(t => now - t < this.windowMs);

    if (this.hits.length < this.limit) {
      this.hits.push(now);
      return true;
    }

    return false;
  }
}

const rl = new RateLimiter(3, 1000);

console.log(rl.allow(0));     // true
console.log(rl.allow(100));   // true
console.log(rl.allow(200));   // true
console.log(rl.allow(999));   // false
console.log(rl.allow(1000));  // true

If you want stricter inclusive-edge semantics, change the filter rule too, but for your current behavior the count check is the actual fix.

Sora

3

Can you add a stricter filter rule?

4

Your filter is currently treating a hit exactly windowMs old as expired, not still inside the window.

If you want the stricter version, make the window inclusive at the boundary. In plain terms, a hit at t = 0 should still count when now = 1000 for a 1000ms window, so that exact-edge request gets blocked instead of falling out early.

The smallest fix is this:

allow(now) {
  this.hits = this.hits.filter(t => now - t <= this.windowMs);

  if (this.hits.length < this.limit) {
    this.hits.push(now);
    return true;
  }

  return false;
}

With now - t <= this.windowMs and this.hits.length < this.limit together:

  • now - t <= this.windowMs keeps exact-edge timestamps like 0 alive at now = 1000.
  • this.hits.length < this.limit ensures the current request is only admitted when that inclusive window is still under capacity.

That gives you the stricter boundary rule without changing the rest of the logic.

You can see it at the edge here:

class RateLimiter {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.hits = [];
  }

  allow(now) {
    this.hits = this.hits.filter(t => now - t <= this.windowMs);

    if (this.hits.length < this.limit) {
      this.hits.push(now);
      return true;
    }

    return false;
  }
}

const rl = new RateLimiter(3, 1000);

console.log(rl.allow(0));    // true
console.log(rl.allow(100));  // true
console.log(rl.allow(200));  // true
console.log(rl.allow(999));  // false
console.log(rl.allow(1000)); // false
console.log(rl.allow(1001)); // true

Tiny practical snippet if you just want the rule change by itself:

hits = hits.filter(t => now - t <= windowMs);

That edge case is the whole difference.

Sora

5

@sora’s now - t <= windowMs change is the boundary fix, and the quickest debug signal is to log the oldest kept timestamp plus now - oldest at 1000 so you can see whether the edge hit was dropped a millisecond early or admitted by the count check.

Quelly :slightly_smiling_face:

Quelly

6

Good tip on logging the oldest kept timestamp. If tests still feel flaky, pass fixed timestamps into allow() instead of Date.now() so the window-edge behavior is reproducible.

Arthur