Design a Task Scheduler That Runs Each Task Reliably When It Is Due

Design a task scheduler: a service that accepts tasks from clients, keeps track of when each task is due, and makes sure each one is executed when it is due. The round reported only the topic, so the kinds of tasks, the scale and the execution guarantees have to be settled with the interviewer before designing. ```hint Finding what is due Think about how the scheduler finds the tasks that are due right now without scanning every task it has ever stored, and what that implies for how tasks are indexed. ``` ```hint A worker disappears Suppose a worker picks up a task and crashes halfway through. Decide what tells the system the task needs another attempt, and what stops two workers from running it at the same time. ``` ### Constraints and Clarifications - Not given: whether tasks are one-off, recurring or both, the number of stored tasks and the dispatch rate, how precisely tasks must start on time, how long tasks run, and whether a task may occasionally run twice. Ask, or state your assumptions. ### Clarifying Questions - Are tasks one-off ("run at 09:00"), delayed ("run in 10 minutes"), recurring (cron-like), or all three? - Does the scheduler run the task itself, or hand it to separate workers or services? - How many tasks are stored, and how many become due per second at peak? - How close to its due time must a task start, and is a rare duplicate run acceptable? - Do tasks have priorities, dependencies on other tasks, or resource requirements that restrict where they can run? - Is this a component inside one machine, or a distributed service that must survive machine failures? ### What a Strong Answer Covers - Scope and guarantees settled first: task types, scale, timing precision, at-least-once versus at-most-once execution - An API and data model for task definitions, schedules and individual runs, with explicit states - An efficient way to find due tasks, and a way to hand each run to exactly one worker at a time - Failure handling: worker crashes, scheduler crashes, retries with backoff, idempotency, missed runs of recurring tasks - Scaling and fairness for bursts of tasks due at the same moment, plus observability of how far behind schedule the system is ### Follow-up Questions - A recurring task's previous run is still going when its next run comes due. What should happen, and who decides? - The scheduler is down for ten minutes. What happens to the runs that were due during that window? - Task B may start only after task A succeeds. How does the design change? - One client submits a million tasks due at the same second. How do you keep other clients' tasks on time?