Distributed Task Scheduler System Design: Jobs, Retries, Leases, and Failures

Distributed Task Scheduler System Design: What Happens When a Job Is Due?

A user schedules a payment for 9:00 AM. At 9:00, the scheduler finds the job and hands it to a worker. The worker calls the payment provider, the charge succeeds, and then the worker crashes before recording success.

What should happen next?

The scheduler cannot simply forget the job: it has no durable confirmation that execution finished. But blindly running it again might charge the customer twice.

That tension is central to distributed task scheduler system design. Finding work at the right time is only the beginning. A production scheduler must preserve jobs across failures, coordinate concurrent schedulers, handle retries without inventing exactly-once guarantees, and make recovery safe even when the outcome of an earlier attempt is unknown.

This article designs a distributed job scheduler for one-time and recurring tasks, with the focus on the correctness boundaries that matter in production.

First, define what the scheduler promises

A task scheduler answers when work becomes eligible to run. It does not inherently guarantee that a worker starts at an exact wall-clock instant, that a remote API succeeds, or that an external side effect happens exactly once.

A useful contract separates four timestamps:

• due_at: the earliest instant a job is eligible to run.
• dispatched_at: when the system hands an execution request to its delivery mechanism.
• started_at: when a worker begins the attempt.
• completed_at: when the system durably records a terminal outcome.

A 9:00 AM job may begin after 9:00 because of polling, queueing, worker capacity, or an outage. The product should define an acceptable scheduling lag and whether a late job should still execute. For workloads with hard deadlines, expiry is a separate policy: running a stale trade or promotion after its validity window may be worse than skipping it.

We'll assume jobs can be scheduled once or on a recurrence, cancelled or rescheduled before execution, retried for eligible failures, and queried for status. We will not assume every job is safe to repeat.

The basic architecture

Client / API
     |
     v
Durable Job Database  <----- Recurrence Generator
     |                       (creates occurrences)
     v
Due-Job Discovery / Claimers
     |
     | atomic DB transaction:
     | claim + dispatch-outbox record
     v
Transactional Outbox
     |
     v
Outbox Relay -----> Durable Queue -----> Workers
                                           |
                                           v
                                    Business Side Effect
                                           |
                                           v
                                  Status / Attempt Store

Lease Reaper ------> expired attempts / safe retry decisions

The database owns the authoritative job state. The queue transports work to workers; it does not replace the scheduler's lifecycle record in this design. The outbox bridges the database-to-queue failure gap. A lease reaper finds attempts that stopped making progress.

This is one reasonable architecture, not a mandatory stack. A smaller scheduler can begin with indexed database polling and workers claiming rows directly. Some workloads use broker-native delayed delivery; others add Redis sorted sets or timing wheels for due-time discovery. Each alternative has different limits and failure semantics.

1. Store jobs durably before promising acceptance

A minimal model might look like this:

jobs
  job_id
  tenant_id
  payload_ref
  due_at
  status
  version
  creation_idempotency_key
  deadline_at

attempts
  attempt_id
  job_id
  generation
  status
  lease_expires_at
  started_at
  completed_at
  error_category

outbox
  event_id
  attempt_id
  payload
  published_at

For recurring work, add a schedule definition containing the recurrence rule, IANA timezone, misfire policy, overlap policy, and the next occurrence to generate. Each generated occurrence gets its own job identity.

The creation API should make a durable write before returning an unqualified success response. If a client times out after the commit, a stable creation idempotency key and a uniqueness constraint let it retry without creating a second logical job.

Job status is not the same as an attempt's status. A job may have multiple attempts; one attempt can fail transiently while the logical job remains eligible for retry. Keep enough attempt history to explain what happened without treating an old attempt's completion as permission to overwrite newer state.

2. Discover due jobs without scanning everything

The simplest viable due-work detector is a database index supporting a query shaped like:

SELECT job_id
FROM jobs
WHERE status = 'SCHEDULED'
  AND due_at <= CURRENT_TIMESTAMP
ORDER BY due_at, job_id
LIMIT 500;

The relevant index, bounded batch size, and query plan matter more than the particular batch size shown here. In a multi-scheduler design, merely selecting rows is not sufficient: two instances could read the same jobs. A claim must be atomic and conditional on current state, commonly using row locks such as FOR UPDATE SKIP LOCKED inside a transaction or an equivalent compare-and-swap transition.

SKIP LOCKED is a useful mechanism, not a universal requirement. Another design gives one elected leader ownership of due-time discovery. At higher scale, ownership can be sharded so independent schedulers process different partitions. Leader-based systems need fencing: a leader whose lease expired may resume after a pause and must not be allowed to make stale authoritative writes.

A Redis sorted set can speed up discovery when database due-time queries become a measured bottleneck. But if Redis is only an index, its loss must not erase jobs: rebuild it from the durable store, validate candidate jobs against authoritative state, and reconcile missing entries. A timing wheel similarly needs a durable backstop if its in-memory state can disappear.

3. The database-to-queue dual-write trap

Consider this dispatch sequence:

