Fair Background Job Queues for Multi-Tenant Systems: Testing Deficit Round-Robin

A shared background queue works well until one tenant enqueues a large batch. After that, every job behind the batch waits, including a password-reset email or a webhook for a different customer. Adding workers shortens the wait but does not change who waits: in a first-in, first-out queue, everyone queued after the batch still waits behind all of it.

This guide shows how to give each tenant a fair share of workers with deficit round-robin (DRR), how to spot a scheduler that only looks fair, and what to do about job costs, retries, and poison messages. It includes a lab that runs a global FIFO queue, a commonly published DRR dispatcher, and a corrected DRR scheduler against the same workload. The published dispatcher turned out to be worse than FIFO.

What goes wrong with one global queue

Picture four workers and one Redis list. At 09:00 tenant B imports a spreadsheet and enqueues 2,000 jobs that take about 50 ms each. At 09:00:00.110 tenant A requests a password reset.

With a single list, A's job is behind 2,000 others. Four workers finish 80 jobs per second, so A waits roughly 25 seconds. With 20,000 jobs it would wait more than four minutes. Nothing is broken, and no alert fires, because the queue is doing exactly what FIFO means.

This is head-of-line blocking: one tenant's backlog delays work that has nothing to do with it. Scaling the worker pool helps everyone a little and fixes nothing structurally, because B's backlog grows to fill whatever capacity you add.

Fair queuing in one paragraph

Fair queuing gives each tenant with pending work a turn, regardless of how much work it has queued. Deficit round-robin is a simple, well-studied way to do that. It was described by George Varghese and M. Shreedhar for network packet scheduling in Efficient Fair Queueing using Deficit Round Robin, where packets have different sizes, which maps neatly onto jobs that have different costs.

The rules are short:

1. Keep one queue per tenant and a rotation list of tenants that currently have work.
2. When a tenant reaches the front of the rotation, add a fixed quantum to its deficit counter, once per turn.
3. While the deficit covers the cost of the tenant's next job, dispatch that job and subtract its cost.
4. When the next job costs more than the remaining deficit, move the tenant to the back of the rotation. It keeps its leftover deficit for next time.
5. When a tenant's queue becomes empty, remove it from the rotation and reset its deficit to zero, so idle tenants cannot save up credit.

Rule 4 is what makes DRR fair for unequal job sizes, and rule 5 keeps a tenant that was idle for an hour from arriving with an hour of banked priority.

Three bugs that make a scheduler only look fair

Many published DRR dispatchers wrap these rules around a Redis set of active tenants and an in-process rotation list. Three small departures from the algorithm are common, and each one changes behavior completely:

• The quantum is added on every call rather than once per turn. A tenant at the front of the rotation receives fresh credit every time a worker asks for a job, so it never runs out.
• The tenant is not rotated after a dispatch. The function returns the popped job immediately, so the same tenant stays at the front.
• The rotation list is only refreshed from Redis when it is empty, and tenants are never removed from it. Tenants that become active after the first refresh never enter the rotation. Once the original tenants drain, the loop keeps finding empty queues and never returns.

Read in isolation, each of these looks like a harmless shortcut. The lab below shows what they add up to.

Lab: FIFO, a published dispatcher, and corrected DRR

The program simulates time in milliseconds, so it prints the same numbers on any machine. It ports the published dispatcher's control flow line by line, replacing Redis calls with in-memory maps (the comment SMEMBERS marks the Redis set read, RPOP returned redis.Nil marks the empty-queue branch). It then runs two scenarios.

Scenario 1 is the story above: four workers, a 2,000-job bulk import at t=0, one job from tenant A at 110 ms, three from tenant C at 215 ms.

Scenario 2 checks fairness when job costs differ: both tenants are backlogged from the start, bulk jobs really take 500 ms, and tenant A's jobs take 50 ms. It runs DRR twice, once with every job costed at 1 and once with bulk jobs costed at 10.

Save the program as main.go in an empty directory and run go run . with Go 1.22 or later. It uses only the standard library.

// Lab: does a per-tenant scheduler actually protect small tenants?
//
// Simulates 4 workers draining a bulk backlog from tenant "bulk" while two
// small tenants submit jobs later. Compares a global FIFO queue, a faithful
// in-memory port of a commonly published "DRR" dispatcher, and a corrected
// deficit round-robin scheduler. Time is simulated in milliseconds, so the
// results are deterministic and independent of the machine.
package main

import (
	"fmt"
	"sort"
)

