System Design HLD-19.17
Design a distributed job scheduler
Design a job scheduler: cron at scale, leader-based or partitioned scanning of due jobs, leases, at-least-once runs, retries and a job state machine.
The problem
On one machine, cron runs a script at 2 am. It works until the machine dies at 1:59, or until you have ten million schedules from thousands of teams: send each user's weekly digest, expire trials, rebuild reports every hour, retry failed webhooks in five minutes. A distributed job scheduler is cron as a service: it stores job definitions, notices when each is due, hands it to a worker, and keeps track of what ran, what failed and what to retry.
Two promises are in tension. Jobs must not be missed when machines fail, and ideally they should not run twice. In a distributed system you cannot have both perfectly: a worker that goes silent may be dead or may be slow. The design picks "at least once" and makes duplicates harmless.
Requirements
Functional
- Create, update, pause and delete jobs: a cron expression or a one-off time, a payload, a target (queue or endpoint), a timeout and a retry policy.
- Run each job when due, on some worker.
- Record every run: start, end, outcome, logs; retry failures with backoff.
- Query job status and history.
Non-functional
- Scale: 10 million job definitions, most running hourly or daily.
- Timeliness: a job starts within a few seconds of its scheduled time.
- Reliability: no run is lost when a scheduler or worker dies.
- Delivery: at least once; jobs are expected to be idempotent.
Out of scope
- Workflows with dependencies between jobs ( Workflow engines ) and running the workers' code itself.
Estimates
- Runs: if the 10M jobs average one run an hour, that is 10M / 3,600, about 2,800 runs per second on average.
- Spikes: people love round numbers. If 30 percent of jobs say "at minute 0", 3 million runs are due at the top of every hour. Dispatching them within a minute needs 50,000 per second, so the scheduler adds a small jitter to jobs that tolerate it and must be able to burst.
- History: 2,800 x 86,400 = about 240 million runs a day. At 200 bytes per run record, 48 GB a day, about 1.4 TB for 30 days of history.
- Definitions: 10M x 1 KB = 10 GB. Small; the challenge is scanning "what is due now" efficiently and safely.
API
POST /v1/jobs { name, schedule: "0 * * * *", payload, target, timeout_s, retry: { max: 5, backoff: "exp" } }
GET /v1/jobs/{job_id}
PATCH /v1/jobs/{job_id} { paused: true }
DELETE /v1/jobs/{job_id}
GET /v1/jobs/{job_id}/runs?cursor=...
# worker side
POST /v1/runs/{run_id}/heartbeat # extends the lease
POST /v1/runs/{run_id}/complete { outcome, output }
Each run carries a run id made from the job id and the scheduled time, so a worker can use it as an idempotency key for its side effects ( Idempotency and safe retries ).
Data model
- Jobs (relational, partitioned by
job_id):job_id, owner, schedule, payload, target, retry_policy, paused, next_run_at, partition. An index on(partition, next_run_at)makes "what is due in my partition" a range scan. - Runs:
run_id (job_id + scheduled_for), job_id, scheduled_for, state, attempt, lease_owner, lease_until, started_at, finished_at, outcome. - Dispatch queue ( Message queues vs pub/sub vs event streams ): runs ready to execute, per worker pool or priority.
High-level design
- Define path A client creates a job with a schedule. The API validates it, computes the first next_run_at and stores it in a partition of the job store chosen by hashing the job id.
- Dispatch path Each scheduler owns some partitions, as assigned by a coordination service. Every second it scans its partitions for jobs with next_run_at in the past, creates a run record, advances next_run_at in the same transaction, and enqueues the run.
- Execute path A worker takes a run, sets a lease on it, renews the lease with heartbeats while working, and marks it done. If the lease expires without a heartbeat, the run is retried on another worker.
Deep dives
Deep dive 1: Who decides what is due
Something must scan for due jobs, and if two schedulers scan the same job, it runs twice. Two designs:
- Leader-based: schedulers elect one leader ( Quorums and leader election ) through a coordination service ( Coordination services (ZooKeeper, etcd) ). Only the leader scans and dispatches. Simple, but one node does all the scanning, and a failover pauses dispatching for the election time. An old leader that was merely slow may wake up and keep dispatching, so its writes must carry a fencing token that the store rejects once a newer leader exists ( Distributed locks and fencing tokens ).
- Partitioned: jobs are hashed into, say, 1,024 partitions, and partitions are assigned to scheduler nodes by the coordinator (or a hash ring). Each node scans only its partitions, so scanning scales out. When a node dies, its partitions move to the others.
Inside a partition the scan is a range query on next_run_at. Creating the run and advancing next_run_at happen in one transaction, so a scheduler crash between them cannot lose or duplicate a run. Even simpler designs skip ownership entirely: all schedulers query ... FOR UPDATE SKIP LOCKED, and the database hands each due row to exactly one of them.
Deep dive 2: Leases and at-least-once
Once a run is dispatched, the worker might crash, hang, or finish and then lose its network before saying so. The scheduler cannot tell these apart, so it uses a lease: the run belongs to a worker until lease_until, extended by heartbeats. When a lease expires, the run is handed to another worker.
That is why runs are at least once: in the sample, a worker finishes the cleanup run but dies before acknowledging it.
# A scheduler loop with leases. Due jobs become runs; a run is leased to a
# worker for 20 s. One worker finishes its work but dies before reporting
# success, so its lease expires and the run is retried: at-least-once.
# Keying the side effect by run id (job + scheduled time) makes it safe.
JOBS = {"cleanup": 30, "report": 60} # job -> interval in seconds
DURATION = {"cleanup": 8, "report": 15}
LEASE, LAST = 20, 120 # schedule runs up to t = 120
next_run = {j: 0 for j in JOBS}
runs = {} # run id -> state
applied, effects = 0, set()
silent = {("cleanup", 30)} # first worker dies before acking
for t in range(0, 160):
for job, every in JOBS.items(): # 1. due jobs become runs
if next_run[job] <= min(t, LAST):
runs[(job, next_run[job])] = {"attempt": 0, "lease": -1,
"done": False, "finish": None}
next_run[job] += every
for rid, r in runs.items():
if not r["done"] and r["lease"] < t: # 2. lease free: (re)start
r["attempt"] += 1
r["lease"], r["finish"] = t + LEASE, t + DURATION[rid[0]]
print(f"t={t:3} {rid[0]:7} run for t={rid[1]:3}, "
f"attempt {r['attempt']}")
if not r["done"] and r["finish"] == t: # 3. work finishes
applied += 1
effects.add(rid) # idempotent: keyed by run id
if rid in silent and r["attempt"] == 1:
print(f"t={t:3} {rid[0]:7} worker dies before acking")
else:
r["done"] = True
print(f"{len(runs)} runs, side effect executed {applied} times, "
f"applied once per run: {len(effects)}")Output
t= 0 cleanup run for t= 0, attempt 1
t= 0 report run for t= 0, attempt 1
t= 30 cleanup run for t= 30, attempt 1
t= 38 cleanup worker dies before acking
t= 51 cleanup run for t= 30, attempt 2
t= 60 cleanup run for t= 60, attempt 1
t= 60 report run for t= 60, attempt 1
t= 90 cleanup run for t= 90, attempt 1
t=120 cleanup run for t=120, attempt 1
t=120 report run for t=120, attempt 1
8 runs, side effect executed 9 times, applied once per run: 8 The 30-second cleanup run finished at t = 38, but nobody heard, so its lease ran out at t = 50 and attempt 2 started at t = 51. The side effect executed 9 times for 8 runs. Because the effect is keyed by the run id ("cleanup for t = 30"), the second execution changed nothing. Real jobs do the same with an idempotency key, an upsert, or a check like "has the digest for this week been sent?" ( Delivery semantics ).
Lease length is a trade-off: short leases retry quickly after a crash but risk a second worker starting while a slow first one is still running; long leases avoid that but delay recovery. Heartbeats let leases stay short while long jobs keep running.
Deep dive 3: The run state machine and retries
Each run moves through scheduled -> queued -> running -> succeeded, or failed -> retrying -> queued with exponential backoff and jitter ( Timeouts, retries, backoff and jitter ), until the retry limit sends it to dead, where an alert fires and a person looks. Timeouts are failures too: a run past its timeout_s is marked failed even if the worker is still heartbeating.
Two scheduling policies need explicit choices:
- Overlap: if the 10:00 run of an hourly job is still running at 11:00, do you start 11:00 anyway, skip it, or queue it? Make it a per-job setting.
- Missed runs: after an outage, a job that should have run 6 times may run once ("catch up to now") or 6 times ("backfill"). Most jobs want once.
Deep dive 4: Spikes at round times
Cron expressions cluster on minute 0 and midnight. Three defences: add a deterministic jitter (hash of the job id mod the allowed delay) for jobs that tolerate it; pre-load runs due in the next minute into the queue a little early with a "not before" time; and size workers by queue depth with autoscaling. The scheduler's own scan stays cheap because it is a range read on an index.
Try it
Think of keys as job partitions and nodes as scheduler nodes.
Try this:
- Remove a node. Which partitions move, and to whom? While they move, why might a few jobs fire a few seconds late?
- With one virtual node each, how uneven is the load? Raise virtual nodes and compare.
- Switch to modulo hashing and remove a node. Why would that be painful for schedulers that cache their partitions' due jobs in memory?
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| Scheduler node dies | Its partitions stop dispatching | Coordinator reassigns partitions; runs persisted, nothing lost |
| Old leader keeps dispatching | Duplicate runs | Fencing tokens checked by the store |
| Worker dies or goes silent | Run stuck | Leases with heartbeats; retry on expiry |
| Retried side effects | Double emails or charges | Run id as idempotency key in jobs |
| Top-of-hour spike | Late runs | Jitter, early queueing, autoscaled workers |
| Poison job | Retries forever | Retry limit, dead state, alerts |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| Partitioned schedulers (chosen) | Scanning scales out; a node failure affects only its partitions | Partition assignment and rebalancing |
| Single leader | Simplest correct design | One node scans everything; dispatch pauses during failover |
| At-least-once with leases (chosen) | No run is lost when workers fail | Jobs must be idempotent |
| Short leases with heartbeats (chosen) | Fast recovery even for long jobs | Heartbeat traffic; slow workers may lose their lease |
Extensions
- Job dependencies (run B after A succeeds), which turns the scheduler into a workflow engine.
- Priorities and quotas per team so one team's million jobs do not starve others.
- Time zones and daylight saving in cron expressions.
- Delayed one-off tasks at very high volume (retry this webhook in 5 minutes), often with timer wheels or delay queues.
In the wild
Where you will see this: cloud schedulers and serverless cron triggers, Kubernetes CronJobs, data pipeline orchestrators, and the background job systems inside most web applications. Whatever the scale, they share the same core: durable definitions with a next run time, a single owner for each due job, leases on running work, and idempotent jobs.
Check yourself
-
Why are scheduled runs at least once rather than exactly once?
Show answer
B. A silent worker may be dead or slow; retrying after its lease expires can repeat work that already happened The scheduler cannot distinguish a crash from a lost acknowledgement, so it retries; jobs must tolerate repeats.
-
Why must creating a run and advancing next_run_at happen in one transaction?
Show answer
B. A crash between them would lose a run or create it twice Both changes describe the same decision; they must commit together.
-
What protects against an old leader that keeps dispatching after a new one is elected?
Show answer
B. Fencing tokens that the store checks and rejects when stale A monotonically increasing token lets the store refuse writes from a deposed leader.
-
Three million jobs are due at minute 0 every hour. What helps most?
Show answer
B. Deterministic jitter for tolerant jobs, early queueing and autoscaled workers Spreading and pre-staging the spike turns it into a manageable stream.
Recap
- Store jobs with next_run_at; scanning for due jobs is a range query per partition.
- Give each partition one scheduler at a time, by leader election or partition assignment, with fencing.
- Create the run and advance next_run_at in one transaction.
- Lease runs to workers with heartbeats; expired leases mean retries, so runs are at least once.
- Make jobs idempotent with the run id, cap retries, and spread spikes with jitter.
Next up
- Crack the system design round learning path