DAG Scheduling
Scheduling a directed acyclic graph means choosing a valid task order and deciding when and how often the whole graph executes.
Ordering a graph
A directed acyclic graph of tasks has no single order, but it has many valid orders, all respecting the dependency edges. Producing one is topological sort: repeatedly emit a task with no unsatisfied dependencies, remove it, and continue. If at some point no such task exists but tasks remain, the graph has a cycle and cannot be scheduled. Orchestrators run this check before execution.
Parallelism within an order
Topological order is not unique precisely because independent tasks can run at the same time. The scheduler exploits this: after each task finishes it releases its dependents, and any dependent whose prerequisites are all complete becomes eligible immediately. The effective runtime is governed by the graph's critical path, the longest chain of dependent tasks, not by the total task count.
Triggers: time and event
- Cron schedules: run at fixed wall-clock times or intervals
- Data-availability triggers: run when an upstream partition lands
- Sensor tasks: poll a condition and unblock the DAG when it holds
- Manual triggers: an operator kicks off a run on demand
Intervals and idempotency keys
Scheduled pipelines usually process a bounded slice of time, an interval such as one day. Each run is stamped with the interval it owns and writes to a partition named for that interval. This makes runs idempotent and reruns safe: re-executing the 2027-03-01 interval overwrites exactly that day's partition. It also makes backfills possible, running a range of past intervals to reconstruct history after a logic change.
Handling late and missing data
Real inputs arrive late or not at all. A scheduler must decide whether to wait, proceed with what is present, or fail. Common patterns are a bounded wait window, a sensor that blocks until data lands, and an explicit data-quality gate that fails the run rather than propagating incomplete output. The choice depends on whether downstream consumers prefer freshness or completeness. See workflow orchestration and partitioning.