Priority Classes and Tenant Fairness in Shared Job Queues

A single queue ordered by availability time is fair in exactly one sense: the job that has waited longest runs first. That property is worth very little when the arrival rates differ. A tenant that enqueues a hundred thousand jobs in a minute owns the head of the queue for as long as it takes to drain them, and every other tenant’s job sits behind that wall. The queue has not malfunctioned; it has done what it was told, and what it was told is not what the system needs.

Two different problems hide in that description. One is priority: a latency-sensitive job should not wait behind a batch job regardless of who submitted it. The other is fairness: among equals, one participant should not consume capacity in proportion to how much it asked for. They are often addressed with the same machinery, and confusing them produces a queue that is neither.

Strict priority and the class it starves

The simplest priority scheme is to order the claim by a priority column, taking the highest class first. It is also the scheme that fails most completely, because it offers no guarantee to any class below the top. A class with a continuous supply of jobs at higher priority consumes the entire worker pool, and the lower class runs only during the gaps. If the higher class never runs out, the lower class never runs.

Adding a second criterion — priority first, then age — produces a bounded form of starvation only if the age term can outweigh the priority term, which turns the ordering into a weighted measure rather than a priority. That is a legitimate design, and it is hard to reason about, because the actual dispatch order depends on the interaction between two incomparable quantities.

The cleaner construction is priority with a floor. The top class is served first, but every class is guaranteed a minimum share of dispatch slots over a window, and the top class can consume the remainder. Guaranteeing a floor without capping the top requires the dispatcher to track how much each class has been served in the current window, which is exactly what a weighted scheduler does.

Priority is also not a property of the queue alone. A job that must start within seconds cannot be protected by any dispatch policy if the worker pool has no free capacity; the guarantee has to reserve capacity, not merely order the waiting jobs.

Weights over job counts

Deficit round robin is the mechanism that turns weights into dispatch decisions with O(1) work per job. Each class holds a backlog, a quantum proportional to its weight, and a deficit counter. On each visit, the class’s deficit increases by its quantum, and jobs are dispatched while the deficit covers their cost; whatever remains carries to the next visit. A job that costs more than the quantum would never be dispatched under that rule alone, so the implementation sends it once the deficit reaches zero rather than letting its size starve it.

type class struct {
    q      []Job
    quantum int
    deficit int
}

func dispatch(classes []*class, c *class, slots *int) {
    c.deficit += c.quantum
    for len(c.q) > 0 && *slots > 0 {
        j := c.q[0]
        if j.cost > c.deficit {
            if c.deficit < 0 {
                return // the deficit carries to the next visit
            }
            c.deficit = 0 // a job larger than the quantum must still get a turn
        }
        c.q = c.q[1:]
        c.deficit -= j.cost // cost in the unit the weight is expressed in
        run(j)
        (*slots)--
    }
}

The unit of cost is the design decision. Counting each job as cost 1 gives job-count fairness: a tenant submitting cheap jobs gets the same number of executions as one submitting expensive jobs, and therefore far less CPU time. Counting by measured duration gives work fairness, which favours whichever class happens to have cheap jobs, since its quantum buys more of them. Neither is universally right, and the choice should be made explicitly — a batch class competing with an interactive class usually wants work fairness, while two tenants on the same class usually want job-count fairness so that neither can convert a large input into a larger share.

Round robin over classes, rather than over individual jobs, is what bounds the delay. A strict round robin over all jobs would give each job an equal turn but let one class’s backlog dominate the timing of every other job’s turn, because the interleaving is uniform over the backlog size.

Pure random selection weighted by class is easier to implement and only statistically fair: it converges over many draws but permits bursts in which one class receives far more than its share. At the scale of a few tens of dispatches per second, those bursts are visible as queueing delay.

Caps that weights cannot express

Weights allocate capacity among classes. They do not restrict an individual tenant’s concurrency, and concurrency is where a single tenant causes the most damage: forty simultaneous jobs from one tenant can hold every connection in a database pool that a dozen other tenants share.

