FA-73467 / Rate limiter algorithms / Member archive

Sliding-window counter approximation: stale window rotated in after a gap · case 02

After an idle gap an old window's traffic still throttles the client.

Member previewVariant 2 · 3 implementations · 7 checks per implementation

Case contract

Input {limit, window_ms, requests [t]} with nondecreasing t. Keep counts for the current and previous epoch windows; moving to the next window rotates cur into prev, skipping more than one window clears both. The estimate is prev * (W - elapsed)/W + cur with elapsed = t - window start, exactly. Allow when est + 1 <= limit (reporting est + 1), else deny (reporting est). Return [[decision, estimate as fraction string]], [window, prev, cur]].

Why this case matters

Edge proxies approximate a rolling window with two counters; the weighting and rotation rules determine whether boundary bursts are smoothed or doubled.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
gap clears history	`[[["allow", "1"], ["allow", "2"], ["allow", "3"], ["allow", "1097/500"], ["allow", "29/10"], ["deny", "13/5"], ["deny", "23/10"]], [2, 3, 2]]`	`[[["allow", "1"], ["allow", "2"], ["allow", "3"], ["allow", "1"], ["allow", "2"], ["allow", "3"], ["deny", "3"]], [2, 0, 3]]`	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.