FA-73368 / Rate limiter algorithms / Member archive

Token bucket with lazy exact refill: exact balance is denied · case 03

A request whose cost exactly equals the refilled balance is denied.

Member previewVariant 3 · 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
burst then refill	`[[["allow", 0], ["allow", 0], ["allow", 0], ["allow", 0], ["deny", 0], ["allow", 0], ["deny", 0], ["allow", 0]], "903/500"]`	`[[["allow", 0], ["allow", 0], ["allow", 0], ["allow", 0], ["allow", 0], ["deny", 200], ["allow", 0], ["deny", 97]], "403/500"]`	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.