Skip to content

Job scheduler

System Design Task: Job Scheduler with PostgreSQL

Problem Statement

Design a production-grade distributed job scheduler backed by PostgreSQL that can reliably enqueue, schedule, and execute millions of jobs per day across a fleet of worker nodes.

The system must handle high-throughput job ingestion, provide exactly-once execution guarantees, and remain performant under sustained load without degrading the database — addressing PostgreSQL-specific challenges like table bloat, VACUUM pressure, and MVCC overhead.

This scheduler will serve as the backbone for async task processing across multiple tenants, so it must be multi-tenant, observable, and operationally resilient.

Functional Requirements

Your system must support:

  1. Job Submission

  2. Submit jobs with a payload, priority, scheduled time, and tenant ID

  3. Support immediate execution and future-scheduled jobs

  4. Idempotent submission via client-provided deduplication keys

  5. Job Execution

  6. Workers poll for and claim jobs with exactly-once semantics

  7. Support configurable retry policies (max attempts, backoff strategy)

  8. Jobs can have a maximum execution timeout

  9. Job Lifecycle Management

  10. States: pending → running → completed / failed / dead

  11. Support cancellation of pending/running jobs

  12. Queryable job history per tenant

  13. Scheduling

  14. One-time delayed jobs (execute at time T)

  15. Recurring/cron jobs (execute every N minutes/hours)

  16. Priority-based ordering within a queue

  17. Multi-Tenancy

  18. Tenant-level isolation for job queues

  19. Per-tenant rate limiting and quota enforcement

  20. Fair scheduling across tenants (no single tenant starves others)

  21. APIs

POST   /api/v1/jobs                    — Submit a job
GET    /api/v1/jobs/{id}               — Get job status
DELETE /api/v1/jobs/{id}               — Cancel a job
GET    /api/v1/jobs?tenant=X&status=Y  — List jobs with filters
POST   /api/v1/jobs/{id}/retry         — Manually retry a failed job

Non-Functional Requirements

Requirement Target
Throughput 10,000+ jobs/sec enqueue, 5,000+ jobs/sec dequeue
Latency Job claim p99 < 50ms
Availability 99.95% uptime
Consistency Exactly-once execution (at-least-once with idempotency)
Retention Hot data: 7 days, Archive: 90 days
Multi-tenancy 1,000+ tenants, fair scheduling
Recovery Automatic requeue of orphaned jobs within 60 seconds

Deep Dive Areas (Required)

You must address all of the following PostgreSQL-specific challenges:

  1. Table Bloat & MVCC (xmin/xmax)
  2. How does PostgreSQL's MVCC model cause bloat in a high-churn job table?
  3. What is the role of xmin and xmax in tuple visibility?
  4. How does VACUUM reclaim dead tuples, and why can it fall behind?

  5. What is transaction ID wraparound and how do you prevent it?

  6. LISTEN/NOTIFY vs Polling

  7. How does PostgreSQL's LISTEN/NOTIFY work internally?
  8. What are its failure modes (connection loss, buffer overflow, no persistence)?

  9. When should you use it vs polling, and can you combine both?

  10. Heartbeat & Lease Problems

  11. How do workers prove they are alive (heartbeat vs lease)?
  12. What happens during GC pauses, network partitions, or clock skew?

  13. How do you avoid the "zombie worker" problem (worker thinks it owns a job, but lease expired)?

  14. Partitioning Strategy

  15. DROP PARTITION vs DELETE — performance and bloat implications
  16. Partitioned tables vs separate tables per tenant vs single table
  17. How does partition pruning affect the ordered scan problem?

  18. Index behavior across partitions (local vs global indexes)

  19. The Ordered Scan Problem

  20. Why does SELECT ... ORDER BY priority, scheduled_at LIMIT 1 FOR UPDATE SKIP LOCKED degrade?
  21. How does index bloat and dead tuple accumulation affect this scan?

  22. What are the alternatives (hash-based sharding, separate priority queues, materialized ready queue)?

  23. Multi-Tenancy Isolation

  24. Schema-per-tenant vs row-level tenancy vs queue-per-tenant
  25. How to prevent a noisy neighbor from starving others
  26. Tenant-aware connection pooling and resource limits

Constraints & Assumptions

  • PostgreSQL is the only persistent store (no Redis, no external queue)
  • Workers are stateless and horizontally scalable
  • Network partitions between workers and DB are possible
  • Clock skew between workers is bounded (NTP, < 1 second)
  • Job payloads are < 64 KB (larger payloads stored in object storage, job carries a reference)

Evaluation Criteria

Criteria Weight
PostgreSQL internals depth 25%
Bloat/VACUUM strategy 20%
Correctness (exactly-once, leases) 20%
Partitioning & scan optimization 15%
Multi-tenancy design 10%
Operational readiness 10%

Reference Systems

Study these for inspiration:

  • Graphile Worker — SKIP LOCKED-based, lightweight
  • pgboss — Node.js, partition-based archival
  • Temporal — Durable execution, lease-based ownership
  • Que — Ruby, advisory lock approach
  • River — Go, LISTEN/NOTIFY + polling hybrid

Interview Kit

Read first: Solution · OLTP §2 Postgres internals, vacuum · Transactions · Resilience §2 retries

Curveballs. The interviewer changes one thing mid-design. The hint in italics is what a strong answer reaches for:

  1. A worker pauses for 40 s mid-job; its lease expires and another worker runs the same job. How do you stop the first one's side effects? (Fencing by lease epoch, idempotency keys downstream.)
  2. Dead tuples from SKIP LOCKED churn make the queue table 10× its live size. (Autovacuum tuning, partition by time and drop partitions.)
  3. A tenant enqueues 50M jobs at once. How do the other tenants keep their latency? (Per-tenant fair scheduling and admission.)
  4. After a 2-hour outage, 30M delayed jobs are due at once. (Constant-work recovery, rate-limited catch-up; see load control §11.5.)

Must answer (security, privacy, operations):

  • Job payloads with personal data: encryption, retention, and deletion when a user leaves
  • Who may enqueue or cancel which tenant's jobs (API authorization)

Phase it (MVP → Growth → Scale): MVP: one Postgres table with FOR UPDATE SKIP LOCKED. Growth: partitioned tables, per-tenant fairness, a dead-letter queue. Scale: shard by tenant, archive to object storage.

Score yourself with the rubric.