FA-73528 / Rate limiter algorithms / Member archive

Hierarchical tenant and global token buckets: tenant charged when the global bucket denies · case 03

A tenant loses its own tokens for requests the shared limit rejected.

Member previewVariant 3 · 3 implementations · 7 checks per implementation

Case contract

Input {tenant_cap, tenant_rate, global_cap, global_rate, requests [[t_s, tenant, cost]]} with nondecreasing whole-second t. Each tenant bucket starts full at its first request and refills from its own last-seen time; the global bucket starts full at t=0. Both refill lazily and are capped by their own capacity. A request needs cost tokens in both; the tenant bucket is checked first ("deny-tenant"), then the global ("deny-global"); both are charged only on admission. Return [decisions, global tokens, sorted [tenant, tokens]].

Why this case matters

Multi-tenant APIs enforce per-tenant and shared limits together; charging or refilling the wrong level leaks capacity between tenants.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
global exhaustion	`[["allow", "allow", "deny-global", "deny-global", "allow"], 3, [["a", 0], ["b", 1], ["c", 2]]]`	`[["allow", "allow", "deny-global", "deny-global", "allow"], 3, [["a", 1], ["b", 1], ["c", 2]]]`	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.