Preventing Tenant Starvation with Weighted Queues

This guide implements the per-tenant fairness layer from Priority Queues & Job Fairness, part of Queue Fundamentals & Architecture, for a multi-tenant worker fleet on Redis.

Problem Statement

One customer triggers a 400,000-row import at 09:00. Every job is legitimate, correctly prioritised as normal work, and enqueued through the supported API. For the next four hours every other tenant's exports, notifications, and webhooks queue behind it, because a single FIFO queue has no concept of whose work it is. Support tickets arrive from customers whose five-second job took forty minutes. You need capacity shared by tenant, with paid tiers given proportionally more, and no ability for a single tenant to consume the fleet no matter how much they enqueue.

Prerequisites

  • A tenant identifier available at enqueue time and carried in the message envelope, not buried in the payload.
  • Redis with Lua scripting for the atomic rotation (a {queue} hash tag if you run Cluster).
  • Worker code you can change: fairness lives in the consumer's selection logic, not in the broker.
  • Per-tenant metrics labelled with a bounded tenant cardinality — bucket the smallest tenants into other if you have tens of thousands.

Step 1 — Split the Queue by Tenant

Replace one list with one list per tenant plus a set of tenants that currently have work. The set is the rotation; the lists hold the jobs.

import json, time, redis
r = redis.Redis(decode_responses=True)

ACTIVE = "{q}:active"                 # sorted set: tenant → last-served timestamp
def tenant_key(t: str) -> str:        # one list per tenant
    return f"{{q}}:t:{t}"

def enqueue(tenant: str, job: dict) -> None:
    pipe = r.pipeline()
    pipe.rpush(tenant_key(tenant), json.dumps(job))
    # Only add to the rotation if absent — never reset an existing fairness position.
    pipe.zadd(ACTIVE, {tenant: time.time()}, nx=True)
    pipe.execute()

The nx=True is load-bearing. Without it, every enqueue rewrites the tenant's rotation score, and a tenant enqueueing continuously keeps re-inserting itself at the front — reproducing the starvation you are trying to remove.

Per-tenant sub-queues and the rotation set Producers enqueue into one list per tenant and register the tenant in an active sorted set scored by last-served time. Workers run a scheduler that picks the least-recently-served tenant, weighted by plan tier, and pops one batch from that tenant's list. Tenants whose list empties are removed from the rotation. One list per tenant, one rotation for the fleet producers q:t:acme · 400,000 jobs q:t:globex · 12 jobs q:t:initech · 3 jobs q:active (zset) tenant → last served weighted picker least-recently-served workers batch Acme's 400,000 jobs do not delay Globex: they simply take 400,000 rotations to finish. Idle tenants leave the rotation, so its size tracks active tenants, not total customers.

Step 2 — Rotate with Deficit Round-Robin

Plain round-robin gives every tenant an equal share, which is usually wrong: an enterprise plan paying twenty times more should get more than 1/N. Deficit round-robin (DRR) assigns each tenant a quantum proportional to its weight, accumulates unused quantum as a deficit, and serves jobs while the deficit allows. It is the same algorithm network schedulers use for weighted bandwidth sharing, and it degrades gracefully when tenants appear and disappear.

WEIGHTS = {"enterprise": 8, "growth": 3, "free": 1}   # relative service share
QUANTUM = 4                                            # base jobs per visit

def quantum_for(tenant: str) -> int:
    return QUANTUM * WEIGHTS[plan_of(tenant)]

def serve_once(worker_id: str) -> int:
    """Serve one tenant's quantum. Returns the number of jobs processed."""
    tenant = next_tenant()          # least-recently-served, see step 3
    if tenant is None:
        return 0
    budget, done = quantum_for(tenant), 0
    while budget > 0:
        raw = r.lpop(tenant_key(tenant))
        if raw is None:
            r.zrem(ACTIVE, tenant)  # emptied — leave the rotation
            break
        process(json.loads(raw))
        budget -= 1
        done += 1
    r.zadd(ACTIVE, {tenant: time.time()}, xx=True)   # back of the rotation
    return done

An enterprise tenant with weight 8 receives 32 jobs per visit against a free tenant's 4, so the realised shares converge on the configured ratio as long as every tenant is visited at a similar rate. Keep the quantum small enough that one visit cannot monopolise a worker for minutes — with 30-second jobs, a quantum of 32 is a sixteen-minute lockout. Size it so quantum × p95_duration stays under a minute, and rely on visit frequency rather than visit length for the weighting when jobs are slow.

Step 3 — Make Tenant Selection Atomic

Every worker in the fleet runs this loop concurrently, so selection must be a single Redis round trip or two workers will pick the same tenant and double-serve it.

-- next_tenant.lua — KEYS[1]=active zset, ARGV[1]=now, ARGV[2]=stride
-- Pop the least-recently-served tenant and immediately push it forward so a
-- concurrent worker sees a different candidate.
local t = redis.call('ZRANGE', KEYS[1], 0, 0)
if #t == 0 then return nil end
redis.call('ZADD', KEYS[1], tonumber(ARGV[1]) + tonumber(ARGV[2]), t[1])
return t[1]

The stride argument (a second or two) reserves the tenant briefly: another worker arriving in the same millisecond sees a score in the near future and picks the next tenant instead. This is a soft reservation rather than a lock — if the first worker dies, the tenant is simply picked up again after the stride elapses, with no lock to clean up.

Step 4 — Cap Admission per Tenant

