Design a Distributed Job Scheduler

Run millions of cron jobs and one-off tasks on time across a fleet, exactly once each, and keep going when a worker dies halfway through one.

Last updated 2026-09-22. Difficulty: medium. Patterns: scheduling, leases, idempotency, queues, fault-tolerance. Reported at Amazon and 5 more with Pro.

Functional requirements

• Schedule recurring jobs. Cron expressions with a time zone, because "09:00 every weekday" means different instants in March depending on where the customer is.
• Schedule one-off jobs at a future time. Send this reminder in 40 days, expire this hold in 10 minutes. The same machinery, with a schedule of one.
• Run each due execution once. The hard requirement. Charging a card twice because a worker retried is the failure this system exists to prevent.
• Retry failures with backoff. A bounded number of attempts with exponential backoff and jitter, then a dead-letter queue and an alert rather than an infinite loop.
• Respect concurrency and ordering per job. A job that overruns its interval must not start a second copy unless it says it may, and some jobs must not run concurrently with each other.
• Observability and control. History per job, why the last run failed, and the ability to pause, resume, trigger now and backfill a missed window.
• Out of scope. The execution environment itself (containers, capacity), workflow orchestration with dependencies between jobs, and data pipeline lineage.

Non-functional requirements

• Scheduling accuracy (within 1 s of due time at p99). Late is usually fine, early never is. "Run at 09:00" that fires at 08:59 breaks business logic that assumes the day has started.
• Scale (10 M scheduled jobs, 100 k executions/s peak). The peak is at the top of the minute and especially the top of the hour: a self-inflicted thundering herd.
• Delivery (at least once, with idempotent execution). Exactly-once execution is not achievable across a network. Say so, then make duplicates harmless.
• Durability (no scheduled job lost). A job accepted and then forgotten is invisible until someone notices a report never arrived. Silent loss is the worst failure mode here.
• Availability (99.99 %). A scheduler outage is not a crash, it is a delay, but a delay long enough becomes a missed window, which for some jobs is a lost day.
• Isolation (no tenant starves another). One customer scheduling a million jobs at midnight must not delay everyone else's.
• Long jobs (up to 6 hours). The execution model must tolerate a task that outlives any single lease renewal interval.

Back-of-envelope estimates

• Scheduled jobs: ~10 M. 100 k tenants × ~100 jobs each = 10 M definitions. At ~1 KB each that is 10 GB of definitions: small. The volume is in executions, not definitions.
• Executions per day: ~1 B. 10 M jobs averaging ~100 runs a day (a mix of per-minute, hourly and daily schedules) = ~1 B executions/day ≈ 12 k/s average.
• Peak burst: ~100 k/s. Everything cron lands on the minute, and a large share on the hour. If 30 % of daily executions are hourly jobs clustered in the first second of the hour, the instantaneous rate is ~100 k/s: roughly eight times the average.
• Due-index scan size: ~100 k rows/s. A scan every second for jobs due in the next window returns the burst-sized set: ~100 k rows at the top of the hour, a few hundred otherwise. The index must make that a range scan, never a table scan.
• Execution record storage: ~300 GB/day. 1 B executions × ~300 B (job id, attempt, start, end, status, error) = ~300 GB/day, retained 30 days hot then rolled up. Execution history is far larger than the jobs themselves.
• Workers needed: ~2 000. Average execution 200 ms of work; 12 k/s × 0.2 s = 2 400 concurrent executions. At ~20 concurrent per worker that is ~120 workers for the average and ~1 000 for the peak, so the queue absorbs the burst rather than the fleet.
• Lease renewal traffic: ~2 k/s. ~2 400 concurrent executions renewing a lease every 30 s = ~80/s normally, rising with long jobs. Trivial, which is what makes leases affordable as the ownership mechanism.

Components

