System Design: Design a Distributed Task Scheduler

Every large-scale system eventually needs a scheduler. Whether it is sending a reminder email in 30 minutes, retrying a failed webhook every hour, or running a nightly data export, the underlying problem is the same: execute a task at a specified time, exactly once, even when machines fail.

A single-node cron job works until it does not. Once you need high availability, horizontal scaling, and visibility into millions of pending tasks, you need a distributed task scheduler.

Functional Requirements

• Accept task submissions with an execution time (immediate, delayed, or periodic).
• Execute each task exactly once at or near its scheduled time.
• Support cancellation and modification of pending tasks.
• Provide visibility into task status (pending, running, completed, failed).
• Support retries with configurable backoff for failed tasks.

Non-Functional Requirements

• Availability: the scheduler must survive individual node failures without losing tasks.
• Scalability: handle tens of millions of scheduled tasks.
• Latency: fire tasks within a few seconds of their scheduled time.
• Durability: once a task is accepted, it must not be lost.

High-Level Architecture

The system has four main components:

1. API layer — accepts task creation, cancellation, and status queries.
2. Task store — a durable database holding all task metadata and execution times.
3. Scheduler nodes — a pool of workers that poll for due tasks and dispatch them.
4. Execution workers — the processes that actually run the task logic.

Clients submit tasks through the API. Each task is written to the task store with a next_run_at timestamp. Scheduler nodes continuously scan for tasks whose next_run_at has passed, claim them, and hand them off to execution workers.

Task Store Design

The task store must support efficient range queries by time. A relational database like PostgreSQL works well here. The core table looks like this:

tasks
  id            UUID PRIMARY KEY
  payload       JSONB
  next_run_at   TIMESTAMP WITH TIME ZONE  (indexed)
  status        ENUM(pending, running, completed, failed)
  owner         VARCHAR  (which scheduler node claimed it)
  version       BIGINT   (optimistic locking)
  retry_count   INT
  max_retries   INT
  interval      INTERVAL (NULL for one-off tasks)
  created_at    TIMESTAMP

The critical index is on (status, next_run_at) so schedulers can efficiently query: “give me pending tasks where next_run_at <= now().”

For very high volumes, you can partition the table by time range or shard by task ID hash.

Sharding Task Ownership

Running a single scheduler node that polls the database creates a bottleneck. Instead, distribute task ownership across N scheduler nodes.

Approach: hash-based partitioning. Assign each scheduler node a range of hash slots. When a task is created, hash its ID and assign it to a slot. Only the node owning that slot will poll for and execute that task.

When a node joins or leaves, you need to rebalance slots. This is the same problem consistent hashing solves. Store the slot-to-node mapping in a coordination service like ZooKeeper or etcd. When membership changes, reassign orphaned slots to surviving nodes.

Each scheduler node runs a polling loop:

1. Query the task store for tasks in its assigned slots where next_run_at <= now() and status = pending.
2. Claim a batch of tasks using optimistic locking: UPDATE tasks SET status = 'running', owner = :me, version = version + 1 WHERE id = :id AND version = :expected_version.
3. Dispatch claimed tasks to execution workers.
4. On completion, mark status = completed. For periodic tasks, compute the next next_run_at and reset status = pending.

Time Wheels for Efficient Scheduling

Polling the database every second is wasteful when most tasks are minutes or hours away. A hierarchical time wheel reduces unnecessary polling.

A time wheel is a circular buffer of buckets, each representing a time slot (for example, one second). Tasks are placed into the bucket matching their fire time. A pointer advances once per tick, and all tasks in the current bucket are fired.

For tasks far in the future, use a multi-level wheel: a coarse wheel with one-minute buckets feeds into a fine wheel with one-second buckets. When the coarse wheel’s pointer advances, it cascades tasks from that minute into the fine wheel.

In practice, each scheduler node maintains an in-memory time wheel populated by pre-fetching tasks from the database that are due within the next few minutes. This drastically reduces database load.

Exactly-Once Execution

The hardest guarantee to provide is exactly-once execution. Consider this failure scenario: a scheduler node claims a task, dispatches it to a worker, and then crashes before recording the result. When the task is reassigned to another node, it might be executed again.

Fencing tokens solve this. When a scheduler node claims a task, it increments the task’s version number. The execution worker receives this version as a fencing token. Any side effects the worker produces (database writes, API calls) must include the fencing token. Downstream systems reject operations with stale tokens.

For idempotent tasks, the simpler approach is to design task handlers to be naturally idempotent. Sending the same email twice is annoying but survivable; debiting an account twice is not. For non-idempotent work, use an idempotency key stored alongside the task.

Failure Recovery

Three failure modes matter:

Worker failure mid-execution. The scheduler sets a timeout on each dispatched task. If the worker does not report completion within the timeout, the scheduler marks the task as failed and schedules a retry (up to max_retries).

Scheduler node failure. The coordination service detects the missing heartbeat and reassigns the dead node’s hash slots to surviving nodes. Those nodes pick up any pending or running-but-timed-out tasks in the reassigned slots.

Database failure. Use a replicated database (PostgreSQL with synchronous replication or a managed service). The task store is the single source of truth, so its durability directly determines the scheduler’s durability.

Periodic Task Handling

Periodic tasks (run every hour, every day at 3 AM) require special care. After a periodic task completes, the scheduler computes the next execution time and updates next_run_at.

If a periodic task’s execution takes longer than its interval, you have two choices: skip (drop the missed execution) or queue (run it immediately after the current execution finishes). Make this configurable per task.

For cron-like expressions, parse them at task creation time and store the next computed fire time. Libraries like croniter handle edge cases around daylight saving time and month boundaries.

Monitoring and Observability

A task scheduler is only trustworthy if you can see what it is doing. Key metrics to track:

• Task lag: the difference between next_run_at and actual execution time. This should be under a few seconds.
• Queue depth: the number of pending tasks. A growing queue signals capacity problems.
• Failure rate: percentage of tasks that exhaust retries.
• Execution duration: p50, p95, and p99 of task run times, broken down by task type.

Expose a dashboard showing pending, running, completed, and failed tasks. Allow operators to search for specific tasks by ID or type, inspect their payload, and manually retry or cancel them.

Scaling Considerations

At moderate scale (millions of tasks per day), a single PostgreSQL instance with proper indexing handles the load. Beyond that, consider:

• Sharding the task store by task ID across multiple database instances.
• Separating hot and cold storage: move completed tasks to an archive table or a cheaper store after a retention period.
• Rate limiting task dispatch: if downstream workers have limited capacity, the scheduler should throttle dispatch to avoid overwhelming them.
• Multi-region deployment: for global systems, run independent scheduler clusters per region with region-affine task assignment.

Summary

A distributed task scheduler combines a durable task store, partitioned scheduler nodes, time-wheel-based polling, and exactly-once execution guarantees. The critical design decisions are how you partition task ownership, how you handle node failures, and how you prevent duplicate execution. Start with a single-node design backed by PostgreSQL, then add sharding and time wheels as scale demands.