Design Job scheduler
Design a distributed job scheduler in a 45-minute interview: storing schedules, finding due jobs, leases and fencing, at-least-once runs with idempotent jobs, retries, cron and fairness.
On this page
How to use this page
This page follows the order of a real system design interview. At each step there is a Your turn box: write your own answer first, then open ours and compare. A scheduler sounds like "cron on more machines", but the interview is about time and failure: finding what is due without scanning everything, and making sure a run happens even when the machine responsible for it dies, without it happening twice in a harmful way.
| Phase | Time in a 45-min interview | What you produce |
|---|---|---|
| 1. Clarify requirements | 5 min | One-off and recurring jobs, timing target, what "once" means |
| 2. Estimate | 5 min | Starts/s on average and in the :00 burst, workers needed |
| 3. API | 3 min | Create, pause, cancel, run now, and the worker's poll/ack |
| 4. Data model | 5 min | Jobs, due index, runs, ready queue, leases |
| 5. High-level design | 10 min | Schedule, come due, run: three flows traced |
| 6. Deep dives | 10–15 min | Due index, leases and fencing, worker failure, idempotency, overlap, the burst |
| 7. Wrap up | 2–3 min | Bottlenecks, failures, what you would monitor |
Teams register jobs to run once at a set time or on a schedule (cron). Jobs must start close to their time, run on a pool of workers, retry on failure, and never run twice at the same time. Users can see job history and status. Skip the job code itself, multi-step workflow DAGs, and a UI beyond basic status.
1. Clarify the requirements
The interviewer says: "Design a distributed cron." Write the questions you would ask, the functional and non-functional requirements with targets, and what you would leave out.
Compare with our answer
The questions that matter most: How many jobs, and how often do they run? How close to the scheduled time must a run start? What happens if a run is missed because we were down: run it late, or skip it? May two runs of the same job overlap? Does the scheduler run the code, or just trigger it? Do we need workflows (B after A)?
A strong answer mentions: one-off and cron jobs · a start-time target in seconds · retries with a limit · no overlapping runs · history and cancel · "at-least-once with idempotent jobs" stated as the honest guarantee · DAG workflows out of scope.
Functional: what it must do
- Schedule a job: One-off at a time, or recurring (cron)
- Run on a worker pool: Any free worker can run any job
- Retries: With backoff, up to a limit
- No overlapping runs: A job never runs twice at the same time
- Status and history: Last runs, durations, errors
- Cancel / pause jobs
Out of scope
The job code itselfMulti-step workflows (DAGs)A rich UI
Non-functional: how well it must work
| Quality | Target | Why |
|---|---|---|
| Timeliness | Start within ~5 s of the scheduled time | |
| Reliability | No job silently skipped | Missed invoices cost money |
| Effectively once | Retries must not double-charge or double-send | Jobs must be idempotent |
| Availability | Survive any single machine or zone failure | |
| Scale | 10 M schedules; ~500 K job starts in the first minute of each hour | Everyone picks :00 |
A cron expression is the classic five-field schedule: minute, hour, day of month, month, day of week. 0 9 * * 1-5 means "09:00 on weekdays". The scheduler never stores a list of future runs; it stores the expression and computes the next run time each time one fires.
2. Back-of-the-envelope estimates
Assume 10 M jobs running on average 4 times a day, 30% of them scheduled exactly on the hour, an average run of 30 s, and 20 concurrent runs per worker. Work out average starts per second, starts in the :00 minute, and workers needed during that minute.
Compare with our answer
- Runs: 10 M × 4 = 40 M a day ÷ 86,400 ≈ 460 starts/s on average.
- Per hour: 40 M ÷ 24 ≈ 1.7 M. 30% of them at :00 = 500 K in one minute, ≈ 8,300/s, 18× the average.
- Workers: by Little's law (jobs in progress = arrival rate × duration), 8,300/s × 30 s ≈ 250 K runs in flight, ÷ 20 per worker ≈ 12,500 workers at the burst, against ~700 on average.
A strong answer mentions: the average · the round-number burst as the real target · Little's law for concurrency · the gap between peak and average, which is why smoothing and autoscaling matter.
Assumptions: scheduled jobs 10 M; runs per job per day 4; share starting at the top of the hour (%) 30; average run time (seconds) 30; concurrent jobs per worker 20.
| Number | Estimate | Why it matters |
|---|---|---|
| Runs per day | 40 M | |
| Job starts per second (avg) | 463 / s | ≈ 460/s on average. |
| Starts in the :00 minute | 500 K | ≈ 500 K in one minute (~8 K/s): the real design target. |
| Workers needed at the burst | 12.5 K | Little’s law: concurrency = arrival rate × duration. |
- Load is spiky: everyone schedules at :00. Add jitter where exact timing isn’t needed.
- Concurrency = rate × duration (Little’s law) sizes the worker pool.
The numbers say: the scheduler's own work is small; the burst is the problem. Moving 8,300 runs a second from an index onto a queue is easy for a few partitions. Running them needs an order of magnitude more workers for one minute an hour, which is why the deep dives include spreading the burst.
3. API
What do teams call to manage jobs, and what does a worker call to take, extend and finish a run?
Compare with our answer
A strong answer mentions: create with a cron expression or run time, a time zone, timeout and retry limit · pause, cancel and run-now · get status and recent runs · a worker poll that returns a run with a lease deadline · heartbeat to extend it · ack on success, nack on failure.
| Call | Request | Response | Notes |
|---|---|---|---|
POST /v1/jobs | { name, schedule: "0 9 * * *" | runAt, payload, timeout, maxRetries, idempotencyKey } | 201 { jobId, nextRunAt } | |
GET /v1/jobs/{id} | – | { schedule, status, nextRunAt, lastRuns[] } | |
POST /v1/jobs/{id}/pause | – | 204 | Also DELETE to cancel |
POST /v1/jobs/{id}/run-now | – | 202 { runId } | Manual trigger |
(worker) lease = poll(queue) | – | { runId, payload, leaseUntil } | Worker heartbeats extend the lease; ack on completion |
Two fields deserve a sentence each. The time zone belongs to the job: "09:00 every day" means 09:00 in Berlin for a Berlin team, which moves relative to UTC twice a year. And idempotencyKey on create stops a team's deploy script from registering the same job twice when it retries.
4. Data model
What is the schedule (the definition), what is the next run, and what is a run? Which store answers "what is due right now?" cheaply?
Compare with our answer
A strong answer mentions: jobs (definitions) in a relational database · a separate due index keyed by time bucket and partition · a runs table for history, one row per attempt · a queue for runs that are ready · lease records with epochs in a coordination service.
jobs Relational (PostgreSQL / Spanner)
job_id, owner, schedule (cron) | run_atpayload, timeout, max_retriespaused, created_at
Definitions and schedules: transactional, modest size.
due index Time-bucketed table or sorted set, partitioned
bucket (minute), partitionnext_run_at, job_id
“Which runs are due in the next minute?” must be a cheap range query, split across partitions.
runs Wide-column / SQL (by job_id, time)
run_id, job_id, scheduled_forstatus: queued | running | succeeded | failedattempt, worker_id, started_at, ended_at, error
History of every attempt; append-heavy.
ready queue Distributed queue (SQS / Kafka)
run_id, job_id, payload, attempt
Hands due runs to workers with visibility timeouts and retries.
leases Coordination service (etcd / ZooKeeper) or DB rows
partition → owner, lease_until, epoch
Which scheduler instance owns which partition; fencing tokens stop stale owners.
The key separation is between the definition (what and when, rarely changes), the next occurrence (one row per job in the due index, rewritten each time it fires), and the run (one row per attempt, append-only). Keeping them apart means the hot query ("what is due this minute in partition 7?") touches a small, time-ordered table, never the full jobs table.
A lease is a lock with an expiry: "scheduler A owns partitions 0–31 until 09:00:15". The owner must renew it before it expires; if it dies, the lease lapses and another instance can take over. An epoch (or fencing token) is a number that increases every time ownership changes, so writes from a previous owner can be recognised and rejected.
5. High-level design
Sketch the path from "register a job" to "a worker runs it", with several scheduler instances for availability. How do they avoid all firing the same job?
Compare with our answer
Compare with the figure. The pieces people most often forget: the due index as its own structure, partitioned ownership of it between schedulers, and the ready queue between schedulers and workers, so that a slow job never delays the scheduler's clock.
The architecture, then a job registered into the due index
- The architecture: an API stores job definitions and puts each next run into a time-bucketed due index. Several scheduler instances each own some partitions of that index through leases, and move due runs to a ready queue. A pool of workers pulls from the queue, records history, and failures retry or end in a dead-letter queue.
- Registering a job stores its definition and computes its next run time, which is written into a time-bucketed due index. Nothing runs yet; the job just waits in the right minute’s bucket.
| Component | What it does |
|---|---|
| Scheduler API | Create, pause, cancel, run-now; computes next run times |
| Jobs DB | Job definitions |
| Due index | Runs bucketed by minute and partition |
| Scheduler instances | Each owns partitions via leases; enqueue due runs |
| Leases (etcd) | Partition ownership with epochs (fencing tokens) |
| Ready queue | Visibility timeouts, retries, dead letters |
| Worker pool | Executes jobs; heartbeats; idempotent |
| Run history | Every attempt for status and debugging |
Trace a recurring job:
- A team registers
send reminders, 0 9 * * *, Europe/Berlin. The API saves the definition and computes the next run, 09:00 tomorrow Berlin time, stored as a UTC instant in the due index under that minute's bucket and the job's partition (hash(job_id) mod P). - At 09:00, the scheduler that holds the lease for that partition reads the bucket, enqueues the run keyed by
(job_id, 09:00), records it in run history, and writes the next occurrence back into the due index. - A worker takes the run from the queue with a visibility timeout, heartbeats while it works, records success, and acknowledges.
6. Deep dives
Two or three sentences each: how does a scheduler find due runs among 10 M jobs? How do three scheduler instances avoid enqueueing the same run? What happens when a worker dies mid-run, or only pauses? How do you stop two runs of the same job overlapping?
Compare with our answer
A strong answer mentions:
- A time-ordered due index split into partitions, read one bucket at a time, not a table scan.
- Partition leases with epochs (fencing tokens), and de-duplication by (job id, scheduled time) as a safety net.
- Visibility timeouts, heartbeats, retries with backoff, a dead-letter queue, and idempotent jobs.
- A per-job run lock and an explicit overlap policy (skip, queue or replace).
Finding due jobs without scanning everything
Next runs filed in minute buckets, split into partitions
- Deep dive: finding due jobs. Next runs are filed in minute buckets, split into partitions, so each tick reads only what’s due now.
| Option | How | Good at | Catch |
|---|---|---|---|
| Scan the jobs table every second | WHERE next_run_at <= now() with no index | Simplest | 10 M rows a second to find a few hundred |
SQL index on next_run_at | SELECT … ORDER BY next_run_at LIMIT 1000 FOR UPDATE SKIP LOCKED | Real and good up to thousands of starts/s on one primary | One primary's write rate caps the whole system |
| Redis sorted set by timestamp | ZRANGEBYSCORE due -inf now LIMIT 0 1000, then remove atomically (a Lua script) | Fast, simple | Asynchronous replication can lose recent entries on failover; must be rebuildable |
| Time buckets × partitions (chosen) | Key (minute, partition); each tick reads the current bucket of its own partitions | Scales by adding partitions; reads are small range queries | More moving parts; bucket granularity limits precision |
SKIP LOCKED (Postgres, MySQL 8) makes concurrent pollers skip rows another transaction has locked, so several instances can share one table without blocking. It's a perfectly good answer for a company-sized scheduler; say so, then explain that at 8,300 starts/s you want the load split across partitions.
Inside a scheduler instance, the next few minutes of its partitions can be loaded into an in-memory priority queue (a heap ordered by time) or a timing wheel (an array of slots, one per second, that a pointer sweeps around), so firing is precise to the second without polling the database every second. The database stays the source of truth; the in-memory copy is rebuilt on restart.
Several schedulers: leases and fencing tokens
Schedulers own partitions through leases, and a dead one's lease expires
- Several schedulers share the work by owning partitions through leases. If one dies, its lease expires and another takes over.
Running one scheduler is a single point of failure; running three that all read everything fires every job three times. So the due index is split into, say, 256 partitions, and each partition is owned by exactly one instance through a lease in etcd or ZooKeeper (coordination services that keep a small amount of data consistent across machines using consensus). When an instance dies, its leases expire within seconds (a 10–15 s lease renewed every few seconds), and the others pick up its partitions, starting with any buckets it hadn't finished.
A lease alone isn't safe. An instance can pause (a long garbage collection, a VM migration) past its lease expiry, wake up, and still believe it owns the partition. A fencing token fixes that: every lease grant has a higher epoch, and the instance includes it in its writes (UPDATE due SET fired = true WHERE … AND epoch <= :mine, or by checking the epoch stored with the partition). The store rejects writes carrying an older epoch, so the stale instance can do no harm.
A worker dies or freezes mid-run
A worker's lease expires, and a fencing token rejects the frozen worker's late write
The ready queue hands a run to one worker and hides it for a visibility timeout (say 60 s). The worker sends heartbeats to extend it while a long job runs, then acknowledges. If the worker crashes, the heartbeats stop, the timeout expires, and the run becomes visible to another worker. After a few failures with exponential backoff and jitter (1 min, 2 min, 4 min, each randomised a little so retries don't arrive together), the run goes to a dead-letter queue (a holding queue for messages that keep failing) and the owning team is alerted. See message queues.
The figure shows the trap: "the timeout expired" doesn't prove the first worker is dead. It may resume and finish its side effect after the second worker did. A fencing token helps only where the resource can check it, such as a database row. An email provider or a payment API can't, so the job itself must be idempotent.
Idempotent jobs: effectively once
No queue can guarantee exactly-once execution across crashes, because the acknowledgement can always be lost after the work is done. The honest contract:
- The scheduler guarantees at-least-once, and gives every run a stable key:
job_id + scheduled_time. Retries of that run keep the key. - The job checks the key before its side effect:
INSERT INTO sent_reminders (run_key) …fails on a duplicate, or the key is passed as an idempotency key to the email or payment API.
At-least-once plus idempotent effects gives effectively once. The general pattern is in duplicates and idempotency, and the worker side of it in long-running and background jobs.
No overlapping runs, and missed runs
An hourly report that sometimes takes 70 minutes would start the next run while the last is still going. Pick an overlap policy per job, as Kubernetes CronJobs do with concurrencyPolicy:
| Policy | Behaviour | Use when |
|---|---|---|
| Allow | Runs may overlap | Independent, idempotent runs |
| Forbid (skip) | Skip the new run while one is active | Reports, syncs: the next run catches up |
| Replace | Cancel the old run, start the new one | Only the latest result matters |
Enforce it with a per-job run lock: a lease keyed by job_id, taken by the worker at start and released at the end (with a TTL so a dead worker's lock expires).
A catch-up policy decides what happens after an outage: if the scheduler was down from 09:00 to 09:20, does the 09:00 run fire late, and do the 09:05, 09:10 and 09:15 runs of a 5-minute job all fire? Common answer: fire each missed run once if it's within a per-job deadline (Kubernetes calls it startingDeadlineSeconds), otherwise record it as missed and alert. Never silently skip.
Time zones and daylight saving
Store schedules with an IANA time zone (Europe/Berlin), compute the next occurrence in that zone, and store the result as a UTC instant. Daylight saving creates two awkward cases: in spring, 02:30 doesn't exist on the change day; in autumn, 02:30 happens twice. Classic cron implementations differ (some run a skipped-hour job right after the change, and avoid running a repeated-hour job twice), so define the behaviour explicitly, document it, and test it. Jobs that must run at a fixed interval regardless of local time ("every 6 hours") should be scheduled in UTC.
The :00 stampede and fairness
Half a million runs due at exactly 09:00 is the design's real peak. Ways to flatten it:
- Pre-enqueue: move runs to the queue a minute early with a delivery delay (SQS supports delays up to 15 minutes), so the queue, not the scheduler, absorbs the burst.
- Jitter for jobs that don't need exact timing: offer
H 9 * * *style schedules (Jenkins's "hash" syntax) that pick a stable random minute per job. - Predictive autoscaling: the due index already says how many runs are due at 09:00, so start workers at 08:55.
- Priorities: an invoice reminder at 09:00 matters more than a cache warm-up; separate queues or priority classes keep urgent jobs on time.
Fairness is the same problem across teams: one team that registers a million jobs for 09:00 shouldn't delay everyone else. Give each tenant a quota of concurrent runs and pull from per-tenant queues in weighted round-robin, so a noisy tenant's backlog grows without starving others.
7. Bottlenecks, failures and monitoring
Scaling bottlenecks
| Bottleneck | Fix |
|---|---|
| Many schedules | Partition the due index; add scheduler instances and partitions |
| Top-of-hour bursts | Pre-enqueue + jitter + autoscaling workers |
| Long-running jobs | Heartbeats; separate pools by job class |
| Run history volume | TTL old runs; aggregate stats |
When things fail
| Failure | What happens |
|---|---|
| Scheduler instance dies | Its leases expire; others take over its partitions within seconds |
| Network partition: old leader still thinks it owns a partition | Fencing token (epoch) makes its writes fail |
| Worker crash | Visibility timeout → retry |
| Job keeps failing | Backoff, then dead-letter queue + alert to the owning team |
What to monitor
Schedule lag (actual start − scheduled time)Queue depthRun success / failure rateRetries and dead lettersLease changesWorker utilisation
8. Follow-up questions
Answer in order. 1) A scheduler instance pauses for 40 s (garbage collection) while holding partitions 0–31. What happens, and what could go wrong? 2) A job "charge every subscriber on the 1st" retries after a worker crash. How do you avoid double charges? 3) The company wants workflows: job B starts when job A succeeds. What would you add?
Compare with our answer
A strong answer mentions:
- Its leases expire; another instance takes over and fires due runs; when the paused instance wakes it may try to fire the same runs, but its old epoch is rejected (fencing), and run de-duplication by (job id, scheduled time) catches anything that slips through.
- The run key (job id + scheduled time) passed down as an idempotency key per subscriber charge (for example
run_key + subscriber_id), so a retry skips charges that already succeeded; process in resumable batches with checkpoints rather than one giant run. - A workflow layer that records dependencies and enqueues B when A's success is recorded, with state per workflow run; or adopt an engine such as Airflow or Temporal instead of growing the scheduler into one.
How would you support workflows (job B after job A)?
Add a DAG engine: runs record dependencies; completion of A enqueues B (see Airflow, Temporal).
How do you handle time zones and daylight saving?
Store schedules with a time zone; compute next run in that zone; define behaviour for skipped/repeated hours.
How do you guarantee fairness between teams?
Per-tenant quotas and separate queues so one team’s 1 M jobs don’t starve others.
- Numbers: 10 M jobs × 4 runs = 40 M/day ≈ 460 starts/s; 500 K at :00 (~8,300/s); Little's law → ~250 K in flight, ~12,500 workers at the burst.
- Store: definition (jobs), next occurrence (due index), attempts (runs). Compute the next occurrence on each fire.
- Due index: time bucket × partition; SQL
FOR UPDATE SKIP LOCKEDis fine at smaller scale; in-memory heap or timing wheel for precision. - Enqueue before marking fired: duplicates over losses; run id = (job id, scheduled time).
- Schedulers: partitions owned via leases in etcd/ZooKeeper; fencing tokens reject stale owners.
- Workers: visibility timeout + heartbeats; retries with exponential backoff and jitter; dead-letter queue + alert.
- Effectively once = at-least-once + idempotent jobs using the run key.
- Policies: overlap (allow, forbid, replace) with a per-job run lock; catch-up deadline for missed runs; time zones with defined DST behaviour.
- Burst and fairness: pre-enqueue with delay, jitter, predictive autoscaling, priorities, per-tenant quotas.
1. A scheduler fires a run by first marking the job's occurrence as fired in the database and then putting the run on the queue. It crashes between the two steps. What happens?
Marking first turns a crash into a silent skip. Enqueue first and accept an occasional duplicate, made harmless by the run key.
2. Three scheduler instances read the same due index for availability. What stops them all firing every job?
Partitioned leases spread the work and give each partition one owner; the epoch (fencing token) stops a stale owner, and run de-duplication is the safety net.
3. A worker takes a run, then freezes for 90 s in garbage collection. The visibility timeout is 60 s. What must the design assume?
When the timeout expires the run reappears and another worker takes it; the frozen worker may then finish too. Only idempotency or fencing at the resource makes that safe.
4. An hourly report sometimes takes 75 minutes, and two runs overlapping corrupt its output table. What is the right fix?
An explicit overlap policy with a per-job lock handles any run length. The other changes only reduce the chance of overlap or slow everything down.
5. At 09:00, 500 K runs become due in one minute, against an average of 460 starts a second. Which change helps most without delaying time-critical jobs?
The due index tells you the burst in advance, so start workers early and let the queue release runs on time. Jitter only for jobs that permit it.
6. A team asks the scheduler to guarantee their "charge subscribers" job runs exactly once. What do you tell them?
An ack can be lost after the work is done, so duplicates are always possible. A stable run key passed to the payment API makes a retry skip charges already made.
7. Your scheduler stores due runs in one Postgres table and several pollers run SELECT … WHERE next_run_at <= now() ORDER BY next_run_at LIMIT 100 FOR UPDATE SKIP LOCKED. When does this design stop being enough?
SKIP LOCKED works well for concurrent pollers, but every fire is a write on one primary. At ~8,300 starts a second you partition the due index across stores.
Score 60% or more and the lesson is marked complete.