Design a Dependency-Aware Job Scheduling System

Topics

Job Scheduling, DAG Execution, Topological Sort, Worker Queues, Retries, Task State Machines, Idempotency, Failure Recovery, Resource Scheduling

Problem Description

Design a scheduler that runs jobs composed of multiple tasks. Each job defines a dependency graph: some tasks can start immediately, while others must wait until their prerequisite tasks complete successfully.

The scheduler should track task state, decide which tasks are ready to run, assign runnable tasks to workers, retry failed attempts when appropriate, and determine when the overall job has succeeded or failed. The focus is on concrete execution mechanics rather than a high-level product workflow.

The design should cover both normal DAG execution and failure behavior. A strong answer should explain task state transitions, dependency tracking, worker leases, retries, idempotency, stuck-worker recovery, and how the system rejects invalid task graphs such as cycles.

Functional Requirements

• Users should be able to submit a job containing tasks and dependency relationships. The scheduler should validate the graph before execution and reject jobs with cycles or missing task references.

• The system should run a task only after all required upstream tasks have completed successfully. Tasks with no remaining prerequisites should become runnable and be placed into a worker queue.

• The scheduler should track task lifecycle states such as pending, runnable, running, succeeded, failed, and retrying. Job-level state should be derived from task outcomes.

• Workers should lease tasks, execute them, heartbeat while running, and report success or failure. If a worker dies or stops heartbeating, the scheduler should reclaim the task and decide whether to retry it.

• The system should support retry policies, failure propagation, and idempotent task execution. A failed task may be retried, skipped, or cause the whole job to fail depending on the job configuration.

Non-Functional Requirements

• Scheduling decisions should be correct under retries, duplicate worker messages, lost acknowledgements, and worker crashes.

• The system should use at-least-once task delivery while preventing duplicate external side effects through idempotency keys.

• The scheduler should scale to many jobs and tasks without repeatedly scanning entire graphs. Ready-task discovery should be incremental.

• Task execution should be observable. Operators should be able to inspect job progress, task attempts, failure reasons, retry counts, and stuck tasks.

• The design should be concrete enough for a low-level systems round: tables, queues, state transitions, leases, heartbeats, and worker assignment should be explicit.

Scale and Constraints

Exact scale may be given during the interview, so candidates should state reasonable assumptions. The system may run many jobs concurrently, and each job may contain anywhere from a few tasks to thousands of dependent tasks.

The task graph should be represented explicitly. A common scheduling approach is to maintain each task’s remaining dependency count, similar to topological sorting. When a task succeeds, the scheduler decrements the indegree of its downstream tasks; any task whose indegree reaches zero becomes runnable.

The system should assume workers and scheduler processes can fail. Because queue delivery may be at least once, task attempts must be safe to replay. For external side effects, a useful deduplication key is (task_id, attempt_id) or a task-level idempotency key depending on the operation.

API / Data Model Expectations

The system should expose APIs for submitting a job, checking job status, listing task states, cancelling a job, and retrieving execution history.

A reasonable data model includes:

The worker queue should contain runnable task IDs rather than the full graph. The durable database should remain the source of truth, while the queue is used for execution dispatch.

Follow-Up Discussion Areas

• DAG scheduling: indegree tracking, dependent lists, topological execution order, and cycle detection during job submission.

• State transitions: how tasks move between pending, runnable, running, retrying, succeeded, and failed.

• Worker coordination: leases, heartbeats, task claiming, task completion, and recovery when a worker disappears.

• Retry behavior: exponential backoff, max attempts, retryable versus non-retryable failures, and preventing runaway retries.

• Failure propagation: whether a failed task cancels the whole job, causes downstream tasks to be skipped, or allows partial job completion.

• Idempotency: at-least-once queue delivery, duplicate attempts, lost acknowledgements, and deduplicating external side effects with task/attempt identifiers.

• Alternate GPU scheduler variant: priority queues, GPU allocation, preemption, checkpointing, starvation prevention, and recovery for long-running training jobs.

What the Candidate Should Focus On

Candidates should focus on the scheduler’s execution core: task graph modeling, ready-task detection, worker assignment, retry state, leases, and failure recovery. A strong answer should show how the system advances a DAG incrementally, handles duplicate or failed execution safely, and keeps task state durable and inspectable.