29. Sliding-Window Token-Rate Limiter

Problem

A lab's public API bills and throttles by tokens, not raw request count — a customer sending one huge prompt should count more against their quota than ten tiny ones. Implement a per-API-key sliding-window token-rate limiter.

Unlike most problems in this set, this one is stateful: you're designing a class, TokenRateLimiter, that holds state across many calls to allow(). Each call to allow(key, timestamp, tokens) admits the request only if the sum of tokens already logged for that key within the trailing window_seconds does not exceed max_tokens once this request's tokens are added, and must decide this using only that key's own history.

Source: src/29_token_rate_limiter.py

class TokenRateLimiter:
    def __init__(self, max_tokens: int, window_seconds: float): ...
    def allow(self, key: str, timestamp: float, tokens: int) -> bool: ...

>>> rl = TokenRateLimiter(max_tokens=100, window_seconds=10)
>>> rl.allow("k", 0, 40)
True
>>> rl.allow("k", 1, 50)
True
>>> rl.allow("k", 2, 20)
False
>>> rl.allow("k", 12, 20)
True

Step-by-Step Approach

1. Store, per key, a log of (timestamp, tokens) pairs for admitted requests — a dict[str, deque[tuple[float, int]]] works well because you need cheap eviction from the front and cheap appends at the back.
2. Also track a running token sum per key, so you never have to re-sum the whole log on every call — that's what turns this from an O(window size) check into an amortized O(1) one.
3. On each allow(key, timestamp, tokens) call, compute the window cutoff: cutoff = timestamp - window_seconds. Any logged entry with timestamp <= cutoff is now outside the rolling window.
4. Evict stale entries from the front of that key's deque while the oldest entry is <= cutoff, subtracting each evicted entry's tokens from the running sum as you go.
5. After eviction, check whether running_sum + tokens <= max_tokens. If so, admit: append the new entry, add its tokens to the sum, return True. Otherwise return False without recording anything (a rejected request shouldn't count against future decisions).
6. Handle edge cases: a single request whose own token count exceeds max_tokens is always rejected regardless of history, and a request landing exactly at the cutoff timestamp is treated as already stale (the window is a trailing, half-open interval).

The key insight is the same as a plain sliding-window-log rate limiter, plus one more piece of running state: because entries are evicted from the front in append order and never re-scanned, maintaining a running sum alongside the deque keeps each call amortized O(1) instead of re-summing the window every time.

Reference solution

from collections import deque


class TokenRateLimiter:
    def __init__(self, max_tokens: int, window_seconds: float):
        self.max_tokens = max_tokens
        self.window_seconds = window_seconds
        # per key: deque of (timestamp, tokens), and a running sum of tokens currently in-window
        self._log: dict[str, deque[tuple[float, int]]] = {}
        self._sum: dict[str, int] = {}

    def allow(self, key: str, timestamp: float, tokens: int) -> bool:
        log = self._log.setdefault(key, deque())
        cutoff = timestamp - self.window_seconds
        cur_sum = self._sum.get(key, 0)
        # evict stale entries from the front; deque stays sorted by append order
        while log and log[0][0] <= cutoff:
            _, stale_tokens = log.popleft()
            cur_sum -= stale_tokens
        if cur_sum + tokens <= self.max_tokens:
            log.append((timestamp, tokens))
            cur_sum += tokens
            self._sum[key] = cur_sum
            return True
        # keep the running sum in sync even on rejection (eviction still happened)
        self._sum[key] = cur_sum
        return False

Key Functions & Tricks

• collections.deque — O(1) append/pop at both ends, vs. O(n) for list.pop(0)
• dict.setdefault(key, deque()) — lazily initializes a new key's log in one expression
• Running token sum alongside the deque — avoids re-summing the window on every call, the difference between amortized O(1) and O(window size) per call
• while log and log[0][0] <= cutoff: ... — evicts stale entries; sorted-by-append-order means only the front ever needs checking
• Persisting the updated sum on rejection too — eviction still happened even when the request itself is denied, so state must stay correct either way

How to Recognize This Pattern