Distributed Job Scheduler (Cron at Scale)

0) Problem Restatement

Design a service that runs jobs at the right time. A job can run once ("send this payment at 3 PM tomorrow") or on a schedule ("run this report every day at 9 AM", written as a cron expression like 0 9 * * *). Teams across the company submit jobs through an API. The system must start each job close to its scheduled time, retry failures, let users cancel jobs, and show the status of every run.

The hard part is reliability. Machines crash all the time, but a job must not be lost, and some jobs (like payments) must never run twice.

1) Requirements

1.1 Functional

• Create, update, pause and cancel jobs (one-time or recurring).
• Run each job close to its scheduled time (within a few seconds).
• Retry failed runs with backoff (wait longer after each failure).
• Support dependencies: job B runs only after job A succeeds (a DAG, or directed acyclic graph, which is a chain of steps with no loops).
• Show run history and status (scheduled, running, succeeded, failed).

1.2 Non-Functional

• No lost jobs: once the API says "created", the job will run.
• No double runs for jobs marked as critical (at-least-once plus idempotency, explained below).
• Scale: millions of jobs per day, with spikes at popular times such as midnight.
• High availability: no single machine should be able to stop all scheduling.

1.3 Scale Estimates

• 10 million job runs per day ≈ 115 runs/second on average.
• Spikes: many cron jobs use 0 0 * * * (midnight), so we may see 50,000 jobs due in the same second.
• Job metadata ≈ 1 KB, so 50M jobs is about 50 GB. Run history grows faster, so we keep 30 days hot and archive the rest.

1.4 API Design

• POST /v1/jobs with { name, schedule: "0 9 * * *" | run_at, payload, target: "http://svc/endpoint" | queue, retries: 3, timeout_sec, idempotency_key } → { job_id }
• PATCH /v1/jobs/{id} to pause, resume or change the schedule.
• DELETE /v1/jobs/{id} to cancel.
• GET /v1/jobs/{id}/runs?limit=20 to see run history.

2) High-Level Architecture

2.1 Overview

• Job API: validates and stores jobs.
• Jobs DB: stores job definitions and the next time each job should run.
• Scheduler: finds jobs that are due and puts a "run" message on a queue. We run many scheduler instances, each owning some partitions of jobs.
• Queue (e.g., Kafka or SQS): holds runs that are ready to execute.
• Workers: take runs from the queue, execute them (call an HTTP endpoint or run a container), and report the result.
• Run History DB: stores every attempt for the status UI.

2.2 Architecture Diagram

flowchart LR
    U["Teams / Services"] --> API["Job API"]
    API --> DB[("Jobs DB - next_run_at index")]
    SCH["Scheduler instances - one per partition"] -->|"poll due jobs"| DB
    SCH -->|"enqueue run"| Q[("Run Queue")]
    Q --> W["Worker Pool"]
    W -->|"execute"| T["Target service or container"]
    W -->|"heartbeat, result"| RH[("Run History DB")]
    W -->|"update next_run_at"| DB
    UI["Status UI"] --> RH

3) Data Model

CREATE TABLE jobs (
  job_id        UUID PRIMARY KEY,
  partition_id  INT,            -- hash(job_id) % 1024
  schedule      TEXT,           -- cron expression, or NULL for one-time
  next_run_at   TIMESTAMP,      -- when the job should run next
  status        TEXT,           -- active, paused, cancelled
  payload       JSONB,
  max_retries   INT,
  version       INT             -- for safe concurrent updates
);
CREATE INDEX ON jobs (partition_id, next_run_at) WHERE status = 'active';

CREATE TABLE job_runs (
  run_id        UUID PRIMARY KEY,
  job_id        UUID,
  scheduled_for TIMESTAMP,
  attempt       INT,
  state         TEXT,           -- queued, running, succeeded, failed
  lease_until   TIMESTAMP,      -- worker must heartbeat before this
  worker_id     TEXT,
  UNIQUE (job_id, scheduled_for, attempt)
);

The UNIQUE (job_id, scheduled_for, attempt) rule is important: even if two schedulers try to create the same run, the database only accepts one.

4) Key Flows

4.1 Finding due jobs

1. Each scheduler instance owns a set of partitions (e.g., instance 3 owns partitions 300–399). Ownership is managed by a coordinator such as ZooKeeper or etcd, or by leases in the DB.
2. Every second, it runs: SELECT ... WHERE partition_id IN (...) AND next_run_at <= now() + 5s.
3. For each due job, it inserts a job_runs row (the unique key blocks duplicates) and pushes the run to the queue.
4. It moves next_run_at forward to the next cron time in the same transaction.

4.2 Running a job

1. A worker pulls a run and sets state = running, lease_until = now + 30s.
2. While working, it sends a heartbeat every 10 seconds to extend the lease.
3. When done, it marks the run succeeded or failed. On failure, it schedules a retry with backoff (e.g., 1 min, 5 min, 25 min).

4.3 When a worker dies

A reaper process looks for runs where state = running and lease_until < now. It means the worker stopped heartbeating, so the run is put back on the queue as a new attempt.

5) Deep Dive A — "Exactly once" in practice

True exactly-once execution across machines is not possible. Picture this: a worker charges a card, then crashes before recording "done". We cannot know whether the charge happened. So we do this instead:

• At-least-once delivery: we would rather run twice than never.
• Idempotency: every run carries an idempotency_key = job_id + scheduled_for. The target service stores keys it has already processed and ignores repeats. A payment service, for example, will not charge the same key twice.
• Fencing tokens: when a run is re-assigned after a lease expires, it gets a higher attempt number. The target rejects writes from older attempts, so a "zombie" worker that wakes up late cannot do damage.

6) Deep Dive B — Handling the midnight spike

50,000 jobs due at 00:00:00 would hammer the DB and the targets.

• Pre-fetch: schedulers look 5–10 seconds ahead and load due jobs into an in-memory timing wheel (a circular array of time buckets). This spreads DB reads out before the spike.
• Queue as a buffer: the queue absorbs the burst, and workers drain it at a safe speed.
• Jitter: for jobs that allow it (allow_jitter: 60s), spread start times randomly across the minute.
• Per-team concurrency limits: stop one team's 40,000 jobs from blocking everyone else.

7) Trade-offs & Alternatives

8) Common Follow-up Questions

• "How do you cancel a job that is already running?" Mark it cancelled. Workers check this flag on each heartbeat and stop. The target should also accept a cancel call.
• "How do you support dependencies (DAGs)?" Store edges between jobs. When a run succeeds, look up its children and enqueue those whose parents have all succeeded.
• "Priorities?" Use separate queues per priority, and let workers pull from high priority first while reserving some capacity for low priority so it never starves.
• "How do you show a job is late?" Track the lag between scheduled_for and the actual start time, and alert when it grows.

9) Wrap-Up

Store jobs with an indexed next_run_at. Let partitioned schedulers find due jobs and push them to a queue, and let workers run them with leases and heartbeats. Accept at-least-once delivery, make it safe with idempotency keys and fencing, and protect the system from midnight spikes with look-ahead loading, queue buffering and per-team limits.