Per-Tenant Rate Limiting of Trigger Fan-Out

A rate limiter protects the receiver; a fair-share allocator protects the other senders. A geofence platform fanning triggers out to thousands of tenant endpoints needs both, and conflating them produces the failure this page is about: a single global limiter that a large tenant’s burst saturates, leaving every small tenant’s triggers queued behind traffic that was never theirs. This page sits under webhook fan-out and retry budgets within Event Routing & Backpressure.

Concept and specification #

A token bucket per subscription is the right primitive: it admits a sustained rate $r$ and tolerates a burst of $B$ tokens, which matches how webhook contracts are actually written (“1,000 requests per second, bursts to 5,000”). Tokens accrue continuously and the check is a comparison, so the cost is a few nanoseconds and no timer is involved.

$$\text{tokens}(t)=\min !\left(B,;\text{tokens}(t_0)+r,(t-t_0)\right)$$

The subtlety is what a deny means. Three responses are possible and they are not interchangeable. Waiting for a token converts the limiter into a queue and reintroduces the head-of-line blocking the per-tenant lanes were built to remove. Dropping loses a trigger. Deferring — routing to the dead-letter path for later replay — preserves the trigger and frees the worker, and is the only one of the three that is both bounded and lossless.

The fair-share layer sits above the per-tenant buckets and allocates the platform’s shared resource — worker concurrency, outbound bandwidth, connection slots — among tenants that are all within their own limits but collectively exceed capacity. Max-min fairness is the right default: give every tenant its demand up to an equal share, then redistribute the unused remainder among those that want more, repeating until capacity is exhausted. It has the property that no tenant can improve its allocation by inflating its demand, which a proportional scheme does not.

Step-by-step implementation #

1. Store tokens lazily, never with a refill timer. A timer per tenant is the same timer-storm problem as dwell triggers; computing the accrual on read is exact and free.

from __future__ import annotations
from dataclasses import dataclass
import time

@dataclass(slots=True)
class TokenBucket:
    rate: float          # tokens per second, from the contract
    burst: float         # bucket capacity
    tokens: float = 0.0
    last: float = 0.0

    def take(self, n: float = 1.0, now: float | None = None) -> bool:
        t = now if now is not None else time.monotonic()
        if self.last == 0.0:
            self.last, self.tokens = t, self.burst
        self.tokens = min(self.burst, self.tokens + (t - self.last) * self.rate)
        self.last = t
        if self.tokens >= n:
            self.tokens -= n
            return True
        return False                       # DENY: caller defers, never waits

    def deficit_s(self, n: float = 1.0) -> float:
        """How long until n tokens exist — for the DLQ's replay-after hint."""
        return max(0.0, (n - self.tokens) / self.rate)

2. Return the deficit with the denial. A deferred trigger should carry a hint about when it becomes deliverable, so the replay scheduler described in replaying dead-letter triggers safely can pace the drain instead of polling.

3. Implement max-min fairness with a single pass over demands. The classic algorithm sorts demands ascending and walks them, which is $O(n\log n)$ per allocation round — fine at a per-second cadence over tens of thousands of tenants.

def max_min_shares(demands: dict[str, float], capacity: float,
                   weights: dict[str, float] | None = None) -> dict[str, float]:
    """Give each tenant its demand up to a fair share, redistributing the rest."""
    w = weights or {k: 1.0 for k in demands}
    remaining, out = capacity, {}
    active = sorted(demands, key=lambda k: demands[k] / w[k])
    total_w = sum(w[k] for k in active)
    for k in active:
        share = remaining * w[k] / total_w if total_w else 0.0
        grant = min(demands[k], share)
        out[k] = grant
        remaining -= grant
        total_w -= w[k]
    return out

4. Measure demand rather than accepting a declared one. A tenant’s demand is what it actually offered in the last window, which the lane’s admission counter already knows. Declared demand is an invitation to inflate.

5. Apply the limiter before the concurrency semaphore, not after. The limiter is a cheap arithmetic check and the semaphore is a scarce resource; checking in that order means a rate-limited trigger never occupies a slot. Reversing them makes a rate-limited tenant hold concurrency while being denied, which is the worst of both.

6. Expose the limit and the remaining tokens to the tenant. Standard RateLimit-Limit and RateLimit-Remaining headers on the delivery request, or a dashboard figure, turn a mysterious gap in a tenant’s trigger stream into a self-service diagnosis.

Benchmark and verification #

Simulated with 4,000 subscriptions, one of which bursts to 40,000 triggers/sec for 90 s against a platform capacity of 60,000/sec:

The single global limiter is the instructive failure: it protects the platform’s aggregate rate and does nothing at all for fairness, because the tokens are consumed by whoever asks first and the bursting tenant asks 40,000 times a second. Its Jain index is indistinguishable from having no limiter at all.

The deny-action row is the largest single improvement in the table: the same per-tenant buckets improve small-tenant P99 by 45× purely by deferring rather than waiting, because waiting holds a worker and defers the worker, not the trigger. And the fair-share layer recovers most of what the large tenant lost — from 68% to 89% delivered — without costing the small tenants anything, because it hands out capacity the small tenants were not using.

Verify with the fairness index rather than with per-tenant graphs, which are unreadable at four thousand tenants. Jain’s index over delivered-to-offered ratios collapses the whole fleet into one number between $1/n$ (one tenant gets everything) and 1 (perfectly fair); alert when it drops below about 0.9, which catches a starving population long before any individual tenant complains.

Failure modes and edge cases #

The monotonic-clock point in the last row is small and bites hard. A bucket accruing against time.time() gains an hour of tokens when the host’s clock steps forward, admitting an unbounded burst, and stalls entirely on a step backwards. time.monotonic() is immune to both, and the same discipline applies everywhere a duration is measured rather than a timestamp recorded — the distinction developed in detecting and correcting device clock drift for device clocks applies just as much to the server’s.

One structural caveat: rate limiting is not backpressure. A limiter shapes what the platform sends; it does not tell the platform’s upstream to produce less. When deferrals become sustained rather than bursty, the correct response is to slow the trigger pipeline itself through the mechanisms in backpressure and flow control strategies, because a dead-letter topic filling at 40,000 triggers/sec is a storage problem arriving a few minutes later.

Related #

• Webhook Fan-Out & Retry Budgets — the parent topic, where these buckets sit inside per-tenant lanes.
• Token Bucket vs Leaky Bucket for Telemetry Shedding — the same primitives applied at ingest rather than egress.
• Replaying Dead-Letter Triggers Safely — where deferred triggers go and how they come back.