Q67 — Design a job scheduler that runs millions of tasks reliably

What the system must do

Users define jobs — units of work to execute at a specific time or on a recurring schedule (cron). The scheduler ensures jobs execute at (approximately) the right time, exactly once (or at-least-once), even if workers crash mid-execution.

Examples: send a weekly digest email at 9 AM every Monday, process a batch report at midnight, retry a failed payment after 24 hours, expire a session token after 30 minutes.

Requirements:

Schedule one-time tasks (fire at timestamp T)
Schedule recurring tasks (cron expressions: "every day at 9 AM")
At-least-once execution (no missed jobs)
Idempotent execution (safe to run twice if needed)
Horizontal scaling of workers
Failure recovery (worker crashes mid-job → job retried)
Scale: millions of scheduled jobs, thousands of executions per second

The core problem: selecting jobs due for execution

Every second, the scheduler must find all jobs whose next_run_at <= now and dispatch them to workers. Naive approach: SELECT * FROM jobs WHERE next_run_at <= NOW() AND status = 'pending'. At millions of jobs, this is a full table scan every second — unusable.

You need an efficient way to retrieve the "what's due right now?" set. Three approaches:

Database index on next_run_at: a B-tree index on next_run_at makes the query SELECT ... WHERE next_run_at <= NOW() LIMIT 100 efficient — it walks the index from the smallest values up to NOW(). With proper indexing and pagination (claim batches of 100 at a time), this works up to millions of jobs.

Redis sorted set: store job IDs in a sorted set where the score is the scheduled Unix timestamp. ZRANGEBYSCORE jobs 0 <now> LIMIT 100 atomically retrieves 100 due jobs. ZREM removes them from the queue after claiming. Extremely fast, but Redis as a primary scheduler store requires persistence (AOF/RDB) and adds operational complexity.

Hierarchical timing wheel: an in-memory data structure used in high-performance timer systems (Kafka, OS kernels). Time is divided into slots (1-second granularity), organized in multiple wheels (seconds, minutes, hours). Jobs are placed in the slot corresponding to their next execution time. Each tick (1 second), the current slot is drained and jobs dispatched. O(1) per job insertion and retrieval.

For most production systems, a database with an index on next_run_at is the practical choice: it's durable, supports complex job metadata, and handles millions of jobs efficiently with proper indexing and partitioning.

Data model

sql

CREATE TABLE jobs (
  id             BIGINT PRIMARY KEY,
  name           TEXT NOT NULL,
  cron_expression TEXT,          -- NULL for one-time jobs
  next_run_at    TIMESTAMPTZ NOT NULL,
  last_run_at    TIMESTAMPTZ,
  status         TEXT NOT NULL,  -- 'pending', 'running', 'completed', 'failed'
  handler        TEXT NOT NULL,  -- which worker type executes this
  payload        JSONB,          -- job parameters
  max_retries    INT DEFAULT 3,
  retry_count    INT DEFAULT 0,
  timeout_secs   INT DEFAULT 300,
  locked_by      TEXT,           -- worker ID that claimed it
  locked_at      TIMESTAMPTZ,    -- when it was claimed
  created_at     TIMESTAMPTZ NOT NULL
);

CREATE INDEX idx_jobs_due ON jobs(next_run_at) WHERE status = 'pending';

The partial index (WHERE status = 'pending') is key — it only indexes rows that need to be polled, keeping the index small and fast.

Claiming jobs — the race condition

Multiple scheduler workers poll for due jobs simultaneously. If two workers both SELECT the same due job and both dispatch it, the job runs twice. This must be prevented.

Optimistic locking with FOR UPDATE SKIP LOCKED:

sql

BEGIN;
SELECT id FROM jobs
WHERE next_run_at <= NOW()
  AND status = 'pending'
ORDER BY next_run_at
LIMIT 10
FOR UPDATE SKIP LOCKED;

UPDATE jobs SET status = 'running', locked_by = 'worker-7', locked_at = NOW()
WHERE id IN (...);
COMMIT;

