Design a Durable Delayed Task Scheduler

Design a delayed task scheduler. A client submits a task with a future execution time, and the system makes that task available to workers when it becomes due. ### Requirements and Constraints For this exercise, assume tasks are independent and submissions contain a task payload and a UTC `run_at` timestamp. Accepted tasks must survive process restarts. Workers may fail, and a failed attempt may need to be retried. These are explicit practice assumptions; no fixed scale, lateness target, recurring-task support, or exactly-once execution guarantee is supplied. Describe submission, durable storage, finding due tasks, dispatch, execution tracking, and recovery. Explain what "run at a given time" means in a distributed system and how the design handles a large group of tasks becoming due together. ### Clarifying Questions - Must execution never start before `run_at`, and how much delay after that time is acceptable? - Does a successful submission acknowledge durable storage or only receipt by a process? - Can task effects be made idempotent, and when is retrying an uncertain attempt acceptable? - Are cancellation, rescheduling, or recurring tasks required, or is the initial scope limited to one-time submissions? ```hint Persistence and waiting are different responsibilities An in-memory timer can wake a process, but it cannot recover an accepted task after that process disappears. Identify the durable record behind the timer. ``` ### What a Strong Answer Covers - Durable acceptance, a task state machine, and an index or equivalent structure for finding due work. - Concurrency control for schedulers claiming the same due task and reliable dispatch after a claim. - An explicit treatment of clock uncertainty, scheduling delay, and tasks submitted with an already-passed execution time. - Retry behavior that distinguishes logical tasks from attempts and explains duplicate-execution limits. - Backpressure and fair draining when more tasks become due than workers can execute immediately. - Recovery of scheduled, claimed, and running work after process or worker failure. ### Follow-up Questions 1. How would you cancel a task that has been claimed but has not started executing? 2. What happens if many tasks share the same `run_at` value and exceed the worker pool's capacity? 3. How would you preserve the scheduling guarantee if two scheduler machines disagree about the current time?