The limiter that allows twice its advertised limit

Your hypothetical API allows ten requests per second. A client sends ten at 09:00:00.990 and another ten at 09:00:01.010. Your counter reports no violation. The backend sees twenty requests in twenty milliseconds.

The code is doing exactly what you asked. The contract is the bug.

Decide what ten per second should mean

A fixed window counts within calendar-aligned intervals. It can admit two full windows around a boundary. This can be acceptable for a calendar quota, but it does not smooth work.

Imagine permissions accumulating while the client is idle. A request spends permission; idle time restores it up to a ceiling. Now the token bucket has a reason to exist.

For capacity $b$, refill rate $r$, request cost $c$, stored tokens $T$, and elapsed time $\Delta t$:

$$T' = \min(b, T + r\Delta t)$$

Admit only if $T' \ge c$, then store $T'-c$. Refill, decision, debit, and timestamp update are one state transition. Starting with a full bucket, admitted cost in any interval of duration $t$ is bounded by:

$$A(t) \le b + rt$$

This is an upper bound, not a promise that every possible arrival pattern attains it. Weighted requests spend multiple tokens; a request whose cost exceeds capacity can never succeed under that rule.

Trace the bucket yourself

Assume $b=4$, $r=2$ tokens/second, and each request costs one. At time zero, five requests arrive together. At 0.25 seconds another arrives; at 0.5 seconds one more arrives.

Here is a runnable Python teaching model. It uses integer microtokens to avoid rounding away partial tokens. Time is supplied explicitly so experiments are deterministic; it is one sequential authority, not a thread-safe distributed service.

pythonCopy
from dataclasses import dataclass

SCALE = 1_000_000  # microtokens per token; timestamps are microseconds

@dataclass
class Bucket:
    capacity: int
    rate: int        # integer tokens per second
    tokens: int      # microtokens
    last_us: int

    def take(self, now_us: int, cost: int = 1) -> bool:
        if self.capacity <= 0 or self.rate <= 0 or cost <= 0:
            raise ValueError("positive capacity, rate, and cost required")
        now_us = max(now_us, self.last_us)  # backward time earns nothing
        self.tokens = min(self.capacity * SCALE,
                          self.tokens + (now_us - self.last_us) * self.rate)
        self.last_us = now_us
        debit = cost * SCALE
        if self.tokens < debit:
            return False
        self.tokens -= debit
        return True

The model runs in $O(1)$ time and state per key. It does not solve huge forward clock jumps, process restart, distributed ownership, or persistence. The executable lab exercises the boundary trace, fractional refill, weighted costs, and a randomized admission-bound experiment.

Two workers spend the same final token

Suppose the shared store contains one token. Worker A reads one; worker B reads one. Both decide to admit and store zero. Each line looks correct, but two requests consumed one permission.

A central store alone is insufficient. It must execute the entire transition atomically, using the same authoritative time basis. Redis scripts are one possible boundary: other commands do not interleave with script execution. Keep scripts bounded because they block other server activity while running. Script atomicity does not imply durability across failover. Redis scripting guarantees.

Expiration also changes correctness. A missing bucket usually starts full. If an empty bucket expires after 100 ms when it needs two seconds to refill, every expiry mints extra capacity. For a fixed rule, expire no earlier than the time required to refill completely; premature eviction has the same problem. A failed store call is not evidence of a denied request—the debit may already have happened.

Choose the mechanism by its boundary behavior

For unit-cost GCRA, let $I=1/r$, tolerance $\tau=(b-1)I$, and theoretical arrival time tat. Admit if now >= tat - tau, then set tat = max(now, tat) + I. With an initial tat=now, this admits exactly $b$ simultaneous unit requests. Do not carry this formula into weighted requests without adjusting the cost rule.

A leaky meter rejects excess work; a leaky queue delays it. Calling both “leaky bucket” without describing the queue hides the latency trade-off. At dispatch rate $r$, a backlog of $q$ equal-cost jobs takes about $q/r$ seconds to reach the head, before execution time.

Tell the caller something actionable

For a replenishing bucket, a positive deficit of $c-T'$ tokens needs $(c-T')/r$ seconds. A whole-second Retry-After rounds up. Return 429 for this client's quota rejection; overload shedding is a different policy, commonly expressed as 503. Do not return a finite wait for a permanently impossible cost greater than the capacity.

Mental model: the limiter is a tiny state machine enforcing a named envelope. Its correctness lives in the atomic transition, the clock, and the lifetime of that state.

Transfer: the expensive report

---

Source trail: 02-distributed-rate-limiting, 14-rate-limiting-algorithms. See the source map for consolidation and reference-retained material.