Library
30 min read

Design a distributed job scheduler

"Send this reminder at 9am." "Rebuild the report every night at 2." "Retry this export in ten minutes." Every product grows a pile of work that has to happen later, at a time, and it has to happen even when the machine that was going to do it has died.

Watch one run go from a schedule to done.

ServicesScheduler APIJob storePartition scannerRun queueWorkersTarget service

Submit. A service asks for a job: call this endpoint every day at 02:00, Asia/Kolkata.

Two promises pull against each other here. Every due run must start, even if a worker or a scanner dies, which pushes you towards running things again. And a run should have its effect once, which pushes you away from running things again. The design is mostly the machinery that lets you keep the first promise without breaking the second.

Where this already exists

This page builds a shared scheduler service, the kind a company runs so that every team does not write its own cron box. The numbers are interview assumptions. You have probably used a small version: Kubernetes CronJob runs a job on a cron schedule and makes you choose a concurrencyPolicy (allow overlapping runs, forbid them, or replace the old one) and a startingDeadlineSeconds for runs that start late. Quartz, the Java scheduler, calls the late run a misfire and makes you pick what to do with it. Both are the decisions this page is about.

A few words used all through this page:

  • A job is the definition: what to call, with what, and when. A run is one execution of a job at one scheduled time.
  • A lease is a claim with an expiry. A worker holding a run's lease is the one allowed to run it, until the lease runs out.
  • A fence token is a number that goes up every time a lease is handed out, so storage can tell an old holder from the current one.
  • A misfire is a run whose time passed while nothing was able to start it.

Step 1: Understand the problem#

Ask what "exactly once" means to them before you draw anything. The answer decides whether you are building a scheduler or a distributed transaction system, and you want to be building a scheduler.

You askThey sayWhat it settles
One off jobs, recurring jobs, or both?Both. "Run at 9am on Friday" and cron schedules like "every day at 02:00".A recurring job is a stream of runs, each with its own id made from the job and the scheduled time. That id is what makes creating a run twice harmless.
How many runs, and when?About 50 million a day, with big spikes on round times like midnight and 9am.The average is small. The busiest minute is the design load, and a scheduler that is fine at the average falls over at 09:00.
How late may a run start?A few seconds is fine. Some jobs say "any time in this five minute window".A scanner that looks for due runs every second or so, not a timer per job, and a window field that lets the system spread a spike.
Must a job run exactly once?It must never be skipped, and running twice should do no harm.At least once execution, plus a run id the target uses as an idempotency key, plus fence tokens for storage writes. Exactly once execution is not on offer, and the design says so.
What happens to runs missed while the scheduler was down?Depends on the job.A misfire policy per job: skip, run once to catch up, or run every missed slot.
Do jobs run inside the scheduler, or call something else?They call a target: an HTTP endpoint or a queue topic owned by the team.The scheduler owns time and delivery, not the work. It cannot make a target's side effects happen once, only hand it what it needs to make them so.

What you are building, and what you cut#

Functional requirements
What the system does.
  • Create, pause and delete one off and recurring jobs. The definition, stored once and changed rarely.
  • Start every due run within seconds of its time. The core promise, and the part that has to survive failures.
  • Retry failed runs with backoff, then give up visibly. Targets fail, and a run that silently vanishes is the worst outcome.
  • A history of runs per job. The first thing anyone asks when a report did not arrive.
Non-functional requirements
How well it has to do it. The numbers you commit to.
  • 50 million runs a day, and a busiest minute far above the average.
  • A due run starts within about 5 seconds, or within its window.
  • No run is skipped because a machine died. Running twice is allowed, with a run id to dedupe on.
  • Survives the loss of any scanner, worker or zone.
Out of scope
What you cut, and say so out loud.
  • Workflows with many dependent steps. That is a workflow engine, and it sits on top of this.
  • Running the job's code. Targets run their own code; the scheduler calls them.
  • Sub second precision. Nobody needs a reminder at 09:00:00.250.
  • Per tenant quotas and billing. Real, and they do not change the core.

Back of the envelope#

A small version first. 50 million runs a day over 86,400 seconds is about 580 a second. If 5% of a day's runs are set for 09:00 exactly, that is 2.5 million runs in one minute, about 42,000 a second, more than 70 times the average. The window slider shows what letting those jobs start any time in the next few minutes does. (The back of the envelope chapter covers the method.)

The average is not the load
50 million
5%
1 minutes
Average starts per second50,000,000 / 86,400 = 579
Runs set for the busiest minute50,000,000 x 5% = 2,500,000
Peak starts per second2,500,000 / (1 x 60) = 41,667
Peak against the average72x
41,667 a second
at the busiest minute, which is the number to design for

Size for the peak, not the average. A window of 1 minute turns the spike into 41,667 starts a second. Most jobs set for 09:00 do not care whether they start at 09:00 or 09:03, and asking for the window is the cheapest capacity you will ever buy.