Rolling windows and rate counters

You’ll recognise it when

• You need “how many in the last N seconds”: hits, page views, messages, errors.
• Calls arrive with a timestamp, and time never goes backwards.
• You must allow or reject each request against a limit: per client, per key, per group.
• The service runs for a long time, so memory must not grow with the number of events.

It’s often confused with the sliding window technique on arrays. That one moves two indexes over a fixed array. Here the window is defined by the clock, events keep arriving, and old ones must be forgotten.

The idea

Picture a row of 60 jars on a shelf, one for each second of the last minute, and a tally on the wall of what’s in all the jars together. Each second you move to the next jar along, wrapping around at the end. Before using a jar, you tip out what it held a minute ago and subtract that from the tally. Counting the last minute is reading the tally.

That’s a ring of time buckets with a running total. Each bucket remembers hits for one second; the bucket for second s lives at s % window. A bucket is reused once its second has left the window, and emptying it keeps total right. Memory is fixed by the window’s length, however many hits arrive.

How it works

RollingCounter(window) answers count(t): the hits in the last window seconds, the interval [t - window + 1, t]. It keeps buckets, the running total, and last, the latest second the clock has reached.

1. hit(t, n) and count(t) start by advancing the clock to t. If t equals last, there’s nothing to do. A t before last is an error: time went backwards.
2. Empty the seconds that left. For each second s from last + 1 to t, the bucket at s % window holds hits from second s - window, which is no longer in the window. Subtract it from total and set it to 0.
3. Skip long gaps in one step. If t - last >= window, every bucket is stale. Reset all of them at once instead of looping over a gap that could be a billion seconds.
4. Record or read. hit adds n to the bucket at t % window and to total. count returns total.

With window = 5: hits at seconds 1, 2 and 2 (three of them) make total = 5, and count(4) covers [0, 4], so 5. A hit at 6 first empties the buckets for seconds 5 and 6, which still hold seconds 0 and 1: total drops by 1 and then gains the new hit, so count(6) is 5. At 7 the bucket for second 2 empties: count(7) is 1. At 12 the gap is at least 5, so everything resets.

Why it’s correct: after advancing to last, each bucket holds the hits of exactly one second in [last - window + 1, last], and total is their sum. Advancing by one second retires exactly one old second and opens one new, empty one.

class RollingCounter:
    """Hits in the last `window` seconds: the interval [t - window + 1, t]."""

    def __init__(self, window):
        self.window = window
        self.buckets = [0] * window   # buckets[s % window] = hits in second s
        self.total = 0                # sum of every bucket still in the window
        self.last = None              # the latest second we've moved the clock to

    def _advance(self, t):
        # Move the clock to second t, emptying buckets that leave the window.
        if self.last is not None and t < self.last:
            raise ValueError("time went backwards")
        if t == self.last:
            return
        if self.last is None or t - self.last >= self.window:
            self.buckets = [0] * self.window       # every bucket is stale
            self.total = 0
        else:
            for s in range(self.last + 1, t + 1):  # at most `window` steps
                self.total -= self.buckets[s % self.window]
                self.buckets[s % self.window] = 0
        self.last = t

    def hit(self, t, n=1):
        self._advance(t)
        self.buckets[t % self.window] += n
        self.total += n

    def count(self, t):
        self._advance(t)
        return self.total

#include <algorithm>
#include <stdexcept>
#include <vector>
using namespace std;

// Hits in the last `window` seconds: the interval [t - window + 1, t].
class RollingCounter {
    long long window;
    vector<long long> buckets;    // buckets[s % window] = hits in second s
    long long total = 0;          // sum of every bucket still in the window
    long long last = -1;          // the latest second we've moved the clock to (-1: none yet)

    // Move the clock to second t, emptying buckets that leave the window.
    void advance(long long t) {
        if (last >= 0 && t < last) throw invalid_argument("time went backwards");
        if (t == last) return;
        if (last < 0 || t - last >= window) {
            fill(buckets.begin(), buckets.end(), 0);   // every bucket is stale
            total = 0;
        } else {
            for (long long s = last + 1; s <= t; s++) {  // at most `window` steps
                total -= buckets[s % window];
                buckets[s % window] = 0;
            }
        }
        last = t;
    }

public:
    explicit RollingCounter(long long window) : window(window), buckets(window, 0) {}

    void hit(long long t, long long n = 1) {
        advance(t);
        buckets[t % window] += n;
        total += n;
    }

    long long count(long long t) {
        advance(t);
        return total;
    }
};

import java.util.*;

