Job Scheduler

What the interviewer is asking

"Design a job scheduler" (or "a distributed cron") asks for the service that runs other teams' work on a clock: the nightly sales report, a cleanup every 10 minutes, a reminder next Friday. Cron on one machine handles a few jobs; the question is what changes with millions of jobs and machines that fail.

The heart of it is two promises: every run starts on time, within seconds, and runs once, not zero times and not twice. The walkthrough follows the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• One-off jobs: run once at a set time, such as Friday at 18:00.
• Repeating jobs: cron-like schedules, such as every 5 minutes or every day at 02:00.
• Retries for runs that fail.
• History: each job's runs and their status.

Park the rest: dependencies between jobs (run B after A succeeds, a DAG), priorities and per-team quotas. Then say the two promises out loud: the deep dives keep them.

2. Data: jobs and runs

A job is registered once and runs many times, so there are two records:

record   fields
job      id, schedule, command and input, owner, next_run_at
run      id, job, scheduled_for, status, attempts, worker, started, finished

The job row changes when the team edits it and when the scheduler moves next_run_at after each run. The run rows are the history: a daily job adds 365 a year. The pair (job, scheduled_for) names exactly one run, which the exactly-once deep dive relies on.

3. The API: two calls

POST /jobs
Idempotency-Key: 5f2c9a
{"schedule": "daily 02:00", "command": "send-report"}
  → 201 Created   {"id": "j7"}

GET /jobs/j7/runs
  → 200 OK   [{"for": "Oct 24 02:00", "status": "succeeded"}, …]

Teams register jobs from scripts, and scripts retry when a reply is lost. Without protection the retry makes a second job, and every report goes out twice. An idempotency key sent on every try, or a job name unique per team, makes the retry return the first job.

4. The busy path: every second, the due jobs

The busy path isn't a user's request: it's the clock. Every second, find the jobs due now, start them, and set each one's next time. For one daily job:

1. A team sends POST /jobs: send-report, every day at 02:00.
2. The job is saved with next_run_at = 02:00 tonight.
3. At 02:00:00 the every-second check finds it due.
4. The command starts, and next_run_at moves to 02:00 tomorrow.
5. The command ends, and the run is saved as succeeded.

Registering happens once; the last three steps happen every day, for every job.

5. The numbers

From the interviewer: 10 million jobs, each running about once a day on average.

• Runs: 10 million a day ÷ 100,000 seconds (a day is 86,400; round it for a quick estimate) = about 100 runs a second, about 116 with the exact 86,400.
• The midnight rush: round times are popular. If 1 million daily jobs are set for 00:00 UTC, a million runs are due in the same second: 10,000 times the average.
• History: 10 million run rows a day at about 500 bytes each is 5 GB a day, about 1.8 TB a year.

The average is easy; the peak and the failures shape the design.

6. Services: a scheduler, a queue and workers

One app that also runs the commands mixes fast work with slow: a report that runs for an hour, or a command that crashes, holds up the polling every job depends on. Split it:

• Job API: registers and edits jobs, and serves the history.
• Scheduler: every second, reads the due jobs, saves a run for each, puts it on the run queue and moves next_run_at on. It never runs a command, so it stays fast.
• Workers: pull runs from the queue, run the command, save the result, then ack (Message Queues).
• Two databases: the jobs DB (10 million rows, read every second) and the runs DB (10 million new rows a day, mostly writes), so the history's writes never slow the poll.

7. Scale: the midnight rush

A million runs due at 00:00:00 is a thundering herd. Say the workers can take about 5,000 new runs a second: with no spread, the last of the million waits 200 s in the queue, over 3 minutes. Most daily jobs don't need the exact second, so each such job gets a random offset, say up to 10 minutes, picked once at registration: jitter. Spread over 10 minutes (600 s), about 1,700 runs are due a second, well under 5,000, and each job keeps the same time every day. The few jobs that need 00:00 sharp keep it and wait their turn in the queue.

Machines to start a million runs in one second would be 10,000 times the average, idle the rest of the day. Starting early is never allowed: a daily report started at 23:57 misses the day's last 3 minutes.

8. Deep dive: finding the due jobs

Reading all 10 million rows every second, about 5 GB, to find about 100 is hopeless. An index on next_run_at keeps the jobs in time order, so the poll reads from the earliest up to now and stops: about 100 rows in an average second, one lookup when nothing is due (Indexes). A common alternative: time buckets, a list of job ids per minute.