FOR UPDATE locks the selected rows. SKIP LOCKED skips rows already locked by other transactions — so two concurrent workers never claim the same job. This is the correct, deadlock-free approach to distributed job claiming.

Handling worker failures — the heartbeat and timeout

A worker claims a job (status = 'running'), starts executing, then crashes. The job is forever stuck in 'running' state — never completed, never retried. The locked_at timestamp solves this.

A separate "reaper" process (or the scheduler itself) periodically runs:

sql

UPDATE jobs SET status = 'pending', locked_by = NULL, locked_at = NULL, retry_count = retry_count + 1
WHERE status = 'running'
  AND locked_at < NOW() - INTERVAL '5 minutes'
  AND retry_count < max_retries;

-- Permanently fail jobs that exceeded max_retries
UPDATE jobs SET status = 'failed'
WHERE status = 'running'
  AND locked_at < NOW() - INTERVAL '5 minutes'
  AND retry_count >= max_retries;

If a job takes more than 5 minutes (the timeout), it's assumed the worker died and the job is reset to pending for retry. Workers that are still alive should send heartbeats (update locked_at every 30 seconds) to avoid being reaped.

This is equivalent to the lease renewal pattern from distributed systems (Q48).

Recurring jobs

When a recurring job completes, schedule the next occurrence. At the end of job execution:

sql

UPDATE jobs SET
  status = 'pending',
  last_run_at = NOW(),
  next_run_at = compute_next_run(cron_expression, NOW()),
  locked_by = NULL,
  locked_at = NULL,
  retry_count = 0
WHERE id = ?;

compute_next_run evaluates the cron expression to find the next scheduled time. Libraries like croniter (Python) or cron-parser (JS) handle this.

Worker architecture

Workers are stateless — they poll for jobs, execute, and update status. The same worker code can run on any machine, enabling horizontal scaling. Adding more workers increases throughput linearly (more parallel job executions) without any coordination beyond the database locking mechanism.

Workers should be typed: a report_generation worker handles report jobs, an email_send worker handles email jobs. Routing is done via the handler field — workers only poll for jobs matching their handler type. This prevents a slow report job from blocking email sends.

For high-throughput systems, replace the polling model with a hybrid: the scheduler publishes due jobs to Kafka topics (one topic per handler type), and workers consume from Kafka. This eliminates polling overhead and provides natural buffering.

The mental model

code

Core problem: "which jobs are due right now?" efficiently at scale
  Solution: DB index on next_run_at (partial: WHERE status = 'pending')
  Poll: SELECT ... WHERE next_run_at <= NOW() LIMIT N FOR UPDATE SKIP LOCKED

Data model: jobs table with {next_run_at, status, locked_by, locked_at, retry_count}

Claiming jobs (preventing duplicates):
  FOR UPDATE SKIP LOCKED → only one worker claims each job
  status = 'running' + locked_by + locked_at → claimed

Failure recovery (worker crashes):
  locked_at > timeout threshold → reaper resets to pending
  Workers heartbeat (update locked_at) while running long jobs
  max_retries cap + status = 'failed' for exhausted jobs

Recurring jobs:
  On completion: compute next_run_at from cron_expression → reset to pending

Workers: stateless, typed by handler, horizontally scalable
  Polling model: simple, works to thousands of executions/sec
  Kafka model: high-throughput, eliminates polling overhead

Execution guarantees:
  At-least-once: reaper retries stuck jobs → possible duplicate if worker completes + crashes before ACK
  Idempotency required in job handlers (same job_id = skip if already done)

Scale:
  Millions of jobs: indexed DB query is fast
  Thousands of executions/sec: many workers + partitioned polling
  Very high scale: Kafka dispatch eliminates DB polling bottleneck

A job scheduler is a reliable execution guarantee wrapped around deferred work. The interesting engineering is in the claiming mechanism (FOR UPDATE SKIP LOCKED), the failure recovery (heartbeats + reaper), and the scale-up path (from DB polling to Kafka dispatch). Everything else follows from those three decisions.