Fixed and sliding windows

Take a limit of 100 requests per minute per user (round numbers keep the examples easy). Now you have to count. That sounds trivial until you ask: which minute? The one on the clock, 8:00 to 8:01? Or the last 60 seconds, whenever "now" is?

The answer changes how much memory you need, how accurate the limit is, and whether a clever client can sneak twice the limit through. In this lesson we'll build three counters, each fixing the flaw in the one before.

Fixed window: one counter per minute

The simplest idea. Cut time into fixed one-minute blocks that line up with the clock. Keep one counter per user per block. Each request adds one. If the counter is already at the limit, reject.

const counts = new Map() // key -> count

function allow(userId, limit = 100) {
  const minute = Math.floor(Date.now() / 60000)
  const key = `${userId}:${minute}`
  const count = (counts.get(key) ?? 0) + 1
  counts.set(key, count)
  return count <= limit
}

The key includes the minute number, so at 8:01:00 a new key starts at zero. Old keys are thrown away (in Redis you'd let them expire, which we'll see in the last lesson).

This is cheap. One small integer per active user. A million active users is a few tens of megabytes. Each check is one increment. It's easy to explain to the support team: "You get 100 a minute, it resets at the top of the minute."

The boundary problem

Fixed windows have one well-known flaw. Watch what a script can do with a limit of 100 per minute:

That's 200 requests in about two seconds, and the limiter never complained. Both windows saw exactly 100.

In a fixed window, a client can send up to twice the limit in a short burst by straddling the boundary between two windows.

Is that a problem? For menu browsing, usually not. 2x a generous limit for a second or two won't hurt anyone. For "5 OTP guesses per minute", letting 10 through is a real weakness.

Everyone resets at once

There's a second, quieter problem. Every user's window resets at the same instant. Clients that were blocked all wait for :00 and then retry together. You get a small spike at the top of every minute. If many clients are well-behaved and honour "try again in N seconds", that spike can be large.

Sliding window log: remember every request

To get rid of the boundary, stop using clock-aligned blocks. Instead, ask the honest question every time: how many requests has this user made in the last 60 seconds?

To answer it, keep a log of timestamps per user. On each request, drop timestamps older than 60 seconds, count what's left, and allow the request if the count is under the limit.

const logs = new Map() // userId -> array of timestamps (ms)

function allow(userId, limit = 100, windowMs = 60000) {
  const now = Date.now()
  const log = (logs.get(userId) ?? []).filter((t) => t > now - windowMs)
  if (log.length >= limit) {
    logs.set(userId, log)
    return false
  }
  log.push(now)
  logs.set(userId, log)
  return true
}

This is exact. At any moment, no user has more than 100 allowed requests in any 60-second span. The boundary trick is gone.

What it costs

The price is memory. Instead of one number per user, you store up to limit timestamps per user.

Back-of-the-envelope for Tiffin: 400,000 active users at dinner, limit 100, 8 bytes per timestamp.

• Raw data: 400,000 × 100 × 8 bytes = 320 MB.
• In Redis, a sorted set stores each timestamp as both a member and a score, plus bookkeeping, so expect a few tens of bytes per entry even in its compact form. That pushes it past a gigabyte.

Compare that to the fixed window's tens of megabytes. For a limit of 5 OTP attempts, the log is tiny and perfectly fine. For a limit of 1,000 requests per minute on a busy API, it gets expensive fast.

It's also more work per request: trim, count, insert. Usually fine, but not free.

Sliding window counter: the clever middle

Here's a trick that gets most of the accuracy of the log for the memory of the fixed window.

Keep the fixed window counters, but remember two of them: the current minute and the previous minute. Then estimate how many requests fall in the last 60 seconds by assuming the previous minute's requests were spread evenly across it.

Say the limit is 100 and it's now 8:01:15:

• The previous window (8:00) had 80 requests.
• The current window (8:01) has 30 so far.
• We're 15 seconds into the current minute, so the last 60 seconds include the final 45 seconds of the previous minute. That's 45/60 = 75% of it.

estimate = previous × overlap + current
         = 80 × 0.75 + 30
         = 60 + 30
         = 90

90 is under 100, so the request is allowed.

How wrong can the estimate be?

The assumption is that the previous minute's requests were evenly spread. If the script sent all 80 in the first second of the previous minute, those requests are actually outside the last 60 seconds, but the estimate still counts 60 of them. The limiter is a bit too strict. If it sent all 80 in the last second, they're all inside, but the estimate counts only 60. The limiter is a bit too loose.

In real traffic, which is mixed and noisy, the error is small. A client that deliberately games the assumption can squeeze extra requests through spread over a minute, but it can't pull off the fixed window's "twice the limit in two seconds": right after a busy minute, the estimate is still close to the previous minute's count, so the new minute starts nearly full. For most APIs, this is the sweet spot: two integers per user, one multiplication per request, and no boundary trick.

Comparing the three

What Tiffin uses

For general API traffic, Tiffin starts with the sliding window counter at 300 requests per minute per user. It's cheap and fair.

For logins and OTPs, the numbers are tiny (5 attempts), so the exact sliding log costs almost nothing and removes the doubling risk where it matters most.

There's one thing all three windows share, though. They treat every request in the window the same, and they don't distinguish "a sudden burst then quiet" from "a steady stream". When a customer opens the Tiffin app, the home screen fires a dozen requests in the same second, then nothing for a while. A window of "10 per second" would block that perfectly normal burst. The next lesson's token bucket is designed for exactly that.