Databricks·Software Engineer·Onsite - System Design / Architecture·Senior

Senior

Apr 2026

Summary

Databricks system design round, one big question about building a job scheduler with DAG-based task dependencies. The scope was broader than I expected and we spent the whole session on it.

Questions Asked (1)

Design a job scheduler where each submitted job is a DAG of tasks with dependency relationships. Tasks with satisfied dependencies should run in parallel up to a configurable worker pool size. The system should detect cyclic graphs, surface per-task and per-job status, handle failures and retries, and support cancel and status query APIs.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This one ran the full session.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and scale, then design the core components: a DAG parser with cycle detection, a dependency-aware scheduler with a worker pool, and a persistent state store for status and retries. Walk through the job lifecycle (submission, execution, failure, cancellation) and discuss trade-offs like push vs. pull scheduling and at-least-once vs. exactly-once semantics.

Pro tip: Emphasize idempotency and state transitions: design tasks to be safely retryable and use a state machine (e.g., PENDING → RUNNING → SUCCEEDED/FAILED) to handle failures and cancellations gracefully. This shows you think about real-world reliability, not just happy paths.

1. Clarify Requirements and Scale

Ask about expected job size, task duration, failure rates, and whether jobs are submitted via API or UI. Confirm the need for persistence, multi-tenancy, and monitoring.

2. Design Data Model and APIs

Define schemas for jobs, tasks, dependencies, and statuses. Specify REST APIs for submit, cancel, and status query, including idempotency keys and pagination.

3. Implement DAG Validation and Scheduling

Use topological sort or DFS for cycle detection. Design a scheduler that tracks in-degree of tasks and pushes ready tasks to a queue, with a worker pool consuming tasks up to a configurable limit.

4. Handle Failures, Retries, and Cancellation

Define retry policies (e.g., exponential backoff, max attempts) and failure propagation (e.g., skip dependents). Implement cancellation by marking tasks as cancelled and cleaning up running tasks.

5. Discuss Scalability and Trade-offs

Address scaling the scheduler (e.g., sharding by job ID), state store choices (SQL vs. NoSQL), and trade-offs like push vs. pull, at-least-once vs. exactly-once, and fairness vs. throughput.

Key Points to Mention

Cycle detection using DFS or Kahn's algorithm, with early rejection at submission time.
Dependency resolution via in-degree tracking and a ready queue, enabling parallel execution up to worker pool size.
State machine for task and job statuses (e.g., PENDING, RUNNING, SUCCEEDED, FAILED, CANCELLED) with atomic transitions.
Retry mechanisms with backoff and idempotent task execution to avoid duplicate side effects.
Cancellation semantics: propagate to running tasks, mark pending tasks as cancelled, and handle race conditions.
Scalability considerations: partitioning jobs, using a distributed queue (e.g., Kafka) and a durable state store (e.g., DynamoDB).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.