Fair scheduling shares processing capacity; it does nothing about storage. A tenant that enqueues ten million jobs still fills Redis, and the fairness rotation cheerfully keeps them all. Pair the scheduler with a per-tenant depth cap enforced at enqueue.

MAX_DEPTH = {"enterprise": 500_000, "growth": 100_000, "free": 5_000}

class QueueFull(Exception):
    pass

def enqueue_guarded(tenant: str, job: dict) -> None:
    depth = r.llen(tenant_key(tenant))
    if depth >= MAX_DEPTH[plan_of(tenant)]:
        # Reject at the edge — a 429 the caller can retry beats silent unbounded growth.
        raise QueueFull(f"{tenant} has {depth} queued jobs; limit reached")
    enqueue(tenant, job)

Rejecting at the edge is far kinder than accepting work you will not process for six hours. Return the current depth and an estimated drain time in the error so the caller can decide whether to back off or batch differently; the throttling patterns in rate limiting and throttling jobs apply directly.

Step 5 — Prove Fairness with Metrics

from prometheus_client import Counter, Gauge
SERVED = Counter("jobs_served_total", "Jobs processed", ["tenant", "plan"])
DEPTH  = Gauge("tenant_queue_depth", "Queued jobs per tenant", ["tenant"])
WAIT   = Gauge("tenant_oldest_job_age_seconds", "Head-of-queue age", ["tenant"])
# Realised share per tenant over ten minutes — compare against configured weight
sum by (tenant) (rate(jobs_served_total[10m]))
  / ignoring(tenant) group_left sum(rate(jobs_served_total[10m]))

# Starvation alarm: a small tenant waiting far longer than its plan implies
- alert: TenantStarved
  expr: max by (tenant) (tenant_oldest_job_age_seconds) > 900
        and on(tenant) (tenant_queue_depth < 100)
  for: 10m
  labels: { severity: warning }
  annotations:
    summary: "{{ $labels.tenant }} has a small backlog that is not draining"

The compound condition matters: a large backlog that is old is expected — that is a big import working through the rotation. A small backlog that is old means the tenant is not being visited at all, which is a real scheduler bug.

Dashboards should show realised share next to configured weight on the same panel. A tenant whose realised share sits persistently below its weight is being under-served by the scheduler; one persistently above it is simply the only tenant with work, which is correct and must not page anyone.

Quantum per visit under deficit round-robin Three tenants are visited in rotation. The enterprise tenant, weighted eight, receives thirty-two jobs per visit. The growth tenant, weighted three, receives twelve. The free tenant, weighted one, receives four. Each is visited at the same frequency, so realised throughput converges on the configured eight to three to one ratio. Same visit frequency, different quantum enterprise (w=8) 32 jobs per visit growth (w=3) 12 per visit free (w=1) 4 per visit Keep quantum x p95 duration under a minute, or one visit locks a worker for too long.

Verification

  1. Flood test. Enqueue 100,000 jobs for tenant A and 100 each for B and C. B and C must complete within a few rotations — seconds, not hours — while A drains steadily in the background.
  2. Weights are realised. With equal backlogs across an enterprise, growth, and free tenant, the ten-minute share ratio must approximate 8:3:1 within about 10%.
  3. Idle tenants cost nothing. ZCARD {q}:active must equal the number of tenants with pending work, not the total tenant count, after a drain.
  4. No double service. Run 40 workers against a single tenant's 10,000 jobs and assert exactly 10,000 processed with no duplicate job IDs.
redis-cli ZRANGE '{q}:active' 0 -1 WITHSCORES | paste - -   # who is in rotation
redis-cli --scan --pattern '{q}:t:*' | while read k; do
  printf '%s %s\n' "$k" "$(redis-cli LLEN "$k")"; done | sort -k2 -rn | head
Per-tenant admission caps bound storage, not just service Three plan tiers with different maximum queue depths. An enterprise tenant may hold five hundred thousand queued jobs, growth one hundred thousand, and free five thousand. Beyond the cap the enqueue is rejected at the edge with a retryable error rather than accepted into an unbounded backlog. Fair scheduling shares workers; caps bound storage enterprise cap 500,000 queued growth cap 100,000 free cap 5,000 — further enqueues rejected with a retryable error Return the current depth and an estimated drain time so the caller can back off intelligently.

Gotchas & Edge Cases

Resetting the rotation score on every enqueue. The single most common bug: it hands continuous producers permanent priority. Use ZADD … NX on enqueue and XX when returning a tenant to the back.

Unbounded metric cardinality. One Prometheus label value per tenant is fine at hundreds, ruinous at hundreds of thousands. Track the top N by depth plus an aggregated other, and keep full detail in logs.

Slow jobs defeat a large quantum. A quantum of 32 with two-minute jobs locks a worker to one tenant for an hour. Bound the quantum by expected duration, not by job count alone.

Fairness does not survive a shared downstream. If every tenant's jobs hit the same rate-limited API, fair scheduling only redistributes who waits. Combine it with per-tenant limits at the dependency, as in rate limiting third-party API calls from workers.

Weights defined per plan drift from what customers actually bought. Plans get renamed, custom contracts appear, and the weight table quietly stops describing reality. Derive the weight from the subscription record at enqueue time and stamp it on the message, rather than looking up a hard-coded table in the worker; the scheduler then honours whatever the billing system says today.

A tenant deleted mid-flight leaves rotation entries. Guard the pop path: if the tenant list is missing or the tenant no longer exists, ZREM it and continue rather than returning an empty batch to the worker loop.

Related