## Design a Reliable Job Scheduler Design a service that accepts jobs to run at specified times and dispatches them to workers. The system should continue scheduling through machine failures, avoid losing accepted jobs, and make duplicate execution safe and observable. ### Constraints & Assumptions - Jobs may be one-time or recurring. - Execution duration varies and workers can fail after receiving a job. - The required delivery semantic, schedule precision, scale, and maximum lateness must be clarified rather than assumed. - External side effects may not be transactionally coupled to scheduler state. - Operators need to pause, cancel, retry, and inspect jobs. ### Clarifying Questions to Ask - How many active schedules and due jobs must the system handle, and how bursty are due times? - What schedule precision and lateness are acceptable? - Are recurring schedules defined in UTC or local time, and how should daylight-saving transitions behave? - Is at-least-once delivery acceptable if handlers receive an idempotency key? - How long can jobs run, and may two runs of one recurring job overlap? ### Part 1 — Define the API and Durable Model Define the operations and records for creating, updating, pausing, canceling, and observing one-time and recurring jobs. Include job versions and execution attempts. #### What This Part Should Cover - Stable job IDs, schedule specifications, payload references, and ownership. - A materialized next-run time for efficient due-job discovery. - Separate schedule, logical run, and attempt records. - Idempotent mutation APIs and audit history. ```hint Separate intent from attempts A recurring schedule is durable intent; each due occurrence is a logical run, and retries are attempts of that same run. ``` ### Part 2 — Find and Dispatch Due Work Design the path from stored schedules to a worker queue. Explain partitioning, ownership, clock usage, and how multiple scheduler instances avoid dispatching the same run without relying on one permanent leader. #### What This Part Should Cover - Indexed due-time queries or time buckets rather than a full-table scan. - Leases, compare-and-set transitions, or database row claims. - Transactional creation of a run and durable publication to the queue. - Recovery when an owner stops after claiming a partition or run. ```hint Close the database-to-queue gap Consider what happens if a scheduler commits a run but crashes before publishing it, or publishes and crashes before recording that fact. ``` ### Part 3 — Execute, Retry, and Deduplicate Explain worker acknowledgments, timeouts, retry policy, dead-letter handling, cancellation races, and protection against duplicate external effects. #### What This Part Should Cover - At-least-once delivery with a stable run-level idempotency key. - Attempt leases and heartbeats for long-running work. - Bounded exponential backoff, terminal failure, and operator replay. - State-transition rules when cancellation overlaps dispatch or execution. ```hint Keep retries on one logical run A retry should not create a second scheduled occurrence; it should create another attempt tied to the original run ID. ``` ### Part 4 — Scale and Operate the Scheduler Describe how the design handles hot time ranges, partitions with unequal load, recurring-job expansion, and production debugging. #### What This Part Should Cover - Partitioning that can be reassigned and rebalanced. - Backpressure when more jobs become due than workers can execute. - Metrics for scheduling lag, dispatch lag, retries, duplicate claims, and stuck attempts. - Reconciliation that finds accepted jobs or runs stranded between states. ```hint Measure lateness by stage Separate time spent waiting to be discovered, waiting to be published, and waiting for a worker so the bottleneck is diagnosable. ``` ### What a Strong Answer Covers - Durable schedule and run state with explicit delivery and time semantics. - No unprotected handoff between due-job discovery, durable state, and queue publication. - Idempotent execution, bounded retries, lease recovery, and cancellation behavior. - A partitioned architecture with reconciliation and stage-specific observability. ### Follow-up Questions 1. How would you schedule millions of jobs for exactly the same minute without overloading the metadata store? 2. What should happen to a local-time recurring job during a skipped or repeated daylight-saving hour? 3. How would you migrate schedule partitions while dispatch is active? 4. Which invariant would a reconciliation job use to detect a lost queue publication?