Design a Distributed Job Scheduler — System Design Walkthrough

"Design a distributed job scheduler" — sometimes phrased as "design cron for a fleet" or "design a task queue" — is a great interview question because almost nothing about it is about the queue. It is about time, failure, and duplication. Anyone can enqueue work; the interesting part is what happens when a worker dies holding a job, or when three scheduler replicas all decide the same cron expression just fired. Below is a walkthrough you can mirror in a real system design interview, narrating each stage as you go. Keep the system design interview cheat sheet open for the shared building blocks.

1. Clarify the requirements

Scope before you draw. The design changes a lot depending on which of these are in play.

Functional requirements

• One-off jobs — run this task once, now or at a specific future time (a delayed job).
• Recurring jobs — run this task on a cron schedule, indefinitely.
• Retries — a failed run should be attempted again, up to a bounded budget.
• Priorities — urgent work should not sit behind a bulk backfill.
• Cancellation and inspection — users can cancel a job and see the history of its runs.

Non-functional requirements

• Durability: an accepted job must survive a scheduler restart. This rules out an in-memory timer wheel as the only store.
• At-least-once execution: we would rather run a job twice than never run it.
• Bounded scheduling delay: a job due at T should start within a few seconds of T, not minutes.
• Horizontal scalability: more workers means more throughput, with no single dispatcher bottleneck.

State the at-least-once choice explicitly and early — it drives half the rest of the answer.

2. The data model: jobs and runs

The single most common mistake is modelling this as one table. Separate the definition from the execution.

jobs                          runs (executions)
----                          ----
job_id        (pk)            run_id          (pk)
owner                         job_id          (fk)
type / payload                scheduled_for   (timestamp)
schedule      (cron | once)   state           (ready|leased|done|failed|dead)
next_run_at   (indexed)       attempt         (int)
priority                      lease_owner     (worker id)
max_attempts                  lease_expires_at
enabled       (bool)          idempotency_key (unique)

A job is the durable definition a user created. A run is one attempt to execute it at one scheduled instant. Keeping runs as their own rows gives you retry history, per-attempt state, and an audit trail for free — and it is what makes the deduplication trick in section 6 possible.

3. Finding the jobs that are due now

This is the heart of the problem. The naive dispatcher loop runs SELECT * FROM jobs WHERE next_run_at <= now() every second. It works at small scale and fails at large scale for a specific reason: without an index it is a full table scan of mostly-not-due rows repeated every tick, and the scan cost grows with total jobs rather than with due jobs.

Three fixes, in escalating order:

• Index next_run_at. Now the query is a bounded range scan over exactly the due prefix. This alone carries you a long way.
• Time bucketing. Partition the schedule into fixed windows — say one bucket per minute — and write each job into the bucket for its next run. The dispatcher reads one small bucket per tick instead of querying a giant shared index.
• Shard the buckets. Assign bucket shards to dispatcher replicas (by hash of job id, or by consistent hashing) so each replica owns a disjoint slice of the timeline. Now due-job lookup scales horizontally and no two dispatchers contend on the same rows.

A useful refinement: keep a short in-memory timer for the next few seconds of work, refilled from the store. The database gives durability; the in-memory layer gives precision without polling every 100 ms.

4. High-level architecture

  API / clients
      |  create, cancel, inspect jobs
      v
 +----------------+        +--------------------------+
 |  Job store     |<-------|  Dispatchers (sharded)   |
 |  jobs + runs   |        |  scan due time-buckets   |
 |  idx next_run  |------->|  create run rows         |
 +----------------+        +------------+-------------+
        ^                               | enqueue
        | complete / retry / heartbeat  v
        |                    +---------------------+
        |                    |  Priority queues    |
        |                    |  high | default |   |
        |                    |  bulk              |
        |                    +----------+----------+
        |                               | lease
        |                    +----------v----------+
        +--------------------|   Worker pool       |
                             |  heartbeat + ack    |
                             +----------+----------+
                                        | exhausted retries
                                        v
                               [ Dead-letter queue ]

  Reaper: lease_expires_at < now  ->  run back to READY

5. Workers, leases, and heartbeats

A worker never "takes" a job outright — it takes a lease. Claiming a run is an atomic conditional update: set state = leased, lease_owner = me, and lease_expires_at = now + 30s, but only if the run is still ready. Only one worker can win that update, which is what prevents two workers grabbing the same run in the same instant.

While executing, the worker heartbeats — periodically pushing lease_expires_at forward to prove it is alive. On success it acks, marking the run done.

Now the failure case the interviewer is actually asking about: the worker is killed mid-job. It stops heartbeating, the lease expires, and a background reaper sweeps expired leases back to ready so another worker picks the run up. Nothing is lost.

The tuning trade-off is worth saying out loud. A short lease recovers from crashes quickly but risks stealing a job from a healthy worker that is merely slow, producing a genuine double execution. A long lease is safe against false steals but leaves work stalled after a real crash. Heartbeating lets you keep the lease short while still supporting long-running jobs.

