Cruxly › System design › Design Exercises

Distributed Job Scheduler

exactly-once execution when the executor can die mid-job

Prompt: design a distributed job scheduler — like cron, but running across a fleet. Jobs run on a schedule or on demand; each job must run, and a job must not run twice concurrently or be silently dropped if the worker executing it crashes.

40 minutes first. The scheduling part is easy. The failure recovery is the entire exercise.

Applying the four moves: Scope — cron-style and on-demand jobs across a fleet, each job runs, never twice concurrently, never silently dropped on a crash; job authoring UI out. Estimate — jobs per second at the top-of-the-hour spike, when a large fraction of all cron jobs fire simultaneously — that spike, not the average, sizes the dispatcher. Sketch — a durable job store, a dispatcher that claims due jobs, and workers holding leased claims. Deep dive — the failure recovery the prompt flags: a worker crashes mid-job, so claims must be leases that expire, and "never twice" plus "never dropped" together mean the job itself has to be idempotent.

Scope, and why 'exactly once' is the wrong target

In scope: schedule definition (cron-style or one-off), reliable dispatch to a worker, execution tracking, retry on failure, preventing concurrent duplicate runs of the same job. Out of scope: the job payloads' own business logic, a UI for authoring schedules, cross-job dependency graphs (DAG scheduling — name it as a real, separate, harder problem if pushed).

Estimate. Say 1 million scheduled jobs, average interval of 1 hour, meaning roughly 280 jobs/s need to start on average, bursting heavily at common boundaries (top of every hour, midnight) because that's how humans schedule things.

The framing that matters more than the number: in a distributed system, a worker can crash between "I started the job" and "I recorded that I finished it." At that boundary, you cannot know from the outside whether the job's side effect happened. True exactly-once execution is not achievable when the executor itself can fail mid-execution — this is the same impossibility that shows up in the payment ledger's "the network timed out, did the charge happen" case elsewhere in this track, just relocated to job execution instead of a card network call.

The achievable target: at-least-once execution, with jobs required to be idempotent. A job that might run twice must produce the same end state either way. This shifts a chunk of the correctness burden onto job authors, and that shift has to be an explicit, stated part of the contract — not a silent assumption the scheduler team makes and the job-owning teams discover during an incident.

Claiming a job: the same primitive as three other exercises

Two schedulers racing for the same due job resolve the same way find-and-claim resolves everywhere else in this track: one conditional update, and the row count tells each side what happened.

Claiming a due job is find-and-claim, the identical primitive from the parking lot, the rate limiter's bucket creation, and ride matching's driver assignment elsewhere in this track:

UPDATE jobs
   SET status = 'claimed', owner = :node_id, claimed_at = now()
 WHERE id = :job_id AND status = 'due'

One conditional update. If it affects zero rows, another node already claimed it — back off, do not execute. This is cheaper and more robust than a separate distributed lock service: the claim and the state transition are the same atomic operation, so there is no window where you hold a lock but haven't yet recorded the claim.

A claim without a lease is a claim that can leak forever. If node A claims the job and then crashes before finishing, the job sits claimed eternally — nobody else will touch it. Attach a lease with a timeout: claimed_at + lease_duration. A separate reaper process periodically finds jobs WHERE status = 'claimed' AND claimed_at < now() - lease_duration and resets them to due, making them claimable again. This is the exact "evaluate expiry on read, not with a sweeper that races the happy path" pattern from seat booking — except here a background reaper is correct, because there is no fast happy-path acquire it could race; it only acts on leases that have already, provably, expired.

Preventing duplicate concurrent runs, and the retry story

Two different problems get conflated if you're not careful: preventing a job from running twice at the same scheduled time, and preventing a retry from running concurrently with the execution it's retrying.

The claim-with-lease mechanism above already solves the first: only the claiming node executes, and the row-level conditional update prevents a second concurrent claim. The second needs one more rule: do not schedule a retry while the original attempt might still be running. A retry should only fire after the lease has definitively expired — otherwise a slow-but- not-dead worker and a "helpful" retry can both be executing the same job at once, which is exactly the double-execution the lease was supposed to prevent.

Idempotency keys, again, doing the same job they do everywhere else in this track. Give each execution attempt a unique ID derived from (job_id, scheduled_time). If the job's own side effect is "call this downstream API," pass that ID through so the downstream system can deduplicate — the identical idempotency-key discipline from the payment ledger and the notification system, just handed down one more layer to whatever the job actually does.

Retry policy needs to distinguish failure types, the same distinction made in the notification system's per-channel retry logic: a transient failure (timeout, 503) retries with backoff; a permanent failure (the job's logic threw a clear, non-retryable error) should not retry at all and instead alert — retrying a job that is deterministically going to fail forever just wastes worker capacity and delays the alert that would actually get someone to fix it.

Scaling the scheduler itself, and the failure modes

Do not have one process tick through 1 million jobs checking due-times every second. Index jobs by their next-due-time and query only WHERE next_run_at <= now(), exactly the same "query by what's actually needed, not scan everything" principle as every other exercise in this track. Partition that index across nodes by a hash of job ID so no single node owns checking all 1 million jobs.

The thundering-herd-at-scheduling-boundary problem is real and specific to this system. Because humans schedule things at round numbers — top of the hour, midnight, the first of the month — due-times cluster heavily at those instants, producing a burst of simultaneous claims rather than smooth load. Mitigation: add small random jitter to next_run_at at schedule-creation time (a job "hourly at :00" actually runs at :00 plus up to a few seconds of jitter), spreading the burst without meaningfully changing when anyone perceives the job as having run.

Failure modes:

The reaper itself is a single point of failure. If nothing resets expired leases, claimed-but-abandoned jobs accumulate forever. Run multiple reaper instances; resetting an already-due job is a no-op, so redundant reapers cost nothing and cost less than a missing one.

Clock skew across nodes. Use a single logical source for "now" when comparing lease expiry — the database's clock, the same discipline as the booking exercise's hold-expiry check — rather than trusting each node's own wall clock, which can disagree by enough to matter at this granularity.

A job that always fails and always retries. Cap retry attempts, and once exhausted, move the job to a dead-letter state and alert rather than retrying forever — the identical DLQ discipline from the queues lesson elsewhere in this track, applied to scheduled work instead of a message queue.

How to say it in the interview

"The hard requirement is that a worker can die mid-job at any instant, and I still need exactly one execution to count — not zero, not two. That is not achievable in the literal sense, so the real target is at-least-once execution with an idempotent job contract, made visible rather than assumed."

Checklist

Named true exactly-once execution as unachievable and at-least-once-plus-idempotency as the real target
Made the idempotency requirement an explicit, stated part of the job contract
Claimed due jobs with one conditional update rather than a separate lock service
Attached a lease with a timeout to every claim
Used a reaper that only resets provably-expired leases, not a sweeper racing the happy path
Prevented a retry from running concurrently with a still-possibly-live original attempt
Passed an idempotency key derived from (job_id, scheduled_time) down to the job's own side effects
Distinguished transient failures (retry with backoff) from permanent ones (alert, don't retry)
Indexed by next-due-time and queried only what's due, rather than scanning every job
Jittered schedule times to avoid a thundering herd at common boundaries
Ran multiple redundant reapers rather than treating it as a single point of failure
Used a single clock source (the database's) for lease-expiry comparisons

Practice this interactively