// Hits in the last `window` seconds: the interval [t - window + 1, t].
class RollingCounter {
    private final int window;
    private final long[] buckets;   // buckets[s % window] = hits in second s
    private long total = 0;         // sum of every bucket still in the window
    private long last = -1;         // the latest second we've moved the clock to (-1: none yet)

    RollingCounter(int window) {
        this.window = window;
        this.buckets = new long[window];
    }

    // Move the clock to second t, emptying buckets that leave the window.
    private void advance(long t) {
        if (last >= 0 && t < last) throw new IllegalArgumentException("time went backwards");
        if (t == last) return;
        if (last < 0 || t - last >= window) {
            Arrays.fill(buckets, 0);                  // every bucket is stale
            total = 0;
        } else {
            for (long s = last + 1; s <= t; s++) {    // at most `window` steps
                total -= buckets[(int) (s % window)];
                buckets[(int) (s % window)] = 0;
            }
        }
        last = t;
    }

    void hit(long t, long n) {
        advance(t);
        buckets[(int) (t % window)] += n;
        total += n;
    }

    long count(long t) {
        advance(t);
        return total;
    }
}

The exact version: a queue of timestamps

When volume is small, the simplest correct answer is a deque of timestamps. Append on each hit; before counting, pop from the left while the oldest is out of the window.

from collections import deque

class HitLog:
    def __init__(self, window):
        self.window = window
        self.times = deque()

    def hit(self, t):
        self.times.append(t)

    def count(self, t):
        while self.times and self.times[0] <= t - self.window:
            self.times.popleft()
        return len(self.times)

It’s exact to any precision and easy to say out loud, but memory grows with the number of hits in the window. A million hits a second means a million timestamps. Start here in an interview, then move to buckets when the interviewer asks about scale.

Rate limiters

A limiter is a counter plus a decision. A sliding-window limiter allows a request if count(t) < limit, then records it. A token bucket allows short bursts: the bucket refills at rate tokens per second up to capacity, and each request spends one token.

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity, self.rate = capacity, rate
        self.tokens = capacity
        self.last = 0.0

    def allow(self, now):
        # refill lazily for the time that passed, never above capacity
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

b = TokenBucket(3, 1)
print([b.allow(t) for t in [0, 0, 0, 0, 1, 1.5, 3]])
# [True, True, True, False, True, False, True]

Nothing ticks in the background: every structure here catches up lazily when it’s called.

Why it’s O(1) amortized

A call that moves the clock forward by d seconds empties at most min(d, window) buckets. Over a whole run, the clock moves forward by at most the total elapsed time, and each jump bigger than the window costs one reset. Per call that’s O(1) amortized for regular traffic, and never more than O(window). count is O(1) because the total is maintained, not summed.

Per key, keep a dict from key to its counter and drop keys that have been idle longer than the window, or memory grows with every key ever seen.

Common mistakes

while q and q[0] < t - window: q.popleft()    # ✗ keeps second t - window
while q and q[0] <= t - window: q.popleft()   # ✓ window is [t - window + 1, t]

return sum(self.buckets)        # ✗ O(window) per query
return self.total               # ✓ kept up to date in _advance

self.buckets[t % w] += 1                     # ✗ may still hold second t - w
self._advance(t); self.buckets[t % w] += 1   # ✓ stale seconds emptied first

now = time.time()          # ✗ can go backwards
now = time.monotonic()     # ✓ only moves forward

Variations

• Per key. A dict of counters, one per user or client. Evict idle keys, and in a threaded server lock per key (or per shard of keys), since a dict of counters isn’t safe to update from several threads.
• Several windows at once. “Last minute, last hour, last day”: keep one ring at one-second resolution and another at one-minute resolution, rather than one huge ring.
• Top talkers. The most active key in the window needs counts per key that also expire, plus a way to find the maximum, such as a heap with lazy deletion.
• Fixed windows. Count per calendar minute (t // 60). It’s cheap, but a client can send 2 × limit requests across a boundary. A sliding window or token bucket fixes that.
• Logger-style rate limits. “Show each message at most once every 10 seconds” needs only the last time each message was shown: a dict from message to time.

Climb the ladder

Our rolling-counter problems in ladder order.

1. Events in the last N seconds: the deque version.
2. Café drink counts over the last N seconds: counts per key, and distinct keys, in a window.
3. Logger Rate Limiter: last-seen time per message.
4. Token Bucket Rate Limiter: lazy refill, capped bursts.
5. Page views in the last five minutes: batched hits, bounded memory.
6. Chat message events aggregation: several views of one window, then a top talker.
7. Key-value store with rolling QPS: windows up to a week, then thread safety.
8. Throttle requests per client: fixed windows, sliding windows, token buckets and shared group limits.