pg-job-queue

A multi-tenant background job queue built on PostgreSQL. It has an HTTP API to enqueue jobs and worker processes that run them. It schedules fairly across tenants, so one customer's flood of jobs can't stall everyone else's. Failed jobs are retried with exponential backoff, and jobs whose worker crashed mid-run are recovered.

Python, Flask, PostgreSQL, Docker. No Redis, no broker — the database the app already has is the queue.

Results

Measured on a 22-core Windows machine with Docker Desktop. PostgreSQL 16 and the workers run in containers on the same machine, with default Postgres settings. Raw output is in bench/results.txt; see Benchmarks to reproduce.

Noisy neighbor. One tenant enqueues 10,000 jobs at once. Meanwhile, five small tenants submit a job every 100 ms between them. 8 workers, 5 ms per job. How long do the small tenants' jobs wait before they start?

claim ordering	small tenants: p50	p95	max
FIFO (oldest first)	7.11 s	13.50 s	14.25 s
fair (this project)	4 ms	6 ms	10 ms

Under FIFO, every small job waits behind whatever is left of the flood. Fair scheduling starts them almost immediately. The big tenant isn't slowed down: its backlog cleared in 11.2 s with fair ordering and 14.6 s with FIFO. With one run each, that gap is run-to-run variation, not a speed-up from fairness.

Throughput. 20,000 no-op jobs, jobs/second, median of 3 runs:

claim strategy	1 worker	2	4	8	16
FOR UPDATE (blocking)	166	194	205	206	208
FOR UPDATE SKIP LOCKED	222	202	393	762	1,363
SKIP LOCKED, 10 jobs per claim	308	366	718	1,420	2,396

With plain FOR UPDATE, every worker goes for the same next row and waits behind whoever locked it, so throughput stays flat at about 200 jobs/s however many workers you add. With SKIP LOCKED, each worker takes a different row: 16 workers do 6.5× the work of plain locking.

Throughput per worker is low because every job is two commits (claim, then complete), and each commit waits for the write-ahead log to reach disk. The bottleneck is that disk flush, not CPU: Docker Desktop showed less than one of the 22 cores busy during the run. That's also why adding workers keeps helping. Postgres group commit lets transactions that commit at the same moment share one flush. Claiming ten jobs at a time cuts the commits per job, which is where the batch row's gain comes from. (The dip from one to two workers is within run-to-run variation.)

Pickup latency. One idle worker, 60 jobs arriving 0.2–1.2 s apart, time from enqueue to start:

wake-up mechanism	p50	p95	max
LISTEN/NOTIFY	6.4 ms	37.6 ms	38.3 ms
polling every 1 s	610 ms	984 ms	995 ms

Crash recovery. 1,000 jobs, 4 workers, and one worker killed with SIGKILL every second (17 kills). All 1,000 jobs finished; 13 were recovered from a killed worker and re-run. None were lost.

How it works

 client ──POST /jobs──▶ API ──vtime + INSERT + NOTIFY──▶ ┌──────────┐
                                                         │   jobs   │◀── maintenance (every worker, ~1/s):
 worker ◀──LISTEN wake-up─────────────────────────────── │ tenants  │      reap expired leases,
   │──claim lowest vtime (FOR UPDATE SKIP LOCKED)──────▶ └──────────┘      promote due scheduled jobs
   │──run handler (heartbeat extends lease)
   └──complete / fail (fenced by worker id + attempt number)

scheduled ──run_at reached──▶ queued ──claim──▶ running ──▶ done
    ▲                                              │
    └────────── failed (backoff) / lease expired ──┴──▶ dead (out of attempts)

Design decisions

1. Fair scheduling with virtual time. With a plain FIFO queue, a tenant that enqueues 50,000 jobs pushes every other tenant's work back by 50,000 jobs. Instead, each job gets a virtual time (start-time fair queuing) when it becomes runnable, and workers always take the lowest one:

vtime = max(queue's current virtual time, tenant's last vtime) + 1 / weight

