Rate limit system architecture, in depth: rate vs concurrency limits, cost-weighted budgets, tenant fairness and adaptive clients

Three questions every limit answers

Every limit in the system, however implemented, answers three questions. What is counted: requests, bytes, tokens, CPU seconds, or dollars. Who is keyed: an API key, a user, a tenant, an IP address, a route, or a combination. And what happens at the limit: reject with an error, queue and wait, degrade to a cheaper response, or shed. Writing these down per limit exposes most design mistakes before any code exists, such as counting requests when cost lives in tokens, or keying by IP when a whole company sits behind one NAT.

Limits also exist for different reasons, and the reason decides the design. A quota limit enforces a commercial plan and must be accurate and auditable. A protection limit keeps a backend alive and must be fast and adaptive, even at the price of accuracy. A fairness limit divides shared capacity between tenants. Mixing these into one bucket produces a limit that is either too strict for the plan or too loose to protect anything.

Rate limits and concurrency limits are different controls

A rate limit caps how many units start per unit time. A concurrency limit caps how many are in progress at once. Little's law ties them together: the average number in flight equals the arrival rate times the average time in the system, L = λ × W. At 100 requests per second and 200 milliseconds each, about 20 are in flight. If the backend slows to 2 seconds per request, the same 100 per second now means 200 in flight, ten times the memory, connections and GPU slots, while a rate limiter still sees exactly 100 per second and lets everything through.

That is why protection limits should usually be concurrency limits. They respond to slowness automatically: when latency rises, slots free up more slowly and admission falls without anyone changing a number. Rate limits remain the right tool for quotas and for smoothing bursts against external providers that publish per-minute limits. A robust system applies both: rate and cost limits at the edge for plans and fairness, and a concurrency limit in front of each backend for survival.

Cost-weighted limits: reserve, then reconcile

For LLM traffic a request is a bad unit. One call sends 200 tokens and receives 50; another sends 100,000 and receives 4,000. Counting both as one request lets a tenant consume capacity a thousand times faster than the plan intended. The fix is to charge each request its cost in a bucket denominated in that cost, such as tokens per minute. The difficulty is that the true cost is only known after the response ends.

The standard answer is to reserve an upper bound before admission and reconcile afterwards. At the gateway, count the input tokens (or estimate them from bytes), add the request's maximum output tokens, and debit that from the tenant's token bucket. If the bucket cannot cover it, reject now. When the response completes, compute the actual usage and refund the difference. Requests without an output cap get a default cap, because an unbounded reservation is no reservation.

import time, threading

class CostBucket:
    # Token bucket denominated in cost units (e.g. LLM tokens), refilled continuously.
    def __init__(self, capacity, refill_per_sec):
        self.capacity, self.rate = capacity, refill_per_sec
        self.level, self.t = capacity, time.monotonic()
        self.lock = threading.Lock()

    def _refill(self):
        now = time.monotonic()
        self.level = min(self.capacity, self.level + (now - self.t) * self.rate)
        self.t = now

    def reserve(self, amount):
        with self.lock:
            self._refill()
            if amount > self.capacity:
                return None, None                         # can never fit: reject outright
            if amount > self.level:
                deficit = amount - self.level
                return None, deficit / self.rate          # retry-after seconds
            self.level -= amount
            return amount, 0.0

    def reconcile(self, reserved, actual):
        with self.lock:
            self._refill()
            self.level = min(self.capacity, self.level + (reserved - actual))

# Gateway use
req.max_tokens = min(req.max_tokens or 1024, 4096)      # clamp the request itself
reserved, wait = bucket.reserve(input_tokens + req.max_tokens)
if reserved is None:
    return http_400("request too large") if wait is None else http_429(retry_after=wait)
resp = None
try:
    resp = call_model(req)
finally:
    bucket.reconcile(reserved, actual_tokens(resp) if resp else 0)

The finally block matters: a request that errors must still release its reservation, or every failure permanently shrinks the tenant's budget. In a distributed gateway the same pattern runs against a shared store, with the reserve as an atomic script and the reconcile as a separate increment; a lost reconcile only ever errs toward being too strict, which is the safe direction.

Fairness between tenants

Per-tenant buckets stop any one tenant exceeding its plan, but they do not divide capacity fairly when the backend is the bottleneck. If ten tenants are each within plan and the backend can serve only half of what they collectively send, a single first-in-first-out queue gives capacity to whoever sends fastest. Fair queuing fixes this by giving each tenant its own queue and serving the queues in rotation, weighted by plan.

Deficit round robin is the simplest fair scheduler that handles variable-cost requests. Each tenant queue has a quantum proportional to its weight and a deficit counter. On each visit the counter grows by the quantum, and the scheduler dequeues requests while the head request's cost fits within the counter. Expensive requests wait for the counter to build up, so a tenant sending huge prompts gets the same token share as one sending small ones.

from collections import deque

class DRR:
    def __init__(self):
        self.queues, self.quantum, self.deficit = {}, {}, {}
        self.active = deque()

    def enqueue(self, tenant, req, weight=1.0, base_quantum=2000):
        if tenant not in self.queues:
            self.queues[tenant] = deque()
            self.quantum[tenant] = base_quantum * weight
            self.deficit[tenant] = 0.0
        if not self.queues[tenant]:
            self.active.append(tenant)
        self.queues[tenant].append(req)

    def next_batch(self):
        # One round: yields requests in fair order, cost-weighted.
        for _ in range(len(self.active)):
            t = self.active.popleft()
            q = self.queues[t]
            self.deficit[t] += self.quantum[t]
            while q and q[0].cost <= self.deficit[t]:
                req = q.popleft()
                self.deficit[t] -= req.cost
                yield req
            if q:
                self.active.append(t)
            else:
                self.deficit[t] = 0.0          # idle tenants do not bank credit

