One rate limit, many tenants: fair queues and adaptive throttling

The gateway in the first article answers one question: may this call start now? It rejects a tenant that is over budget, immediately, with a time to retry. That is the right behaviour for interactive traffic. It is the wrong behaviour for the other half of an LLM system's workload: imports, re-indexing, nightly summaries, bulk classification. Batch work does not want to be rejected. It wants to wait its turn, without taking everyone else's.

This article covers the layer that decides whose turn it is. It has two parts: a fair queue that shares capacity between tenants by cost, and an adaptive throttle that paces calls from what the provider says is left of the quota. As in the rest of the series, the code is type-checked and tested in CI.

The problem with one queue

The obvious design is a single job queue: tenants enqueue work, workers take jobs from the front and call the model. It works until the first large customer imports their archive.

Ten thousand summarisation jobs land in the queue in a minute. Every other tenant's jobs, a single document here, a nightly report there, wait behind all ten thousand. Depending on your rate limit that is hours. From the small tenants' point of view the product is broken, and nothing in your monitoring says so, because every component is working exactly as designed.

The problem is not capacity. It is that first-in-first-out treats the queue as one customer. In a multi-tenant system it is many, and fairness has to be between them, not between jobs.

Fair queueing by cost

Fair queueing is an old problem in networking, where many flows share one link, and the solutions transfer directly. We use deficit round robin, which is simple, has constant cost per job and is fair by size rather than by count.

/**
 * Deficit round robin across tenants. Each tenant with work gets a quantum of
 * cost per round (scaled by its weight) and may dequeue jobs while its deficit
 * covers them. A tenant with ten thousand queued jobs gets the same share per
 * round as a tenant with one, so small tenants are never stuck behind a large
 * import. Expired jobs are dropped at dequeue instead of wasting quota.
 */
export class FairQueue<T> {
  private readonly queues = new Map<string, Job<T>[]>();
  private readonly deficit = new Map<string, number>();
  private readonly active: string[] = [];
  private cursor = 0;
  private granted = false;

  constructor(
    private readonly o: { quantum: number; maxPerTenant: number; weight?: (tenantId: string) => number },
    private readonly now: () => number = Date.now,
  ) {}

  enqueue(job: Job<T>): Enqueue {
    let q = this.queues.get(job.tenantId);
    if (!q) { q = []; this.queues.set(job.tenantId, q); }
    if (q.length >= this.o.maxPerTenant) return { ok: false, reason: 'queue_full' }; // backpressure per tenant
    q.push(job);
    if (!this.active.includes(job.tenantId)) { this.active.push(job.tenantId); this.deficit.set(job.tenantId, 0); }
    return { ok: true };
  }

  /** Next job to run, or undefined if nothing is queued. Calls onExpired for dropped jobs. */
  dequeue(onExpired: (job: Job<T>) => void = () => {}): Job<T> | undefined {
    while (this.active.length) {
      if (this.cursor >= this.active.length) this.cursor = 0;
      const tenant = this.active[this.cursor]!;
      const q = this.queues.get(tenant)!;
      while (q.length && q[0]!.deadline <= this.now()) onExpired(q.shift()!);
      if (!q.length) { this.remove(tenant); continue; }
      // Each visit to a tenant tops up its deficit once, then it may spend it.
      if (!this.granted) {
        this.deficit.set(tenant, this.deficit.get(tenant)! + this.o.quantum * (this.o.weight?.(tenant) ?? 1));
        this.granted = true;
      }
      const head = q[0]!;
      if (head.cost <= this.deficit.get(tenant)!) {
        this.deficit.set(tenant, this.deficit.get(tenant)! - head.cost);
        q.shift();
        if (!q.length) this.remove(tenant);
        return head;
      }
      this.cursor++; // not enough deficit: move on, keep what was earned
      this.granted = false;
    }
    return undefined;
  }

  size(tenantId?: string): number {
    if (tenantId) return this.queues.get(tenantId)?.length ?? 0;
    let n = 0; for (const q of this.queues.values()) n += q.length; return n;
  }

  private remove(tenant: string): void {
    const i = this.active.indexOf(tenant);
    this.active.splice(i, 1);
    this.deficit.delete(tenant);
    if (i < this.cursor) this.cursor--;
    this.granted = false;
  }
}

The scheduler keeps one queue per tenant with work, and a pointer that moves round them in turn.

1. Each visit adds a quantum to the tenant's deficit, scaled by the tenant's weight.
2. The tenant may run jobs while its deficit covers their cost. Each job's estimated token cost is subtracted.
3. When the next job costs more than the remaining deficit, the pointer moves on. The deficit is kept, so a tenant with a large job accumulates enough over a few rounds to run it.
4. A tenant whose queue empties leaves the round and its deficit is reset, so it cannot bank credit while idle and then burst.

The tests show the property that matters: with five hundred jobs queued for one tenant and three for another, the small tenant's jobs run second, fourth and sixth, interleaved with the large one, not after it.

