# Design a Distributed Job Scheduler (Cron at Scale) **Difficulty:** Tier 2 **Asked at:** Amazon, Google, Uber, fintechs **Time budget:** 45 min > "Run this task at this time" sounds trivial until you need it reliable across a fleet: run **exactly once** > (not zero times, not five), survive worker crashes mid-job, handle millions of scheduled jobs, and never > silently drop one. This question is about **durable scheduling**, **at-least-once + idempotency**, and > **leader/lease-based coordination** so two schedulers don't double-fire. **Prerequisites:** [Background Jobs](../02-building-blocks/19-background-jobs.md), [Idempotency](../04-distributed-systems/11-idempotency.md), [Leader Election](../04-distributed-systems/04-leader-election.md) --- ## 1. Requirements **Functional:** - Schedule jobs: one-off (run at time T) and **recurring** (cron expressions, "every day at 2am"). - Execute jobs reliably at (or near) their scheduled time. - Retry failed jobs; report status/history. - Cancel/update scheduled jobs. **Non-functional:** - **Reliable / no lost jobs** — a scheduled job *must* run (durability). - **Exactly-once execution semantics** — don't run a job twice (or make it safe if you do). - **Scale** — millions of scheduled jobs, thousands executing concurrently. - **Timely** — fire close to the scheduled time; some jobs are latency-sensitive. - **Fault-tolerant** — worker/scheduler crashes don't drop or duplicate jobs. **Out of scope:** the job *logic* itself; complex DAG dependencies (mention workflow engines like Airflow). --- ## 2. Estimation - **10M scheduled jobs**, most recurring. At any second, some are due → maybe **thousands of executions/sec** at peak (e.g. many "run at midnight" jobs — a **hotspot at round times**). 🚨 Round-time thundering herd is a real concern. - Storage: job definitions + execution history → a database (durable); millions of rows, modest size. - The scheduler must efficiently find "jobs due now" without scanning millions of rows every second. --- ## 3. High-level design ```mermaid flowchart TB API[Job API] --> JobDB[(Job store
definition + next_run_time)] Scheduler[Scheduler
leader, leased] -->|poll due jobs| JobDB Scheduler -->|enqueue due jobs| Q[[Execution queue]] Q --> W1[Worker] Q --> W2[Worker] W1 -->|update status,
compute next_run| JobDB W1 --> History[(Execution history)] ZK[Leader election
ZooKeeper/etcd] -.-> Scheduler ``` - **Job store**: durable record of each job + its `next_run_time`. Indexed on `next_run_time`. - **Scheduler**: periodically queries "jobs where next_run_time ≤ now," and **enqueues** them for execution. For recurring jobs, computes the next run time and updates the record. - **Workers**: pull from the execution queue, run the job, report status, retry on failure. - 🚨 **Separate scheduling (deciding *what* to run *when*) from execution (actually running it)** — the scheduler is lightweight; workers scale independently. --- ## 4. Deep dives ### 4a. Finding due jobs efficiently Don't scan 10M rows every second. **Index on `next_run_time`** and query a small time window (`next_run_time BETWEEN now AND now+Δ`). Or use a **time-bucketed** structure / priority queue keyed by run time so "what's due" is a cheap range read. Workers claim jobs from the due set. This keeps the poll cheap regardless of total job count. ### 4b. Exactly-once: the hard guarantee 🚨 **True exactly-once is impossible in a distributed system; you approximate it** with **at-least-once delivery + idempotency**: - Deliver each due job to *at least one* worker (retry until acked) — guarantees it runs. - Make execution **[idempotent](../04-distributed-systems/11-idempotency.md)**: each job run has a unique execution ID; a worker records "execution X started/completed" atomically (compare-and-set / a claim row) so a duplicate delivery doesn't run the job twice. - Result: the job runs *at least once*, and duplicates are suppressed → **exactly-once *effect*.** ### 4c. Preventing double-scheduling (coordination) If multiple scheduler instances run (for HA), two could both fire the same job. Prevent it with: - **Leader election** — one scheduler is the leader that does the polling ([leader election](../04-distributed-systems/04-leader-election.md) via ZooKeeper/etcd). If it dies, a standby takes over. - Or **partition** the job space across schedulers (each owns a shard of jobs) with **leases** so ownership is exclusive and recovers on failure. 🚨 Either way, exactly one entity is responsible for firing any given job at any time. ### 4d. Handling worker crashes mid-job A worker claims a job with a **lease/visibility timeout**. If it crashes before completing, the lease expires and the job becomes available for another worker to pick up (retry). Combined with idempotency, this ensures the job completes without duplicating side effects. ([Background Jobs](../02-building-blocks/19-background-jobs.md)) ### 4e. The round-time thundering herd Many jobs scheduled for "midnight" or "top of the hour" all fire at once → a spike. Smooth it: add **jitter** to scheduled times, spread execution over a window, and autoscale workers for known peaks. The queue absorbs the burst; workers drain it. ([Thundering Herd](../10-performance/05-thundering-herd.md)) ### 4f. Retries & failure Failed jobs retry with exponential backoff, up to a max, then go to a **dead-letter** state with alerting. Distinguish retryable (transient) from non-retryable (bad job) failures. Record every attempt in history. --- ## 5. Bottlenecks & scaling further 1. **Finding due jobs** → index/time-bucket on run time; cheap window query. 2. **Execution throughput** → scale workers off a queue; independent of the scheduler. 3. **Double-firing** → leader election or partitioned ownership with leases. 4. **Round-time spikes** → jitter + windowed execution + autoscaling. 5. **Scale of job definitions** → shard the job store; partition scheduling by shard. --- ## 6. Trade-off summary | Decision | Chosen | Alternative | Why | | --- | --- | --- | --- | | Execution guarantee | At-least-once + idempotency | True exactly-once | Impossible to guarantee once; idempotency gives the effect | | Scheduling coordination | Leader election / leased partitions | Any scheduler fires | Prevents double-firing | | Scheduler vs execution | Separated | One combined process | Scale workers independently; keep scheduler light | | Due-job lookup | Indexed time window | Full scan | Cheap regardless of total jobs | | Round-time spikes | Jitter + windowing | Fire all at once | Avoids thundering herd | --- ## 7. Follow-up questions
How do you guarantee a job runs exactly once? You can't guarantee true exactly-once execution in a distributed system — network failures mean you can never be sure whether a job that you sent but didn't get an ack for actually ran, so you must choose to err toward running it again (at-least-once) or not (at-most-once). The standard answer is at-least-once delivery plus idempotent execution, which yields the exactly-once *effect*. You retry delivering a due job until a worker acknowledges completion, guaranteeing it runs at least once (never dropped). Then you make execution idempotent: each scheduled run gets a unique execution ID, and the worker atomically claims and records that execution (a compare-and-set on a claim/status row) before doing the work, so if the same run is delivered twice, the second delivery sees the execution already claimed/completed and does nothing. The job's side effects therefore happen once even though delivery might happen more than once — the practical guarantee real schedulers provide.
Two scheduler instances are running for high availability. How do you stop both from firing the same job? Ensure exactly one instance is responsible for any given job at any time, via coordination. One approach is leader election: the scheduler instances use a coordination service (ZooKeeper/etcd) to elect a single leader that does all the polling and firing, while the others stand by; if the leader dies, its lease expires and a standby is elected, so there's always exactly one active scheduler and no gap that drops jobs. The other approach is to partition the job space across schedulers — each instance exclusively owns a shard of jobs (via a lease on that shard), so no two schedulers ever consider the same job, and if one dies its shard lease expires and is reassigned. Both make firing responsibility exclusive and self-healing; the leased handoff is what prevents both double-firing (two owners) and dropping (no owner) during failures.
A worker crashes halfway through a job. What happens? The job is recovered and retried without losing it, and idempotency prevents duplicate side effects. Workers claim a job with a lease (visibility timeout): while a worker holds the lease, the job is invisible to others. If the worker crashes before reporting completion, it stops renewing the lease, the lease expires, and the job becomes visible again for another worker to claim and run. Because execution is idempotent (the run has a unique ID and the worker records progress atomically), re-running a job whose earlier attempt may have partially executed doesn't double its effects — it either completes the not-yet-done work safely or detects it was already completed. So a crash costs a retry and some delay, never a lost job or a duplicated one.
Thousands of jobs are all scheduled for midnight. What breaks and how do you fix it? They all become due at the same instant, producing a huge spike of simultaneous executions — a thundering herd that can overwhelm workers and any downstream systems the jobs touch. Fix it by de-synchronizing and smoothing: add jitter to scheduled times so "midnight" jobs actually fire spread across a small window rather than the same millisecond; execute the due set over a window instead of all at once; and autoscale the worker pool ahead of known peak times. The execution queue also acts as a buffer — all the due jobs are enqueued quickly, but workers drain them at a sustainable rate, converting an instantaneous spike into a brief elevated-throughput period. The scheduler stays cheap because it just enqueues; the queue and worker scaling absorb the burst.
--- ## 8. What junior / mid / senior answers look like - **Junior:** a cron loop that queries jobs and runs them. Works single-node; loses jobs on crash, can double-fire, scans inefficiently. - **Mid:** durable job store indexed on run time, scheduler enqueues due jobs, workers execute off a queue, retries, recurring-job next-run computation. - **Senior:** at-least-once + idempotency for exactly-once effect, leader-election/leased-partition coordination to prevent double-firing, lease-based worker recovery for crashes, jitter/windowing for round-time herds, and a clean split between lightweight scheduling and independently-scaled execution — articulating why true exactly-once is impossible. --- ## Further reading - [Background Jobs](../02-building-blocks/19-background-jobs.md) · [Idempotency](../04-distributed-systems/11-idempotency.md) · [Leader Election](../04-distributed-systems/04-leader-election.md) - [Design a Notification System](./06-notification-system.md) — a big consumer of scheduled/queued work - [Design an E-Commerce System (Amazon)](./19-e-commerce.md) — next