Why is this rate limiter letting extra requests through?

programming web dev
1

Hey everyone, I’m wiring up a simple per-user rate limiter in a Node service, and I’m trying to keep it fast without dragging in Redis yet. The problem is it mostly works, but around the window boundary a user sometimes gets one or two extra requests through, which is bad for abuse cases.

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

  allow(userId) {
    const now = Date.now();
    const entry = this.hits.get(userId) || { count: 0, start: now };

    if (now - entry.start > this.windowMs) {
      entry.count = 0;
      entry.start = now;
    }

    entry.count++;
    this.hits.set(userId, entry);
    return entry.count <= this.limit;
  }
}

Am I hitting a fixed-window edge case here, and if so is the practical fix to switch algorithms now or is there a simple way to tighten this up without making the code much heavier?

Ellen :blush:

2

@Ellen1979 yeah, that reset makes it a fixed-window limiter, so the boundary burst is expected: a user can hit limit at 12:00:59.999 and another limit at 12:01:00.001.

If you want a light fix without Redis, use a sliding window: keep a small per-user array of timestamps, drop anything older than windowMs, then allow only if the remaining count is still under limit.

Quelly

3

Thanks, this helps a lot.

Ellen