A per-tenant cap is a separate mechanism, enforced at claim time:

UPDATE tenant_runtime t
SET active = active + 1
WHERE t.tenant_id = $1 AND t.active < t.max_active
RETURNING t.active;

Zero rows returned means the tenant is at its cap and the job must be returned to the queue with a short availability delay rather than held. A plain read of active followed by an increment admits more than the cap when two workers claim at once; the conditional update makes the check and the increment one operation.

Choosing the cap requires knowing what the shared resource is. If the constraint is worker memory, the cap should be per byte of working set, not per job. If the constraint is a downstream API’s rate limit, the cap should be a token bucket shared with the interactive path, since a tenant’s background jobs and its request traffic draw on the same allowance. A cap expressed in jobs is a proxy, and it is only accurate when jobs are homogeneous.

At enqueue, a complementary limit bounds the backlog: a tenant with a million queued jobs has an unbounded wait even if its concurrency is capped, and the queue’s index and claim costs grow with its presence. Rejecting or deferring enqueues beyond a per-tenant depth is admission control, and it moves the failure to where the producer can see it rather than hiding it in queue depth.

The long job that holds the pool

A job that runs for thirty minutes holds its worker for thirty minutes. With a pool of twenty workers, four such jobs consume twenty percent of the pool for half an hour, and the dispatch policy cannot recover the capacity because the workers are not idle — they are busy.

The structural answer is a separate pool for long jobs, with its own concurrency limit and its own workers. Short jobs keep their latency, and long jobs queue only against each other. The dispatcher routes by expected duration class, which must be declared by the job type rather than measured, since the measurement only exists after the first run.

A second-order effect: a pool dedicated to long jobs is idle whenever long jobs are absent, which wastes capacity that the short pool could use. Sharing requires that the long pool yield its workers when its queue is empty, which is a pool-sizing problem rather than a scheduling one, and depends on the workers being able to switch classes at the claim step.

Preemption — stopping a running job to give its worker to a higher class — is usually not worth attempting. Jobs hold partial state, and interrupting them requires the checkpointing discipline that Visibility Timeouts and Lease Heartbeats describes for jobs that outlive a single claim. Reserving capacity is the cheaper guarantee.

Batching and the granularity of fairness

A worker that claims twenty jobs in one statement takes them from whichever class the claim statement selected. If the claim is LIMIT 20 ordered by priority, the worker receives twenty high-priority jobs, and its next twenty will come from wherever the backlog is, so the effective ratio over a batch boundary is coarse: the class weights are quantised to the batch size.

The consequence is that weights must be expressed at a granularity coarser than the batch, or batching must be per class. A 90/10 split with batch size 20 is representable as two jobs per batch for the low class; a 99/1 split is not representable at all, and the low class either never appears in a batch or appears in every twentieth batch as a burst.

The claim statement must also be per class, since a single ordered claim cannot honour deficits that live in the dispatcher — it is the same conditional-update claim as The Job Record State Machine describes, with a class predicate added. With classes stored as separate queues or as a class column with a per-class index, each claim names its class and takes from that class’s ordered set. The dispatcher state then survives restarts only if it is derivable from the stored data — for example, by choosing the class whose recent completion count is furthest below its target share — which is a good reason to prefer a stateless selection rule over an in-memory deficit counter.

What to measure

Throughput per class says nothing about fairness. A class can receive its full target share of executions while its jobs wait hours, because the arrivals vastly outnumber the completions; the share is being met and the latency is still unacceptable.

The measurement that matches the goal is the wait time distribution per class — specifically the time between available_at and claim — and its p99 rather than its mean, because fairness is violated at the tail. A per-tenant version of the same measurement catches the case where the class aggregate looks healthy while one tenant’s jobs never reach the head.

Two counters give early warning without histograms: the number of jobs currently claimable per class, and the age of the oldest claimable job per class. A class whose oldest claimable job keeps ageing is being starved, whatever the completion counts say. That check is cheap enough to run continuously, and it is the one that would have caught the failure the single ordered queue produces by design.