How Would You Design a Distributed Job Scheduler?

Prompt and scope

Design a multi-tenant distributed job scheduler. It supports one-time jobs and cron jobs with IANA time zones, stores 20 million active schedules, creates 200 million occurrences per day, and may have 500,000 triggers at the top of an hour. Under normal peak load, strict jobs must reach a durable queue within 5 seconds of their scheduled time at p99. Jobs that do not require an exact time may be spread across a 5-minute flexible window.

The API supports creating, pausing, resuming, updating, and canceling schedules. Delivery is at least once. The scheduler is responsible for turning a scheduled time into an occurrence and placing it on a target queue. Container placement, DAG dependencies, and arbitrary workflow orchestration are out of scope. Actual task completion time is not part of the 5-second scheduling SLO.

This question fits mid-to-senior backend, platform, infrastructure, and system design roles. Public 2026 system design material still treats a job scheduler as a standalone interview problem, while current AWS and Kubernetes documentation exposes practical boundaries around flexible windows, duplicate or missing creation, misfires, time zones, and retries. The core challenge is not parsing cron. It is reliably materializing one scheduled time into a traceable, retryable, idempotent execution.

What the interviewer evaluates

The first signal is separating Schedule, Occurrence, and Attempt. A schedule describes future timing. An occurrence represents one specific scheduled time. An attempt represents one delivery or processing try for that occurrence. A single row with next_run_at and status mixes retries, history, updates, and the next trigger.

The second signal is refusing to promise exactly-once casually. A scheduler may crash after enqueueing but before recording success, and a worker may complete a side effect before losing its acknowledgment. Kubernetes explicitly notes that a CronJob can sometimes create two Jobs or no Job and therefore recommends idempotent jobs. A standard queue's visibility lease also cannot absolutely prevent duplicate delivery. A strong answer chooses at-least-once delivery and makes the business effect idempotent with a stable occurrence ID.

The third signal is handling synchronized peaks. The daily average is only about 2,315 occurrences per second, but placing 500,000 strict triggers on queues within 5 seconds requires roughly 100,000 dispatches per second. Capacity based on the average fails at the top of the hour. One global time-ordered heap also creates a capacity and availability hot spot.

Finally, time and failure behavior must be a product contract: whether cron means local wall-clock time or a fixed interval, what happens to nonexistent and repeated daylight-saving times, whether a ten-minute outage causes catch-up or skips, whether runs may overlap, and what update or cancellation means after an occurrence has been queued.

Questions to clarify

• What does five seconds measure? Define it as enqueued_at - scheduled_for, covering scheduling and enqueueing only. If completion is required, the capacity model changes completely.
• Are one-time, cron, and fixed-rate schedules all required? This design supports one-time and cron. Every 24 hours differs from 09:00 local time across daylight-saving changes and must not use the same calculation.
• Are duplicates preferable to omissions? This design chooses at-least-once delivery and handles duplicates with idempotency. A non-repeatable external effect needs an idempotency key or an explicit residual risk.
• What happens to occurrences missed during downtime? Each schedule needs a misfire_policy, maximum lateness, and catch-up cap. Otherwise recovery may suddenly create millions of obsolete occurrences.
• May one schedule overlap itself? The default is ALLOW, with SKIP_IF_RUNNING as another option. Replacing arbitrary in-flight work is unsafe when side effects cannot be undone.
• How strong are update and cancellation guarantees? Pending occurrences from old versions should become invalid. Deleting a schedule cannot recall work that a worker already claimed or completed, so the API must report the actual state.
• What is the target? This design puts occurrences on durable queues for registered handlers. Arbitrary user code is excluded so sandboxing and compute placement do not obscure the scheduling problem.
• What tenant isolation is required? Enforce separate quotas for schedule count, trigger rate, running concurrency, and catch-up rate. One top-of-hour batch cannot consume every shard and queue.

30-second answer

