Distributed Task Scheduler

DAG workflows on a sharded scheduler

Design a scheduler that runs workflows of dependent tasks (DAGs) across many workers: tasks start only when their upstreams succeed, several schedulers share the work safely, and duplicate runs are expected and made harmless.

Overview

A workflow scheduler runs pipelines of dependent tasks: extract yesterday's orders, then clean and enrich them in parallel, then join the results, then publish a report and an export. Each pipeline is a DAG (directed acyclic graph): tasks are nodes, and an edge from A to B means B may start only after A succeeds. Every day, or on some trigger, the scheduler creates a run of the DAG and walks it: whenever a task's upstreams are done, the task becomes ready and is handed to a worker.

The Job Scheduler topic covers firing single jobs on time (cron, time zones, claiming runs). This problem is about what sits on top: dependencies, many scheduler processes working at once, and the correctness traps that come with them. Interviewers probe three things. How does the scheduler decide what is ready, cheaply, for thousands of runs? How do several schedulers split the work without two of them acting on the same run? And what happens to 'exactly once' when a scheduler pauses for thirty seconds and wakes up thinking it is still in charge?

Questions to ask first

What is a workflow? — A DAG of tasks defined in code or config; about 20 tasks on average
How much work? — 50,000 DAGs, 200,000 runs a day, 30% of them starting in the hour after midnight UTC
Task length? — Seconds to hours; the scheduler never runs task code itself
What does 'succeeded' mean? — The worker reported success; retries happen inside the task's retry policy
Can a task run twice? — Yes, rarely; tasks must be idempotent, and the platform says so
Availability? — Scheduling continues if any scheduler process or machine dies

What you will be able to do

Model a workflow as a DAG, find ready tasks, propagate failures and compute the critical path.
Store run and task state so that 'what is ready now' is one indexed query.
Split scheduling across shards with leases, and elect a leader for work only one process may do.
Use fencing tokens so a paused, deposed scheduler cannot corrupt state.
Explain what exactly-once really means here and how to get the effect of it.

Key concepts

DAG
Topological order
Trigger rules
Upstream failed
Critical path
Scheduler shards
Leases
Leader election
Fencing tokens
At-least-once plus idempotency

Functional requirements

Define a workflow as a DAG of tasks; reject definitions with cycles
Create runs on a schedule, on demand, or for a range of past dates (backfill)
Start a task when its trigger rule is met (by default, all upstreams succeeded)
Retry failed tasks per policy; mark downstream tasks upstream_failed when a dependency fails
Limit concurrency per DAG and per resource pool
Clear and rerun a failed task and everything downstream of it

Non-functional requirements

A ready task is queued within 5 seconds (a target we chose)
No run is lost or stuck if a scheduler process dies
No two schedulers act on the same run at the same time; a deposed one cannot write
Tasks may run more than once; the platform guarantees at least once and documents it
Scheduling scales out by adding scheduler processes

Interview questions

How does the scheduler decide a task is ready?
Can the scheduler guarantee each task runs exactly once?
How do several schedulers avoid stepping on each other?
What is a fencing token and why do you need it?
How would you implement leader election?
A daily DAG takes 6 hours. How do you make it faster?
How do you stop one team's backfill from starving everyone else?
How is this different from the job scheduler design?