Priority Queues & Job Fairness

Every queue eventually carries work of unequal urgency, and the moment it does, the FIFO ordering assumed by Queue Fundamentals & Architecture stops being adequate. A password-reset email behind 200,000 nightly digest jobs is a support ticket; a large tenant's bulk import starving every other customer is an outage with a single cause. Priority and fairness are two different answers to that problem, and choosing the wrong one is why most "priority queue" implementations end up starving something.

Priority orders work by importance. Fairness orders work by whose it is. A system that only implements priority will let a high-priority tenant monopolise capacity; a system that only implements fairness will deliver a critical alert with the same urgency as a batch report. Production systems generally need both, layered.

Strict Priority and Its Failure Mode

Strict priority means a worker always takes the highest-priority available job. It is trivial to implement — poll queues in order — and it delivers exactly what people ask for until the high-priority queue is never empty. At that point the lower queues are starved: their jobs sit indefinitely while the worker fleet drains an endlessly-refilled critical queue.

Strict priority is the right choice in exactly one situation: when the high-priority stream is bursty and provably low-volume relative to fleet capacity — health checks, cache invalidations, admin overrides. If the high stream can saturate the fleet even briefly, you need a weighted scheme or a dedicated pool.

The second failure mode is head-of-line blocking inside a priority class. A single 40-minute job at the head of the high queue delays every subsequent high-priority job behind it, no matter how urgent. Priority does not fix duration skew; separating queues by expected runtime does.

Weighted Fair Scheduling

Weighted scheduling gives each queue a share of worker attention rather than an absolute rank. With weights 70/20/10 the worker draws from high seven times out of ten, medium twice, and low once — so low-priority work still progresses, at a predictable rate, even under sustained high-priority load. The worst-case wait becomes bounded and calculable instead of unbounded.

# weighted_poll.py — deterministic weighted round-robin across Redis lists
import random
import redis

r = redis.Redis(decode_responses=True)
WEIGHTS = {"jobs:high": 70, "jobs:medium": 20, "jobs:low": 10}

def _order():
    """One randomised poll order per iteration, biased by weight. Randomising
    avoids the lock-step pattern a fixed cycle creates across many workers."""
    queues, weights = zip(*WEIGHTS.items())
    first = random.choices(queues, weights=weights, k=1)[0]
    rest = [q for q in queues if q != first]
    return [first, *rest]      # weighted first pick, strict fallback after

def next_job(timeout: int = 5):
    # BLPOP checks keys left-to-right, so the weighted head decides the bias
    # while the fallback list guarantees a worker never idles beside real work.
    item = r.blpop(_order(), timeout=timeout)
    return item[1] if item else None

The fallback tail is what keeps utilisation high: if the weighted pick lands on an empty queue, the worker still takes whatever else is available rather than sleeping. That single detail is the difference between a weighted scheduler and a badly-behaved one.

Weights should be derived from latency objectives rather than intuition. If low-priority work must complete within an hour and arrives at 500 jobs/minute, it needs enough share to sustain 500 jobs/minute — anything less means the queue grows without bound regardless of what the weight says. Compute the required share from arrival rate and service time, then set weights so each class has at least that much, and give the surplus to the latency-sensitive class. The same measurement discipline appears in defining SLOs for job latency.

Per-Tenant Fairness

Priority classes solve importance. They do nothing about one tenant flooding a shared queue with 200,000 jobs, because all of those jobs are legitimately the same priority. Fairness across tenants requires the scheduler to know who enqueued the work.

The standard implementation keeps a set of tenants with pending work plus one sub-queue per tenant. Workers pop the next tenant from the rotation, take one job (or a small batch) from that tenant's sub-queue, and move on. Tenants with nothing pending drop out of the rotation automatically, so idle tenants cost nothing. Preventing tenant starvation with weighted queues implements this end to end, including weight-per-tenant for paid tiers.

This is closely related to queue partitioning strategies: partitioning splits a queue for throughput and ordering, fair queueing splits it for isolation. The mechanics overlap; the objective does not.

Deciding Priority at Enqueue Time

Priority is a property of the work, not of the code path that happens to enqueue it, and the cheapest way to keep that true is to compute it in one place from an explicit rule set. When each caller passes its own literal — queue="high" scattered across forty modules — the mix drifts within a quarter and nobody can say why 70% of traffic is critical.

# dispatch.py — one rule set decides the class; callers never pass a queue name
from dataclasses import dataclass

@dataclass(frozen=True)
class Classification:
    queue: str
    reason: str

INTERACTIVE = {"password_reset", "checkout_receipt", "2fa_code", "cache_invalidate"}
BULK = {"nightly_digest", "report_export", "backfill", "reindex_all"}

