FA-73342 / Rate limiter algorithms / Member archive

Token bucket with lazy exact refill: refill not capped at capacity · case 02

After an idle period a client can burst far beyond the configured capacity.

Member previewVariant 2 · 3 implementations · 8 checks per implementation

Case contract

Input {capacity, rate (tokens per second), requests [[t_ms, cost]]}. The bucket starts full at t=0. At each request, elapsed = max(0, t - last); tokens = min(capacity, tokens + elapsed*rate/1000) in exact rational arithmetic; last = max(last, t) so a regressing clock neither drains nor re-credits. A cost above capacity can never succeed ("never"). Otherwise allow when tokens >= cost and deduct; else deny with wait = ceil((cost - tokens) * 1000 / rate) ms. Return [[decision, wait]], final tokens].

Why this case matters

API gateways and client SDKs meter requests with lazily refilled token buckets; the refill, clock and boundary rules decide who is throttled and what wait is advertised.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
idle overflow capped	`[[["allow", 0], ["allow", 0], ["allow", 0], ["allow", 0]], "123/5"]`	`[[["allow", 0], ["allow", 0], ["deny", 332], ["deny", 134]], "3/5"]`	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.