Sliding windows and rate-limit boundaries

Define a window that can be tested

This exercise allows at most limit accepted requests for one logical client during (now - window, now]. Requests exactly one window old have expired. Rejected requests do not consume a slot. Timestamps must be finite and nondecreasing, including rejected attempts.

Use caller-supplied times for deterministic tests. A real single-process implementation could obtain elapsed time from a monotonic clock. Wall-clock adjustments and timestamps from another host need a different policy.

Keep only active accepted timestamps

Save as rate_window.py:

from collections import deque
from math import isfinite


class SlidingWindow:
    def __init__(self, limit, window):
        if type(limit) is not int or limit <= 0:
            raise ValueError("limit must be a positive integer")
        if type(window) not in (int, float) or not isfinite(window) or window <= 0:
            raise ValueError("window must be positive and finite")
        self.limit, self.window = limit, window
        self.accepted = deque()
        self.last = None

    def allow(self, now):
        if type(now) not in (int, float) or not isfinite(now):
            raise ValueError("now must be finite")
        if self.last is not None and now < self.last:
            raise ValueError("time moved backwards")
        self.last = now
        while self.accepted and self.accepted[0] <= now - self.window:
            self.accepted.popleft()
        if len(self.accepted) >= self.limit:
            return False
        self.accepted.append(now)
        return True


limiter = SlidingWindow(2, 60)
assert [limiter.allow(t) for t in [0, 1, 2, 60, 60]] == [
    True, True, False, True, False,
]

An accepted timestamp enters and leaves the deque once, giving amortized constant work per request and O(limit) stored timestamps for this one client. A single call after a quiet period can remove many timestamps. Adding clients also requires a policy for expiring inactive client keys.

Trace the exact expiry time

With limit 2 and window 60, time 0 is accepted and time 1 is accepted. Time 2 is rejected because both earlier accepted requests remain in the active window. At time 60, the time-0 request expires: the window is (0, 60]. Time 1 remains, so one new request at 60 is accepted. Another attempt at 60 is rejected. At time 61, time 1 expires and another slot becomes available.

Run python3 rate_window.py. In a scratch example, create a new instance after two accepted requests. The new instance accepts again because it has no history. That is the intended restart limitation. A timestamp earlier than the last attempted timestamp is rejected even when the last attempt was rate-limited; accepting it could corrupt the time-order assumption used for expiry.

Explain what the local algorithm cannot promise

Two replicas each allowing two requests can jointly accept four. This class is neither thread-safe nor durable across restarts. A distributed limiter needs an atomic shared decision, an explicit clock/window policy, and a decision about what to do when its store is unavailable.

A rate limit controls arrivals; a queue buffers work; a concurrency cap bounds work in progress. They solve related but different problems. For a future MicroBank API design, choose the principal to limit, the response on rejection, and how legitimate retries interact with idempotency. This teaching class lacks the shared state, concurrency handling, and durability required for a production payment control.

Checkpoint and revision

Test identical timestamps, the exact expiry boundary, backwards time, infinity, and restart behavior. Simulate two independent limiters to demonstrate the replica problem. Explain why keeping only a rolling count loses the exact arrival times needed by this particular policy.

Checkpoint answer: a count alone cannot tell which accepted request expires next. The deque preserves precisely that information. Two independent replicas can collectively accept four requests under this fixture, so a shared limit needs a different implementation. Bring these invariants and counterexamples into the offline toolkit lab.

Sources

Python deque↗, Python monotonic clocks↗, and Google SRE: handling overload↗.