Why Fixed-Window Rate Limiters Fail (And How to Fix Them with Math)

If you’ve ever built an Express API, you’ve probably reached for standard rate-limiting middleware to protect your login or payment endpoints from DDoS and brute-force attacks.

Under the hood, most simple limiters use a Fixed-Window Counter. It’s easy to write: count incoming requests, and once the minute rolls over, reset the counter to zero.

However, from a security and algorithmic standpoint, Fixed-Window counters have a massive blind spot.

---

The Boundary Vulnerability (The 2-Second Spike)

Imagine your endpoint allows a maximum of 100 requests per minute, resetting every full minute on the clock (:00).

Here is how an attacker bypasses that limit without breaking your rules:

1. At 12:00:59, the attacker fires 100 requests. (Allowed: 100/100 used).
2. At 12:01:00, the clock resets your counter back to 0.
3. At 12:01:01, the attacker fires another 100 requests. (Allowed: 100/100 used).

To your server code, everything looks fine. But in reality, 200 requests slammed your backend within a 2-second window. In FinTech or authentication systems, that burst is more than enough to overwhelm payment gateways or run a successful credential-stuffing attack.

---

The Algorithmic Fix: Sliding Window Counter

To stop boundary spikes, we need a continuously sliding window rather than a rigid clock reset.

Attempt 1: The Sliding Window Log (High Memory)

You store a timestamps array (a Deque) for every user request and drop timestamps older than 60 seconds. While accurate, storing every single request timestamp takes $O(N)$ space. If your API receives millions of requests, your server memory dies instantly.

Attempt 2: Sliding Window Counter (Optimal O(1) Math)

Instead of keeping thousands of timestamps, we track only two integers: the request count of the previous window and the count of the current window.

When a request arrives, we calculate an estimated request count by weighting the previous window based on how much time has passed in the current window:

$$\text{Estimated Requests} = \text{Current Count} + \left(\text{Previous Count} \times \frac{\text{Window Size} - \text{Time Elapsed}}{\text{Window Size}}\right)$$

If the time elapsed in the current window is 75%, we only count 25% of the previous window's traffic.

• Time Complexity: O(1) lookup and arithmetic.
• Space Complexity: O(1) memory footprint (just two counter variables per IP).

---

Building the Middleware in Node.js

Here is a lightweight implementation using JavaScript Map to track state:

class SlidingWindowRateLimiter {
  constructor(limit, windowMs) {
    this.limit = limit; // e.g., 100 requests
    this.windowMs = windowMs; // e.g., 60000ms (1 minute)
    this.hits = new Map();
  }

  isAllowed(ip) {
    const now = Date.now();
    const currentWindowKey = Math.floor(now / this.windowMs);
    const timeElapsedInCurrentWindow = now % this.windowMs;

    const record = this.hits.get(ip) || {
      prevWindowKey: currentWindowKey - 1,
      prevCount: 0,
      currWindowKey: currentWindowKey,
      currCount: 0,
    };

    // Roll windows over if time has progressed
    if (record.currWindowKey !== currentWindowKey) {
      if (record.currWindowKey === currentWindowKey - 1) {
        record.prevCount = record.currCount;
      } else {
        record.prevCount = 0; // Previous window is too old
      }
      record.currWindowKey = currentWindowKey;
      record.currCount = 0;
    }

    // Calculate sliding weight formula
    const weight = (this.windowMs - timeElapsedInCurrentWindow) / this.windowMs;
    const estimatedRequests = Math.floor(record.prevCount * weight) + record.currCount;

    if (estimatedRequests >= this.limit) {
      return { allowed: false, currentCount: estimatedRequests };
    }

    // Increment and store current count
    record.currCount += 1;
    this.hits.set(ip, record);

    return { allowed: true, currentCount: estimatedRequests + 1 };
  }
}

// Express Middleware Wrap
const limiter = new SlidingWindowRateLimiter(100, 60000);

function rateLimiterMiddleware(req, res, next) {
  const clientIP = req.ip || req.headers['x-forwarded-for'];
  const result = limiter.isAllowed(clientIP);

  res.setHeader('X-RateLimit-Limit', 100);
  res.setHeader('X-RateLimit-Remaining', Math.max(0, 100 - result.currentCount));

  if (!result.allowed) {
    return res.status(429).json({
      error: 'Too Many Requests',
      message: 'Rate limit exceeded. Please try again shortly.',
    });
  }

  next();
}

---

Why This Matters for High-Performance Systems

1. Sub-Millisecond Speed: The decision math executes in fractions of a microsecond without iterating over huge arrays.
2. Boundary Smoothness: An attacker trying the 12:00:59 / 12:01:01 spike will be blocked instantly because the weight of the 12:00:59 burst carries over into the calculation.
3. Production Readiness: In a distributed multi-node infrastructure, this exact math scales cleanly to Redis using simple INCR and hash keys.

Applying basic competitive programming data structures and math to API security turns naive middleware into enterprise-grade defense.