• Tenant service: The application that registers jobs and receives their executions, usually as an HTTP callback or a message. It owns the idempotency of its own handler, which is the other half of the correctness story.
• Schedule API: Create, update, pause, delete, trigger now and backfill. Validates the cron expression and time zone, computes the first due time, and writes the definition.
• Job store (sharded SQL, index on next_run_at): One row per job: schedule, payload, target, retry policy, concurrency policy, and next_run_at. The index on (shard, next_run_at) is the whole design: every dispatcher query is a range scan on it.
• Dispatcher (one owner per partition): Wakes each second, claims jobs due in the next window from its partitions, enqueues an execution for each, and advances next_run_at. Partition ownership is leased, so exactly one dispatcher claims any given job.
• Near-term timer wheel (in-memory, next 60 s): Jobs due within the next minute held in a hierarchical timer wheel so firing is O(1) per tick rather than a database query per second. The store remains the authority; this is a latency optimisation that can be rebuilt at any time.
• Execution queue (partitioned by tenant): Absorbs the top-of-the-hour burst and decouples deciding from doing. Partitioned per tenant with weighted draining so one tenant's midnight flood cannot starve everyone else.
• Worker pool: Takes an execution, acquires a lease, invokes the target, renews the lease while it runs, and reports the outcome. Stateless and autoscaled on queue depth.
• Lease store (Redis / etcd with TTL): execution_id → worker, with a short TTL renewed by a heartbeat. A worker that dies stops renewing and its lease expires, which is how work is recovered without anyone having to detect the death directly.
• Job target: The thing actually run: an HTTP endpoint, a queue message, a container. Given an idempotency key derived from the execution so a duplicate delivery is recognisable as one.
• Execution history (time-partitioned): One row per attempt with status, timing and error. The answer to "did it run and what happened", and the source of the per-job dashboards.
• Retry scheduler: Turns a failure into a future execution with exponential backoff and jitter, up to the policy limit, then dead-letters. Reuses the same due-time mechanism rather than inventing a second one.
• Reaper: Finds executions whose lease expired without an outcome and requeues them. The only thing standing between a worker dying and a job silently never running.
• Monitoring & alerts: Lateness distribution, failure rate per tenant, dead-letter depth, and missed-window alerts. A scheduler that is quietly an hour late looks healthy from the inside unless lateness is measured explicitly.

User flows

1. A daily job fires and runs. The happy path, and the shape of the whole system: decide, enqueue, lease, invoke, record, reschedule.
   1. A tenant registers "every weekday at 09:00 Europe/London". The API validates the expression, resolves the time zone, and computes the first next_run_at in UTC. Storing UTC plus the original zone (never a fixed offset) is what makes the job survive a daylight-saving change.
   2. The dispatcher that owns this partition scans for jobs due in the next window. A range scan on (partition, next_run_at) with a limit. Exactly one dispatcher owns the partition through a lease, so no two dispatchers can claim the same job and no coordination is needed per job.
   3. Jobs due within the minute are loaded into the in-memory timer wheel. Firing from a timer wheel is O(1) per tick and accurate to the millisecond. Polling the database every second would be accurate to a second at best and would put the whole burst on one query.
   4. At 08:00:00 UTC the timer fires and an execution is enqueued. The execution carries a deterministic id (job id plus scheduled time plus attempt) which is the idempotency key the target will see. Deriving it rather than generating it is what makes a duplicate recognisable.
   5. next_run_at is advanced to the next occurrence in the same transaction as the claim. Advancing before enqueueing, in one transaction, means a dispatcher crash cannot fire the same occurrence twice. It can lose the enqueue (which the reaper and the missed-window check catch) and losing is recoverable in a way that double-charging a card is not.
   6. A worker takes it, acquires a lease, and invokes the target. The lease makes ownership explicit and time-bounded. The idempotency key goes in the request so the tenant can reject a duplicate delivery at their end.
   7. The outcome is recorded and the lease released. Status, duration and any error, written before the lease is released so an execution can never be both finished and unrecorded. The history is what the tenant's dashboard and the alerting read.
2. Midnight: everything is due at once. The scale-breaking case, and it is self-inflicted: cron expressions cluster on round numbers.
   1. At 00:00:00 several hundred thousand jobs become due in the same second. Daily jobs overwhelmingly use midnight, and hourly ones the top of the hour. The distribution of due times is the least uniform thing in the system, and every component has to be designed against that rather than against the average.
   2. Dispatchers claim in bounded batches rather than in one enormous scan. A limit per scan and many partitions scanning in parallel. One unbounded query returning 300 000 rows is a long transaction on the busiest table at the busiest moment.
   3. Executions are enqueued as fast as they are claimed; the queue absorbs the rest. This is why the queue exists. Deciding is fast and bursty; doing is slow and steady. Without the buffer the worker fleet would have to be sized for the peak second of the day.
   4. Workers drain at their sustainable rate; jobs run late, not lost. Lateness is the correct degradation and should be measured as a first-class metric per job. A daily report starting ninety seconds late is fine; the alert threshold belongs to the tenant, not to us.
   5. Per-tenant queue partitions stop one tenant's flood from starving the rest. Weighted draining across tenant partitions with a cap on concurrent executions per tenant. Without it, one customer scheduling a million midnight jobs delays everyone: the noisy-neighbour failure that makes a shared scheduler unusable.
   6. New schedules are jittered at creation to flatten future peaks. For expressions that do not demand an exact second, spread within the minute deterministically by hashing the job id. It costs nothing, it is stable across runs, and it is the cheapest capacity win available.
