System Design question·Asked atMMetaGGoogleOOpenAI
Job Scheduler
Design a distributed job scheduler - 1,000 jobs running at once, bursts of 200 submissions per second, runtimes from 30 seconds to 2 hours, and a p95 start within 10 seconds of eligibility. The staff-level signal is keeping the job, the run and the lease as three separate facts, treating the database row as the truth and the queue as a hint, and naming for every guarantee the invariant and the one atomic condition that enforces it.
Advanced60 min read
S+
Written by a Staff+ Engineer and an Engineering Manager
12+ years of experience in distributed scheduling and workflow orchestration. Tech lead for job execution platforms processing millions of tasks daily. Over 12 years of industry experience with 6 years in engineering leadership, building and scaling tech infrastructure teams that deliver end-to-end large-scale distributed systems.
You have time for about eight questions. Spend the first ones on the answers that change the architecture: what survives after the API says yes, whether a job may run twice, and how start latency is measured. Recurring schedules and callbacks are quick scope checks, so leave them for the end. The answers below are the ones the interviewer gave in a real staff-level mock, ordered by how much each one moves the design.
Swipe to see all columns
Scope Decisions
Question
Agreed answer
Why it matters
What survives after the API answers 201?
An acknowledged job survives any process crash
Submission must commit to a database before it answers (Phase 1)
Can a job run twice?
Yes. An attempt can repeat after a failure. A successful job still publishes one result
At-least-once execution with one guarded result (DD1, DD8)
How quickly must an eligible job start?
p95 under 10 s from the moment it is eligible, counted while a compatible worker is free and the tenant is within its quota
The trigger path gets a time budget (DD6), and the metric needs an exact definition (DD5)
How many jobs, and how long do they run?
Up to 1,000 running at once, bursts of 200 submissions per second, median 30 s, p95 5 min, a few up to 2 hours
Submissions outrun workers 15 to 1, so a backlog is normal (DD3). Long jobs need leases and checkpoints (DD2, DD8)
One tenant or many?
Many teams share the fleet. One tenant's burst must leave the others able to make progress
Who gets the next free slot is a policy, not arrival order (DD3, DD4)
When can a job be scheduled?
Now, or once at a future time. Recurring schedules are out of scope
A due-time trigger is required (DD6). Cron is an extension (DD9)
Do jobs wait for external callbacks?
No. Out of scope
A run is one continuous execution on one worker
Cancellation?
The user can request cancellation in any state
Cancel races with start and with completion (DD7)
Out of scope (say this out loud): recurring schedules, waits on external callbacks, job dependencies and workflows, autoscaling of the worker fleet, the sandbox a worker runs code in, and exactly-once side effects. Each is a good extension question; none should eat the first ten minutes.
Four FRs, each mapping to a phase in the High Level Design.
FR1 — Submit a job to run now or at a future time
A client calls POST /jobs with a job type, an input, an optional scheduled_at and an idempotency key. The job is stored durably before the API answers. A retry with the same key returns the same job.
FR2 — Run each job once it is eligible
When a job's time arrives, the platform hands it to a free worker, runs it, and retries it after a transient failure. A long job continues from its last checkpoint.
FR3 — Track status and logs, and retrieve the result
The client can read the status of a job, the logs of each attempt, and one final result once the job has succeeded.
FR4 — Request cancellation
The client can ask to cancel a job in any state. A job that has not started never starts. A running job is told to stop.
Tip
The key principle behind all four FRs
Swipe to see all columns
Four facts and the conclusions they do not supportRead each row as: the fact on the left does not, by itself, imply the claim in the middle.
Fact
Does not imply
Why the gap exists
The API returned 201
The job is in a queue
201 means a row is committed in the database. The queue hears about the job later, through the outbox.
NFR1 — Scale. Up to 1,000 jobs running at once, bursts of 200 submissions per second, runtimes from 30 seconds to 2 hours.
NFR2 — Start latency. p95 under 10 seconds from the moment a job is eligible to the moment it starts, counted while a compatible worker is free and the tenant is within its quota. Waiting for capacity is a different number, tracked per tenant.
NFR3 — Durability and correctness. A job that was acknowledged survives any process crash. Execution is at least once: an attempt can repeat. A successful job has one canonical result, and a late or stale worker can never replace it.
NFR4 — Availability and recovery. 99.9% for submission and status. Transient failures are retried, a long job resumes from its last checkpoint, and recovery still works after every worker and every dispatcher process has restarted.
NFR5 — Fairness between tenants. One tenant's burst leaves the other tenants able to make progress, and shares are measured in worker time, not in job count.
Bursts of 200 per second. Each one is a single insert of about 1 KB: easy for one PostgreSQL primary
Worker slots
1,000. One slot runs one job
Mean runtime (assumption)
About 75 s: a median of 30 s with a long tail up to 2 hours
Drain rate
1,000 slots / 75 s ≈ 13 jobs per second, about 1.1 million jobs per day with a full fleet
A one-minute burst
200 × 60 = 12,000 jobs. At 13 jobs per second they take about 15 minutes to drain
The number that identifies the real system is not 200 writes per second. It is the gap between what comes in and what goes out:
Code
submissions during a burst 200 jobs / s
completions with a full fleet 13 jobs / s (1,000 slots / 75 s mean runtime)
Submissions can arrive fifteen times faster than workers finish. A backlog is the normal state, not an incident. Two questions follow from that, and they shape most of the design: who gets the next free slot, and how do we tell a job that waits for a good reason from a job that is stuck. Every number above is an illustrative assumption, to be replaced by the measured runtime distribution of the real workload.
Interviewer signal: candidates who size the database for 200 writes per second have done arithmetic. Candidates who notice that 200 in and 13 out makes a queue unavoidable, and then define start latency so that it excludes waiting for capacity and quota, have found the system.
These nine questions give the rest of the design its purpose. Raise them before drawing the final architecture — every component below exists because one of them forces it.
[DD1] Worker failover and stale results: worker A's lease expires, worker B claims the job, then A returns and reports success. What does the system do, and what does the client see?
[DD2] Claimed, acknowledged, then crashed: the claim is committed, the queue message is acknowledged, and the worker dies before it starts. What brings the job back?
[DD3] Multi-tenant fairness: team A has 50,000 jobs waiting and team B submits 10. Whose job gets the next free worker?
[DD4] Unequal job durations: A's jobs take 30 minutes and B's take 30 seconds. Is alternating job starts fair? What do you share instead?
[DD5] Observability: name one way the scheduler fails its users while the submission API looks healthy, and the metric that catches it first.
[DD6] The due-time trigger: 12,000 jobs become due in the same second. How are they found and promoted inside the 10-second budget, with more than one scheduler running?
[DD7] Cancellation races: cancel arrives while the job sits in the queue, or in the same moment the worker reports success. What is the final state?
[DD8] Retries and checkpoints: a 2-hour job loses its worker at minute 110, and another job fails on every attempt. How do you retry without wasting hours or looping forever?
[DD9] Recurring schedules (extension): the interviewer puts "every day at 09:00" back in scope. How do you add it without changing how a job runs?
A job is a promise the platform made when it answered 201. Promises live in PostgreSQL. The ready queue only says "there is probably work for you": a message can be lost, delayed or delivered twice. So no decision is ever taken from a message alone. A worker that receives a message must still win a conditional update on the job row before it may run anything.
2. Job, run and lease: three objects, three lifetimes#
A Job is what the client asked for. It keeps its identity and its final result for as long as the client cares. A JobRun is one attempt to execute it. A retry creates a new run and the old one stays as history. A Lease says which run may finish the job right now, and it expires on its own. Putting all three in one row is the root of most wrong answers: a retry overwrites the history, and a stale worker cannot be told apart from the current one.
The platform cannot know whether a silent worker is dead or only slow. To make progress it must be willing to start a second attempt, so two workers can run the same job at the same time. That is accepted. What is not accepted is two results. Only the run that still holds the lease can commit the outcome, and that check happens inside the same database transaction that writes it.
Tip
The core recognition
This is a small, strongly consistent state machine in PostgreSQL, wrapped in an unreliable delivery pipeline and a shared worker fleet. Everything interesting lives at the hand-offs: where a due job becomes a queue message, where a message becomes a claim, where a claim changes owner, and where a result is published.
Design Decisions
Design choice
Reason
Commit the Job row before replying 201, with a unique index on (tenant_id, idempotency_key)
An acknowledged job survives any crash, and a client retry returns the same job
Job (the request) + JobRun (one attempt) + Lease (who may finish it now)
Five entities carry the whole design. Spend your explanation on Job, JobRun and Lease — keeping them apart is the architectural point. The outbox and the tenant settings are supporting rows.
Job
What the client asked for, and the one place its final result is recorded.
Swipe to see all columns
Job
Field
Type
Comment
job_id
STRING
Primary key. It never changes, however many attempts the job needs
tenant_id, creator_id
STRING
Who owns the job. The tenant comes from the login token
JobRun
One attempt to execute a job. Also called an attempt. Runs are never deleted or reused.
Swipe to see all columns
JobRun
Field
Type
Comment
run_id
STRING
Primary key, for example job_a_run_1
job_id, attempt
STRING, INT
Lease
The right of one run to finish one job, for a limited time. A lease row exists only while a run owns the job.
Swipe to see all columns
Lease
Field
Type
Comment
job_id
STRING
Primary key: a job has at most one lease at a time
run_id
STRING
The run that holds the lease
fencing_token
OutboxEvent
An instruction to publish a message, stored next to the state change it announces.
Swipe to see all columns
OutboxEvent
Field
Type
Comment
event_id
STRING
Primary key, for example ev-1
type, payload
STRING, JSON
Tenant
The settings that decide how a shared fleet is divided.
Swipe to see all columns
Tenant
Field
Type
Comment
tenant_id
STRING
Primary key. Every user belongs to one tenant
share
INT
The tenant's configured weight in the fleet. It is set by the platform, never derived from how much the tenant submits (DD3)
Two state machines and one rule:
Code
Job PENDING -> READY -> RUNNING -> SUCCEEDED | FAILED
RUNNING -> READY (lease expired, attempts left, no wait needed)
RUNNING -> PENDING (the attempt failed, eligible again after a wait)
PENDING | READY -> CANCELLED
RUNNING -> CANCELLING -> CANCELLED
JobRun CLAIMED -> RUNNING -> SUCCEEDED | FAILED | TIMED_OUT | CANCELLED
CLAIMED -> TIMED_OUT (claimed, never started)
Lease exists only while one run owns the job; deleted when that run ends or expires
Every arrow above is a conditional update that names the state it expects. There is no unconditional write to a status, and no path to SUCCEEDED that does not pass the lease check. PENDING simply means "waiting for its eligible time", for a first run or for a retry; attempt tells which.
Storage split
Swipe to see all columns
Storage
Store
Data
Consistency
PostgreSQL
jobs, job_runs, leases, outbox, tenants
Strong, transactional. Every guarantee in this design is a condition on one of these rows
Job ready queue
One message per ready job, in one logical queue per tenant and worker pool
At least once. It can be rebuilt from the READY rows in PostgreSQL at any time
Every call carries a bearer token, and the tenant is taken from that token, never from a body field.
Swipe to see all columns
Public API
Endpoint
Request
Response
POST /jobs
Idempotency-Key header plus the job (contract below)
201 with the job id after the row is committed, or 409 when the key was used for a different job
GET /jobs/{job_id}
No body
Status, attempt number, last error, and result_ref once the job has succeeded
Swipe to see all columns
POST /jobs, the call that creates a promiseRequest parts on top, the responses below.
Part
Value
Meaning
Authorization header
Bearer token
tenant_id and creator_id are taken from the token
Idempotency-Key header
k1 (required)
The same tenant, key and payload always return the same job
Submission is synchronous up to the commit and nothing more. Everything after it, from promotion to the result, happens in the background, and the client observes it through the status call.
Internal (workers and events)
Swipe to see all columns
Worker to dispatcher
Call
Arguments
Returns
POST /workers/{worker_id}/pull
pool, free slots. A long poll
A job to run with its run_id, fencing_token, input and last checkpoint, or nothing
POST /runs/{run_id}/heartbeat
fencing_token
Swipe to see all columns
Event on the ready queue
Event
Payload
Producer to consumer
JobReady
event_id, job_id, tenant_id, pool
Outbox relay to the dispatcher. It carries no state: the dispatcher reads the truth from PostgreSQL when it claims
Workers never talk to PostgreSQL or to the queue. They talk to the dispatcher, and the dispatcher writes on their behalf. That keeps every guarded write in one place.
Present the design as four short stories, each drawn in its own colour on one whiteboard: Phase 1 submit (black), Phase 2 promote (blue), Phase 3 claim and run (green), Phase 4 status and result (purple). Every story has four to six numbered steps. The number on an arrow in the picture is the same number in the animation and in the step table below it, so you can always find your place.
Swipe to see all columns
The four phases
Phase
Colour
Story
What it leaves behind
Phase 1: Submit (FR1)
Black
The client submits job_a to run in one hour
Job job_a is PENDING in PostgreSQL
Phase 2: Promote (FR2)
Blue
The hour passes and the due job goes to the ready queue
job_a is READY, event ev-1 is published
Figure 1High Level Design: four phases, one colour each, every arrow numbered within its phase
How to read the picture
One colour is one phase. A component is drawn in the colour of the phase that first needs it. Later phases reuse it. The job service is black because Phase 1 introduces it, and Phase 4 calls it again.
The numbers are the order of steps inside one phase. Black 1 to 4 is the submission, blue 1 to 5 is the promotion, green 1 to 6 is the run, purple 1 to 5 is reading the outcome.
PostgreSQL is the only source of truth. The scheduler, the relay and the dispatcher keep no state of their own that matters. Each can crash and restart at any step, and the rows tell it where to continue.
The text blocks are the rows. They show example values. A value written by a later phase is drawn in that phase's colour: READY is blue because Phase 2 writes it, and SUCCEEDED is green because Phase 3 writes it.
Each phase below is an interactive walkthrough of the same picture. It plays on its own, and you can pause it, step with the arrow keys, and click any component to read its role. Under the drawing, API call shows the request of the step, and Data change shows the rows it writes.
Cancellation is not a fifth phase. It is a small detour through the same components, and it is covered at the end of this section.
A message is in the ready queue
The job should run
The message can be a duplicate, and the job can be cancelled by now. The claim on the database row decides.
A worker is running the job
That worker may finish it
Its lease can expire and another run can own the job. Only the commit of the lease holder counts.
The API is green and workers report no errors
Jobs start on time
A stopped scheduler produces no error at all. Only the age of the oldest due job shows it.
Most of the design exists to keep those four distinctions honest.
Heartbeats
1,000 running jobs / 10 s = 100 lease renewals per second
Lease table
At most 1,000 rows, one per job that is claimed right now
Job rows
1.1 million per day × ~1 KB ≈ 1 GB per day. Partition by month and archive old partitions
Start budget
1 s scheduler tick + 1 s relay + 1 s claim + 3 s for the worker to start the job = 6 s of the 10 s
Retries keep their history, and ownership is one authoritative row
The scheduler marks a due job READY and inserts an outbox row in one transaction; a relay publishes it
A job can never be READY without a durable instruction to dispatch it
A queue message is a hint; the claim is a conditional update on the Job row
A lost, duplicate or late message cannot start a job twice, or start a cancelled job
Claim = Job RUNNING + new JobRun + Lease, in one transaction
A run and its lease always appear together
Heartbeats renew the lease row in PostgreSQL; an expired lease is the only trigger for takeover
Recovery works even when every worker and every dispatcher has restarted
Completion deletes the lease under a guard (run, token, expiry) in the same transaction that writes SUCCEEDED
A stale worker can never publish a result
Every run writes under its own immutable prefix; result_ref points at the winner
A stale upload cannot overwrite the winner's bytes
One ready queue per tenant and pool; the dispatcher serves tenants by their share of slot time
One tenant's backlog cannot starve the others, and long jobs pay for what they hold
First alert: the age of the oldest due job that has not started
It is the only signal that can see a job that never started
job_type, input_ref
STRING
What to run and where its input is
idempotency_key, payload_hash
STRING
Unique per tenant. The same key with a different payload is a 409
scheduled_at
TIMESTAMP
The time the client asked for. Left out means run now
eligible_at
TIMESTAMP
When the job may next be handed to a worker: the scheduled time at first, a later time after a failed attempt. Start latency is measured from here