“I would separate schedules, occurrences, and attempts. A schedule stores the expression, IANA time zone, version, and next trigger. Scheduler nodes shard by time bucket and schedule-ID hash and materialize only a bounded horizon. The occurrence ID is derived from schedule ID, version, and original scheduled time; a unique constraint prevents duplicate materialization during failover. The occurrence, next trigger, and outbox commit in one transaction, then a relay writes to a durable queue at least once. Workers process under renewable visibility leases, while business handlers deduplicate by occurrence ID. Strict jobs are provisioned for peak rate, and flexible jobs use deterministic jitter. Misfire, overlap, time-zone, and cancellation behavior are explicit policies. I would validate with 500,000 simultaneous triggers, crashes at every handoff, daylight-saving boundaries, and cancellation races.”

Step-by-step deep dive

Calculate the data plane before drawing components:

average = 200,000,000 / 86,400 ≈ 2,315 occurrences/s
strict_peak = 500,000 / 5 = 100,000 dispatches/s

The strict peak is more than 43 times the daily average. If an active schedule and an occurrence each use about 1 KB of logical storage, schedule metadata is roughly 20 GB and occurrences add roughly 200 GB per day. Indexes, replicas, queue messages, and history retention add more. These are sizing assumptions for partitioning and storage tiers; actual fields and indexes must be load-tested.

The control plane validates expressions, authorizes tenants, enforces quotas, creates idempotently, and versions updates. A simplified model is:

Schedule(schedule_id, tenant_id, expression, time_zone, version,
         next_run_at, state, misfire_policy, max_lateness,
         overlap_policy, flexible_window)

Occurrence(occurrence_id, schedule_id, schedule_version,
           scheduled_for, available_at, state, attempt_count)

Attempt(attempt_id, occurrence_id, lease_token, started_at,
        finished_at, result)

UNIQUE(schedule_id, schedule_version, scheduled_for)

The create API accepts a caller idempotency key. It validates the cron expression and time zone and previews several future triggers so a syntactically valid but unintended expression is caught early. Store next_run_at in UTC while retaining the original expression and IANA zone. A daily local-time job must derive its next time from zone rules rather than adding 24 hours to the previous UTC timestamp.

Time-zone edges require a stable contract. This design skips a nonexistent local time during spring-forward and runs once when fall-back repeats a wall-clock time. A time-zone update affects only future occurrences under a new schedule version. AWS Scheduler documents the same skip-and-run-once behavior, but it remains a product choice here rather than a universal scheduler rule. A future fixed-rate type would use elapsed duration and would not shift with daylight saving.

The schedule store has an index equivalent to (time_bucket, shard, next_run_at), with shard = hash(schedule_id) mod N. Scheduler nodes lease multiple logical shards and scan a bounded planning horizon, such as the next few minutes. A single global leader limits capacity and recovery. Shard leases reduce duplicate scans, while database uniqueness and conditional writes provide the final correctness boundary.

For each due schedule, one transaction inserts a deterministic Occurrence, conditionally advances next_run_at from the current schedule version, and writes a dispatch outbox row with available_at. If two nodes overlap during a lease transition, uniqueness leaves one (schedule_id, version, scheduled_for) occurrence. The conditional update prevents an old node from moving the next trigger backward.

Do not generate an infinite cron history in advance. A planning horizon that is too short passes storage jitter directly into the 5-second SLO. One that is too long makes updates and cancellations invalidate a large set of old-version occurrences. Choose a horizon that covers scheduler failover and enqueue budgets, then tune it from measured lag. A one-time schedule becomes terminal; a recurring schedule keeps only a next-trigger cursor while old occurrences move to tiered history.

Near available_at, a dispatch relay writes outbox events to durable queues partitioned by tenant and priority. If the relay crashes after the queue accepts a message but before the database acknowledgment, it sends the same occurrence_id again. That duplicate is intentional. Marking sent before enqueue can omit work, while enqueueing before marking can duplicate it. A transactional outbox makes the trade-off an explicit, idempotently retryable at-least-once path.

Five hundred thousand top-of-hour jobs require more than extra polling threads. Split each time bucket into enough schedule-ID hash shards. If load tests show that one shard safely performs Q dispatches per second with real transactions, indexes, and queue writes, the strict plane needs at least ceil(100,000 / Q) simultaneously available shards plus failure headroom. The queue applies tenant-weighted fairness and rate quotas so one tenant cannot consume the strict lane.

