js-sliding-window-log-epoch-trap

Answer

The rate limiter must match a naive per-request reference exactly. The naive reference keeps accepted timestamps verbatim and, for a request at time t, prunes every entry s <= t - windowMs before counting. Two bugs plague typical "optimized" implementations:

1. The epoch trap: bucketing with epoch = Math.floor(t / windowMs) and resetting counts on an epoch change. floor flips exactly at the boundary, so a request arriving at t % windowMs === 0 either drops the just-expired boundary (false accept) or double-counts it (false reject). Timestamps must never be bucketed — store them verbatim.
2. The off-by-one prune: pruning with < cutoff instead of <= cutoff keeps an entry that is exactly windowMs old. s == t - W means the window (t - W, t] is fully elapsed for that entry — it must be removed, or the count inflates and requests get falsely rejected.

'use strict';

class SlidingWindowLog {
  constructor({ limit, windowMs, now = () => performance.now() }) {
    if (!Number.isInteger(limit) || limit <= 0) throw new RangeError('limit must be a positive integer');
    if (!Number.isFinite(windowMs) || windowMs <= 0) throw new RangeError('windowMs must be positive');
    this.limit = limit;
    this.windowMs = windowMs;
    this.now = now; // monotonic clock (performance.now)
    this.log = [];  // timestamps of accepted requests, arrival order
  }

  tryAcquire(t) {
    const now = t === undefined ? this.now() : t; // deterministic when given
    const cutoff = now - this.windowMs;

    // Prune entries at or past the window edge: `<=`, never `<`.
    const log = this.log;
    let i = 0;
    while (i < log.length && log[i] <= cutoff) i++;
    if (i > 0) log.splice(0, i);

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

module.exports = { SlidingWindowLog };

Why it's correct: a request accepted at s is inside the window for request t iff s > t - W, so the cutoff is exact and boundary hits (t % W === 0) fall out naturally. Memory is O(limit): the log is pruned before every check and only grows on accept, so log.length <= limit at all times regardless of how long the process runs or how far timestamps advance.