Design a Task Scheduler Across Multiple Compute Clusters

Design a task scheduling system that assigns many tasks to multiple compute clusters and tracks each task through completion. ### Requirements and Constraints The essential scope is task scheduling across multiple clusters. For this design exercise, use the following explicit assumptions: tasks are independent, each task declares its resource requirements, clusters advertise their capabilities and available capacity, and a task may be retried after a failure. There is no specified throughput, latency target, dependency graph, or particular cloud provider. Explain how a task is submitted, queued, assigned to a compatible cluster, started, and completed. Include the durable task state, the placement decision, and the communication between the scheduler and cluster agents. Address concurrent scheduling, stale capacity information, a scheduler crash, and a cluster becoming unreachable while a task is running. ### Clarifying Questions - Must tasks run on a particular cluster, or may any cluster with matching capabilities accept them? - Can task execution produce external side effects, and can those effects be made idempotent across retries? - When capacity is insufficient, should the queue favor submission order, explicit priorities, or fairness between submitting groups? - Does an unreachable cluster need to recover its running tasks before they can be retried elsewhere, or is duplicate execution acceptable? ```hint Separate assignment from execution A durable assignment can survive the scheduler process that created it. Consider what evidence distinguishes a current assignment from an old worker's delayed completion message. ``` ```hint Treat capacity as a changing observation Two schedulers may choose the same free resources, and a cluster report can become stale before an assignment arrives. Decide which component makes the final admission decision. ``` ### What a Strong Answer Covers - A task state machine and persistent records that allow queued and assigned work to be recovered after a scheduler crash. - Placement that considers cluster compatibility and resource capacity, including an explicit response when no cluster can accept a task. - A concurrency mechanism that prevents conflicting task claims, plus cluster-side admission that protects actual resource limits. - Retry and completion rules that distinguish attempts and explain the limits of preventing duplicate external effects. - A response to unreachable clusters that separates suspected failure from confirmed termination of their tasks. - Queue fairness, backpressure, and measurements that expose stranded tasks, repeated retries, or unusable cluster capacity. ### Follow-up Questions 1. How would the design change if some tasks could run only on a small subset of clusters with a particular capability? 2. What happens when an old task attempt reports success after a replacement attempt has already started? 3. If one cluster stops reporting capacity while it is still executing work, when would you permit replacement execution elsewhere?