Two rules make it work. The poll reads next_run_at ≤ now, not = now, so a late poll still finds what it missed. And the next time is counted from the time the run was for, not from when the poll ran, so delays never shift a job. Six jobs, polled at the start of each minute (A every 2 minutes, B every 3, C every 5, cron-like on the clock's minutes; D daily at 02:03; E once at 02:05; F daily at 00:00, not due here):

poll    enqueued   next_run_at after the poll
02:00   A B C      A 02:02, B 02:03, C 02:05
02:01   none       no rows: nothing is due
02:02   A          A 02:04
02:03   B D        B 02:06, D Oct 25 02:03
02:04   A          A 02:06
02:05   C E        C 02:10, E none: a one-off leaves the index
02:06   A B        A 02:08, B 02:09

9. Deep dive: exactly once

Two schedulers. One scheduler is a single point of failure, but two that both poll enqueue every run twice. Elect a leader: only it polls, and a standby takes over when it goes quiet. A coordination service such as etcd or ZooKeeper runs the election by majority vote (Consensus and Leader Election); each new leader gets a higher term, and writes stamped with an older term are refused (fencing).

A takeover repeats work. If the leader crashes after enqueueing r57 but before moving next_run_at, the new leader finds the job still due and would enqueue it again. The fix is a unique key on (job, scheduled_for) in the runs table: the second insert of (j7, 02:00) is refused, so the new leader knows the run exists and only moves next_run_at on. The database checks and writes in one step, like the conditional update in Concurrency and Locks.

for job in due_jobs(now):                    # next_run_at <= now, from the index
    run_id = save_run(job.id, job.next_run_at)  # None if (job, scheduled_for) exists
    if run_id:
        queue.put(run_id)
    move_next_run_at(job)                   # from the schedule, not from now

One gap remains: a crash between saving a run and enqueueing it. A sweep that re-enqueues runs left queued too long covers it; since a worker claims a run with a conditional update (queued → running), an extra copy is harmless.

A worker crash. A worker can die after the work and before its ack; two minutes later the queue hands the run to another worker, which sends the report again. The unique key can't help: it's the same run. The queue gives at least once, so the job's effect must be idempotent: the command gets the run id and uses it as an idempotency key (send report r57 once). At least once plus idempotent jobs is what "exactly once" means in practice: effectively once.

10. Deep dive: retries and timeouts

Workers send a heartbeat every 30 s while a run goes. A run whose heartbeats stop for 2 minutes has lost its worker and goes to another one. A run that hangs still beats, so each job also has a timeout, 1 hour here: past it, the worker kills the command, and that counts as a failed try. Failed tries retry with backoff, then go to dead letters with an alert to the owner:

try   starts            result
1     02:00             failed
2     02:01 (+1 min)    failed
3     02:03 (+2 min)    failed
4     02:07 (+4 min)    failed: dead letters, alert the owner

Retry only jobs that are safe to repeat. A job that charges 10,000 cards and times out partway has charged an unknown number, and a blind retry charges some twice. Either it keys each charge by the run id and the customer, so a retry skips cards already charged, or it's marked not to retry and its failure goes to its owner. Teams say which when they register the job.

11. Deep dive: missed runs

If the scheduler is down from 02:00 to 02:10, standby and all, its next poll finds every job that fell due in those 10 minutes at once. Each job picks a policy:

• Catch up, running the missed run once, late, when each run matters on its own: yesterday's report, today's renewals, a one-off email that never comes again.
• Skip, moving next_run_at to the next time from now, when the next run does the same work: health checks, dashboard refreshes, cleanups. Catching up an every-minute refresh would run it 10 times in a row, just as the system restarts.

What breaks first

• Round times: jobs crowd onto the hour. Watch how late the oldest waiting run is: the scheduler's most telling number.
• The jobs DB: one leader polling one index has a limit; past it, partition the jobs by id, each partition with its own leader.
• The runs DB: about 1.8 TB a year. Keep recent runs at hand and move old ones to cheaper storage.
• Overlapping runs: a job every minute that takes 5 minutes has 5 copies running at once. Let each job say whether its runs may overlap.

Summary: the order to follow

1. Scope: one-off and repeating jobs, retries, a history; on time and once.
2. Data: a job row with next_run_at; a row per run.
3. API: POST /jobs with an idempotency key; GET /jobs/{id}/runs.
4. Busy path: every second, start the jobs due now.
5. Numbers: about 100 runs a second, 1 million at 00:00.
6. Services: the scheduler only enqueues; workers run the commands.
7. Scale: jitter for jobs that allow it, the queue for the rest.
8. Deep dives: an index on next_run_at; one leader, a unique (job, scheduled_for) and idempotent jobs; heartbeats, timeouts and backoff; catch up or skip.

The same shape fits any work on a timer, such as reminders and billing runs: find what's due from an index, enqueue it once, make the work safe to repeat.