6. Idempotency and the exactly-once question

Sooner or later the interviewer asks whether you can guarantee exactly-once. The honest, senior answer is no — and then you explain why.

A worker can finish the work and crash before recording completion. From the outside, "finished but unacknowledged" and "never finished" look identical, so the system must choose: retry (risking duplicates) or not (risking lost work). Choosing at-least-once and then making duplicates harmless is the standard resolution. Exactly-once is at-least-once delivery plus idempotent handlers.

Concretely: give each run a stable idempotency_key — deterministic, derived from job id plus the scheduled instant, not randomly generated per attempt. The handler records that key transactionally alongside its side effect, and a repeated delivery with the same key becomes a no-op. This is the same discipline that makes retries safe in payment flows and in the delivery pipeline of a notification system.

7. Retries, backoff, and dead-letter queues

When a run fails, reschedule it rather than dropping it — but not immediately, and not forever.

• Exponential backoff. Delay attempt n by roughly base * 2^n, capped at a ceiling. Immediate retries just re-hit a downstream that is already unhealthy.
• Jitter. Add randomness to the delay so a batch of runs that failed together does not retry in perfect lockstep and re-create the same thundering herd. Pair this with a rate limiter in front of fragile downstreams.
• Bounded attempts. After max_attempts, move the run to a dead-letter queue: state dead, last error recorded, alert raised. A poison-pill job that can never succeed must not consume worker capacity indefinitely. Engineers triage the DLQ, fix the cause, and replay.

8. Preventing duplicate cron ticks

Run three scheduler replicas for availability and they all observe 0 * * * * firing at the same second. Without coordination the job runs three times. Two answers:

• Leader election. Replicas elect a leader through a coordination service; only the leader enqueues runs. Simple, but there is a window during failover where the old leader may still believe it holds the lock.
• Deterministic uniqueness. Let every replica try, but make the run row's key (job_id, scheduled_for) unique. The first insert wins; the others get a constraint violation and quietly drop it. This is usually the better answer because correctness comes from the storage layer rather than from clock agreement.

Mention clock skew while you are here: schedulers should compute ticks against a synchronized time source, and the uniqueness key should use the scheduled instant, not each replica's local now().

9. Priorities, fairness, and observability

Priorities. The simplest implementation is separate queues per priority class with workers preferring higher classes. Pure strict priority starves the bottom class, so weight the polling — workers pull from bulk some fraction of the time regardless of backlog.

Fairness across tenants. One customer submitting a million jobs should not freeze everyone else. Partition per tenant, round-robin across partitions, and cap concurrent runs per tenant so a noisy neighbour cannot monopolise the pool.

Observability. Track scheduling delay (actual start minus scheduled_for), queue depth per priority, run duration percentiles, attempt distribution, and DLQ growth rate. Scheduling delay tells you whether the scheduler is healthy; DLQ growth tells you something is broken.

FAQ

How does a job scheduler find the jobs that are due right now?

The standard approach is to store a next_run_at timestamp on every job and put a database index on it, so the dispatcher queries for rows where next_run_at is less than or equal to now, ordered by that column. Scanning the whole jobs table on every tick does not scale, because most rows are not due. At larger scale the schedule is partitioned into time buckets, such as one bucket per minute, and buckets are sharded across dispatchers so each one only reads the small slice of the timeline it owns.

Can a job scheduler guarantee exactly-once execution?

Not on its own. In a distributed system a worker can execute a job and then crash before it records completion, so the system cannot tell the difference between work that finished and work that did not. Practical schedulers therefore deliver at-least-once and push the final guarantee into the handler: give every run a stable idempotency key, have the handler check whether that key was already processed, and make the side effect safe to repeat. Exactly-once in practice means at-least-once delivery plus idempotent handlers.

What happens when a worker crashes mid-job?

A worker does not own a job outright; it takes a lease with an expiry and renews that lease with periodic heartbeats while it works. If the worker dies, it stops heartbeating, the lease expires, and a reaper process returns the run to the ready state so another worker can claim it. The trade-off is lease duration: too short and healthy long-running jobs get taken away and duplicated, too long and recovery from a real crash is slow.

How do you stop two schedulers from firing the same cron job twice?

Every scheduler replica sees the same cron expression fire at the same instant, so you need a single writer per tick. Two common answers are leader election, where one elected node is the only one allowed to enqueue runs, and a uniqueness constraint, where the run row carries a deterministic key such as job id plus the scheduled tick timestamp and the database rejects the duplicate insert. The uniqueness constraint is usually the more robust answer because it stays correct even during a leadership handover.

What is a dead-letter queue in a job scheduler?

A dead-letter queue holds runs that have exhausted their retry budget. Instead of retrying a permanently broken job forever and burning worker capacity, the scheduler moves it aside after a configured number of attempts, records the last error, and raises an alert. Engineers can then inspect the payload, fix the underlying cause, and replay the run. It keeps a poison-pill job from starving healthy traffic.