Jobs with a 5-minute window use deterministic jitter: available_at = scheduled_for + hash(occurrence_id) mod 300s. The same occurrence gets the same time after retries and failovers, making behavior reproducible while spreading correlated triggers. Strict jobs keep the original time and reserved capacity. Amazon's Builders' Library likewise identifies jitter on periodic housekeeping jobs as a way to reduce correlated failure.

A worker receives an occurrence under a time-bounded visibility lease and renews it with heartbeats for long work. Lease expiry makes the message visible again, and duplicate delivery cannot be excluded even during the window. The state machine therefore cannot treat a lease as exactly-once:

SCHEDULED -> ENQUEUED -> RUNNING -> SUCCEEDED
                         |   |
                         |   +-> RETRY_WAIT -> ENQUEUED
                         +------> DEAD

Side states: MISSED, CANCELED, SKIPPED_OVERLAP

Each claim gets a new lease_token or increasing attempt generation. Completion updates must match the current token so a timed-out worker cannot overwrite a newer attempt's state. This fencing protects scheduler state, not an external effect already performed by the old worker. Business idempotency uses occurrence_id as a unique key in the same transaction as the effect, or as the downstream API's idempotency key. If an external target lacks idempotency and cannot be queried, duplicate risk remains.

Retry by error class. Permanent parameter errors go to DEAD. Network failures, throttling, and temporary 5xx responses use exponential backoff with full jitter, bounded by maximum attempts, occurrence deadline, and tenant budget. A queue DLQ retains exhausted occurrences. Manual replay keeps the same occurrence_id; assigning a new ID would bypass deduplication.

Control-plane recovery needs explicit misfire policies. SKIP marks occurrences past maximum lateness as MISSED. FIRE_ONCE emits only the latest missed occurrence. CATCH_UP emits at most K, subject to a tenant catch-up rate. Kubernetes's starting deadline and missed-schedule limits expose the same decision: unbounded recovery either loses needed work or creates a recovery storm.

SKIP_IF_RUNNING atomically checks for a current RUNNING occurrence of the same schedule before marking the new one SKIPPED_OVERLAP. Without an atomic state transition, two occurrences may both observe no predecessor. Canceling or updating increments the schedule version and invalidates unclaimed old-version occurrences. Workers recheck the version and cancellation marker before the side effect. Started work requires cooperative cancellation, and completed external effects cannot be rolled back by the scheduler.

Observability follows the guarantees: p50/p95/p99 for schedule_lag = enqueued_at - scheduled_for; pending rows per time bucket; materialization lag; uniqueness conflicts; outbox backlog; queue age; duplicate claims; retries and DLQ; MISSED and overlap skips; tenant throttling; clock offset; and time spent in each occurrence state. API availability does not prove that expected occurrences reached queues on time.

Acceptance testing first injects 500,000 strict occurrences at the top of an hour and checks 5-second p99 plus tenant fairness. Then crash schedulers before insertion, after transaction commit, and after queue send; assert no silent omission and deduplication by the same occurrence ID. Also cover a worker losing acknowledgment after its effect, lease expiry, all three misfire policies after a ten-minute control-plane outage, both daylight-saving transitions, update and cancellation races, long-run overlap, and one tenant's catch-up storm.

Strong sample answer

“I would define the SLO as scheduled time to durable queue acceptance, excluding execution. Two hundred million daily triggers average about 2,315 per second, but 500,000 top-of-hour triggers within five seconds require a strict plane sized for 100,000 per second. Flexible work can be spread deterministically across five minutes.

The model separates schedules, occurrences, and attempts. A schedule stores its cron expression, IANA zone, version, and next_run_at. An occurrence ID derives from schedule ID, version, and scheduled_for and has a unique constraint. Scheduler nodes shard by time bucket and schedule-ID hash and lease shards for scanning. A transaction inserts the occurrence, advances the next trigger, and writes a dispatch outbox, so failover does not silently omit work and a repeated relay sends only the same occurrence ID.

The queue and workers use at-least-once semantics. Workers have renewable visibility leases, and completion must match the current lease token. The business handler uses the occurrence ID as a database unique key or downstream idempotency key. Lease expiry can then add attempts without adding business effects; an external target without idempotency retains an explicit duplicate risk.

