FA-73794 / Rate limiter algorithms / Member archive

Rolling window over a ring of sub-window counters: rolling total includes expired slots · case 04

After an idle period, slots from long ago still count toward the limit.

Member previewVariant 4 · 3 implementations · 6 checks per implementation

Case contract

Input {slots N, slot_ms B, limit, requests [t]} with nondecreasing t. Epoch e = t div B maps to slot e mod N; each slot remembers the epoch it counts and is zeroed when reused for a newer epoch. The rolling total sums slots whose epoch lies in (e - N, e]. Admit while total < limit and count the request in the current slot. Return [decisions, slot counts, slot epochs].

Why this case matters

Rolling-window limiters in service meshes keep a ring of small buckets; forgetting to zero reused buckets or summing stale ones replays old traffic into current decisions.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
long idle gap	`[["allow", "allow", "allow", "deny", "deny"], [1, 1, 0], [0, 25, -1]]`	`[["allow", "allow", "allow", "allow", "deny"], [1, 2, 0], [0, 25, -1]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.