type job struct {
	tenant   string
	enqueued int // ms
	duration int // ms of worker time
	cost     int // scheduler's cost estimate
}

type scheduler interface {
	enqueue(j job)
	next() (job, bool, error)
}

// ---- 1. Global FIFO -------------------------------------------------------

type fifo struct{ q []job }

func (f *fifo) enqueue(j job) { f.q = append(f.q, j) }
func (f *fifo) next() (job, bool, error) {
	if len(f.q) == 0 {
		return job{}, false, nil
	}
	j := f.q[0]
	f.q = f.q[1:]
	return j, true, nil
}

// ---- 2. Port of the published dispatcher ----------------------------------
// Same control flow as the Redis version: a shared "active tenant" set,
// a local rotation list refreshed only when empty, quantum added on every call.

type publishedDRR struct {
	queues   map[string][]job
	set      map[string]bool // stands in for the Redis SET active_tenant_queues
	active   []string
	deficits map[string]int
	quantum  int
}

func (s *publishedDRR) enqueue(j job) {
	s.queues[j.tenant] = append(s.queues[j.tenant], j)
	s.set[j.tenant] = true // SADD on enqueue
}

func (s *publishedDRR) next() (job, bool, error) {
	if len(s.active) == 0 {
		for t := range s.set { // SMEMBERS
			s.active = append(s.active, t)
		}
		sort.Strings(s.active)
		if len(s.active) == 0 {
			return job{}, false, nil
		}
	}
	for spins := 0; len(s.active) > 0; spins++ {
		if spins > 1_000_000 {
			return job{}, false, fmt.Errorf("livelock: dispatcher loops without returning")
		}
		t := s.active[0]
		s.deficits[t] += s.quantum
		for s.deficits[t] > 0 {
			q := s.queues[t]
			if len(q) == 0 { // RPOP returned redis.Nil
				delete(s.set, t)
				s.deficits[t] = 0
				break
			}
			s.queues[t] = q[1:]
			s.deficits[t]--
			return q[0], true, nil
		}
		s.active = append(s.active[1:], t)
	}
	return job{}, false, nil
}

// ---- 3. Corrected deficit round-robin -------------------------------------

type drr struct {
	queues   map[string][]job
	active   []string // tenants with a backlog, in rotation order
	deficits map[string]int
	fresh    bool // true when the head tenant has not yet received its quantum
	quantum  int
}

func (s *drr) enqueue(j job) {
	if len(s.queues[j.tenant]) == 0 {
		s.active = append(s.active, j.tenant)
		if len(s.active) == 1 {
			s.fresh = true
		}
	}
	s.queues[j.tenant] = append(s.queues[j.tenant], j)
}

func (s *drr) next() (job, bool, error) {
	for len(s.active) > 0 {
		t := s.active[0]
		if s.fresh {
			s.deficits[t] += s.quantum
			s.fresh = false
		}
		q := s.queues[t]
		if s.deficits[t] >= q[0].cost {
			s.deficits[t] -= q[0].cost
			s.queues[t] = q[1:]
			if len(s.queues[t]) == 0 { // idle tenants do not bank credit
				s.deficits[t] = 0
				s.active = s.active[1:]
				s.fresh = true
			}
			return q[0], true, nil
		}
		s.active = append(s.active[1:], t) // keep the remaining deficit
		s.fresh = true
	}
	return job{}, false, nil
}

// ---- Simulation -----------------------------------------------------------

type result struct {
	waits   map[string][]int // per-tenant queue wait in ms
	busy    map[string]int   // worker-ms consumed per tenant
	err     error
	horizon int
}

func simulate(s scheduler, arrivals []job, workers, horizon int) result {
	r := result{waits: map[string][]int{}, busy: map[string]int{}, horizon: horizon}
	sort.SliceStable(arrivals, func(i, j int) bool { return arrivals[i].enqueued < arrivals[j].enqueued })
	freeAt := make([]int, workers)
	ai := 0
	for t := 0; t <= horizon; t++ {
		for ai < len(arrivals) && arrivals[ai].enqueued == t {
			s.enqueue(arrivals[ai])
			ai++
		}
		for w := range freeAt {
			if freeAt[w] > t {
				continue
			}
			j, ok, err := s.next()
			if err != nil {
				r.err = fmt.Errorf("t=%dms: %w", t, err)
				return r
			}
			if !ok {
				break
			}
			r.waits[j.tenant] = append(r.waits[j.tenant], t-j.enqueued)
			r.busy[j.tenant] += j.duration
			freeAt[w] = t + j.duration
		}
	}
	return r
}

