Infrastructure · Design 32

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.

AdvancedInterview priority: Medium55 min
On this page
  1. How to use this page
  2. 1. Clarify the requirements
  3. 2. Back-of-the-envelope estimates
  4. 3. API
  5. 4. Data model
  6. 5. High-level design
  7. 6. Deep dives
  8. 7. Bottlenecks, failures and monitoring
  9. 8. Follow-up questions
  10. Quiz

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.

PhaseTime in a 45-min interviewWhat you produce
1. Clarify requirements5 minOne-off and recurring jobs, timing target, what "once" means
2. Estimate5 minStarts/s on average and in the :00 burst, workers needed
3. API3 minCreate, pause, cancel, run now, and the worker's poll/ack
4. Data model5 minJobs, due index, runs, ready queue, leases
5. High-level design10 minSchedule, come due, run: three flows traced
6. Deep dives10–15 minDue index, leases and fencing, worker failure, idempotency, overlap, the burst
7. Wrap up2–3 minBottlenecks, 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

Your turn: scope it

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

QualityTargetWhy
TimelinessStart within ~5 s of the scheduled time
ReliabilityNo job silently skippedMissed invoices cost money
Effectively onceRetries must not double-charge or double-sendJobs must be idempotent
AvailabilitySurvive any single machine or zone failure
Scale10 M schedules; ~500 K job starts in the first minute of each hourEveryone 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

Your turn: the numbers

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.

NumberEstimateWhy it matters
Runs per day40 M
Job starts per second (avg)463 / s≈ 460/s on average.
Starts in the :00 minute500 K≈ 500 K in one minute (~8 K/s): the real design target.
Workers needed at the burst12.5 KLittle’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

Your turn: the 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.

CallRequestResponseNotes
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–204Also 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

Your turn: the stores

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_at
  • payload, timeout, max_retries
  • paused, created_at

Definitions and schedules: transactional, modest size.

due index Time-bucketed table or sorted set, partitioned

  • bucket (minute), partition
  • next_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_for
  • status: queued | running | succeeded | failed
  • attempt, 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

Your turn: draw it

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

  1. 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.
  2. 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.
ComponentWhat it does
Scheduler APICreate, pause, cancel, run-now; computes next run times
Jobs DBJob definitions
Due indexRuns bucketed by minute and partition
Scheduler instancesEach owns partitions via leases; enqueue due runs
Leases (etcd)Partition ownership with epochs (fencing tokens)
Ready queueVisibility timeouts, retries, dead letters
Worker poolExecutes jobs; heartbeats; idempotent
Run historyEvery attempt for status and debugging

Trace a recurring job:

  1. 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).
  2. 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.
  3. A worker takes the run from the queue with a visibility timeout, heartbeats while it works, records success, and acknowledges.

6. Deep dives

Your turn: the hard parts

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

  1. Deep dive: finding due jobs. Next runs are filed in minute buckets, split into partitions, so each tick reads only what’s due now.
OptionHowGood atCatch
Scan the jobs table every secondWHERE next_run_at <= now() with no indexSimplest10 M rows a second to find a few hundred
SQL index on next_run_atSELECT … ORDER BY next_run_at LIMIT 1000 FOR UPDATE SKIP LOCKEDReal and good up to thousands of starts/s on one primaryOne primary's write rate caps the whole system
Redis sorted set by timestampZRANGEBYSCORE due -inf now LIMIT 0 1000, then remove atomically (a Lua script)Fast, simpleAsynchronous 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 partitionsScales by adding partitions; reads are small range queriesMore 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

  1. 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:

PolicyBehaviourUse when
AllowRuns may overlapIndependent, idempotent runs
Forbid (skip)Skip the new run while one is activeReports, syncs: the next run catches up
ReplaceCancel the old run, start the new oneOnly 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

BottleneckFix
Many schedulesPartition the due index; add scheduler instances and partitions
Top-of-hour burstsPre-enqueue + jitter + autoscaling workers
Long-running jobsHeartbeats; separate pools by job class
Run history volumeTTL old runs; aggregate stats

When things fail

FailureWhat happens
Scheduler instance diesIts leases expire; others take over its partitions within seconds
Network partition: old leader still thinks it owns a partitionFencing token (epoch) makes its writes fail
Worker crashVisibility timeout → retry
Job keeps failingBackoff, 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

Your turn: the interviewer pushes

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:

  1. 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.
  2. 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.
  3. 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.

Job scheduler on one page
  • 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 LOCKED is 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.
Mock interviewPractise it as a mock interview: scope, size and the big decisionsOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

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?

2. Three scheduler instances read the same due index for availability. What stops them all firing every job?

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?

4. An hourly report sometimes takes 75 minutes, and two runs overlapping corrupt its output table. What is the right fix?

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?

6. A team asks the scheduler to guarantee their "charge subscribers" job runs exactly once. What do you tell them?

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?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.