The flooding tenant's jobs get vtimes 1, 2, 3, …, 50,000. A tenant that shows up later starts at the queue's current virtual time (the vtime at the head of the queue). Its jobs interleave with the flood instead of waiting behind it. An idle tenant doesn't bank credit while it's away: it restarts from the current virtual time too, not from where it left off. Weights divide the workers proportionally, so a tenant with weight 3 gets three jobs run for every one from a weight-1 tenant.

The point of doing this at enqueue time is that the claim path doesn't change. Claiming is still one SKIP LOCKED index scan, with no per-tenant locks, counters, or extra round trips. The throughput numbers above are with fair ordering on.

2. FOR UPDATE SKIP LOCKED to claim work. The claim is a single statement. A CTE selects the lowest-vtime runnable ids FOR UPDATE SKIP LOCKED LIMIT n, and an UPDATE … FROM that CTE marks them running. Rows another worker has locked are skipped instead of waited on, so N workers take N different jobs at once, and no job can be handed out twice. The test suite checks this directly: 8 threads racing over 2,000 jobs claim each exactly once. With the lock removed, the same test catches duplicate claims.

3. Leases, not long-held locks. Claiming flips the job to running, records locked_until = now() + lease, and commits immediately. No transaction or row lock stays open while the job runs. If a worker dies, nothing is left locked; the lease runs out and the job is recovered. Holding a row lock for the length of the job would tie up a database connection per running job and leave crashed work stuck until the connection timed out.

4. Heartbeats for long jobs. While a handler runs, a background thread extends the lease every lease/3 seconds, so a 10-minute job with a 30-second lease isn't mistaken for a dead worker. If the heartbeat finds it no longer owns the job, it stops.

5. Fencing with the attempt number. A worker that stalls (GC pause, network partition) can come back after its lease expired and the job was given to someone else. complete() and fail() only apply WHERE locked_by = me AND attempts = <the attempt I claimed>, so a stale worker's late write is rejected instead of overwriting the new owner's run. Checking the worker id alone isn't enough: the same worker can be handed the same job again, and only the attempt number tells the two runs apart.

6. A separate scheduled state. Delayed jobs and retries waiting out their backoff sit in scheduled, outside the claim index. Each worker's maintenance step promotes due ones to queued, assigning a fair vtime at that moment. The claim query never has to scan past jobs that aren't due yet, and a job that's been backing off doesn't jump the line when it comes back.

7. Retries with exponential backoff and full jitter. A failed job is rescheduled random(0, min(cap, base·2^(attempt-1))) seconds later. Without jitter, a burst of jobs failing against the same downstream service would all retry in lockstep and hit it in waves. Handlers raise PermanentError for failures retrying can't fix (bad input), which sends the job straight to dead. Each lease expiry also counts as an attempt, so a job that crashes every worker that touches it ends up dead instead of looping forever.

8. Idempotency keys enforced by a unique constraint. POST /jobs with an idempotency_key that already exists returns the original job (200) instead of creating a second one (201). Deduplication is INSERT … ON CONFLICT DO NOTHING on a unique column, not a check-then-insert in Python, so it holds under concurrency: 10 simultaneous requests with the same key create exactly one row. The losing requests roll back their whole transaction, so the tenant isn't charged virtual time for jobs that were never created.

9. LISTEN/NOTIFY instead of polling. Enqueue sends pg_notify in the same transaction as the INSERT. Postgres delivers notifications only on commit, so a woken worker never looks for a row it can't see yet. A fallback poll still runs, because a notification can be missed while a worker reconnects.

10. Partial indexes, and deadlock-free promotion. Each query has an index containing only the rows it can match: runnable jobs by (queue, vtime, id), scheduled jobs by run_at, running jobs by lease expiry. They stay small however many finished jobs pile up. When promoting a batch, tenant rows are locked in sorted order, so two workers promoting at the same moment can't deadlock.