func scenario1() []job {
	var a []job
	for i := 0; i < 2000; i++ { // bulk import: 2,000 x 50 ms
		a = append(a, job{"bulk", 0, 50, 1})
	}
	a = append(a, job{"tenant-a", 110, 50, 1}) // one password-reset email
	for i := 0; i < 3; i++ {
		a = append(a, job{"tenant-c", 215, 50, 1}) // three webhook deliveries
	}
	return a
}

func scenario2(costAware bool) []job {
	var a []job
	for i := 0; i < 400; i++ { // bulk jobs are 10x longer than they look
		c := 1
		if costAware {
			c = 10
		}
		a = append(a, job{"bulk", 0, 500, c})
	}
	for i := 0; i < 400; i++ {
		a = append(a, job{"tenant-a", 0, 50, 1})
	}
	return a
}

func describe(name string, r result, tenants ...string) {
	fmt.Printf("%-26s", name)
	if r.err != nil {
		fmt.Printf(" STOPPED: %v\n", r.err)
	}
	for _, t := range tenants {
		w := r.waits[t]
		if len(w) == 0 {
			fmt.Printf("  %s: never started within %d ms", t, r.horizon)
			continue
		}
		max := 0
		for _, x := range w {
			if x > max {
				max = x
			}
		}
		fmt.Printf("  %s: max wait %d ms", t, max)
	}
	fmt.Println()
}

func share(r result, window int, tenants ...string) {
	total := 0
	for _, t := range tenants {
		total += r.busy[t]
	}
	for _, t := range tenants {
		fmt.Printf("    %-9s %5.1f%% of dispatched worker time\n", t, 100*float64(r.busy[t])/float64(total))
	}
}

func main() {
	const workers = 4
	fmt.Println("Scenario 1: 4 workers, bulk=2,000 x 50 ms at t=0; tenant-a 1 job at t=110 ms; tenant-c 3 jobs at t=215 ms")
	describe("global FIFO", simulate(&fifo{}, scenario1(), workers, 40000), "tenant-a", "tenant-c")
	describe("published dispatcher", simulate(&publishedDRR{queues: map[string][]job{}, set: map[string]bool{}, deficits: map[string]int{}, quantum: 5}, scenario1(), workers, 40000), "tenant-a", "tenant-c")
	describe("corrected DRR (quantum 5)", simulate(&drr{queues: map[string][]job{}, deficits: map[string]int{}, quantum: 5}, scenario1(), workers, 40000), "tenant-a", "tenant-c")

	fmt.Println("\nScenario 2: both tenants backlogged at t=0; bulk jobs take 500 ms, tenant-a jobs take 50 ms; first 10 s measured")
	for _, aware := range []bool{false, true} {
		name := "DRR, every job cost=1"
		if aware {
			name = "DRR, bulk cost=10"
		}
		r := simulate(&drr{queues: map[string][]job{}, deficits: map[string]int{}, quantum: 10}, scenario2(aware), workers, 10000)
		fmt.Println(name)
		share(r, 10000, "bulk", "tenant-a")
	}
}

Output recorded on November 3, 2026 (Go 1.26.5, windows/amd64):

Scenario 1: 4 workers, bulk=2,000 x 50 ms at t=0; tenant-a 1 job at t=110 ms; tenant-c 3 jobs at t=215 ms
global FIFO                 tenant-a: max wait 24890 ms  tenant-c: max wait 24785 ms
published dispatcher       STOPPED: t=25000ms: livelock: dispatcher loops without returning
  tenant-a: never started within 40000 ms  tenant-c: never started within 40000 ms
corrected DRR (quantum 5)   tenant-a: max wait 40 ms  tenant-c: max wait 35 ms

Scenario 2: both tenants backlogged at t=0; bulk jobs take 500 ms, tenant-a jobs take 50 ms; first 10 s measured
DRR, every job cost=1
    bulk       91.6% of dispatched worker time
    tenant-a    8.4% of dispatched worker time
DRR, bulk cost=10
    bulk       51.8% of dispatched worker time
    tenant-a   48.2% of dispatched worker time

What the output means

FIFO behaved as predicted. Tenant A waited 24.9 seconds for a job that takes 50 ms. Tenant C waited almost as long.

The published dispatcher never served tenants A or C. Its rotation list was filled at t=0, when only the bulk tenant had work, and was never refreshed while that list was non-empty. When the bulk queue drained at 25 seconds, the loop kept visiting the empty bulk queue, adding quantum, finding nothing, and rotating it back in. In the Redis version that loop runs while holding the scheduler mutex, so every worker blocks. That is a full outage for background jobs, not a fairness problem.

