Distributed Rate-Limit Reservations and Refunds: One Shared Capacity Ledger for Concurrent Requests

Three gateways each see that a tenant has 1,000 tokens remaining, so they simultaneously admit three requests estimated to consume 600 each; the executor ultimately uses only 200, and the client retries after timing out. Checking remaining > 0 only once at ingress oversells capacity, charging only after success leaves concurrency unbounded, and immediately issuing a full refund on timeout may let a still-running request occupy capacity for free.

API Rate-Limiting Strategies introduces fixed windows, sliding windows, and token buckets, while LLM Rate Limiting and Quotas discusses common dimensions. This article no longer compares algorithms. Instead, it handles the state between estimated cost, actual usage, and cancellation: how one admission first reserves capacity, then settles or releases it exactly once.

Freeze Policy Generation and Reservation Identity

Publish admissionBudget.v1, fixing the subject key, route, region, capacity unit, refill rule, burst, estimator digest, maximum single reservation, hold TTL, priority, emergency mode, and policy generation. RFC 2697 describes token-bucket meter parameters, but business reservations across gateways still require a linearizable ledger; RFC 6585's 429 only indicates too many requests and may carry Retry-After, not prove how the internal balance is calculated.

limitReservation.v1 stores the reservation ID, canonical request digest, subject, policy generation, accounting epoch, reserved units, actual units, operation ID, expiresAt, and state. The same idempotency key with a different request digest must be rejected. States are REQUESTED -> RESERVED -> STARTED -> SETTLED; an unstarted reservation can move to RELEASED, while expiry contention enters EXPIRING -> EXPIRED; a lost debit response becomes RESERVATION_UNKNOWN, and an unknown execution result becomes USAGE_UNKNOWN.

schema: limitReservation.v1
reservation: rl-01J...
subject: tenant-7/chat.generate
policyGeneration: 31
accountingEpoch: 2026-07-19T14:00Z
requestDigest: sha256:71a...
reservedUnits: 600
state: RESERVED

Only the Ledger May Spend Capacity

The sole admission point, reserveCapacity, locks (subject, route, accountingEpoch, policyGeneration) in a linearizable transaction, and reduces available capacity only after writing a reservation receipt. Duplicate requests return the same receipt. When a connection drops, query using the original reservation ID; do not change the ID and deduct again. Offline emergency capacity may be moved atomically from available into retiredForEmergency by the central ledger only while healthy, then issue non-overlapping signed emergencyShard.v1 instances; after a partition, the central balance must not be copied ad hoc.

Before starting, the executor uses CAS to change RESERVED to STARTED and bind an operation ID; an expiry task may only turn items still in RESERVED into EXPIRED. A completion receipt supplies actual units, and settleUsage atomically writes SETTLED and returns the unused difference. If actual usage exceeds the reservation, consume available capacity first; record all of the remainder in overdraftIssued and spent, set the state to SETTLED_WITH_DEBT, and immediately suspend new admission for that subject/route. The policy specifies the maximum overdraft and a hard execution limit; excess usage must still record the full breach debt and freeze the route, rather than being removed from the conservation equation.

Central conservation is opening + minted + overdraftIssued = available + reserved + spent + retiredForEmergency + overdraftRepaid; debt is issued - repaid. Subsequent refills write overdraftRepaid first, and admission resumes only after the debt reaches zero. Each emergency shard additionally satisfies allocated = localAvailable + localReserved + localSpent + localRetired, and is bound to gateway identity, boot epoch, fence, expiry, and signature. A restart cannot inherit an old shard; after reconnecting, only terminal receipts can remint confirmed unused capacity under a new generation, while used capacity and UNKNOWN remain retired. AI Platform Tenant Quotas handles multidimensional limits, and Prepaid Credits Reservation and Settlement is a financial-value ledger; they must not share a source of truth.

Fairness is addressed after capacity conservation. A scheduler may select already-RESERVED requests by tenant weight and priority, but it cannot bypass the ledger. Rejection responses carry the matched policy generation, limiting dimension, and a conservative Retry-After, without exposing other tenants' balances. Recovery from call timeouts and unknown effects follows Cross-Service Deadlines: cancellation propagation does not mean execution has stopped; only an operation receipt can resolve USAGE_UNKNOWN.

Test Conservation with Duplicates, Timeouts, and Generation Switches

Fault injection covers two gateways reserving simultaneously, contention between STARTED and EXPIRED, actual usage exceeding the reservation, lost debt-repayment ACKs, central-ledger partitions, two gateways reusing a shard, replaying an old shard after process restart, duplicate recovery of unused capacity, lost refund ACKs, and cross-generation behavior. Assert conservation for the central ledger and every shard, that available never becomes negative, that admission is 0 while debt remains outstanding, that duplicate refunds/recovery are 0, and that UNKNOWN is not treated as unconsumed.

Release gates require central/shard conservation discrepancies, overspending, second reservations, duplicate shard consumption, and unrecorded debt all to be 0 across one million interleavings; UNKNOWN p99 must converge within 10 minutes, and each tenant's error must remain within its fairness budget. Roll out in shadow mode first, then enable real reservations for 1% of routes; keep emergency shards disabled initially. Rollback stops admission for the new generation, but retains settlement, debt, and shard-reconciliation workers until everything reaches zero; the old rate limiter may spend only its own preallocated budget and must never return an entire block of retired capacity.