Problem RestatementProblem
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.
RequirementsRequirements
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
/v1/jobswith { name, schedule: "0 9 * * *" | run_at, payload, target: "http://svc/endpoint" | queue, retries: 3, timeout_sec, idempotency_key } → { job_id }/v1/jobs/{id}to pause, resume or change the schedule./v1/jobs/{id}to cancel./v1/jobs/{id}/runs?limit=20to see run history.High-Level ArchitectureArchitecture
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
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
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"] --> RHData ModelData 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.
Key FlowsFlows
4.1 Finding due jobs
- 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.
- Every second, it runs:
SELECT ... WHERE partition_id IN (...) AND next_run_at <= now() + 5s. - For each due job, it inserts a
job_runsrow (the unique key blocks duplicates) and pushes the run to the queue. - It moves
next_run_atforward to the next cron time in the same transaction.
4.2 Running a job
- A worker pulls a run and sets
state = running,lease_until = now + 30s. - While working, it sends a heartbeat every 10 seconds to extend the lease.
- When done, it marks the run
succeededorfailed. 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.
Deep Dive A — Running each due job once when workers crashDeep dive
Machines die mid-job all the time. The question is what the system does with a job whose worker went silent.
Claim the job by deleting it
A worker picks the next due row, deletes it so nobody else takes it, and runs the job.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
sequenceDiagram
participant W as Worker
participant DB as Jobs table
W->>DB: SELECT next due job
DB-->>W: job 812 - send payout
W->>DB: DELETE job 812
W-->>W: starts the payout, then crashes
Note over DB: no record left - the payout never runs and nobody knowsThe claim is a deletion, so a crash erases the job. This is the failure mode that loses money quietly: there is nothing left to alert on.
Lease the job with a timeout
Do not delete. Set status = running, leased_by = worker_7, lease_until = now + 60s. A sweeper finds rows whose lease has expired and puts them back in the queue, so a crashed worker's job gets picked up by someone else.
Nothing is lost now, but something worse is possible. A worker that is merely slow — a long garbage-collection pause, a network partition — has not crashed. Its lease expires, a second worker starts the same job, and then the first one wakes up and finishes too. Two payouts, no error anywhere.
Lease, fence, and make the target idempotent
Three pieces, and each one covers a gap the others leave:
- At-least-once delivery. Accept that a job may run twice. Trying to prevent that in the scheduler is the mistake; the fix belongs at the target.
- Idempotency key =
job_id + scheduled_for. The payment service stores keys it has already handled and ignores a repeat, so the second run is a no-op rather than a second payout. - Fencing token. Each re-assignment gets a higher attempt number, passed along with the call. The target rejects writes carrying a token lower than the highest it has seen, so the zombie worker that wakes up late cannot overwrite the newer run's result.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
sequenceDiagram
participant W1 as Worker 1 - stalled
participant W2 as Worker 2
participant T as Target service
W1->>T: run job 812 - token 4
Note over W1: long GC pause, lease expires
W2->>T: run job 812 - token 5
T-->>W2: done - highest token now 5
W1->>T: finally arrives - token 4
T-->>W1: rejected - stale tokenExactly-once execution across machines is not achievable; exactly-once effect is, and that is what this buys.
Deep Dive B — Handling the midnight spikeDeep dive
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.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Finding due jobs | Indexed next_run_at + polling | Simple, durable | Delay queues (SQS delay, Redis sorted set): less DB load, harder to edit or cancel |
| Scheduler scaling | Partitioned instances with leases | No single leader bottleneck | Single leader + standby: simpler, limited throughput |
| Delivery | At-least-once + idempotency keys | Achievable and safe | "Exactly once": not truly possible |
| Execution | Queue + worker pool | Absorbs spikes | Scheduler calls targets directly: fewer parts, no buffering |
Common Follow-up QuestionsFollow-ups
- "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_forand the actual start time, and alert when it grows.
Wrap-UpWrap-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.