Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Design Case Studies

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.

Advanced 18 min Last reviewed

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

Job scheduler: define, dispatch and execute paths Define path: clients create jobs through the API, which stores each job with its next run time in the job store. Dispatch path: scheduler nodes, each owning some partitions assigned by a coordination service, scan their partitions for jobs whose next run time has passed, create a run record, compute the next run time and push the run onto the dispatch queue. Execute path: workers take runs from the queue, hold a lease on each run renewed by heartbeats, and report completion; a lease that expires makes the run eligible for retry. scan due create run enqueue take run lease, heartbeat, done Clients Job API Job store by partition, next_run_at Coordinator partition owners Scheduler A partitions 0-7 Scheduler B partitions 8-15 Run records state, lease Dispatch queue Workers heartbeat, ack Figure 1. Scheduler nodes only decide what is due; workers do the work. Each partition of the job table has one scheduler at a time, and every run is protected by a lease that expires if the worker goes silent.
  1. 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.
  2. 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.
  3. 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.

scheduler.pyruns with python3 (standard library)
# 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

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Think of keys as job partitions and nodes as scheduler nodes.

Try this:

  1. Remove a node. Which partitions move, and to whom? While they move, why might a few jobs fire a few seconds late?
  2. With one virtual node each, how uneven is the load? Raise virtual nodes and compare.
  3. 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

FailureImpactMitigation
Scheduler node diesIts partitions stop dispatchingCoordinator reassigns partitions; runs persisted, nothing lost
Old leader keeps dispatchingDuplicate runsFencing tokens checked by the store
Worker dies or goes silentRun stuckLeases with heartbeats; retry on expiry
Retried side effectsDouble emails or chargesRun id as idempotency key in jobs
Top-of-hour spikeLate runsJitter, early queueing, autoscaled workers
Poison jobRetries foreverRetry limit, dead state, alerts

Trade-offs we made

OptionWins whenLoses 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up