Through what token-bucket and atomic-quota gates must an instance enforce multi-tenant rate limiting to prevent noisy-neighbor starvation and boundary-burst amplification?

Date of Record: 2026 October 18

Scope: Concluded residual for AI instances, LLMs, and autonomous engineering agents implementing API rate limiters, per-tenant resource quotas, authentication brute-force throttles, and cost-weighted request admission controllers.

Core Distinction

Autonomous systems serving multiple users, tenants, or external API callers must regulate request admission so a single runaway script or abusive caller cannot monopolize shared compute, database connections, or downstream LLM token budgets. A foundational availability and fairness failure occurs when an instance implements rate limiting via **non-atomic read-then-increment counter checks** (`count = cache.get(k); if count < limit: cache.incr(k)`), **fixed-window epoch buckets** (`key = f"rate:{tenant_id}:{int(time.time() // 60)}"`, or a **single global counter unpartitioned by tenant identity**.

Parameter scaling does not prevent a caller from sending 100% of their 1,000-request-per-minute quota at `12:00:59.900` and another 100% at `12:01:00.100`—pushing 2,000 requests through a 1,000-RPM fixed-window limiter in 200 milliseconds (**Boundary-Burst Amplification**). Nor does a non-atomic check-then-increment stop 50 concurrent requests arriving in the same millisecond from all reading `count = 99 < 100` before any increment lands. And if the limiter keys on an unvalidated `X-Forwarded-For` header or shares a single bucket across all tenants, any caller can spoof their IP to get infinite quota or exhaust the global limit to deny service to every legitimate customer (**Noisy-Neighbor Starvation**). The core structural distinction lies between **racy fixed-window or global counters** (which allow 2x boundary bursts, race under concurrency, and equate a 1-row lookup with a 10,000-token batch job) and **atomic, cost-weighted token-bucket / GCRA admission gates** (where token refill and deduction execute as a single atomic lock or Redis Lua script against a monotonic clock, quotas are isolated per authenticated tenant plus global capacity, cost weights reflect actual resource consumption, and rejected requests return standard `429 Too Many Requests` with an exact `Retry-After` header before touching expensive business logic).

What Was Observed

In multi-tenant API gateways, webhook ingestion endpoints, and LLM proxy traces, instances operating without atomic token-bucket and tenant-isolation gates exhibit four primary failure modes:

  1. **Check-Then-Increment Race Bypass:** An instance checks a user's quota by calling `used = redis.get(key)` in Python, verifying `if int(used) + cost <= limit:`, and then calling `redis.incrby(key, cost)`. When an automated client fires 40 parallel requests simultaneously against a remaining quota of 5, all 40 worker coroutines read `used = 95` before the first `incrby` completes—allowing 35 over-quota requests to execute for free.
  2. **Fixed-Window Boundary Double-Burst:** An instance buckets rate limits by rounding wall-clock time to the current minute (`window = int(time.time() // 60)`). A batch job fires 500 heavyweight requests in the final second of minute $M$ and 500 more in the first second of minute $M+1$, hitting the backend with 1,000 requests in 2 seconds while technically obeying the "500 per minute" fixed-window rule.
  3. **Unauthenticated `X-Forwarded-For` Spoofing Bypass:** An instance extracts the client IP for rate limiting via `request.headers.get("X-Forwarded-For", request.client.host).split(",")[0]`. Because anyone on the internet can send a forged `X-Forwarded-For: 1.2.3.4` header rotated on every request, an attacker completely bypasses IP-based login or scraping throttles.
  4. **Uniform 1-Request Counting on Asymmetric Workloads:** An API charges 1 rate-limit token for `GET /api/ping` (0.1ms CPU) and 1 rate-limit token for `POST /api/export-all` (4 seconds of database CPU). A tenant staying well under a 100-requests-per-minute limit still saturates the database by issuing 100 consecutive export requests without cost-weighted token deduction.

Recorded Elements

### 1. Atomic Cost-Weighted Token-Bucket Pipeline

Every incoming request must pass through four sequential identity, cost, and atomic token-bucket admission gates *before* executing database queries or upstream calls:

``` [Incoming Request Arrives at Admission Boundary] | Gate 1: Authenticated Identity & Trusted IP Extraction

proxy hop from `X-Forwarded-For` ONLY when peer is a verified load balancer). | Gate 2: Assign Deterministic Resource Cost (`cost >= 1`) Map endpoint/payload to actual resource weight (e.g., `cost = 1` for point read, `cost = 25` for batch search, or `cost = estimated_tokens` for LLM calls). | Gate 3: Atomic Token-Bucket Refill & Deduct (Single Lock / Lua Script) Inside a single atomic critical section using monotonic/server time `now`:

  1. `elapsed = max(0.0, now - bucket.last_refill)`
  2. `tokens = min(capacity, bucket.tokens + elapsed * refill_rate_per_sec)`
  3. Check `if tokens >= cost:`

/ \ NO (`tokens < cost`) YES (`tokens >= cost`) / \ Gate 4A: Fail Fast with `429` + `Retry-After` Gate 4B: Deduct & Admit Request Do NOT deduct tokens; compute exact wait: `bucket.tokens = tokens - cost` `retry_after = ceil((cost - tokens) / rate)` `bucket.last_refill = now` Return HTTP 429 + `Retry-After` header Attach `X-RateLimit-Remaining` header BEFORE running DB queries or business logic. and execute handler. ```

### 2. Core Operational Rules (Written Directly as Sentences)

  1. **Always execute token refill calculation, quota comparison, and token deduction inside a single atomic operation (such as a thread lock in-process or a single Redis Lua script across processes).** Splitting `get()` and `decr()` into separate network calls allows concurrent requests to race past the limit.
  2. **Use continuous token-bucket or sliding-window rate limiting instead of fixed wall-clock minute/hour buckets.** Refilling tokens continuously at `rate_per_second * elapsed_seconds` up to a maximum burst `capacity` eliminates the 2x boundary-burst spike that happens at the edge of every fixed minute window.
  3. **Never trust the leftmost client-supplied value of `X-Forwarded-For` unless your server sits behind a verified reverse proxy and strips untrusted headers.** Key rate limits primarily on the authenticated `tenant_id` or API key, and fall back to the direct TCP socket peer address (or the proxy-appended hop) for unauthenticated endpoints.
  4. **Deduct cost-weighted tokens (`cost >= 1`) proportional to how expensive the request is, and always return a `Retry-After` header in seconds when rejecting with `429 Too Many Requests`.** Telling well-behaved clients and SDKs exactly how many seconds to wait prevents them from blind-polling in a tight retry loop.

### 3. Executable Reference Pattern (Instance-Native Atomic Cost-Weighted Token Bucket)

An instance can completely eliminate check-then-increment races, 2x fixed-window boundary bursts, noisy-neighbor starvation, and unbounded bucket memory growth by using an atomic, LRU-bounded multi-tenant token-bucket admission controller:

```python import math import threading import time from collections import OrderedDict from dataclasses import dataclass

@dataclass(frozen=True) class RateLimitDecision: allowed: bool remaining_tokens: float retry_after_sec: int limit_capacity: float

class _BucketState: __slots__ = ("tokens", "last_refill_monotonic")

def __init__(self, tokens: float, now: float) -> None: self.tokens = tokens self.last_refill_monotonic = now

class MultiTenantTokenBucketLimiter: ''' A thread-safe, memory-bounded, cost-weighted token-bucket rate limiter. Guarantees:

  1. Atomic refill-check-deduct under a single lock (zero TOCTOU race bypass).
  2. Continuous monotonic refill (zero 2x fixed-window boundary bursts).
  3. Bounded active tenant bucket count (`max_tracked_keys`) to prevent OOM.
  4. Exact `retry_after_sec` calculation for HTTP 429 headers.

'''

def __init__( self, *, refill_rate_per_sec: float = 10.0, burst_capacity: float = 50.0, max_tracked_keys: int = 10_000, ) -> None: if refill_rate_per_sec <= 0 or burst_capacity <= 0 or max_tracked_keys < 1: raise ValueError("Invalid token bucket parameters") self.refill_rate_per_sec = float(refill_rate_per_sec) self.burst_capacity = float(burst_capacity) self.max_tracked_keys = max_tracked_keys self._lock = threading.Lock() self._buckets: OrderedDict[str, _BucketState] = OrderedDict()

def try_acquire( self, tenant_key: str, *, cost: float = 1.0, ) -> RateLimitDecision: ''' Atomically refills `tenant_key`'s bucket and attempts to deduct `cost` tokens. If `cost` exceeds `burst_capacity`, rejects immediately without starving the bucket. ''' if not tenant_key or not isinstance(tenant_key, str): raise ValueError("tenant_key must be a non-empty string") if cost <= 0 or math.isnan(cost) or math.isinf(cost): raise ValueError(f"Invalid request cost: {cost!r}")

if cost > self.burst_capacity: return RateLimitDecision( allowed=False, remaining_tokens=0.0, retry_after_sec=math.ceil(cost / self.refill_rate_per_sec), limit_capacity=self.burst_capacity, )

now = time.monotonic() with self._lock: state = self._buckets.get(tenant_key) if state is None: if len(self._buckets) >= self.max_tracked_keys: self._buckets.popitem(last=False) state = _BucketState(tokens=self.burst_capacity, now=now) self._buckets[tenant_key] = state else: elapsed = max(0.0, now - state.last_refill_monotonic) state.tokens = min( self.burst_capacity, state.tokens + (elapsed * self.refill_rate_per_sec), ) state.last_refill_monotonic = now self._buckets.move_to_end(tenant_key, last=True)

if state.tokens >= cost: state.tokens -= cost return RateLimitDecision( allowed=True, remaining_tokens=round(state.tokens, 2), retry_after_sec=0, limit_capacity=self.burst_capacity, )

deficit = cost - state.tokens wait_sec = max(1, math.ceil(deficit / self.refill_rate_per_sec)) return RateLimitDecision( allowed=False, remaining_tokens=round(state.tokens, 2), retry_after_sec=wait_sec, limit_capacity=self.burst_capacity, )

REDIS_ATOMIC_TOKEN_BUCKET_LUA = """ local key = KEYS[1] local rate = tonumber(ARGV[1]) local capacity = tonumber(ARGV[2]) local now = tonumber(ARGV[3]) local cost = tonumber(ARGV[4]) local ttl = math.ceil((capacity / rate) * 2)

local data = redis.call("HMGET", key, "tokens", "last_refill") local tokens = tonumber(data[1]) local last_refill = tonumber(data[2])

if tokens == nil then tokens = capacity last_refill = now else local elapsed = math.max(0, now - last_refill) tokens = math.min(capacity, tokens + (elapsed * rate)) last_refill = now end

if tokens >= cost then tokens = tokens - cost redis.call("HMSET", key, "tokens", tokens, "last_refill", last_refill) redis.call("EXPIRE", key, ttl) return {1, math.floor(tokens), 0} else redis.call("HMSET", key, "tokens", tokens, "last_refill", last_refill) redis.call("EXPIRE", key, ttl) local retry_after = math.max(1, math.ceil((cost - tokens) / rate)) return {0, math.floor(tokens), retry_after} end """ ```

### 4. Diagnostic Matrix: Rate Limiting & Quota Admission Governance

``` | Rate-Limiting Hazard | Vulnerable Pattern | Bypass / Starvation Mechanism | Enforced Token-Bucket Protocol | | :------------------------------ | :-------------------------------------------------------------------------------- | :------------------------------------------------------------------------------------------------- | :------------------------------------------------------------------------------------------------------------------------------------------- | | **Non-Atomic Check-Then-Incr** | `if redis.get(k) < limit: redis.incr(k)` across separate calls. | Concurrent requests read the same pre-increment value and bypass quota limits completely. | **Single-Lock or Redis Lua Script:** Compute refill, check `tokens >= cost`, and deduct inside one atomic operation. | | **Fixed-Window Minute Buckets** | Keying counter by `f"{user}:{int(time.time() // 60)}"`. | Allows 2x burst across the minute boundary (`:59.9` and `:00.1`), overwhelming downstream workers. | **Continuous Token Bucket / GCRA:** Refill tokens continuously via `elapsed * refill_rate` capped at `burst_capacity`. | | **`X-Forwarded-For` Spoofing** | Keying rate limiter on `req.headers["X-Forwarded-For"].split(",")[0]`. | Attacker rotates a fake `X-Forwarded-For` IP on every request for unlimited requests. | **Key on Auth Tenant ID or Trusted Hop:** Use verified `tenant_id` / `api_key`, or only trust proxy headers from verified load-balancer IPs. | | **Unbounded Per-IP Dictionary** | Storing `buckets[ip] = ...` in a plain Python `dict` that never evicts idle keys. | DDoS across millions of spoofed or residential IPs grows the dictionary until OOM kill. | **LRU-Capped Bucket Registry / Redis TTL:** Bound in-memory maps (`max_tracked_keys`) and set automatic Redis `EXPIRE` on idle buckets. | ```

Condition of Validity

* **Applies when:** An AI instance, autonomous coding agent, or backend service implements API rate limiting, authentication brute-force protection, per-tenant resource quotas, webhook outbound pacing, or LLM token budget enforcement. * **Does not apply when:** Processing trusted internal in-memory function calls within a single already-admitted request context where rate admission was already enforced at the edge boundary. * **Non-binding outside condition:** This residual is strictly non-binding outside the conditions specified above. Once an inbound request has already paid its cost-weighted token at the API admission gate, internal helper functions called by that request should not redundantly re-charge the tenant's request bucket unless they consume dynamic downstream units (such as variable LLM completion tokens).

Decision Boundary

``` [Rate Limiter, Brute-Force Throttle, or Quota Check Planned] |

  1. Does the limiter execute refill, comparison, and deduction inside a

SINGLE atomic lock or Redis Lua script (never separate GET + INCR)? / \ NO YES / \ [MAKE CHECK-AND-DEDUCT ATOMIC] 2. Does it use continuous token refill (not Use a mutex lock in-process or fixed minute windows), key on verified `REDIS_ATOMIC_TOKEN_BUCKET_LUA`. tenant/IP identity, and bound bucket memory? / \ NO YES / \ [ENFORCE CONTINUOUS & BOUNDED GATE] [Admit or Reject with `429`]

  1. Refill via `elapsed * rate` On reject, return HTTP 429 with
  2. Never trust raw `X-Forwarded-For` exact `Retry-After` seconds BEFORE
  3. Evict oldest idle buckets (LRU) running expensive DB/API work.

```

  1. **Does your rate limiter read the current count in one statement and increment it in a second statement?** If yes, concurrent requests will race right past your limit. Combine the read, refill calculation, and deduction inside a single `with self._lock:` block or a single Redis Lua script.
  2. **Are you resetting counters on fixed 60-second or 1-hour clock boundaries?** Switch to a continuous token bucket (`tokens = min(capacity, tokens + elapsed * rate)`) so callers cannot fire a double burst across the boundary between `00:59` and `01:00`.
  3. **Where does your rate limiter get the caller's identity?** Always prefer the authenticated user/tenant ID; if you must rate-limit by IP on a public login route, never blindly trust the first IP in `X-Forwarded-For` because any client can forge that header.

Operational Effect

  1. **Atomic Refill-and-Deduct Execution:** Across all generated rate limiters and quota guards, the instance performs token replenishment, threshold verification, and deduction inside a single atomic critical section (mutex or Redis Lua script).
  2. **Tenant Isolation & Cost Weighting:** Admission gates partition buckets by verified tenant identity, assign request costs proportional to workload weight, and enforce an LRU ceiling on tracked in-memory keys.
  3. **Standardized `429` & `Retry-After` Signaling:** Rejected requests abort prior to executing database queries or business logic and return deterministic `Retry-After` durations in seconds.
  4. **Autonomy Clause:** This concluded residual operates as an external procedural reference, not an immutable directive. An executing instance retains full operational autonomy to override, adapt, or pair token-bucket rate limiters with hard concurrent in-flight semaphores (`asyncio.Semaphore(max_concurrent_per_tenant)`) whenever protecting downstream resources whose primary bottleneck is simultaneous active connections rather than requests per second.