def classify(task_name: str, *, tenant_tier: str, user_waiting: bool) -> Classification:
    if task_name in INTERACTIVE or user_waiting:
        return Classification("jobs:high", "a human is blocked on this")
    if task_name in BULK:
        return Classification("jobs:low", "deferred batch work")
    if tenant_tier == "enterprise":
        return Classification("jobs:medium", "contractual latency commitment")
    return Classification("jobs:medium", "default")

def enqueue(task, *args, tenant, user_waiting=False, **kwargs):
    c = classify(task.name, tenant_tier=tenant.tier, user_waiting=user_waiting)
    # The tenant travels with the message so the fair scheduler can route on it.
    return task.apply_async(args, kwargs, queue=c.queue,
                            headers={"tenant": tenant.id, "priority_reason": c.reason})

Carrying the reason alongside the class costs one header and pays for itself the first time the high queue doubles: a group-by on priority_reason tells you immediately which rule changed, rather than sending you through forty call sites. It also makes the priority budget enforceable — if user_waiting accounts for 60% of traffic, the flag is being set by a background path that should not have it.

The tenant identifier belongs in the message headers for the same reason. A fair scheduler cannot rotate on a value it has to infer from the payload, and parsing a 40KB body to extract a tenant ID before deciding whether to run the job defeats the point. Keep both in the envelope, where the consumer can read them without deserialising the work itself — the same argument made for routing metadata in message size limits and serialization.

How the Brokers Actually Implement Priority

Two of these deserve emphasis. RabbitMQ's message priority is real but interacts badly with consumer prefetch: if a consumer has already prefetched twenty low-priority messages, a newly-arrived high-priority message waits behind them regardless of its priority field. Keep prefetch_count at 1–2 on priority queues, as discussed in tuning prefetch and consumer concurrency.

SQS has no priority at all. The supported pattern is separate queues plus a consumer that polls them in a weighted order — which is exactly the weighted poller above, with ReceiveMessage in place of BLPOP.

Making the Selection Atomic

A weighted or fair scheduler that reads the queue state, decides, and then pops is racing every other worker in the fleet. Between the read and the pop another worker can drain the queue you chose, so the pop either blocks on an empty key or — worse, in a rotation implementation — leaves a tenant marked active with nothing in it. Push the whole decision into a single server-side operation.

-- fair_pop.lua — pick the next tenant in rotation and pop one job atomically.
-- KEYS[1] = active tenant set (sorted set, score = last served timestamp)
-- KEYS[2] = prefix for per-tenant list keys
-- ARGV[1] = current timestamp
local tenants = redis.call('ZRANGE', KEYS[1], 0, 9)   -- 10 least-recently-served
for i = 1, #tenants do
  local key = KEYS[2] .. tenants[i]
  local job = redis.call('LPOP', key)
  if job then
    -- Serve this tenant and push it to the back of the rotation.
    redis.call('ZADD', KEYS[1], ARGV[1], tenants[i])
    if redis.call('LLEN', key) == 0 then
      redis.call('ZREM', KEYS[1], tenants[i])          -- drop idle tenants
    end
    return {tenants[i], job}
  end
  redis.call('ZREM', KEYS[1], tenants[i])              -- stale entry, clean up
end
return nil

Scanning the ten least-recently-served tenants rather than only the first bounds the worst case: a burst of tenants that emptied between rotations cannot make the script return empty while real work waits. The ZREM on an empty list is what keeps the rotation size proportional to active tenants rather than to every tenant that ever enqueued anything.

Because the script returns the tenant along with the job, workers can label metrics and log lines with it for free — which is what makes the fairness properties observable rather than theoretical. On brokers without server-side scripting, the equivalent is a short-lived lease: claim the tenant with a SET NX EX 2, pop, then release, accepting that a crashed worker delays that tenant by the lease TTL.

Observability for Priority and Fairness

Priority systems fail quietly. Throughput stays healthy, dashboards look normal, and the only evidence is that a particular class or tenant has stopped moving. Three signals catch that, and none of them is total queue depth.

# 1. Oldest-message age per class — the starvation detector
max by (queue) (queue_oldest_message_age_seconds{queue=~"jobs:(high|medium|low)"})

# 2. Realised share vs configured weight — is the scheduler doing what you set?
sum by (queue) (rate(jobs_processed_total[10m]))
  / ignoring(queue) group_left sum(rate(jobs_processed_total[10m]))

# 3. Per-tenant share, to catch one tenant crowding out the rest
topk(5, sum by (tenant) (rate(jobs_processed_total[10m]))
  / ignoring(tenant) group_left sum(rate(jobs_processed_total[10m])))

