system-design

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, Idempotency, Leader Election

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

flowchart TB
    API[Job API] --> JobDB[(Job store<br/>definition + next_run_time)]
    Scheduler[Scheduler<br/>leader, leased] -->|poll due jobs| JobDB
    Scheduler -->|enqueue due jobs| Q[[Execution queue]]
    Q --> W1[Worker]
    Q --> W2[Worker]
    W1 -->|update status,<br/>compute next_run| JobDB
    W1 --> History[(Execution history)]
    ZK[Leader election<br/>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: 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 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)

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)

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

Finding due jobs → index/time-bucket on run time; cheap window query.
Execution throughput → scale workers off a queue; independent of the scheduler.
Double-firing → leader election or partitioned ownership with leases.
Round-time spikes → jitter + windowed execution + autoscaling.
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.