Fair by cost, not by count. A tenant whose jobs are ten times larger gets the same share of tokens, and therefore a tenth of the jobs. Counting jobs instead would let a tenant with large documents consume most of the quota while appearing to get an equal share. The test with 1,000-token and 100-token jobs asserts equal token totals.

Weights express plans. A tenant on a larger plan can have a weight of three, and gets three times the share in each round. The weights are a product decision, but the mechanism should exist from the start, because adding it later means migrating every queued job.

Backpressure and deadlines

A queue without limits is a promise you cannot keep. If tenants can enqueue without bound, a runaway integration can fill memory or the database, and every job behind it becomes stale before it runs.

Bound the queue per tenant. When a tenant's queue is full, enqueue rejects with queue_full and the caller gets a clear error: slow down, or try again later. Other tenants are unaffected. A global limit alone would let one tenant fill the queue and block everyone else from enqueueing at all.

Give every job a deadline. A summary requested for a meeting at nine is worthless at ten. The scheduler drops expired jobs when it reaches them, reports them through a callback, and does not spend quota on them. Jobs without a natural deadline still get one, so nothing waits forever.

Reading the quota instead of guessing it

The second half of the problem is how fast to drain the queue. The tempting answer is a constant: the provider allows N tokens per minute, so run at N. It is wrong for three reasons. Limits differ by account tier and change as your usage grows. Limits differ by model, so a route that falls back to another model has a different budget. And the quota is shared with everything else using the same account, including the interactive traffic you cannot see from the batch workers.

The provider knows the answer, and most providers say it in every response.

export interface QuotaSnapshot {
  limit?: number;
  remaining: number;
  /** Milliseconds until the window resets, relative to when the response was received. */
  resetMs: number;
}

/** "1s", "6m0s", "250ms", "1h2m3.5s" → milliseconds. */
export function parseDuration(s: string): number | undefined {
  const re = /(\d+(?:\.\d+)?)(ms|h|m|s)/g;
  let total = 0, matched = '';
  for (const m of s.matchAll(re)) {
    const n = Number(m[1]);
    total += m[2] === 'h' ? n * 3_600_000 : m[2] === 'm' ? n * 60_000 : m[2] === 's' ? n * 1_000 : n;
    matched += m[0];
  }
  return matched === s.trim() && matched ? Math.round(total) : undefined;
}

/**
 * Providers report quota in different dialects. Read what is there instead of
 * hard-coding limits, because limits change with your account tier and differ
 * between models. Supports:
 *   - the IETF draft field:   RateLimit: "default";r=12;t=30
 *   - common vendor headers:  x-ratelimit-remaining-tokens / x-ratelimit-reset-tokens
 *   - classic headers:        X-RateLimit-Remaining / X-RateLimit-Reset (seconds or epoch)
 * Returns the most restrictive quota found, or undefined if there is none.
 */
export function parseQuota(headers: Headers, nowMs: number, unit: 'requests' | 'tokens' = 'tokens'): QuotaSnapshot | undefined {
  const found: QuotaSnapshot[] = [];

  const draft = headers.get('ratelimit');
  if (draft) {
    for (const item of draft.split(',')) {
      const r = item.match(/;\s*r=(\d+)/), t = item.match(/;\s*t=(\d+)/);
      if (r && t) found.push({ remaining: Number(r[1]), resetMs: Number(t[1]) * 1000 });
    }
  }

  const rem = headers.get(`x-ratelimit-remaining-${unit}`);
  const reset = headers.get(`x-ratelimit-reset-${unit}`);
  if (rem !== null && reset !== null) {
    const ms = parseDuration(reset);
    if (ms !== undefined) {
      const lim = headers.get(`x-ratelimit-limit-${unit}`);
      found.push({ remaining: Number(rem), resetMs: ms, ...(lim !== null ? { limit: Number(lim) } : {}) });
    }
  }

  const cRem = headers.get('x-ratelimit-remaining'), cReset = headers.get('x-ratelimit-reset');
  if (cRem !== null && cReset !== null) {
    const v = Number(cReset);
    // Large values are epoch seconds; small ones are seconds until reset.
    const resetMs = v > 1e9 ? Math.max(0, v * 1000 - nowMs) : v * 1000;
    const lim = headers.get('x-ratelimit-limit');
    found.push({ remaining: Number(cRem), resetMs, ...(lim !== null ? { limit: Number(lim) } : {}) });
  }

  return found.filter((q) => Number.isFinite(q.remaining) && Number.isFinite(q.resetMs))
    .sort((a, b) => a.remaining - b.remaining)[0];
}

Providers use different dialects for the same information, so the parser reads three of them:

When several are present, the most restrictive wins. When none is present, the parser returns nothing, and the throttle falls back to reacting to 429 responses alone. Check the exact header names against your provider's documentation; they are not standardised yet, and the IETF draft is still a draft.