Corrected DRR served A within 40 ms and C within 35 ms. Those waits are the time until the next worker finished its current 50 ms bulk job. The bulk import still completed; it just shared workers.

Scenario 2 shows that DRR is fair in cost units, not in time. When every job is costed at 1, the scheduler alternates jobs fairly, but bulk jobs are ten times longer, so the bulk tenant received 91.6% of worker time. When the bulk jobs carried a cost of 10, worker time split 51.8% to 48.2%. The scheduler is only as fair as your cost estimate.

Limits of this lab

The simulation has no network latency, no worker crashes, and no retries, and its job durations are fixed. It shows the logic of each scheduler, not the throughput of Redis. Port your real scheduler into the same harness and replay a recorded day of enqueue events before trusting it.

Choosing job costs

A cost is your estimate of how much worker time a job consumes. You do not need precision; you need the right order of magnitude.

Most teams start with one cost per job type and add input-based costs for the two or three job types whose durations vary the most. Record the estimated and actual cost on every job so you can see when an estimate goes stale.

Priority classes still matter

Fairness between tenants does not make a password reset more urgent than a nightly export from the same tenant. Run separate queues per class (for example interactive, default, and bulk) and give each class its own worker pool or a reserved share of workers.

Size the interactive pool from its arrival rate and job duration, then add headroom for retries. Test the reservation by flooding the bulk class in a staging environment and watching interactive queue age. The noisy-neighbor guide covers the same idea at the API layer, where per-tenant rate limits decide what gets into the system in the first place.

Retries, poison messages, and dead-letter queues

A poison message is a job that fails every time: malformed input, a bug triggered by one tenant's data, or a call to a dependency that will never succeed. If failures go straight back into the queue, a poison job can cycle forever and, if it crashes the worker process, take workers down with it.

Three controls handle most cases:

1. Retry with backoff and jitter. Wait longer after each failure and add randomness so retries from many jobs do not arrive together. The Google SRE chapter on cascading failures explains how synchronized retries amplify an outage.
2. Cap the attempts. After a fixed number of failures, move the job aside instead of retrying it again. The right number depends on whether failures are usually transient; three to eight is common.
3. Move exhausted jobs to a dead-letter queue with the error, the attempt count, and the tenant ID, and alert on its growth. Amazon SQS implements this with a redrive policy and a maxReceiveCount, described in Using dead-letter queues in Amazon SQS.

Count retries against the tenant's deficit too. Otherwise a tenant whose jobs fail repeatedly gets extra turns at everyone else's expense.

Restoring tenant context inside workers

A job runs long after the HTTP request that created it, so the request's authentication and tenant context are gone. Put the tenant ID and the acting user ID in the job payload, and have the worker re-establish both before running the handler: open a transaction, set the tenant for row-level security, and pass a context that carries the tenant to logs and traces.

The row-level security guide shows a transaction wrapper that sets the tenant with a bound parameter, and the tracing guide shows how to carry trace context through message headers. Treat the tenant ID in a payload as data your own service wrote, not as a claim from a client; a job created by one tenant must never be able to name another tenant.

Managed queues with fairness built in

You do not always need to write a scheduler. Amazon SQS added fair queues for standard queues, which use the message group ID to recognize a tenant that is building a backlog and deliver other tenants' messages first; see Amazon SQS fair queues. Other brokers and job frameworks offer weighted queues or per-key concurrency limits.

Whichever you use, run Scenario 1 against it in a test environment. The question is simple: when one tenant enqueues thousands of jobs, how long does a different tenant's single job wait?

What to monitor

• Oldest job age per priority class. This is the number customers feel. Alert on it, not on queue length.
• Oldest job age for the most-delayed tenant. A fair scheduler keeps this close to the class average.
• Share of worker time per tenant during contention, compared with the share your costs intended.
• Estimated versus actual job cost by job type.
• Dead-letter queue growth, broken down by job type and tenant.

Where to start

If you run a single shared queue today, measure the oldest-job age during your largest tenant's busiest hour before changing anything. If it is acceptable, a separate interactive queue may be all you need. If it is not, add per-tenant queues with DRR, cost each job type, and replay a real day of traffic through the scheduler in a harness like the one above before you deploy it. Whatever you adopt, test the case of a tenant that becomes active after the backlog starts, because that is exactly where the published dispatcher failed.