Concepts / State, data structures and algorithms inside objects / Sliding windows and counters

Sliding windows and counters

Rate limiters and hit counters as objects with bounded memory.

Low-level design conceptState, data structures and algorithms inside objects2 Nov 2026

01The intuition

The problem it solves

A website wants to answer one question at any moment: how many visits happened in the last five minutes. The first version records every visit with its time and counts the recent ones on demand.

import time

class Visits:
    def __init__(self) -> None:
        self.times: list[float] = []

    def hit(self) -> None:
        self.times.append(time.time())

    def count_last(self, seconds: float = 300) -> int:
        cutoff = time.time() - seconds
        return sum(1 for t in self.times if t > cutoff)

At 1,000 visits a second this list grows by 86 million entries a day and never shrinks, and every count walks all of it. The question only ever concerns a window of time, so the structure should forget everything outside it, and should not need one entry per event.

Build it one piece at a time

Step one: a queue of timestamps. New hits go on the back; before answering, drop from the front everything older than the window. Memory is now bounded by the number of hits inside the window, and each timestamp is pushed once and popped once.

from collections import deque
from typing import Callable

class Visits:
    def __init__(self, window: float = 300, clock: Callable[[], float] = time.time) -> None:
        self.window, self.clock = window, clock
        self.times: deque[float] = deque()

    def hit(self) -> None:
        self.times.append(self.clock())

    def count(self) -> int:
        cutoff = self.clock() - self.window
        while self.times and self.times[0] <= cutoff:
            self.times.popleft()
        return len(self.times)

Step two: at 1,000 hits a second the window still holds 300,000 timestamps. Trade exactness for buckets: one integer per second, 300 of them in a ring. A hit adds one to the bucket for the current second; the count sums the ring. Memory is now 300 integers no matter the traffic.

class Visits:
    def __init__(self, window: int = 300, clock: Callable[[], float] = time.time) -> None:
        self.window, self.clock = window, clock
        self.counts = [0] * window        # bucket per second
        self.stamps = [0] * window        # which second each bucket holds

    def _bucket(self) -> int:
        now = int(self.clock())
        i = now % self.window
        if self.stamps[i] != now:         # bucket is stale: reuse it
            self.stamps[i] = now
            self.counts[i] = 0
        return i

    def hit(self) -> None:
        self.counts[self._bucket()] += 1

    def count(self) -> int:
        now = int(self.clock())
        return sum(c for c, s in zip(self.counts, self.stamps) if now - s < self.window)

Step three: a rate limiter is the same object with a decision attached. Allow a request if the count in the window is below the limit, else reject. A token bucket is the continuous cousin: tokens refill at a steady rate up to a cap, and a request spends one.

class TokenBucket:
    def __init__(self, rate: float, capacity: int, clock: Callable[[], float] = time.time) -> None:
        self.rate, self.capacity, self.clock = rate, capacity, clock
        self.tokens = float(capacity)
        self.last = clock()

    def allow(self) -> bool:
        now = self.clock()
        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

Ring state with a 4-second window and hits at t = 10, 10, 11, 13, then a count at t = 14:

Bucket indexstampcountinside window at 14?
0120yes
1131yes
2102no (14 − 10 = 4)
3111yes

The count is 2, and the two hits from second 10 have aged out without anyone deleting them.

Why it works

The queue version keeps the invariant that every timestamp in the deque is inside the window at the moment of the last count, so its length is the answer. The ring keeps a weaker invariant: a bucket holds the count for the second written in its stamp, and a stale stamp means the bucket is empty for counting purposes. Overwriting on reuse is what makes expiry free.

Where it breaks: the ring is approximate at the edge. A window of 300 seconds counted at 14.9 includes all of second 10 or none of it, so the true window is between 299 and 300 seconds. If exactness matters, keep the deque, or keep two levels of buckets. The other trap is the boundary comparison: whether a hit at exactly the cutoff counts must be decided once and tested.

memory: list = all hits ever; deque = hits in window (300,000 at 1,000/s); ring = 300 integers

The trade-off you must say out loud

Exact timestamps cost memory proportional to traffic; buckets cost fixed memory and lose precision of one bucket width; a token bucket uses two floats and allows short bursts up to the capacity. Say which the problem needs: a hit counter for a dashboard can be approximate, a billing limiter cannot. The follow-up that usually comes next is concurrency, many threads calling hit at once, where a lock around the bucket update or an atomic counter per bucket is the honest first answer.

Where it shows up in the 100 Google problems

02Used in these problems