11. Graceful shutdown. On SIGTERM (docker stop) a worker finishes the job in hand, then exits, rather than abandoning it and making it wait out a lease.

Delivery guarantee

At-least-once. A job is never lost, but if a worker dies after doing the work and before recording it, the job runs again. Handlers must be idempotent; for side effects like charging a card, pass the job id through as the downstream idempotency key. Exactly-once execution across a crash isn't possible without the downstream system's cooperation.

Running it

docker compose up --build

This starts Postgres, applies the schema, then starts the API on port 8000 and a worker service with two processes.

curl -X POST localhost:8000/jobs -H "Content-Type: application/json" \
     -d '{"task": "word_count", "tenant": "acme", "payload": {"text": "hello job queue"}}'
curl localhost:8000/jobs/1
curl localhost:8000/metrics

endpoint
POST /jobs	{task, payload?, tenant?, queue?, idempotency_key?, max_attempts?, delay_seconds?} → 201, or 200 for a repeated key
POST /jobs/batch	{task, payloads: [...], tenant?, queue?}, up to 1,000 jobs in one statement
GET /jobs/<id>	job status, attempts, last error
POST /jobs/<id>/retry	requeue a dead job (409 if it isn't dead)
PUT /tenants/<tenant>	{weight, queue?}: a tenant's share of the workers
GET /stats	job counts by queue and status
GET /metrics	Prometheus format: jobs by status, age of the oldest runnable job, largest backlogs by tenant
GET /health	liveness and database check

Without Docker: set DATABASE_URL, then python init_db.py, gunicorn app:app, and python worker.py --concurrency 4. Tasks are plain Python functions registered in handlers.py.

Tests

37 tests, all against a real PostgreSQL database, run in CI on every push. Locking, SKIP LOCKED, and LISTEN/NOTIFY only exist in Postgres, so mocks couldn't test them.

docker compose run --rm api pytest -q

Covered:

• Fairness: a late tenant interleaves with a 1,000-job flood, three tenants take strict turns, weights divide work 3:1, idle tenants don't bank credit, and a tenant's new jobs never overtake its own backlog. All five fail if the claim is switched to FIFO.
• Concurrency: exclusive claims with 8 threads racing, distinct vtimes under 8 concurrent enqueuers, and idempotency under 10 concurrent duplicate requests.
• Failure handling: retry → dead, backoff scheduling, permanent failures, lease expiry and recovery, fencing of stale workers (including the same-worker case), jobs that keep crashing workers, and heartbeats keeping a long job's lease.
• Worker loop: a notification waking an idle worker, a worker recovering a crashed worker's job, and retries running to completion.
• API: validation, batch enqueue, weights, metrics, and JSON errors.

Benchmarks

One command runs everything and prints a single report. It uses its own database (jobq_bench), so the running API and workers are unaffected:

docker compose run --rm worker python bench/run_all.py

Or individually: bench_fairness.py, bench_throughput.py, bench_latency.py, chaos.py.

It takes 30–60 minutes on Docker Desktop, mostly in the throughput step. The throughput jobs are no-ops, so those numbers measure queue overhead, not useful work. They depend heavily on how fast the disk flushes: Postgres runs with synchronous_commit = on, so every claim and every completion waits for the write-ahead log to reach disk.

Limitations and what I'd do next

• Table growth. Finished jobs stay in the table. A production version would delete or archive done rows on a schedule, or partition by created_at and drop old partitions.
• Ceiling. Every claim and completion is a write to one table. That suits thousands of jobs per second; at much higher volume, a log-based system like Kafka is the right tool.
• Fairness is per job, not per second of work. A tenant whose jobs each take 10× longer gets 10× the worker time. Charging vtime by measured duration would fix that.
• Concurrency caps per tenant (at most N of a tenant's jobs running at once) aren't implemented. Doing it exactly needs a per-tenant counter, which reintroduces a lock on the claim path.
• Connection poolers. LISTEN needs a dedicated session, so workers must connect directly to Postgres, not through PgBouncer in transaction mode.