Design a Distributed Job Scheduler
A job scheduler has to start 100M runs a day on time, survive workers that die mid-run, and absorb the wave of cron jobs that all fire at the top of the hour. The design indexes runs by due time and hands each one to a worker under a lease.
1 · Requirements
The Prompt
Run 100M one-off and cron jobs a day at their scheduled times across a worker fleet, with retries, at-least-once execution, and run status.
Functional
- Schedule one-off jobs and recurring cron jobs
- Run each job on a worker fleet at its scheduled time
- Retry failed runs with backoff, up to a limit
- Pause, resume, and cancel jobs, and show the status of every run
Non-Functional
- Runs start within a few seconds of their due time
- Every run executes at least once, even when workers crash
- Absorbs the top-of-hour wave without dropping runs
2 · Estimates
Drill This Phase First
Show the Answer and Estimates
Answer
About 6,000
100M divided by 86,400 seconds is about 1,200 starts a second. Each runs 5 seconds, so about 1,200 times 5, or 6,000, are running at any moment.
- Runs
- 100M runs a day: about 1,200 starts a second on average
- Concurrency
- Jobs average 5 seconds, so about 6,000 run at once. At 20 slots per worker, that is about 300 workers
- Top of Hour
- About a third of each hour's 4.2M runs fire at minute 0: about 1.4M in the first minute, roughly 23,000 a second
- Wave
- Scaling to 1,500 workers, or 30,000 slots, before each hour drains that wave at 6,000 a second in about 4 minutes
- Storage
- 10M job definitions at 1 KB is 10 GB. 100M runs a day at 500 bytes is 50 GB a day, or 1.5 TB for 30 days of history
- Scans
- 16 scheduler shards looking 10 seconds ahead at 23,000 runs a second: about 14,000 rows per shard per scan
3 · API
POST /jobs { name, schedule (cron) | run_at, payload, retry: { max, backoff }, timeout_s } → { job_id, next_run_at }
GET /jobs/:id → { schedule, next_run_at, last_run: { status, started_at } }
GET /jobs/:id/runs?limit= → { runs[{ run_id, status, attempt, started_at, ended_at }] }
POST /jobs/:id/pause and POST /jobs/:id/resume → 204
DELETE /jobs/:id → 204 (cancels future runs)Data Model
jobs (SQL, sharded by job_id):
job_id (PK) : uuid
owner_id : uuid
schedule : string? cron expression
run_at : timestamp? one-off jobs
payload : json
max_retries : int
timeout_s : int
status : enum(active|paused|deleted)
runs (SQL, same shard as the job, index (status, due_at)):
run_id (PK) : uuid idempotency key for the job
job_id : uuid
due_at : timestamp
status : enum(scheduled|queued|running|succeeded|failed|dead)
attempt : int
lease_expires_at : timestamp?
fencing_token : bigint rises with each attempt
worker_id : string?4 · High-Level Design
5 · Deep Dives
Finding Due Runs
Index runs by status and due_at, and have each scheduler scan its shard for runs due in the next 10 seconds, mark them queued, and push them to the queue. When a cron run is queued, the scheduler inserts the next occurrence, so the table always holds each job's next run. One leader per shard, chosen with a lease in etcd or ZooKeeper, keeps two schedulers from queueing the same run, and a sweep requeues any run stuck in queued.
Leases, Heartbeats, and Retries
A worker claims a run with a lease a few times longer than its heartbeat interval and renews it while the job runs. If the worker dies, the lease lapses and the run returns to the queue as a new attempt. Failed runs wait in a retry queue with exponential backoff and jitter until max_retries, then move to a dead letter list that alerts the owner.
Duplicates and the Hourly Spike
A lease can lapse while a slow worker is still running, so two copies of a run may overlap. Pass the run_id as an idempotency key, and give each attempt a rising fencing token so the downstream system rejects writes from a stale worker. For the top of the hour, add a few seconds of jitter to jobs that allow it and scale the fleet ahead of time.
6 · Wrap Up
The Short Version
Store runs in a sharded database indexed by due time. One scheduler per shard scans the next few seconds of due runs and queues them, and workers run each under a lease with heartbeats. Idempotent jobs make at-least-once delivery safe.