3. A worker dies halfway through a job. The failure path. Nobody detects the death directly; the lease simply stops being renewed.
   1. A worker acquires a 60-second lease and starts a job that takes minutes. The lease is short and renewed every 20 seconds or so. Short leases mean fast recovery; renewal is what lets a long job hold ownership without a long lease.
   2. The worker is terminated mid-execution. The genuinely unknowable part: the target may have completed the work, partly completed it, or not started. The scheduler cannot tell, which is why the tenant's idempotency is the other half of the contract.
   3. The lease expires because nothing renews it. Expiry by TTL means no failure detector, no consensus about liveness, and no split brain about who owns the work: the absence of a heartbeat is the signal.
   4. The reaper finds an expired lease with no recorded outcome and requeues the execution. The requeue keeps the same execution id and increments a delivery counter, so the target sees the same idempotency key and can recognise a repeat of work it may already have done.
   5. A new worker picks it up and invokes the target with the same key. If the target completed the first time, it returns its stored result and does nothing. This is the moment the whole at-least-once design either works or produces a duplicate charge, and it works only because the key is deterministic.
   6. Repeated reaping is capped and the execution is dead-lettered with an alert. An execution that has been reaped several times is usually killing its worker (memory, a poison payload) so requeueing forever converts one bad job into a fleet-wide outage. Cap it and alert.
4. A job fails and is retried. Retries reuse the scheduling machinery rather than inventing a parallel one.
   1. The target returns a 500 and the worker records the failure. The error is stored with the attempt, because "it failed" without the reason turns every support conversation into an investigation.
   2. The retry scheduler computes the next attempt time with exponential backoff and jitter. Base times two to the attempt, with full jitter. Without jitter, a downstream outage that fails ten thousand jobs retries all of them in lockstep and keeps the target down: the retry storm that turns a blip into an incident.
   3. The attempt is written as a future execution in the same due-time index. One mechanism for "run this later", whether it is a cron occurrence, a one-off, or a retry. A separate retry queue with its own timing is a second scheduler to get wrong.
   4. The attempt runs with the same execution id and an incremented attempt number. The attempt number is visible to the target, which is often useful: a handler may behave differently on a fifth attempt, such as skipping an optional enrichment step.
   5. After the policy limit the execution is dead-lettered and the tenant is alerted. Dead-lettered, not deleted: the payload is kept so it can be inspected and replayed after a fix. A missed occurrence must never be invisible, because nobody notices an absence.
   6. A tenant-wide failure rate above a threshold pauses that tenant's retries. A circuit breaker per tenant target. If every job for one tenant is failing, their endpoint is down, and continuing to retry a million jobs helps nobody and hurts them.
5. The clocks go back. The correctness case people forget. "09:00 every day" is ambiguous twice a year and the answer must be deliberate.
   1. A job is defined as 01:30 daily in a zone that moves its clocks. On the spring-forward day 01:30 does not exist; on the autumn day it happens twice. Storing a fixed UTC offset instead of the zone silently drifts the job by an hour for half the year.
   2. The next occurrence is computed in local time, then converted to UTC. Always in that order, with a current time-zone database. Computing in UTC and adding an offset gets the transition days wrong, which is the bug that reaches production every March.
   3. A skipped local time is resolved by a documented rule. Most schedulers fire at the first valid instant after the gap: 03:00 when the clocks jump from 02:00. What matters is that it is documented and tested, not which rule you pick.
   4. A repeated local time fires once, not twice. Because next_run_at is a UTC instant and is advanced strictly forwards past the second occurrence, the duplicate cannot be generated. The monotonic UTC cursor is what makes this correct by construction rather than by a special case.
   5. A time-zone database update shifts future occurrences and they are recomputed. Zones change by legislation with little notice. A job pinned to a stale database fires at the wrong local time, so updates trigger a recompute of stored next_run_at values and the shifted set is reported.

Deep dives

Related

• Design a Payment System
• Design a Matchmaking System
• Design a Notification System
• Design an LLM Inference Service
• Run this question for a friend: the interviewer kit