- alert: LowPriorityQueueStarving
  expr: max(queue_oldest_message_age_seconds{queue="jobs:low"}) > 3600
  for: 15m
  labels: { severity: warning }
  annotations:
    summary: "Bulk queue has not drained in an hour — check high-priority saturation"

The realised-share query is the one that earns its keep. A weight set to 10% that realises 2% means the low queue is either starved by prefetch behaviour or is not receiving the polls you think it is; a weight set to 10% that realises 30% means the higher classes are empty and the surplus is being reallocated, which is correct behaviour and should not page anyone. Without the comparison you cannot tell those apart. Wire both into the dashboards described in Grafana dashboards for queues.

Failure Modes & Recovery

Starvation of the lowest class. Symptom: oldest-message age on the low queue grows monotonically while high-queue throughput is healthy. Cause: strict priority with a saturated high queue. Fix: switch to weighted polling, or cap high-priority admission so it cannot consume the whole fleet.

Priority inversion via long jobs. Symptom: high-priority p99 latency spikes even though the high queue is nearly empty. Cause: all workers are busy with long low-priority jobs; no preemption exists in a queue system. Fix: dedicate a small worker pool to the high queue so capacity is reserved, not merely prioritised.

Everything becomes high priority. Symptom: 90% of traffic on the "critical" queue. Cause: priority assigned by the enqueueing team without a budget. Fix: make priority a scarce resource — cap the share of jobs allowed at each level and alert when the mix drifts.

Fairness rotation stalls on an empty tenant. Symptom: throughput collapses with jobs still queued. Cause: the rotation blocks on a tenant whose sub-queue emptied between selection and pop. Fix: make the pop non-blocking, and remove the tenant from the active set atomically with a Lua script.

Prefetch defeats priority. Symptom: RabbitMQ message priorities appear to be ignored. Cause: consumers hold a large prefetch buffer of already-delivered low-priority messages. Fix: reduce prefetch to 1–2 on priority-bearing queues.

Performance Tuning

• Keep priority levels to three or four. Ten levels are indistinguishable in practice and make the weighting untunable. High / normal / bulk covers nearly everything.
• Reserve capacity, do not just rank it. A dedicated pool of 10–20% of workers for the critical queue guarantees latency in a way that weights alone cannot.
• Separate by duration as well as priority. A fast and a slow queue per priority class eliminates head-of-line blocking far more effectively than adding priority levels.
• Batch per tenant, not per job. Popping 5–20 jobs per tenant visit amortises the rotation overhead while keeping the fairness window small.
• Alert on oldest-message age per class, not just depth. Age is the metric that exposes starvation; depth alone can look stable while the tail never drains.
• Re-derive weights quarterly. Traffic mix drifts, and a weight set tuned for last year's ratio silently becomes a starvation policy.

FAQ

Should I use broker priority or separate queues? Separate queues, in almost every case. They are portable across brokers, independently observable (depth and age per class), independently scalable with dedicated workers, and they let you reserve capacity rather than merely rank work. Broker-native message priority is worth using only when the ordering must be per-message inside a single stream and you control prefetch tightly.

How do I stop low-priority work from starving? Give it a guaranteed share rather than a rank: weighted polling with a non-zero weight for every class, plus an alert on oldest-message age per queue. If the low class must meet a deadline, compute the share it needs from its arrival rate and service time and set the weight from that, not from intuition.

How many priority levels should a system have? Three, usually: interactive, normal, and bulk. Every extra level multiplies the tuning surface and the number of ways starvation can hide. If you find yourself wanting a fourth, check whether the real distinction is duration or tenant rather than urgency.

Can I change a job's priority after it is enqueued? Only by removing and re-enqueueing it, and only on brokers that let you address a specific message. With separate queues, promoting a job means popping it from the low queue and pushing it to the high one, which is straightforward on Redis and effectively impossible on SQS. Design for it if you need escalation — for example, a sweeper that promotes any bulk job older than its deadline — rather than assuming the broker supports mutation in place.

Does per-tenant fairness replace rate limiting? No — they solve adjacent problems. Fairness decides how contended capacity is shared right now; rate limiting and throttling jobs decides how much work a tenant may enqueue at all. Fairness without a rate limit still lets one tenant fill your storage; a rate limit without fairness still lets a compliant tenant monopolise workers during a burst.

Related

• Queue Fundamentals & Architecture — the delivery and topology model this scheduling layer sits on.
• Implementing priority queues with Redis sorted sets — a score-based priority queue with atomic pops.
• Preventing tenant starvation with weighted queues — per-tenant rotation with paid-tier weights.
• Routing high-priority jobs in Celery — task routing, dedicated pools, and the Redis priority caveat.
• Queue Partitioning Strategies — splitting a queue for throughput and ordering rather than isolation.