## Design a Durable Task Scheduling Service The initial prompt is “design a task scheduler.” Begin by distinguishing an in-process timer, a durable delayed-job service, and a workflow orchestrator. For the remainder of the exercise, design a distributed service that accepts one-time and recurring tasks, makes due work available to executors, and preserves task state across failures. ### Constraints & Assumptions - Scheduling and task execution are separate responsibilities. - Delivery may be at least once; callers need a way to make execution effects safe. - A task can be scheduled, cancelled, retried, or inspected. - Recurring schedules need explicit time-zone and missed-run semantics. - Do not assume task volume, timing precision, payload size, or execution duration; identify the values that change the architecture. ### Part 1 — Define the Scheduling Contract Specify APIs, task states, delivery semantics, and the meaning of one-time and recurring schedules. #### What This Part Should Cover - Stable task and occurrence identifiers plus idempotent creation. - `run_at`, recurrence rule, time zone, payload reference, priority, and retry policy. - Scheduled, leased, completed, failed, and cancelled states with legal transitions. - A stated precision target and behavior for late or missed recurring runs. ```hint Give each recurrence an occurrence identity Retries of one due occurrence must not be confused with the next scheduled occurrence. ``` ### Part 2 — Store, Find, and Claim Due Work Design the durable data model and the path that finds tasks whose scheduled time has arrived. Explain how several scheduler instances avoid dispatching the same occurrence as if it were new work. #### What This Part Should Cover - An index or time-bucket structure keyed by due time and partition. - Atomic claim or lease acquisition with an expiry. - Bounded polling or promotion into a ready queue rather than a full-table scan. - Conditional state updates and an outbox where database and queue writes must agree. ```hint Claim before dispatch Multiple pollers can observe the same due row, so only one should win the current lease transition. ``` ### Part 3 — Recover from Failure and Scale Handle scheduler crash, executor crash, expired leases, duplicate delivery, retry exhaustion, cancellation races, clock skew, hot time buckets, and overload. #### What This Part Should Cover - Lease renewal and safe redispatch after expiry. - Idempotency keys or deduplication at the task's side-effect boundary. - Backoff, dead-letter handling, and operator-driven replay. - Sharding, tenant fairness, backpressure, and protection of near-term work from large backfills. ```hint Exactly once is an end-to-end claim Removing queue duplicates does not make an external database write or API call happen exactly once. ``` ### Part 4 — Operate and Verify the Scheduler Describe observability, repair jobs, and tests for time and concurrency edge cases. #### What This Part Should Cover - Due-to-dispatch lag, oldest overdue task, lease expiry, retry, dead-letter, and cancellation metrics. - Reconciliation of scheduled occurrences with claims and terminal outcomes. - Tests around time-zone transitions, boundary timestamps, concurrent claim, and crash recovery. - Safe schema or recurrence-rule evolution for already scheduled work. ```hint Watch overdue age, not only queue size A small backlog can still contain a task that the scheduler has skipped for hours. ``` ### What a Strong Answer Covers - Resolves the ambiguous scope before choosing components. - Defines occurrence identity, delivery semantics, leases, retries, and cancellation precisely. - Finds due work without scanning all tasks and claims it safely under concurrency. - Connects partitioning and backpressure to stated timing and volume assumptions. - Includes reconciliation, observability, and time-focused failure tests. ### Follow-up Questions 1. How would you support millions of tasks scheduled for the same second? 2. What should happen to a recurring task after the scheduler is unavailable for several occurrences? 3. How would an executor make a payment-like side effect idempotent? 4. How would you change the design for sub-second timing precision?