Design a Distributed Job Scheduler

Cron & Task Scheduling System Design

Overview

A distributed job scheduler runs arbitrary tasks at a time you choose. You hand it a job — "send this report at 09:00," "clean up temp files every night at 2am," "rebuild the search index after the ingest finishes" — and it makes sure the job runs, on some worker in a pool, close to when it should, even if machines crash in between. Think of it as the engine behind cron, Airflow, Kubernetes CronJobs, or a cloud "scheduled tasks" product.

There are three flavors of work it must handle: a one-off job that fires once at a future time, a recurring job that fires on a repeating cron schedule, and a job that only runs after other jobs finish — a DAG of dependencies.

The action looks trivial — "run a function later" — but doing it reliably at scale is not. The scheduler must survive crashes (a job scheduled for next week can't live in a process timer), find "what's due now" among millions of jobs without scanning the whole table, run each job reliably even when a worker dies mid-execution, and not drift or double-run recurring jobs. We'll scope it, size it, model the data, design the API and architecture, then go deep on the three hard parts: finding due jobs efficiently, reliable at-least-once execution via leasing, and recurring jobs plus DAG dependencies.

Functional requirements

• Schedule a one-off job. Register a task to run once at a future run_at time. Once accepted, it must be stored durably.
• Schedule a recurring job. Register a task with a cron expression; the system fires it on every matching tick, indefinitely, without drift.
• Execute reliably on a worker pool. Each due job runs on some worker, at least once, close to its scheduled time.
• Retry on failure. A failed job is retried with backoff up to N attempts, then parked in a dead-letter store for inspection.
• Dependencies (DAG). A job can declare upstream jobs; it runs only after all upstreams succeed.
• Cancel / inspect. A caller can cancel a pending job and query a job's state and run history.

Out of scope (state it): the job's actual business logic (we run an opaque handler / container), sub-second real-time scheduling, and cross-region replication. We build the scheduler, not the tasks it runs.

Non-functional requirements

• Durability. Once accepted, a schedule survives crashes and restarts — it lives in a database, never only in a process timer.
• At-least-once execution. Every due job runs at least once. We prefer running a job twice (and rely on idempotency) over silently dropping it. Exactly-once dispatch under crashes is impossible; we're honest about that (deep dive 2).
• Bounded scheduling delay. A job fires within a small, bounded delay of its run_at (seconds, occasionally a minute under a burst), not the exact millisecond.
• Horizontal scalability. Millions of jobs can be due in the same second; the system drains the burst by adding workers, not by making one poller faster.
• No lost or double-drifting recurring jobs. A recurring job neither skips a tick nor slowly drifts off its schedule; overlapping runs of the same job are prevented.

Estimations

State assumptions; the goal is to justify a time-indexed store, leased workers, and bucket sharding — not to be exact.

Rounded assumptions

• Scheduled jobs live at once: ~100M jobs registered (many recurring, waiting for their next tick). This is the backlog the store must hold and index.
• Average execution rate: ~10K jobs/sec fire on a normal minute. This is the non-hot steady state — it excludes the top-of-hour and midnight spikes below, which are billed to the peak line, not the average. Modest — the create path and steady state are easy.
• Peak same-second fan-out: everyone writes 0 * * * * and 0 0 * * *, so the top of the hour and midnight are hot. Assume ~2M jobs due at 00:00 that must drain within ~60s → ~33K executions/sec — several times the average, and bursty.

How the numbers affect the design

Storage. A job row: ids (~32 B), cron/run_at (~16 B), next_run_at (8 B), status (1 B), attempt/lease (~24 B), handler ref + timestamps (~80 B) ≈ ~150 B. 100M jobs × ~150 B ≈ ~15 GB — small, but only useful if it's indexed by next_run_at so "what's due now" is a range read, not a scan.

Core entities / data model

Two things are stored: the job definition (what to run and when) and each execution (one attempt to run it, with a state machine). Separating them is what lets a recurring job accumulate a run history and lets retries be tracked per attempt.

An Execution.status is a forward-only state machine that only moves through legal transitions:

stateDiagram-v2
    [*] --> PENDING
    PENDING --> LEASED
    LEASED --> RUNNING
    RUNNING --> SUCCEEDED
    RUNNING --> FAILED
    LEASED --> PENDING
    RUNNING --> PENDING
    FAILED --> PENDING
    FAILED --> DEAD_LETTER
    SUCCEEDED --> [*]
    DEAD_LETTER --> [*]

The execution queue's visibility timeout is the single re-delivery mechanism; the Execution row just mirrors that queue state. LEASED --> PENDING and RUNNING --> PENDING are the crash-recovery edges: a worker that leased or was mid-run when it died stops renewing, its queue message becomes visible again, and the row returns to PENDING to be re-leased. The RUNNING --> PENDING edge matters most — a worker most often dies while running, not while merely holding a lease. FAILED --> PENDING is a retry (if attempts remain); FAILED --> DEAD_LETTER fires once attempts are exhausted (deep dive 2).

API design

A small REST API. Every create carries an idempotency key so a retried registration never creates two jobs.

Schedule a job

POST /api/jobs
Header: Idempotency-Key: <client-uuid>
Body: { "type": "recurring", "cron_expr": "0 2 * * *", "handler": "reports.nightly", "payload": {...}, "max_attempts": 3 }
201 Created
Returns: { "job_id": "job_42", "status": "SCHEDULED", "next_run_at": "2026-07-12T02:00:00Z" }

Register a one-off (type: one_off with run_at) or recurring (cron_expr) job. The server computes next_run_at (for cron, the first tick after now), writes the Job and its DueIndex row in one transaction, and returns. A one-off with a DAG dependency omits run_at and instead sets depends_on (deep dive 3).

Cancel a job

DELETE /api/jobs/{job_id}
200 OK  → { "job_id": "job_42", "status": "CANCELLED" }
409 Conflict  (if an execution is already RUNNING)

Cancel is a compare-and-set from SCHEDULED to CANCELLED; a job whose current execution is already RUNNING can't be cancelled mid-flight (returns 409), and a repeat cancel returns 200 idempotently.

Get a job and its run history

GET /api/jobs/{job_id}
200 OK → { "job_id": "job_42", "type": "recurring", "next_run_at": "...",
           "recent_executions": [ { "scheduled_for": "...", "attempt": 2, "status": "SUCCEEDED" }, ... ] }

Read the definition plus recent executions — the read-heavy path, served from a replica.

List failed / dead-lettered jobs

GET /api/dead-letter?cursor=<opaque>&limit=20
200 OK → { "items": [ { "job_id": "...", "last_error": "...", "attempts": 3 }, ... ], "next_cursor": "..." }

Operators inspect and replay jobs that exhausted retries, paginated with an opaque cursor.

High-level architecture

Two paths matter: a create path that durably records a schedule, and an execution path where a dispatcher moves due jobs into a queue and leased workers run them at least once.

1. Create path (register a schedule)

flowchart LR
    Client[Client / Service] -->|"POST job + Idempotency-Key"| API[Scheduler API]
    API -->|"insert key unique or return stored result"| DB[(Jobs DB)]
    API -->|"write Job + DueIndex row in one tx"| DB
    API -->|"return job_id + next_run_at"| Client

1. The request arrives with an idempotency key; the API tries to insert it. If it already exists, this is a retry — return the stored result.
2. Compute next_run_at, then write the Job and its DueIndex row in one transaction, so a job is never stored without being findable.
3. Return. The job is durable and will be picked up when its bucket comes due — no in-memory timer involved.

2. Execution path (fire due jobs, at least once)

flowchart LR
    Disp[Dispatcher] -->|"1. range read next_run_at <= now"| DB[(Jobs DB)]
    Disp -->|"2. enqueue due jobs"| Q[[Execution Queue]]
    W[Worker] -->|"3. lease job visibility timeout"| Q
    W -->|"4. run handler"| Handler[Job Handler]
    W -->|"5. ack success or nack for retry"| Q
    W -->|"6. record execution result"| DB

1. A Dispatcher does an indexed range read for jobs whose next_run_at <= now (deep dive 1), judged against an authoritative server clock, not the worker's wall clock.
2. It moves each due job into an Execution Queue and, atomically, advances the job past this tick (stamps the next next_run_at for recurring jobs) so it isn't re-selected next poll.
3. A Worker leases a job from the queue with a visibility timeout — the job is hidden from other workers while leased.
4. The worker runs the handler.
5. On success it acks (deletes the message); on failure or timeout the job becomes visible again and is retried (deep dive 2).
6. It records the execution's terminal state (SUCCEEDED / FAILED / DEAD_LETTER) in the DB.

3. Combined architecture

flowchart LR
    Client[Client / Service] --> API[Scheduler API]
    API -->|"Job + DueIndex + idempotency key one tx"| DB[(Jobs DB)]
    Dispatchers[Dispatchers - leased per bucket-shard] -->|"range read due jobs"| DB
    Dispatchers -->|"enqueue"| Q[[Execution Queue]]
    Dispatchers -->|"stamp next_run_at at enqueue"| DB
    Workers[Worker Pool] -->|"lease / ack / nack"| Q
    Workers -->|"record execution result"| DB
    Workers -->|"exhausted retries"| DLQ[(Dead Letter)]
    API -->|"reads"| Replica[(Read Replica)]

The Jobs DB is the durable hub holding jobs, the due-index, and executions. Dispatchers scan the due-index (each leasing a bucket-shard so two dispatchers don't drain the same slice), enqueue due jobs, and — for recurring jobs — stamp the next next_run_at atomically at enqueue time so the same tick can't be re-selected (deep dive 3). The Worker Pool scales horizontally, leasing jobs from the queue and running them; a crashed worker's lease expires and the job is re-delivered. Reads go to a replica.

Deep dives

1. The scheduling store + finding due jobs — without scanning the whole table

The defining constraint: among ~100M scheduled jobs, find the few thousand due this second cheaply, and drain a hot bucket where millions fire at once. Here are three approaches, worst to best.

  every 1s: scan all 100M rows to find ~10K that are due
  → 100M row reads/sec just to locate due work
  → the store melts; latency climbs; due jobs fire late

flowchart LR
    Bucket["Bucket 2026-07-12T00:00<br/>2M due, split into 32 shards"] --> S0["shard 0"]
    Bucket --> S1["shard 1"]
    Bucket --> Sdots["..."]
    Bucket --> S31["shard 31"]
    S0 -->|"lease"| WA["dispatcher A<br/>~62K rows"]
    S1 -->|"lease"| WB["dispatcher B<br/>~62K rows"]
    Sdots -->|"lease"| Wdots["...<br/>(2M / 32 ≈ 62K each)"]
    S31 -->|"lease"| WZ["dispatcher Z<br/>~62K rows"]
    WA --> Drain["32 dispatchers drain<br/>the minute in parallel"]
    WB --> Drain
    Wdots --> Drain
    WZ --> Drain
    style Bucket fill:#dcfce7,stroke:#16a34a,color:#14532d

The hot bucket. When millions share one second, add jitter where exact timing isn't required — spread run_at over a ±30s window at schedule time so the herd arrives smoothly instead of at one instant. Jobs that must fire at 00:00:00 keep their exact time and rely on sharding. If the fleet still lags, jobs wait in their durable bucket and drain oldest-first — a job fires late, never dropped.

2. Reliable execution — leasing, at-least-once, and idempotency

A due job will be dispatched at least once, and under crashes sometimes more. A worker leases a job, runs it, then dies before acking; its lease expires; another worker re-runs it. You cannot prevent every duplicate, so the goal is an exactly-once effect — at-least-once execution plus an idempotent job.

Leasing (visibility timeout). When a worker pulls a job from the queue, the job isn't deleted — it's hidden for a lease window (say 60s). The worker runs the handler and acks on success, which deletes the message. If the worker crashes, its lease expires, the job becomes visible again, and another worker re-runs it. That single mechanism is what makes a crashed worker not drop the job.

crash after running, before ack:
  worker A: lease job_42 (visibility 60s) → run handler → CRASH at 40s
  at 60s: lease expires → job_42 visible again
  worker B: lease job_42 → run handler → ack
  → job ran (twice); with an idempotent handler the effect is once

Idempotency is mandatory. Because the job can run more than once, the job must be safe to repeat — writing "sent email for run 2026-07-12" guarded by a unique idempotency key (the execution_id or (job_id, scheduled_for)), so a second run is a no-op. The lease reduces how often a job double-runs; idempotency is what makes the double-run harmless.

  worker A: pop job_42 (deleted from queue) → run → CRASH mid-run
  → job_42 is gone from the queue and never finished
  → the job is silently lost

  attempt 1: run → fail → nack → wait 1s
  attempt 2: run → fail → nack → wait 2s
  attempt 3: run → fail → nack → attempts exhausted
  → move to DEAD_LETTER; alert operators; stop retrying

3. Recurring jobs + dependencies — no drift, no overlap, run after upstreams

Recurring: schedule-driven, next run stamped at dispatch, anchored to the schedule. This is not completion-chained. When the dispatcher selects a recurring job's due tick, in the same transaction that enqueues the execution it computes and stamps the job's next next_run_at from the cron expression (and clears the current DueIndex row). That atomic advance is what stops the same tick being re-selected on the next poll — a double-dispatch — and it happens independent of when (or whether) the run completes. The critical detail is what you anchor to.

  scheduled 12:00:00, actually ran 12:00:20, finished 12:01:50
  next = finished + 1h = 13:01:50   ✗ drifted 110s
  next tick: 13:01:50 + 1h = 14:03:40   ✗ drift compounds every hour

  scheduled 12:00:00, ran 12:00:20, finished 12:01:50
  next = cron_next("0 * * * *", after=12:00:00) = 13:00:00   ✓ no drift
  even if a run is late, the next tick stays on the clock

Avoid overlapping runs. Because next-run advancement is schedule-driven, a fresh tick can come due while the previous run is still RUNNING (its runtime exceeded the interval). Choose an explicit overlap policy — skip the new tick, queue it behind the running one, or allow concurrent runs — and enforce it at dispatch with a per-job_id compare-and-set (e.g. skip enqueuing if an execution is currently RUNNING). Which policy is right depends on the job; the point is to decide, not to overlap by accident.

DAG dependencies: trigger downstream on upstream success. A dependent job has no run_at and therefore no DueIndex row — it's event-driven, not time-driven, so a null-run_at dependent never shows up in a dispatcher's range read. Store the DAG edges (depends_on[]) and a completion counter per downstream job. When an upstream execution reaches SUCCEEDED, decrement each downstream's outstanding-dependency count; only when a downstream's count hits zero is it inserted into the execution queue.

flowchart LR
    A[extract] --> C[join]
    B[load-refs] --> C
    C --> D[transform]
    C --> E[validate]
    D --> F[publish]
    E --> F
    F -->|"runs only after<br/>transform AND validate succeed"| Done[done]

join waits for both extract and load-refs; publish waits for both transform and validate. If an upstream fails after its retries and dead-letters, the downstream never becomes eligible — propagate a BLOCKED/UPSTREAM_FAILED state so it's visible, not silently stuck. The decrement must be idempotent (keyed by upstream execution_id), or an at-least-once "upstream succeeded" signal could count a completion twice and fire the downstream early.

Tradeoffs & bottlenecks

• Poll the store vs an in-memory timer wheel. Polling an indexed due-index is simple, durable, and horizontally scalable but fires within a bounded delay and costs periodic queries. A timer wheel fires near-exactly with no polling but is volatile — it must be rebuilt from the DB on restart and can't be the source of truth. Most systems poll; a timer wheel is a latency optimization layered over the durable store.
• At-least-once (idempotent jobs) vs exactly-once. At-least-once + idempotency is simple and robust and is the default. True exactly-once needs distributed transactions or a dedup ledger across the queue and the handler's side effects — much harder, rarely worth it when the handler can be made idempotent.
• Central scheduler vs sharded. A single dispatcher is simple but a SPOF and a throughput ceiling. Sharding the due-index across a dispatcher fleet scales and removes the SPOF at the cost of coordination (leases, a lease monitor, per-bucket N tuning).
• SQL table vs a queue as the store. A SQL due-index gives rich range queries (next_run_at <= now), transactions, and easy cancel/inspect, but you build the polling loop. A message queue with native delayed-delivery gives leasing and visibility timeouts for free but is awkward for "list all jobs due next week" or editing a schedule. Common pattern: SQL as the durable schedule, a queue as the execution buffer — exactly the split in the architecture above.
• Lease duration. Too long delays recovery of a genuinely-crashed worker; too short re-delivers still-running jobs as false duplicates. Tune to job runtime, and heartbeat-renew for long jobs.

Extensions if asked

• Priorities. A priority field so urgent jobs jump the queue — a priority queue or per-priority lanes, guarding against starving low-priority work.
• Per-tenant rate limiting. Cap executions/sec per tenant so one noisy tenant's million jobs don't starve others in a shared hot bucket (token buckets / weighted draining).
• Exactly-once via dedup. A dedup table keyed by execution_id that the handler consults, turning at-least-once delivery into an exactly-once effect even for non-idempotent side effects.
• Backfills. Re-running a recurring job for missed historical ticks (a schedule was paused, or a bug is fixed) — generate the missing scheduled_for executions and drain them.
• Observability / alerting. Metrics on lag (oldest un-drained bucket), failure rate, dead-letter growth, and per-job SLA breaches, with alerts on failed or overdue jobs.

What interviewers look for & common mistakes

What interviewers usually reward:

• A durable, time-indexed, shardable store — jobs as rows indexed by next_run_at, found with a range read, drained by leased dispatchers — never in-process timers.
• At-least-once execution via leasing — a visibility-timeout lease so a crashed worker's job is re-delivered, plus idempotent handlers so re-runs are harmless.
• Honest delivery semantics — naming that exactly-once dispatch is impossible and you achieve an exactly-once effect with at-least-once + idempotency.
• Recurring without drift — anchoring next_run_at to the cron schedule, not to finish time, and preventing overlapping runs.
• DAG dependencies — triggering downstream on upstream success with an idempotent completion count.

Before you finish, a quick mistake check:

• Did you index by next_run_at and range-read due jobs, instead of scanning the whole table every tick?
• Did you lease each job (visibility timeout) so a crashed worker's job is retried, instead of dropping it?
• Are handlers idempotent so at-least-once doesn't double-run harmful side effects?
• Do recurring jobs anchor the next run to the cron schedule, not now + interval (avoiding drift)?
• Do you retry with backoff and dead-letter after N attempts, instead of retrying a poison job forever?
• Did you shard the hot bucket so a same-second burst is drained by many workers, and drain oldest-first under backpressure?