1. Update a job to QUEUED in the database.
2. Publish an execution message to Kafka, SQS, or another broker.

If the process crashes between steps, the database says the job was dispatched, but the broker never received it. Reversing the order creates the mirror failure: the broker receives a message, but the database update fails, so a retry may publish it again.

A transactional outbox handles the first problem without pretending the database and broker share one atomic transaction. In one database transaction, the scheduler records the job/attempt transition and inserts an outbox event. A relay later publishes that event to the broker and records publication progress.

The relay itself can crash after publishing but before marking the event published. It may then publish the same event again. Thus the outbox supports eventual, at-least-once publication, assuming the relay and broker recover and retry successfully; it does not make downstream execution exactly once.

Messages need stable identities. Repeated delivery of the same dispatch event should not create an unrelated business operation. The worker checks authoritative job and attempt state before claiming execution, and downstream effects still require their own idempotency protections.

4. Worker leases handle crashes, not exactly-once effects

A worker claims an attempt with a lease. While running, it renews the lease if the design supports long-running work. If the worker dies, a separate reaper can detect the expired lease and make the job eligible for another attempt.

But lease expiry is not proof that the old worker stopped. A long garbage-collection pause, lost heartbeat, or network partition can cause a live worker to lose its lease while it continues processing. Another worker may start at the same time.

To protect scheduler state, attach an increasing attempt generation or fencing token to conditional writes. A stale worker must not be able to mark a superseded attempt successful or overwrite the current state. Fencing protects only resources that actually validate it; it cannot retroactively undo a payment sent to an external provider.

The lease duration and heartbeat cadence must be chosen against real pause times, execution durations, and acceptable recovery latency. There is no universally correct TTL or heartbeat ratio.

5. Retry correctness depends on where the side effect happens

Return to the payment example. Worker A successfully charges the customer but crashes before saving the result. Worker B eventually receives a retry. From the scheduler's local records, the outcome is ambiguous.

A database flag saying started is not enough. If a worker writes that flag and crashes before the charge, treating the flag as proof of completion silently loses the payment. A completion marker written before an external effect has the same flaw.

There are three importantly different cases:

Local database mutation. If the business change and completion record live in the same database, commit them in one transaction, with appropriate uniqueness or conditional constraints. Either both commit or neither does.

External API supporting idempotency. Send a stable business-operation idempotency key that survives retries and worker replacement. The provider's documented deduplication semantics and retention window determine what guarantee this actually gives. An internal attempt ID is usually the wrong key because it changes across attempts.

External API without reliable idempotency. A timeout cannot reveal whether the operation happened. Durable pending state, provider-side lookup where available, and reconciliation may resolve uncertainty. If the provider offers neither deduplication nor reliable outcome lookup, the scheduler cannot promise exactly-once external effects. The product must explicitly choose how to handle that residual risk.

This is why at-least-once execution attempts and exactly-once business effects are not interchangeable claims.

6. Retry policy is more than exponential backoff

Retries begin with failure classification:

• Transient failures, such as some timeouts or temporary service unavailability, may be retried if the operation is safe to retry.
• Rate-limit responses require respecting the provider's applicable retry guidance and quotas; an HTTP 429 is not permission to retry immediately.
• Permanent validation or business-rule failures generally should not be retried unchanged.
• Ambiguous outcomes require idempotency or reconciliation, not optimistic assumptions.

Use bounded attempts, capped exponential backoff with jitter, execution deadlines, and a dead-letter or terminal-failure path. Backoff spreads attempts over time, but does not by itself cap aggregate load on a struggling dependency. A dependency-scoped rate limit or retry budget, and circuit breaking when appropriate, prevent thousands of independently reasonable retries from combining into a retry storm.

A dead-letter queue is not a garbage bin. Preserve job identity, failure reason, and attempt history. Replays should be authorized, observable, rate-limited, and idempotent. A replay may create a new attempt, but it must not invent a new business operation identity.

7. Recurring schedules need separate occurrence identities

“Every day at 9:00 AM” is a schedule definition, not one job repeatedly moved back to SCHEDULED.

Generate individual occurrences, each with a deterministic identity based on the schedule and nominal occurrence. A unique constraint ensures two generators recovering from a failover do not create duplicate logical occurrences.

For a recurring schedule, store the recurrence rule and an IANA timezone, such as Asia/Kolkata or America/New_York. A fixed UTC offset is not sufficient for local-time recurrences across daylight-saving changes. Every occurrence must be resolved using the timezone rules applicable to that date.

Two edge cases need explicit product decisions: during spring-forward, a configured local time might not exist; during fall-back, it might occur twice. Decide whether to skip, shift, or select a particular occurrence rather than relying silently on a date library's default.

After downtime, decide whether to skip missed runs, catch up all valid runs, or coalesce missed runs. For billing, every period might matter; for a transient reminder, replaying all missed notifications could be actively harmful. Also specify whether successive occurrences may overlap, should queue behind one another, or should skip while an earlier occurrence is still running.

8. Cancellation is a race, not just a status update

