Distributed Job Scheduler
IntermediateOverview
A distributed job scheduler runs tasks at specified times or intervals - cron at scale. It accepts one-off and recurring jobs, guarantees each scheduled run executes (despite worker crashes), scales to millions of jobs, and does not double-run a job just because a node failed mid-execution. The tension is between not missing a run (at-least-once) and not duplicating side effects, resolved with idempotency and careful ownership.
Functional Requirements
- Submit a one-time job (run at time T) or a recurring job (cron expression).
- Execute each due job on a worker, with retries on failure.
- Track job status (scheduled, running, succeeded, failed) and expose it.
- Support priorities and per-job timeouts; allow cancellation.
Non-Functional Requirements
- Reliability: every due job runs at least once, even across worker/scheduler crashes.
- No double execution of side effects: at-least-once delivery with idempotent jobs.
- Scalability: millions of scheduled jobs; thousands of executions/sec.
- Timeliness: a job starts close to its scheduled time (low scheduling latency).
- Fault tolerance: no single point of failure in the scheduling path.
Capacity Estimation
Assume 10M scheduled jobs, with 10K jobs/sec becoming due at peak.
- QPS: 10K executions/sec at peak; job submissions much lower (~hundreds/sec).
- Storage: 10M jobs x ~1 KB (definition, schedule, state) = ~10 GB for definitions; execution history grows over time and is tiered/archived.
- Due-scan load: the scheduler must efficiently find "all jobs due in the next window" - an index on
next_run_timeis essential; scanning 10M rows per tick would not keep up. - Workers: at ~100 jobs/sec per worker (I/O-bound jobs), peak needs ~100+ workers, auto-scaled by queue depth.
The core driver is efficiently finding due jobs and dispatching them without missing or duplicating runs.
High-Level Architecture
The architecture consists of three main components: a durable Database (to store jobs and schedules), a fleet of Schedulers (that constantly poll the DB for jobs whose time has come), and a fleet of Workers (that pull due jobs from a Message Queue to execute them). A ZooKeeper or Redis cluster is often used to elect a leader among the Schedulers to prevent duplicate dispatch.
Data Model
| Entity | Fields / Schema | Storage Choice |
|---|---|---|
| job | job_id (PK), type, payload, cron/run_at, next_run_time, status, owner, attempts | Relational or wide-column, indexed on next_run_time (PostgreSQL or Cassandra) |
| execution | execution_id, job_id, started_at, finished_at, result, attempt | Append-only history store |
| lease | job_id, worker_id, lease_expiry | KV store with TTL (Redis) |
Detailed Design
Finding Due Jobs Efficiently
Jobs are indexed by next_run_time. The scheduler periodically queries "jobs where next_run_time <= now" - an indexed range scan, not a full table scan. For very high precision/scale, a hierarchical timing wheel (bucketed by time) makes "what's due now" an O(1) bucket read instead of a database query. After dispatching a recurring job, the scheduler computes its next next_run_time from the cron expression and updates the row.
Avoiding Duplicate Dispatch
If two scheduler instances both scan and dispatch, a job runs twice. Two standard defenses:
- Single active scheduler via leader election: only the leader dispatches; standbys take over on failure. Simple, but the leader's throughput caps the system.
- Sharded schedulers: partition the job space (by
job_idhash) across scheduler instances, each owning a slice, so dispatch parallelizes with no overlap.
Either way, dispatch marks the job with a conditional update (optimistic lock) so the same due instance isn't enqueued twice.
Execution with At-Least-Once + Leases
The scheduler enqueues due jobs onto a partitioned task queue (e.g., RabbitMQ or SQS); workers pull, acquire a lease (a TTL claim) on the job, and execute. If a worker crashes, its lease expires and another worker re-runs the job - guaranteeing execution but implying a job may run more than once. Therefore jobs must be idempotent.
Retries and Dead-Lettering
A failed job is retried with exponential backoff up to a limit; persistent failures go to a dead-letter queue for inspection so they don't loop forever. Per-job timeouts prevent a hung task from holding a worker indefinitely.
Bottlenecks & Solutions
The primary bottleneck is the Database Polling step. Continually querying a massive relational database for "jobs due now" creates severe load and limits scaling. To fix this, high-scale systems transition from database polling to in-memory Timing Wheels or push the scheduling logic into specialized message brokers (like RabbitMQ delayed messages or AWS SQS visibility timeouts).