Queues & eventsAdvanced
A job scheduler that runs a job once, on time, on some machine
Cron on one box is five minutes of work. Cron on twenty boxes, where any of them can die mid-job, is this.
The brief
Users schedule jobs — once at a time, or on a repeating schedule.
Jobs are executed by a pool of workers. Workers are ordinary machines and can disappear without warning.
Requirements
Functional
- Schedule a one-off job for a future time
- Schedule a recurring job
- Cancel a scheduled job, including one that is about to run
- Report what happened to each run
Non-functional
- A job must not run twice concurrently on two workers
- A job whose worker dies mid-run must eventually run again
- Late is usually survivable; silently never running is not
Back-of-envelope
Assume
- 1 million scheduled jobs in the system
- Peak of 2,000 jobs due in the same second — schedules cluster on the hour and nobody schedules for 3:07
- A job takes 5 seconds on average
Therefore
- Steady rate is low, but the clustering is the design constraint: 2,000 due at once, not spread across the minute.
- Concurrency: 2,000 × 5 s = 10,000 worker-seconds to clear one spike. Twenty workers take about eight minutes; two hundred take about fifty seconds.
- The polling query is 'jobs due before now, not yet claimed' — a range scan on a time index, run repeatedly by every worker.
Averaging 2,000 jobs over 60 seconds would have said 33 per second and hidden the spike completely. The clustering is stated as its own assumption because it is the one that sizes the worker pool.
The interface
POST /jobs { runAt | schedule, payload } → 201 { jobId }One endpoint for both one-off and recurring, because a one-off is a schedule that fires once. Two endpoints means two claim paths and two places to get the lease wrong.
DELETE /jobs/{id} → 204, or 409 if it is already claimedThe 409 is the honest answer to the cancel race. Returning 204 for a job that a worker claimed a millisecond ago tells the caller it was cancelled when it is about to run.
GET /jobs/{id}/runs → [{ startedAt, finishedAt, outcome, attempt }]Runs are plural and that is the API admitting at-least-once. A field called `status` on the job would imply one execution, which is the guarantee this system deliberately does not make.
What is stored
jobs
A partial index on (nextRunAt) WHERE state = 'DUE' is the hottest object in the system and stays small — a million jobs, but only the due ones are in the index every worker is hammering. leaseGeneration is what makes fencing possible; see the failures below.
id · schedule · payload · state · nextRunAt · leaseUntil · leaseOwner · leaseGeneration · attemptA partial index on (nextRunAt) WHERE state = 'DUE' is the hottest object in the system and stays small — a million jobs, but only the due ones are in the index every worker is hammering. leaseGeneration is what makes fencing possible; see the failures below.
runs
A separate table because a job has many runs, and because 'report what happened to each run' is a functional requirement that a single mutable status column on the job cannot satisfy.
jobId · attempt · workerId · startedAt · finishedAt · outcomeA separate table because a job has many runs, and because 'report what happened to each run' is a functional requirement that a single mutable status column on the job cannot satisfy.
The design
The schedule storeJobs with a next-run time, indexed on it. This index is read constantly by every worker, which makes it the hottest thing in the system.
ClaimingA worker atomically marks a due job as claimed, by itself, with a lease expiry — in one operation. Read-then-write is the bug: two workers read the same due job and both proceed.
The leaseA claim expires. A worker that dies stops renewing, the lease lapses, and another worker picks the job up. This is what makes crash recovery automatic rather than a manual queue drain.
RecurrenceOn completion, compute the next run from the SCHEDULE, not from the finish time. Otherwise a job that runs slow drifts a little later forever.
The decisions
Each of these could go the other way. The choice, the reason, and what it costs — a design that lists only what it chose teaches the choice; one that lists what it gave up teaches the judgement.
Poll a table, or use a message queue with delayed delivery?Chose — Poll a table, when cancellation mattersBecause — A message already sitting in a queue with a 30-day delay is hard to cancel or reschedule. A row is trivially updatable right up to the moment it is claimed.Constant polling against a hot index, and every worker running the same query. A queue would have given you the dispatch for free.
At-least-once or at-most-once execution?Chose — At-least-once, and require jobs to be idempotentBecause — At-most-once means a job whose worker died is simply never run, and you cannot tell that case from a job that completed. Silently skipping is the worse failure for almost every job anyone schedules.Every job author now has to make their job safe to run twice, and most will not until it bites them. This must be in the API documentation, not in a design document nobody reads.
How long is the lease?Chose — Longer than the slowest job, and renewed while runningBecause — A lease shorter than the job means a healthy worker's job gets stolen mid-run and executed concurrently — precisely what the lease exists to prevent.A long lease means a crashed worker's job waits that long before anyone retries it. Renewal is what lets the lease be short and the job be long, at the price of a heartbeat.
What breaks first
In order. Each names what you would actually observe, and each fix carries its cost.
Every worker polling the same indexSymptom — The polling query is cheap once and ruinous two hundred times a second. Past a certain worker count the database spends more time answering 'what is due?' than the workers spend doing the jobs.Fix — Claim in batches of N, and jitter the poll interval so the fleet stops arriving in lockstep.A worker that dies holding a batch strands N jobs for a lease duration instead of one. The batch size is a direct trade between database load and worst-case recovery time.
The 2,000-at-once spikeSymptom — 10,000 worker-seconds arriving in one second. On twenty workers the last job in the spike starts about eight minutes late, and it is late for no reason a user can see.Fix — Autoscale on the count of jobs due in the next minute — a number you can read directly — rather than on CPU, which only rises after the backlog exists.Scaling reacts after the spike has begun, so the first spike of the day is always slow. Keeping two hundred workers warm for a schedule that clusters on the hour means paying for idle capacity fifty-eight minutes an hour.
Contention on the claim itselfSymptom — Every worker targets the same handful of oldest due rows, so they queue on the same locks and most of them lose.Fix — SKIP LOCKED, so a blocked worker takes the next row rather than waiting for the one in front.Execution order stops being strictly by due time. For a scheduler that is usually fine, and it must be a sentence in the documentation rather than a surprise.
When something fails
A worker dies mid-runIt stops renewing, the lease lapses, another worker claims the job, and it runs a second time in total. That is at-least-once working, not failing — and it is why the API documentation has to say jobs must be idempotent.
A worker is paused past its lease and wakes up believing it still owns the jobTwo workers own it, and the lease alone cannot stop the older one — it has already been paused, so it cannot be asked anything. Its writes have to carry the leaseGeneration it claimed with, and be rejected as stale. Without a fence, a lease is a hope with a timestamp on it.
The database is unreachableNothing runs and nothing is lost: nextRunAt is durable, so jobs come back late rather than never. That is exactly the asymmetry the requirements asked for, and it is the payoff for polling a table instead of holding schedules in memory.
A job fails every single timeWithout an attempt cap it retries forever and holds worker capacity for jobs that will succeed. Cap the attempts and move it somewhere a human will see it; a retry loop with no end is an outage that reports itself as busy.
Scaling it
Each step is triggered by a number, not a feeling — and carries what it costs.
10× jobs — ten millionMove — Partition the table by nextRunAt bucket, so the due partition is small and the far-future ones are never touched.Cancelling a job now has to find it across partitions, and rescheduling moves a row between them — both on the path that was previously a single primary-key update.
10× the spikeMove — Hash jobs into shards and give each worker a disjoint slice, so no two workers contend for the same rows at all.Idle workers on one slice cannot help a backed-up slice. You have removed contention by removing the pool's ability to rebalance itself.
Sub-second precisionMove — In-memory timers on the workers, with the table as durable backup rather than as the dispatch mechanism.A different system with different failure modes — memory is not durable, and every crash now loses the next few seconds of schedule. If the requirement is really sub-second, say that this design is the wrong one rather than stretching it.
What gets probed
The design is the easy half. These are where the conversation goes, and each has a defensible answer above.
- A worker claims a job and is paused by a long GC for longer than its lease. Two workers now believe they own it. What happens?
- 2,000 jobs come due at once and you have 20 workers. What does the last one's latency look like?
- A user cancels a job one millisecond before a worker claims it. Who wins, and is that the answer you want?
- A recurring job takes longer than its interval. What should happen?