1. DAG 基础概念：有向无环图的定义、核心价值与队列对比
1.1 有向无环图的数学定义
有向无环图（Directed Acyclic Graph，DAG）是图论中一种特殊的有向图结构，它由顶点集合 V 和有向边集合 E 组成，且满足两个核心约束：
- 有向性：每条边
e = (u → v)具有明确的方向，表示从顶点u指向顶点v，u称为前驱，v称为后继。 - 无环性：图中不存在任何一条路径使得起点与终点重合，即不存在有向环。这是 DAG 区别于一般有向图的本质特征。
在任务调度语境下，每个顶点代表一个计算任务或数据处理单元，每条有向边代表任务之间的依赖关系——前驱任务必须完成后，后继任务才能开始执行。
关键推论：DAG 的拓扑排序保证了所有任务可以按照依赖顺序线性执行，且至少存在一种合法的执行序列。这是 DAG 能够驱动复杂工作流调度的数学基础。
1.2 DAG 在任务调度中的核心价值
DAG 之所以成为分布式任务调度的事实标准，源于以下四个不可替代的价值：
| 价值维度 | 具体描述 | 典型场景 |
|---|---|---|
| 依赖建模 | 精确表达任务间的数据依赖与控制依赖，避免竞态条件 | ETL 流水线、模型训练管线 |
| 并行度挖掘 | 无依赖关系的任务可并发执行，最大化资源利用率 | 数据分片处理、批量计算 |
| 容错边界 | 单任务失败仅影响其下游子图，支持局部重试与恢复 | Spark Stage 失败重算 |
| 可观测性 | 天然形成执行拓扑，便于追踪数据血缘与性能瓶颈 | Airflow 任务监控、数据血缘审计 |
架构启示：DAG 的价值不仅在于"能做什么"，更在于"不能做什么"——无环约束强制系统设计者显式管理依赖，从而避免死锁和无限循环，这是生产级调度系统的基本前提。
1.3 DAG 与普通任务队列的核心区别
普通任务队列（如 FIFO 队列、优先级队列）与 DAG 调度在架构理念上存在本质差异。下表从六个关键维度进行对比：
| 对比维度 | 普通任务队列 | DAG 调度 |
|---|---|---|
| 依赖表达 | 隐式或不存在，任务间无关联 | 显式有向边，精确描述前驱/后继 |
| 执行顺序 | 按入队顺序或优先级出队 | 按拓扑排序 + 就绪条件触发 |
| 并行策略 | 消费者线程池竞争消费 | 无依赖任务自动并行，依赖链串行 |
| 失败影响 | 单任务失败不影响其他任务 | 失败传播至下游，需局部重试或剪枝 |
| 数据传递 | 通常通过消息体或共享存储 | 边可携带数据引用、分区信息或传输策略 |
| 适用规模 | 适合无状态、独立任务 | 适合复杂工作流、多阶段流水线 |
常见误区：不要将 DAG 调度与"有向图调度"混为一谈。普通有向图若存在环，调度器必须引入循环检测与终止条件，否则会导致任务无限循环。DAG 的无环特性从根本上规避了这一问题。
1.4 DAG 调度架构示意
下图展示了一个典型的 DAG 任务调度拓扑，包含 6 个任务节点和 7 条依赖边，清晰呈现了分层依赖与并行执行的关系：
1.5 从队列到 DAG：架构演进路径
理解 DAG 与普通队列的区别后，可以梳理出一条清晰的架构演进路径：
- 单体队列阶段：所有任务进入单一 FIFO 队列，消费者按序处理。问题在于无法表达依赖，且并行度受限于消费者数量。
- 多级队列阶段：按任务类型或优先级拆分多个队列，引入简单的依赖检查。但依赖关系仍分散在业务代码中，难以维护。
- DAG 调度阶段：将依赖关系提升为图结构的一等公民，调度器根据拓扑排序自动决定执行顺序，数据传递通过边定义，实现调度逻辑与业务逻辑的解耦。
架构决策点：当系统中任务数量超过 50 个、依赖层级超过 3 层、或需要细粒度容错时，从队列模型迁移到 DAG 模型带来的收益将显著超过迁移成本。这是分布式系统架构中一个重要的"拐点判断"。
1.6 小结：DAG 作为调度原语
DAG 不仅仅是一种数据结构，更是一种调度原语。它将任务间的"时序约束"显式化为图结构，使得调度器可以：
- 通过拓扑排序自动推导合法执行序列
- 通过入度检测识别就绪任务，触发并行执行
- 通过子图隔离实现局部容错与重试
- 通过边属性携带数据传输策略，为数据流设计提供基础