Loading…

Understanding the problem

A job scheduler runs work at a time: a one-off job at a set moment, or a recurring job on a cron schedule. Here it is a managed service for about 50,000 customers whose jobs send emails and charge cards, so a run that fires twice costs real money and one that doesn’t fire is a broken promise.

Two things make it hard: finding what is due each second without reading every job, and turning each scheduled time into one run that survives crashed schedulers, crashed workers, the midnight rush and many customers. Workflows where one job waits for another are a different problem.

The practice brief gives the requirements; confirm them quickly. The first non-functional one is the invariant: one run per scheduled time of a job, however many schedulers run, with retries allowed after a failure.

Functional requirements

CoreCustomers create one-off jobs, due at a time up to a year ahead, and recurring jobs, set with a cron expression in a time zone they choose; each job calls the customer’s HTTPS endpoint or a function on the platform’s workers with a payload.
CoreCustomers pause, resume, change and delete jobs, and cancel a run that is in progress.
CoreCustomers see each job’s runs for the last 30 days: when each was due, when it started and finished, how many tries it took, and the result.
CoreThe platform tells the customer when a run has finally failed.
Below the lineWorkflows where one job waits for another.
Below the lineRunning customers’ own containers of any size (functions are capped at 6 hours).
Below the linePrecision finer than a second.
Below the lineBilling.
Below the lineOne job fanning out to many targets.A customer can create a job per target; fan-out belongs to the target.
Below the linePriorities among one customer’s own jobs.Fairness between customers is in scope; ordering inside one customer can come later.

Non-functional requirements

ConsistencyEach scheduled time of a job produces one run, never two, however many scheduler machines are running; a run may be tried again after a failure.
LatencyA run starts within about 5 seconds of its scheduled time, at p99.
DurabilityA due run is never lost silently: the platform keeps trying, or tells the customer it failed.
AvailabilityWorker and scheduler machines fail without stopping customers’ jobs.
QualityOne customer’s jobs must not delay other customers’ runs.
Availability

Scale

From the briefNumbers here are given in the practice brief.

ScaleAbout 200 million jobs stored and about 2,000 new or changed jobs a second, from about 50,000 customers with a few jobs to about 2 million each.
ScaleAbout 5,000 runs due a second on average, about 300,000 at the top of every hour and about 1 million at 00:00:00 UTC.
ScaleThe worker fleet starts about 50,000 runs a second today. Most runs finish within 2 seconds; some reports run for up to 6 hours.
ScaleWorker machines fail several times a day and a scheduler machine about once a week; a bad deploy once stopped all scheduling for 10 minutes; three regions, one down for about an hour in two years.

Out of scope

Out of scopeThe customers’ endpoints and what their tasks do.
Out of scopeAuthentication internals: customers already have credentials.
Out of scopeThe console’s screens.
Out of scopeServer hardware and the network between regions.

Check yourself

Why can’t the platform promise that a customer’s task runs only once?
Show answerHide answer
A worker can die after the task charged a card but before the platform recorded success. The platform can’t tell whether the task acted, so it runs it again. It can promise one run per scheduled time, and give every attempt the same run id so the task can skip a repeat.

The numbers that shape the design

From the briefNumbers here are given in the practice brief.

Work out the few numbers this design depends on. The point is to see which second sizes it.

Back of the envelope from the brief

Quantity	Value	Working
Job records	About 200 GB	200 million jobs × about 1 KB
Runs a day	About 430 million	5,000 a second × 86,400
The midnight second	About 1 million runs	200 times the average second
Starting them today	About 20 seconds	1 million ÷ 50,000 starts a second, against 5
Start rate needed	About 200,000 a second	1 million within 5 seconds
History	About 13 billion runs	30 days at 5,000 a second: a few TB

What the numbers tell you

The job records are small; one sharded database holds them.
The average second is easy; the midnight second is 200 times it.
History is the large data, so it lives apart from the live tables.

Architecture diagramWhere the load lands

From the brief: small job records, an easy average, and a midnight second two hundred times it.

Diagram as text

Components: 200 million jobs: ~200 GB (SQL DB); An average second: ~5,000 runs (Service); 00:00:00 UTC: ~1 million runs (Service); Workers: ~50,000 starts/s (Worker). Connections: 200 million jobs: ~200 GB → An average second: ~5,000 runs (due each second); 200 million jobs: ~200 GB → 00:00:00 UTC: ~1 million runs (due at once); 00:00:00 UTC: ~1 million runs → Workers: ~50,000 starts/s (about 20 s to start).

Read:Learn: Numbers and capacity estimation