The adaptive throttle

The throttle sits between the scheduler and the gateway and answers one question per job: can a call of this cost start now?

/**
 * Paces outgoing calls from what the provider says is left. Keeps a reserve
 * so interactive traffic still has headroom when batch work is running, and
 * stops completely until the reset when the provider returns 429.
 */
export class AdaptiveThrottle {
  private remaining = Number.POSITIVE_INFINITY;
  private resetAt = 0;
  private pausedUntil = 0;
  private limit = 0;

  constructor(private readonly reserveFraction: number, private readonly now: () => number = Date.now) {}

  observe(q: QuotaSnapshot, limitHint?: number): void {
    this.remaining = q.remaining;
    this.resetAt = this.now() + q.resetMs;
    const limit = q.limit ?? limitHint;
    if (limit) this.limit = limit;
  }

  onTooManyRequests(retryAfterMs: number): void {
    this.pausedUntil = Math.max(this.pausedUntil, this.now() + retryAfterMs);
    this.remaining = 0;
  }

  /**
   * Can a call of this cost start now? `priority: 'interactive'` may use the
   * reserve; batch work may not.
   */
  canStart(cost: number, priority: 'interactive' | 'batch'): { ok: true } | { ok: false; waitMs: number } {
    const now = this.now();
    if (now < this.pausedUntil) return { ok: false, waitMs: this.pausedUntil - now };
    if (now >= this.resetAt) this.remaining = Number.POSITIVE_INFINITY; // window rolled over; trust the next response
    const reserve = priority === 'batch' ? Math.ceil(this.limit * this.reserveFraction) : 0;
    if (this.remaining - cost >= reserve) {
      this.remaining -= cost; // optimistic local accounting until the next response corrects it
      return { ok: true };
    }
    return { ok: false, waitMs: Math.max(0, this.resetAt - now) };
  }
}

It tracks what the provider last said. After each response, observe records the remaining quota and the reset time. Between responses it subtracts the cost of calls it lets through, so a burst of parallel workers does not all see the same stale number.

It keeps a reserve for interactive traffic. Batch work may only start if the remaining quota stays above a fraction of the limit; interactive calls may use the reserve. When an import is running at full speed, a user who opens the assistant still gets an answer.

It stops completely after a 429. A 429 with Retry-After means the provider has already started refusing work. Every call made before the reset is wasted and makes the recovery slower. The throttle pauses all starts until the provider's reset, interactive included.

It trusts the reset. When the reset time passes, local accounting is discarded and the next response sets the real value.

Two paths, one quota

Putting it together, there are two ways into the provider:

Interactive calls come from a user who is waiting. They go through the gateway's admission control, which rejects immediately if the tenant is over budget, and then through the throttle with interactive priority, which lets them use the reserve. They never queue behind batch work.

Batch calls are enqueued per tenant with a deadline and a cost estimate. Workers take the next job from the fair queue, ask the throttle with batch priority, and wait if the answer is no. They run as fast as the quota allows and no faster, and they leave the reserve alone.

The interesting failure modes are at the boundaries. If interactive traffic alone exceeds the quota, batch work stops entirely, which is correct, and your alerting should tell you that the reserve is too small or that you need a higher tier. If a single tenant's batch work is starved by others for longer than its deadlines, the jobs expire and the tenant should see that in the product, not discover it from missing results.

What to monitor

A scheduler that fails quietly is worse than one that fails loudly. These are the numbers worth a dashboard and an alert:

Testing a scheduler

Schedulers are pure logic around a clock, which makes them easy to test without a network and easy to get subtly wrong without tests. The suite for this article checks:

• Interleaving: a small tenant's jobs run between a large tenant's backlog, not after it.
• Cost fairness: tenants with ten times larger jobs get equal token totals.
• Weights: a weight of three gives three times the share.
• Backpressure: a full queue for one tenant does not block another.
• Deadlines: expired jobs are dropped and reported, and the next live job runs.
• Header dialects: each format parses, durations like 6m0s convert, and the most restrictive quota wins.
• Throttle reserve and pause: batch stops at the reserve, interactive does not, and a 429 stops both until the reset.

Cost and latency trade-offs, including when batch APIs are cheaper than running the same work through this queue, are the subject of the next article. Tenant isolation more broadly is covered in the multi-tenancy article, and the whole series is on the Luniat Engineering page.

References

1. M. Shreedhar and George Varghese, "Efficient fair queueing using deficit round robin", SIGCOMM, 1995.
2. Alan Demers, Srinivasan Keshav and Scott Shenker, "Analysis and simulation of a fair queueing algorithm", SIGCOMM, 1989.
3. IETF HTTPAPI working group, RateLimit header fields for HTTP, Internet-Draft.
4. Google, Site Reliability Engineering, chapter "Handling Overload", O'Reilly, 2016.
5. IETF, RFC 9110 HTTP Semantics, section 10.2.3: Retry-After, 2022.