The pipeline as a graph — why DAG, not stages, is the right mental model

A pipeline is a directed acyclic graph. Nodes are jobs; edges are dependencies. The graph is what the scheduler walks. The “stages” model is one particular graph: a totally ordered chain. The DAG model is the more general one, and the model every modern CI vendor implements.

Nodes and edges

Nodes are jobs. Edges are dependencies: an edge from A to B means “B cannot start until A has completed”. The edge is the ordering guarantee; the absence of an edge is the opportunity for parallelism.

flowchart LR
    L["lint"] --> T["test"]
    L --> S["scan"]
    T --> P["package"]
    S --> P

File order is not execution order; the DAG is the contract.

DAG versus stages

The stages model forces every job in stage N to wait for every job in stage N-1: convenient when dependencies are regular, painful when they are not. The DAG model removes the constraint: a job declares exactly the predecessors it needs. Every edge is deliberate; every missing edge is deliberate too.

Reading the DAG from a workflow file

The graph is implicit in needs: clauses. Reading every job’s needs: list yields (job, predecessors) pairs; plotting them yields the DAG.

grep -E '^  [a-z-]+:$|needs:' .github/workflows/ci.yml

A reviewer who reads the DAG sees the actual execution order.

What the scheduler does

The scheduler builds the DAG in memory and maintains a “ready” set of jobs whose incoming edges are all satisfied. It starts every ready job as soon as a runner is available. The algorithm is topological: a job never starts before its predecessors.

Wall-clock cost is the critical path, not the sum of job durations.

Production discipline

1. Draw the DAG before merging.
2. File order is irrelevant; the DAG is the execution order.
3. Review needs: for every job.
4. Watch for unintended fan-in.

Cross-course references

• Ansible for Production Sysadmins - Part XXXVII (RepoArch) applies the same DAG concept to AWX workflows.
• Linux for Production Sysadmins - Part XXX uses DAG concepts for systemd After=.

Quiz