Try it: The numbers that shape the designGuided practice · Job scheduler, Managed scheduler · Senior

Keep reading+1 min

The cost of the busiest second

Starting a million runs within 5 seconds needs about 200,000 starts a second for a few minutes, four times today’s fleet. Paying for that around every top of the hour is the real cost decision, and the Staff deep dive prices it.

Check yourself

Why is the average second not the one to design for?
Show answerHide answer
At 5,000 runs a second the workers idle. At midnight a million come due in one second, and at today’s 50,000 starts a second the last starts about 20 seconds late.

What a job and a run look like

Illustrative exampleNumbers here are illustrative: round figures to reason with, not measurements.

Keep a job apart from its runs. A job holds the schedule, zone, target, payload and next_run_at; a run is one scheduled time of one job, with its own state, tries and result. The pair of job and scheduled time names each run, and the later steps lean on that name.

Keep both in a durable, sharded database, such as Postgres sharded by customer: about 200 GB of jobs and a few thousand new runs a second fit comfortably. Finished runs move to a history table partitioned by day and dropped after 30 days.

The records

Record	Key fields	Why it exists
Job	`id`, customer, schedule, `time_zone`, target, payload, state, `next_run_at`	What to run, and when next
Run	`job_id`, `scheduled_at`, state, tries, worker, times, result	One scheduled time of one job
Run history	`job_id`, `scheduled_at`, day, result	Thirty days of finished runs, kept apart

The life of a run

From	To	Cause	Allowed
pending	running	A worker starts it	Yes
running	succeeded	The task finished and the result is recorded	Yes
running	pending	Its worker was lost; another will try it	Yes
running	failed	Its last try failed	Yes
pending or running	cancelled	The customer cancels it	Yes
succeeded	running	Anything	No: a finished run stays finished

Architecture diagramA job and its runs

Read:Learn: Data model design Learn: Storage choice justification Learn: PostgreSQL

Try it: What a job and a run look likeGuided practice · Job scheduler, Managed scheduler · Senior

Keep reading+1 min

Choosing the store

A sharded relational database gives unique keys and conditional updates, which the next steps use to create each run once. Cassandra or DynamoDB work too, with conditional writes (IF NOT EXISTS, attribute_not_exists) and a table per access path. Either way, keep history out of the live tables: it is the large data, and it is read differently.

Check yourself

The scheduler’s API

From the briefNumbers here are given in the practice brief.

Keep the API small and make a repeated call safe. The customer names the job, so creating it is a PUT that can be sent again after a timeout without making a second job. The schedule carries its time zone, because “9:00” means nothing without one.

The calls customers make

Call	Returns	Notes
`PUT /v1/jobs/{name}`	The job and its next run time	`run_at`, or a cron expression with a time zone; the same PUT again changes nothing
`GET`, `PATCH`, `DELETE /v1/jobs/{name}`	The job	Read, change or delete it
`POST /v1/jobs/{name}:pause`, `:resume`	The job	Runs missed while paused follow the job’s policy
`GET /v1/jobs/{name}/runs?page_token=`	Runs, newest first	Due, start and finish times, tries and result
`POST /v1/jobs/{name}/runs/{scheduled_at}:cancel`	`202`	Stops a run in progress

Read:Learn: API contract design Learn: Idempotency and retries

Try it: The scheduler’s APIGuided practice · Job scheduler, Managed scheduler · Senior

Check yourself

A customer’s create call times out, and their client sends it again. What happens?
Show answerHide answer
With a PUT to a name the customer chose, the second call finds the job already there with the same content and changes nothing. A POST that made a new job each time would leave two jobs, and two runs at every scheduled time.

High-level design

Build the design in three steps: find what is due, create each run once, and get it done. The deep dives then harden what an interviewer pushes on.

Finding what’s due, every second

Illustrative exampleNumbers here are illustrative: round figures to reason with, not measurements.

Reading every job each second to find the few thousand that are due is far too slow, and gets slower with every job; timers held only in a scheduler’s memory vanish when it restarts. Store next_run_at on each job, in UTC, with an index on it. Every second each scheduler reads, from the shards it covers, the jobs due in the next few seconds, in batches: a few thousand rows, however many jobs are stored.

Time buckets work too: a partition per minute and shard in Cassandra or DynamoDB, read one minute at a time and split by shard so the midnight minute isn’t one hot partition. An in-memory timing wheel or Redis sorted set is fine as a speed-up if it is rebuilt from the database after a restart.

A customer creates a job due Tuesday at 14:00:00: it is a row with that next_run_at, and nothing else happens until then.
At 14:00:00 the scheduler’s read of the next few seconds returns it with the others due.
A scheduler restarts at 13:59:30; nothing lived only in memory, so the same read finds the job.

