Design a distributed job scheduler

01The design, in the six-step framework

1. Requirements

Interviewers add twists: machines with variable CPU and RAM, jobs with dependencies, a function that places jobs on a rack. Clarify first: is this cron at scale (time-triggered, many small jobs) or a workload scheduler (placement under resource constraints)? Design the cron-at-scale core with placement as a deep dive; the GPU variant is its own problem.

Functional

• Users register jobs with a schedule (cron expression or one-off time), a command or container, resource needs, a timeout, and a retry policy.
• Jobs run on time, on some healthy worker, and exactly once per scheduled firing even when schedulers or workers crash.
• Dependencies: a job may run only after other jobs' runs of the same period succeed.
• Users see run history, logs and status, and can pause, cancel or re-run.
• Out of scope: the container runtime itself, cluster autoscaling.

Non-functional

• Scale: 10 million registered jobs, 50 million runs a day, bursts of 100,000 runs due in the same minute (top of the hour).
• Timeliness: a run starts within 5 seconds of its due time at p99 when capacity exists.
• Correctness: no duplicate runs, no missed runs; a run's final state is durable.
• Availability: 99.95 percent for scheduling; a scheduler node failure delays runs by seconds, not minutes.

2. Core entities

• Job: job id, owner, schedule, payload (image, command, env), resources (CPU, RAM), timeout, retry policy, dependencies, status (active, paused).
• Run: run id, job id, scheduled time, state (due, dispatched, running, succeeded, failed, cancelled), attempt, worker, started, finished, exit info.
• Worker: worker id, capacity, free resources, heartbeat time, running run ids.
• Partition: a slice of job ids owned by one scheduler instance under a lease.

3. API

• POST /jobs with schedule, payload, resources, retries, dependencies; PATCH /jobs/{id}; POST /jobs/{id}/pause.
• GET /jobs/{id}/runs?from=&to= and GET /runs/{id} with log links; POST /runs/{id}/cancel; POST /jobs/{id}/run-now.
• Worker-facing: POST /workers/{id}/heartbeat with free resources and run states; POST /runs/{id}/ack, /started, /finished.

4. High-level design

1. Registering a job computes its next due time and stores it; jobs are hashed into partitions (say 64).
2. Each scheduler instance leases some partitions and keeps their jobs in a min-heap by due time. Every second it pops jobs that are due, creates a run row with a unique key of (job id, scheduled time), and enqueues the run.
3. The dispatcher takes runs from the queue and assigns each to a worker with enough free resources; the worker acknowledges, runs it, and reports state transitions.
4. Heartbeats from workers update free capacity; a worker that stops heartbeating has its runs re-queued after a timeout.

5. Deep dives

How is "exactly once per firing" achieved when schedulers can crash or double up?

Two mechanisms, layered. Partition leases from a lock service ensure that normally one scheduler owns a job; a scheduler that loses its lease stops scheduling that partition before the lease expires. Leases can still overlap for a moment (clock skew, a slow instance), so the real guard is the database: the run row's unique key (job id, scheduled time) makes the second creation fail, and only the creator enqueues. Dispatch is at-least-once, so the worker-side start is idempotent on run id: a worker asked to start a run it already has ignores the duplicate, and the run state machine rejects out-of-order transitions. Say this ordering out loud: lease for efficiency, unique key for correctness.

How does the top-of-the-hour burst start 100,000 runs within seconds?

The heap pop is cheap; the costs are run creation (100,000 inserts, batched into a few hundred bulk writes) and dispatch. The dispatcher is sharded by queue partition and places runs in parallel; with 500 workers each able to start a run in 50 ms that is 10,000 starts a second, so the burst drains in 10 seconds, slightly over the 5-second target. Two fixes: jitter, where jobs that do not need the exact minute are offered a spread window and the scheduler assigns a stable offset within it; and pre-dispatch, where runs due in the next 30 seconds are placed on workers early and started by a local timer. The p99 target then holds for jobs that insist on the exact second.

How are resources and placement handled when workers differ?

Each worker advertises CPU, RAM and labels; each job states its needs. The dispatcher keeps an in-memory view of free capacity from heartbeats and picks a worker by best fit (the smallest free slot that fits, to avoid fragmenting big machines), with a reservation applied immediately so two dispatchers do not oversubscribe the same worker; reservations are confirmed by the worker's acknowledgement or released after a timeout. The "write a function that schedules jobs on a rack" variant is this best-fit loop, and it is worth coding it when asked: sort jobs by size descending, place each on the fittest machine, which is the first-fit-decreasing heuristic for bin packing. For dependencies, a run is created in state waiting and moved to due when every upstream run for the same period succeeds, tracked with a counter on the run row updated by the finish handler.

What happens when workers or runs fail?

A worker missing three heartbeats (30 seconds) is marked dead; its runs are marked lost and re-queued if the job's policy allows retries, with the attempt number incremented and exponential backoff. A run that exceeds its timeout is killed by the worker and marked failed. Retries of non-idempotent jobs are the owner's decision: the policy defaults to no retry for jobs that do not declare idempotency. Failure detection on the scheduler side is the lease: a dead scheduler's partitions are taken over within the lease period, and the new owner reloads the partition's jobs from the database, including any whose due time passed during the gap, which it fires immediately (catch-up) or skips, per job policy.

6. What a strong answer sounds like

• Separate scheduling (when) from dispatch (where) and name the state machine of a run.
• Explain exactly-once as lease plus unique run key plus idempotent worker start.
• Quantify the burst and give jitter and pre-dispatch as the levers.
• Describe best-fit placement with reservations, and be ready to code first-fit decreasing.
• Follow-ups to expect: priorities and fairness across teams (weighted queues), very long jobs (checkpointing, see the GPU variant), and observability (per-job lateness histograms, which is the metric that tells you when to add schedulers or workers).
• A common mistake is a single scheduler that scans the whole table every second; partition and keep due times in memory.

02Where this question was reported

• IGotAnOffer · SWE: 'Design a task-scheduling system'; mid-level 'job queue'
• IGotAnOffer · 'task scheduling system'; 'function that schedules jobs on a rack of machines' with CPU/RAM constraints
• Exponent · 'distributed job scheduler for cron jobs across machines with variable CPU and RAM'
• DesignGurus · 'Distributed Job Scheduler'
• PracHub · 'Task Scheduler for Opaque Long-Running GPU Jobs (Design Sora)', Hard, Senior+
• PracHub · 'task scheduler with dependencies', Hard
• scaleengineer.com · 'Design a distributed job scheduler'
• Blind · Job scheduler
• Prepfully · Candidate reports: cron jobs across machines with variable CPU/RAM.