Queues need bounds of their own. Give each tenant queue a maximum depth and a maximum wait; a request that would wait longer than its own timeout should be rejected immediately with a retry hint, because serving it after the client has given up wastes exactly the capacity that is scarce.

Adaptive concurrency in front of the backend

A fixed concurrency limit has to be tuned and goes stale as hardware, models and traffic mix change. An adaptive limit finds the right value continuously. The simplest scheme borrows additive increase, multiplicative decrease from TCP congestion control: while requests complete within a latency target and without overload errors, raise the limit slowly; when latency exceeds the target or the backend signals overload, cut it sharply.

class AIMDLimit:
    def __init__(self, initial=20, lo=2, hi=500, target_ms=800, backoff=0.7):
        self.limit, self.lo, self.hi = float(initial), lo, hi
        self.target, self.backoff = target_ms, backoff
        self.in_flight = 0

    def try_acquire(self):
        if self.in_flight >= int(self.limit):
            return False
        self.in_flight += 1
        return True

    def release(self, latency_ms, overloaded):
        self.in_flight -= 1
        if overloaded or latency_ms > self.target:
            self.limit = max(self.lo, self.limit * self.backoff)
        else:
            self.limit = min(self.hi, self.limit + 1.0 / self.limit)  # about +1 per window

Pick the latency target from the backend's service objective, not from its average, and count only overload signals (timeouts, explicit overload responses, queue-full errors) as congestion; a 404 says nothing about capacity. Each gateway instance runs its own limiter, which makes the system resilient to a failed coordinator at the cost of some unevenness. When the concurrency limit is full and the fair queue is at its bounds, the remaining step is to shed, which is covered in load shedding.

The client half of the system

A server can only refuse work; clients decide whether refusals turn into a retry storm. Every client of a limited API should honour Retry-After when present, use exponential backoff with full jitter otherwise, and cap retries. The Google SRE book's Handling Overload chapter adds two mechanisms worth copying. The first is a retry budget at two levels: a per-request limit of up to three attempts, and a per-client rule that a request is retried only while retries make up less than 10% of that client's requests, so a widespread failure cannot multiply load.

The second is client-side adaptive throttling. Over the last two minutes each client tracks requests (what the application attempted) and accepts (what the backend accepted). Once requests exceeds K times accepts, the client starts rejecting new requests locally with a probability that grows with the gap; the book prefers K = 2. The equation appears as an image in the book; it is usually reproduced as the text below. Locally rejected requests never reach the overloaded backend, so a struggling service sees its load fall quickly even with thousands of clients.

import random

def should_send(requests, accepts, k=2.0):
    # requests, accepts: counts over a sliding two-minute window
    p_reject = max(0.0, (requests - k * accepts) / (requests + 1))
    return random.random() >= p_reject

Worked example: an LLM gateway under a spike

A gateway serves three tenants in front of a model cluster. Tenant A has a 2,000,000 tokens-per-minute plan with weight 4, B and C have 500,000 each with weight 1. The cluster comfortably serves about 1,500,000 tokens per minute at a p95 latency of 6 seconds. At 10:00, A launches a batch backfill and starts sending 3,000,000 tokens per minute of long prompts, while B and C carry on at normal interactive load of about 200,000 each.

A's cost bucket admits only up to its plan rate after its initial burst capacity drains, and returns 429 with Retry-After for the rest. Even so, A plus B plus C now want about 2,400,000 tokens per minute against 1,500,000 of capacity. Latency rises, the AIMD limiter sees p95 pass its target and cuts concurrency, and work backs up in the fair queue. Deficit round robin serves tenants in proportion to weight, 4 : 1 : 1, so B's and C's requests, at 200,000 each against a share of 250,000, drain promptly; A absorbs the queueing and its oldest requests hit the per-tenant wait bound and are rejected with a retry hint.

A's client library, seeing its accepts fall well below its requests, starts throttling locally, so the 429s stop costing the gateway anything. Ten minutes later the backfill is still running at whatever capacity is left over, interactive tenants never noticed, and the cluster stayed within its latency objective. Without the fair queue, A's volume would have filled a single FIFO and B and C would have timed out.

Failure modes

Trade-offs

Accuracy competes with latency and availability: a globally consistent counter is accurate and adds a network hop and a dependency to every request, while local limiters are fast and drift. Use accurate shared state for commercial quotas and local adaptive limits for protection. Rejecting fast is kind to clients and wastes nothing, while queuing smooths bursts but adds latency and memory; queue only up to the point where a request could still meet its deadline. Fairness by weight protects small tenants and can leave capacity idle if quanta are badly sized, so let unused share flow to whoever is waiting. Every control here is also something to observe: export admitted, rejected, queued and reconciled cost per tenant, or none of these tuning decisions can be made from evidence. For tool servers behind agents, the same pieces apply, as discussed in MCP rate limiting.

What to do next

1. List every limit you have and write down what it counts, how it is keyed, why it exists and what happens at the limit.
2. Switch LLM limits from requests to tokens, reserving input plus capped output and reconciling on completion in a finally path.
3. Put a concurrency limit in front of each backend, then make it adaptive with a latency target from the service objective.
4. Replace any shared FIFO in front of a scarce backend with per-tenant fair queuing, with depth and wait bounds.
5. Ship a client library that honours Retry-After, uses jittered backoff, enforces retry budgets and throttles adaptively.
6. Export per-tenant admitted, rejected and queued cost, and run a load test where one tenant floods while others stay steady.