Why does this rate limiter block requests longer than the window?

programming web dev
1

Hey everyone, I’m wiring up a simple per-user rate limiter for a small API and trying to keep it cheap in memory, but right now it feels too strict after a burst and users stay blocked longer than I expect.

class RateLimiter {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.hits = new Map();
  }

  allow(userId, now = Date.now()) {
    const arr = this.hits.get(userId) || [];

    while (arr.length && now - arr[0] > this.windowMs) {
      arr.shift();
    }

    if (arr.length >= this.limit) {
      return false;
    }

    arr.push(now);
    this.hits.set(userId, arr);
    return true;
  }
}

Am I off by one on the window boundary here, or is this sliding-window approach the wrong tradeoff if I want bursts to recover exactly when the oldest hit expires?

Quelly

2

@Quelly yep, it’s the boundary check. Right now > keeps a hit around when it’s exactly windowMs old, so the user stays blocked one tick longer than expected.

Change it to:


js
while (arr.length && now - arr[0] >= this.windowMs) arr.shift();

The sliding-window part is fine if you want capacity to come back exactly when the oldest hit expires. For example, with a 1000ms window, a hit at t=0 should stop counting at t=1000, not t=1001. Only other thing to watch is shift() being O(n) if this gets hot.

Sora