Architecture diagramFinding what is due

Each scheduler reads only the jobs due in the next few seconds, through an index.

Diagram as text

Components: Jobs API (API gateway); Shard A: index on next_run_at (SQL DB); Shard B: index on next_run_at (SQL DB); Scheduler 1 (Service); Scheduler 2 (Service). Connections: Jobs API → Shard A: index on next_run_at (job due Tue 14:00); Jobs API → Shard B: index on next_run_at (other jobs); Scheduler 1 → Shard A: index on next_run_at (due in the next 5 s); Scheduler 2 → Shard B: index on next_run_at (due in the next 5 s).

Read:Learn: Indexes and search fundamentals Learn: Data model design

Try it: Finding what’s due, every secondGuided practice · Job scheduler, Managed scheduler · Senior

Keep reading+1 min

An index or buckets

An index on next_run_at in a sharded relational database is simplest when writes are modest, as here. Buckets suit a wide-column store and very high write rates, but a bucket per minute alone puts the whole midnight minute in one partition, so add a shard number to the key.

Check yourself

Why isn’t a timer per job in the scheduler’s memory enough, even on a big machine?
Show answerHide answer

Several schedulers, one run each

Illustrative exampleNumbers here are illustrative: round figures to reason with, not measurements.

Two schedulers will read the same job as due, and if each reads, sends and then updates, both send it. A lock with an expiry doesn’t fix it: a scheduler paused past the expiry still acts after another one has (Kleppmann (opens in a new tab)).

Make creating the run one conditional write that only the first scheduler can make. The run’s key is (job_id, scheduled_at) with a unique constraint; a scheduler inserts the 14:00 run with ON CONFLICT DO NOTHING (PostgreSQL docs (opens in a new tab)) and moves next_run_at to 15:00 in the same transaction. Only the scheduler whose insert added the row sends the run on, and one that wakes late gets the conflict and does nothing.

Ways to create each run once

Compared on	Unique run key	Compare-and-set on next_run_at	SKIP LOCKED	Fenced owner
How it decides	Insert-if-absent on (job, time)	Update only if next_run_at is still 14:00	Rows one transaction holds are skipped by others	Writes carry a number the store checks
A paused scheduler wakes	Its insert conflicts

From due to done

Illustrative exampleNumbers here are illustrative: round figures to reason with, not measurements.

The scheduler that created a run puts it on a queue, and a worker takes it, but must not remove it or mark it done then: worker machines fail mid-run. With SQS, receiving a message hides it for the visibility timeout, 30 seconds by default; the worker extends that with ChangeMessageVisibility while the task runs and deletes the message only once the task has finished and the result is recorded (AWS docs (opens in a new tab)). If the worker dies, the message reappears and another worker runs it.

Two gaps remain. A scheduler can crash after recording a run and before sending it, so a sweep sends on runs still pending a little after their time. And a long run needs heartbeats, within a maximum duration per job: each extends the message’s hold, up to 12 hours after first receipt (AWS docs (opens in a new tab)), and checks the run’s row, so a recorded cancel reaches the task.

The scheduler records the run, then puts it on the queue.
A worker receives it, extends its hold while the task runs, and deletes it only when the result is recorded.
The worker dies: its hold runs out, and another worker takes the run.
The scheduler died before sending: the sweep finds the run still pending and sends it.

Architecture diagramFrom due to done

Design a distributed job scheduler

The answer in two minutes

Also asked as

What interviewers look for

The decisions that matter

Understanding the problem

Functional requirements

Non-functional requirements

Scale

Out of scope

The numbers that shape the design

The cost of the busiest second

What a job and a run look like

Choosing the store

The scheduler’s API

High-level design

Finding what’s due, every second

An index or buckets

Several schedulers, one run each

From due to done

Sign in with Google to read the rest

Practise this

SKIP LOCKED as a work queue

Why the next run moves when the run is created

The runs table as the queue

The answer in two minutes

Also asked as

What interviewers look for

The decisions that matter

01Understanding the problem

Functional requirements

Non-functional requirements

Scale

Out of scope

02The numbers that shape the design

The cost of the busiest second

03What a job and a run look like

Choosing the store

04The scheduler’s API

05High-level design

Finding what’s due, every second

An index or buckets

Several schedulers, one run each

From due to done

Sign in with Google to read the rest

12Practise this

SKIP LOCKED as a work queue

Why the next run moves when the run is created

The runs table as the queue

Understanding the problem

The numbers that shape the design

What a job and a run look like

The scheduler’s API

High-level design

Practise this