Cancelling a scheduled job before it is claimed is relatively straightforward. Cancelling a queued job is harder because its message may already be in transit. A worker should check authoritative state and the dispatched version before beginning work; a stale message must not bypass a recorded cancellation.

That check still does not make cancellation of running external work instantaneous or reversible. Cancellation may be cooperative, and there can be a race after the final pre-execution check. A precise API distinguishes cancellation requested, cancelled before execution, and already running or completed. Never promise that a successfully returned cancellation can undo an email already sent or a charge already made.

Rescheduling also changes job version and due time; old queued messages must not cause execution against an obsolete schedule.

9. What happens at the 9:00 AM burst?

Imagine millions of jobs become due at the same moment. It is tempting to prescribe Redis or a bigger queue immediately. Neither is a universal answer.

The first bottleneck might be the due-time index, claim contention, outbox relay, broker ingress, worker concurrency, network egress, or a third-party API's quota. Measure due-to-dispatch lag, queue waiting time, worker start lag, oldest overdue job age, retry rate, and downstream throttling to identify where capacity is actually exhausted.

Bound due-job scans, partition hot scheduling ranges when needed, enforce per-tenant quotas and fairness, and pace dispatch to sustainable downstream throughput. Predictable bursts may justify pre-scaling workers.

Pre-staging work before its due time can help only if execution is still gated by eligible_at. Starting a 9:00 AM payment at 8:59 merely to flatten the graph is a correctness regression unless early execution is explicitly allowed.

A backlog is not necessarily data loss. But a scheduler that keeps accepting jobs faster than they can execute needs an explicit lateness and admission-control policy; a queue cannot manufacture downstream capacity.

10. Recovery paths worth designing before production

Scheduler crashes. Durable due jobs remain discoverable. Another claimer or a fenced new leader takes over, then performs a bounded catch-up scan rather than dispatching every overdue job at once.

Database primary fails. Job creation and authoritative transitions may become unavailable. Reject uncommitted new requests explicitly instead of pretending an in-memory buffer is durable. Replica promotion's data-loss exposure depends on replication acknowledgments and actual lag, not a universal recovery number.

Broker is unavailable. Outbox events remain durable and publication lag rises. Once the broker returns, drain the outbox at a controlled rate.

Worker crashes or an ACK is lost. A lease expiry or broker redelivery may cause another attempt. That is expected at-least-once behavior; side-effect idempotency or reconciliation is the safety boundary.

A leader resumes after losing ownership. Conditional state transitions and fencing reject stale authoritative writes. Merely holding a time-limited lock is insufficient.

A region fails. A standby region can take over only under a defined ownership and fencing protocol, using whatever state was durably replicated. Recovery time and potential data loss are properties of the chosen replication and failover design, not free guarantees of “multi-region.”

11. The trade-offs that change the design

Decision	Simpler starting point	When a different approach earns its cost
Due-time discovery	Indexed database polling	Redis index, timing wheel, or sharding when measured due-discovery limits justify them
Scheduler coordination	Atomic competing DB claimers	Leader election or shard ownership for particular contention and operational requirements
Dispatch	Direct database-backed worker claims for a small design	Queue + transactional outbox for decoupled, durable, high-throughput handoff
Worker recovery	Fixed leases for bounded short jobs	Renewable leases and checkpoints for long or variable-duration jobs
Missed recurrences	Explicit per-schedule misfire policy	Different catch-up behavior by workload, not a universal replay-all rule
Regional topology	One authoritative region with standby	More complex cross-region ownership only when availability needs justify it

The goal is not to collect the most distributed components. It is to add mechanisms that solve a demonstrated bottleneck or close a specific correctness gap.

A practical way to reason through the interview

Start by asking what “run at 9:00” means, how late jobs may be, whether retries and overlap are acceptable, and which external side effects cannot safely repeat. Establish peak due-job rate and burstiness as assumptions, not universal scale thresholds.

Then evolve the design in order: durable jobs; indexed due discovery and atomic claiming; a dispatch boundary; worker leases; retry classification; idempotency at the business-effect boundary; and failure recovery. Add an outbox when dispatch crosses a database/broker boundary. Add a fast due-time index or sharded ownership only when its benefits outweigh the consistency and operational costs.

A strong system design explanation follows one job through an actual failure. The most revealing question is often not “how do you schedule a million jobs?” but “what do you do when the external effect succeeded and your worker cannot prove it?”

The essential takeaway

A distributed task scheduler is a durable coordination system under uncertain execution outcomes. Its clock determines eligibility, its store preserves intent, its dispatcher delivers work, and its workers perform effects. Those boundaries can fail independently.

Reliable scheduling therefore comes from a combination of atomic claims, durable dispatch, leases and fencing, bounded retries, explicit recurrence semantics, and idempotency or reconciliation at the point where the business effect actually occurs. None of these alone provides a universal exactly-once guarantee.

For the full visual and production-oriented treatment, explore Distributed Task Scheduler — Complete Design, Architecture Deep Dive, Trade-offs & Decisions, and Failure & Scale Scenarios on SeeItFlow. The Visual Design Journey walks through the design's evolution interactively.