Window counting limiters

A window counter answers one question: how many requests did this client make in the last period? It splits time into windows, such as one calendar minute, and counts requests in each. The three variants differ in how they handle the edges of a window. That edge behavior is the trade-off.

The big idea

Picture a bouncer who lets in 100 people per hour. He keeps a tally and resets it on the hour. The rule is easy to run, but the reset leaves a gap. Someone who lets 100 people in at 12:59 and 100 more at 1:00 has followed both hours' rules.

The analogy works for one bouncer. Across many servers, the tally itself must be shared, and that is a separate problem covered in the distributed limiter.

Walking through it

Fixed window

Keep one counter per client per window. Reject once the counter goes over the limit.

function fixedWindowAllow(counts: Map<string, number>, key: string, limit: number, nowMs: number, windowMs = 60_000) {
  const k = `${key}:${Math.floor(nowMs / windowMs)}`
  const n = (counts.get(k) ?? 0) + 1
  counts.set(k, n) // in a real store, a TTL removes old windows
  return n <= limit
}

const counts = new Map<string, number>()
let allowed = 0
for (let i = 0; i < 100; i++) allowed += fixedWindowAllow(counts, "client-1", 100, 59_000) ? 1 : 0 // 12:00:59
for (let i = 0; i < 100; i++) allowed += fixedWindowAllow(counts, "client-1", 100, 60_000) ? 1 : 0 // 12:01:00
console.log(allowed, "requests allowed in 2 seconds")

Output:

200 requests allowed in 2 seconds

Both windows were within the limit, yet the service absorbed 200 requests in two seconds. That is the boundary burst: up to twice the intended rate across a window edge. For abuse limits this is often acceptable. For protecting a fragile backend, it is not.

Sliding window log

Store a timestamp for every accepted request. Count the timestamps in the last window. There is no boundary effect, because the window really slides. The cost is memory. A limit of 10,000 per hour across 1 million keys can mean up to 10 billion timestamps. In Redis this is usually a sorted set, which works for small limits such as login attempts.

Sliding window counter

Keep two counters, for the current window and the previous one. Estimate the sliding count by weighting the previous window by how much of it still overlaps the last minute:

Limit 100 per minute. It is 12:01:15, so 15 s into the current minute.
previous window (12:00) = 84 requests
current window  (12:01) = 30 requests
overlap of previous     = 1 − 15/60 = 0.75

estimate = 30 + 84 × 0.75 = 30 + 63 = 93   → allow (93 < 100)

This assumes requests in the previous window were spread evenly. That is wrong for any one client, but the error is small in aggregate. Cloudflare reported that across 400 million requests, only about 0.003% were wrongly allowed or limited. Memory is two counters per key.

Common mistakes

• Trusting fixed windows at the edge. A client can double the limit by timing bursts around the boundary.
• Forgetting to expire old windows. Without a TTL, every window counter stays in memory forever.
• Using a sliding log for large limits. Memory grows with the limit, not with the number of active clients.

Check yourself

1. A fixed window allows 100 requests per minute. A client sends 100 requests at 12:00:58 and 100 more at 12:01:02. How many get through?

   Answer: 200. The two bursts fall in different windows, and each is within its own limit.

2. The sliding counter multiplies the previous window by 0.75. What does 0.75 represent?

   Answer: the share of the previous window that still falls inside the last 60 seconds.

Key takeaways

• A fixed window is one counter per window, cheap and simple, but it allows bursts of up to twice the limit at a boundary.
• A sliding log is exact, but its memory grows with the limit.
• A sliding counter estimates the sliding count from two counters. It is accurate in aggregate and cheap.
• Always set a TTL on window state.

Further learning

Next, see how a bucket with a fixed capacity and refill rate allows bursts without boundary effects in the token bucket.