Misfire, overlap, time-zone, and cancellation behavior are API policies. After downtime, a schedule can skip, fire once, or catch up at most K times. A nonexistent cron time is skipped and a repeated wall-clock time runs once. Updates increment the version, and workers recheck before side effects. I would test the top-of-hour peak, every crash window, duplicate messages, daylight-saving boundaries, and cancellation races, while monitoring schedule lag, due backlog, duplicate claims, missed occurrences, DLQ, and tenant throttling.”

Common mistakes

• Combining schedule, occurrence, and attempt in one row → Retries overwrite history and updates cannot identify old occurrences → Separate Schedule, Occurrence, and Attempt.
• Sizing for the 2,315-per-second daily average → Five hundred thousand top-of-hour triggers cause severe lag → Load-test shards at the strict peak and spread flexible work deterministically.
• Using one global leader with an in-memory min-heap → The leader becomes a capacity and recovery bottleneck, and restart rebuilds all future work → Use a durable time index, logical shards, and a bounded horizon.
• Marking sent before writing the queue → A queue failure silently omits an occurrence → Write an outbox transactionally and relay at least once.
• Claiming locks and visibility timeouts guarantee exactly-once → Timeout and lost acknowledgment still overlap attempts → Combine stable occurrence IDs, fencing tokens, and business idempotency.
• Replaying every missed historical occurrence after recovery → Millions of obsolete tasks create a second outage → Set maximum lateness, catch-up caps, and tenant rates.
• Adding 24 hours in UTC for a local daily cron → Wall-clock time drifts across daylight saving → Retain the IANA zone and compute the next local occurrence.
• Deleting a row to pause or cancel → Materialized or queued work may still run, and audit history disappears → Invalidate by version and recheck state before side effects.
• Putting every tenant on one FIFO queue → A large top-of-hour batch blocks other tenants → Use tenant-aware fair scheduling and separate trigger and concurrency quotas.
• Monitoring only API success → A schedule can be created successfully and never fire on time → Track schedule lag, due backlog, missed occurrences, and state reconciliation.

Follow-ups

Follow-up 1: What if a scheduler crashes after queue send but before updating the outbox?

The relay sends the same occurrence_id again. The queue consumer and business target deduplicate on that ID, and the outbox acknowledgment is conditional. Duplication is chosen over omission because the database and queue do not share one transaction. A transactional log may narrow the window, but external effects still require idempotency.

Follow-up 2: How would you support active-active regions?

Assign each schedule one home region and an increasing generation. Only the region holding the current generation may materialize occurrences, while execution queues may route to target regions. Failover advances the generation before the new region resumes from the durable cursor. A globally unique occurrence key or aggregation layer remains the final duplicate boundary. A single-writer control plane with regional failover is simpler when cross-region writes are unnecessary.

Follow-up 3: At fall-back, local 01:30 happens twice. How many runs should occur?

There is no universal answer; it is part of the schedule contract. This design runs once by collapsing the two UTC candidates with local date, wall-clock time, and zone. A financial reconciliation that requires both physical instants would choose two occurrences with different scheduled_for values. The API should preview future runs before saving.

Follow-up 4: A job runs for two hours but recurs hourly. What happens?

ALLOW runs them concurrently. SKIP_IF_RUNNING atomically marks the new occurrence SKIPPED_OVERLAP. If the product requires waiting, add QUEUE_ONE and retain at most one pending occurrence. Replacing the old run is safe only when handlers support cooperative cancellation because effects may already exist.

Follow-up 5: The scheduler is down for a day. How do you recover without overwhelming targets?

Apply SKIP, FIRE_ONCE, or bounded CATCH_UP per schedule, then throttle by tenant and target capacity. Resume scanning from durable next_run_at rather than replacing the cursor with the current time. Track oldest pending time and estimated drain duration, and isolate strict new work from catch-up capacity.

Follow-up 6: How do you prove there was no silent omission?

An offline reconciler independently recomputes the expected occurrence set from schedule versions and time rules, then compares it with the Occurrence unique-key set. Each expected item must be succeeded, failed, canceled, missed, or absent. Online metrics detect lag; reconciliation detects gaps where the system reported no error because an occurrence was never created.