Design a Fair Distributed Job Scheduler with Unknown Runtimes

Design a distributed job scheduler for a comparatively modest workload. Jobs may run for very different lengths of time, and their duration is unknown before execution. The scheduler should allocate work fairly and ensure that submitted jobs are not silently lost or starved. Explain how you would choose a simple architecture, define fairness, dispatch work, recover from failures, and reason about eventual completion without assuming accurate runtime estimates. ### Constraints & Assumptions - The source emphasizes smaller-than-usual scale and avoiding unnecessary complexity. It supplies no job count, arrival rate, worker count, or runtime distribution. - **Practice fairness model:** jobs belong to submitters; each submitter has a FIFO queue, and active submitters should receive scheduling opportunities fairly. State how the answer changes if fairness instead concerns individual jobs or measured compute time. - Begin with non-preemptive jobs: once started, a job runs until it finishes or fails. Checkpointing and safe preemption are not assumed. - Jobs can fail or a worker can disappear. Define whether “completed” means successful execution or a visible terminal outcome; do not promise success for a permanently failing job. - No job-dependency graph or recurring calendar schedule is specified. Focus on durable submission, fair dispatch, execution tracking, and recovery. ### Clarifying Questions to Ask - Is fairness defined per submitter, per job, or by actual resource consumption? - Are jobs guaranteed to finish in finite time, and can they be retried safely after an uncertain worker failure? - Can a running job be checkpointed or canceled without losing all useful work? - Are resource needs homogeneous, or do jobs require different capacities or worker capabilities? - What should happen to a job that repeatedly fails or runs without observable progress? ### Part 1 — Use a Small Durable Core Describe the job records, queue representation, scheduler, and workers. Explain how jobs become visible for scheduling and how a dispatch decision is claimed without assigning one job to several healthy workers. #### What This Part Should Cover - A modest-scale architecture with durable job and attempt state. - Atomic claims, a single scheduling authority or equivalent coordination, and worker capacity checks. - Submission deduplication and explicit queued, running, and terminal states. ### Part 2 — Define Fairness with Unknown Durations Choose a dispatch policy for the practice fairness model. Explain what it guarantees and what it cannot guarantee when short and long jobs share a non-preemptive worker pool. #### What This Part Should Cover - Fair scheduling opportunities without requiring advance runtime predictions. - The difference between equal job starts, equal compute time, and equal completion latency. - Conditions for eventual dispatch and the limitations caused by long or nonterminating jobs. ### Part 3 — Recover Without Losing Jobs Describe worker failure detection, retry eligibility, stale-worker completion, duplicate side effects, and overload. Explain which operational signals show that fairness or completion is failing. #### What This Part Should Cover - Leases or heartbeats with attempt identity and fenced state transitions. - Retry policies that do not let failing jobs monopolize dispatch. - Honest delivery semantics, bounded resource use, and visible stuck or failed outcomes. ```hint Count starts and occupied time separately A submitter whose jobs run much longer can occupy more worker time even when every submitter receives the same number of starts. Decide which fairness guarantee your policy actually provides. ``` ```hint A missed heartbeat is uncertain A worker can lose contact with the scheduler while its job continues running. Decide how a new attempt and a late result from the old attempt are distinguished. ``` ### What a Strong Answer Covers - A simple durable design justified by the modest scale. - A precise, achievable fairness policy for unknown non-preemptive runtimes. - No silent job loss across submission, claiming, execution, and completion. - Recovery and observability that make starvation, uncertainty, and permanently failing jobs visible. ### Follow-up Questions - How would safe checkpointing change your options for sharing compute time between long and short jobs? - What happens when new jobs arrive faster than workers can finish them? - How would you keep a large submitter from occupying every worker while still using idle capacity efficiently?