2. DAG基础概念：有向无环图定义、顶点与边、拓扑排序、DAG在任务调度中的应用场景
2.1 有向无环图（DAG）定义
有向无环图（Directed Acyclic Graph，简称DAG）是图论中的一种特殊结构，由一组顶点（Vertex）和一组有向边（Directed Edge）组成，且图中不存在任何环路。这意味着从任意一个顶点出发，沿着有向边的方向行进，永远无法回到该顶点。
在任务调度领域，DAG是描述任务依赖关系的标准数学模型。每个顶点代表一个任务单元，每条有向边代表任务之间的依赖约束（即前驱任务完成后才能执行后继任务）。
核心特征： DAG保证了任务执行的无环性，这是调度系统避免死锁和循环依赖的数学基础。任何包含环路的图都不能作为合法的任务调度模型。
2.2 顶点与边
DAG由两个基本元素构成，其定义和属性如下表所示：
| 元素 | 符号 | 定义 | 在任务调度中的含义 |
|---|---|---|---|
| 顶点（Vertex） | V | 图中的节点，表示一个独立实体 | 一个具体的任务、作业或计算步骤 |
| 有向边（Directed Edge） | E | 从一个顶点指向另一个顶点的箭头，表示方向性关系 | 任务之间的依赖约束：前驱→后继 |
| 入度（In-degree） | deg⁻(v) | 指向该顶点的边的数量 | 该任务依赖的前驱任务个数 |
| 出度（Out-degree） | deg⁺(v) | 从该顶点出发的边的数量 | 该任务被多少个后继任务依赖 |
顶点与边的关键规则：
- 每个顶点可以有多个前驱（入度 > 1），表示该任务需要等待多个上游任务完成。
- 每个顶点可以有多个后继（出度 > 1），表示该任务的结果被多个下游任务使用。
- 入度为0的顶点称为源点（Source），代表可立即执行的任务。
- 出度为0的顶点称为汇点（Sink），代表最终产出任务。
2.3 拓扑排序
拓扑排序（Topological Sorting）是对DAG中所有顶点的一种线性排序，使得对于每条有向边 u→v，顶点 u 在排序中都出现在顶点 v 之前。拓扑排序是任务调度系统确定执行顺序的核心算法。
拓扑排序的经典算法（Kahn算法）：
- 计算所有顶点的入度。
- 将所有入度为0的顶点加入队列（这些任务可以立即执行）。
- 从队列中取出一个顶点，将其加入拓扑序列。
- 移除该顶点的所有出边，并将这些边指向的顶点的入度减1。
- 如果某个顶点的入度变为0，将其加入队列。
- 重复步骤3-5，直到队列为空。
- 如果拓扑序列中的顶点数等于图中的顶点总数，则排序成功；否则图中存在环。
实践要点： 在分布式任务调度中，拓扑排序不仅用于确定执行顺序，还用于并行度分析。同一层级的顶点（入度同时变为0的任务）可以并行执行，这是调度系统优化吞吐量的关键依据。
拓扑排序结果示例： 对于上图中的DAG，可能的拓扑排序序列为：A → B → C → D 或 A → C → B → D。两种序列都满足依赖约束，说明DAG的拓扑排序不一定唯一。
2.4 DAG在任务调度中的应用场景
DAG模型在任务调度领域有广泛的应用，覆盖从批处理到实时流计算的多种场景。下表总结了典型应用场景及其DAG特征：
| 应用场景 | 顶点含义 | 边含义 | 典型系统 |
|---|---|---|---|
| 数据管道（ETL） | 数据抽取、转换、加载步骤 | 数据上下游依赖 | Apache Airflow, Azkaban |
| 分布式计算作业 | Map/Reduce/Join 算子 | 数据shuffle依赖 | Apache Spark, MapReduce |
| CI/CD流水线 | 代码检查、编译、测试、部署 | 阶段执行顺序 | Jenkins Pipeline, GitLab CI |
| 工作流编排 | 微服务调用、API编排 | 服务调用链 | Apache DolphinScheduler, Temporal |
| 机器学习训练 | 数据预处理、模型训练、评估 | 数据/模型依赖 | Kubeflow, MLflow |
2.5 DAG在任务调度中的核心价值
DAG模型为任务调度系统提供了以下关键能力：
- 依赖管理： 通过有向边精确表达任务间的先后顺序和数据依赖，避免人工维护复杂的执行顺序。
- 并行执行： 拓扑排序自动识别可并行执行的任务层级，最大化资源利用率和系统吞吐量。
- 容错与重试： 当某个任务失败时，调度系统可以基于DAG结构精确计算受影响的下游任务，实现局部重试而非全局重启。
- 可视化与可观测性： DAG天然适合图形化展示，帮助运维人员直观理解任务执行状态和瓶颈。
- 动态扩展： 新增任务只需在DAG中插入新的顶点和边，不影响已有任务的拓扑结构。
常见误区： 并非所有任务依赖关系都适合用DAG建模。例如，循环依赖（任务A依赖B，B依赖A）在DAG中是不允许的。在实际系统中，循环依赖通常需要通过异步解耦或引入中间状态来打破。
2.6 小结
DAG作为任务调度的核心数学模型，通过顶点表示任务、有向边表示依赖、拓扑排序确定执行顺序，为分布式系统提供了严谨且灵活的任务编排能力。理解DAG的基础概念是后续学习服务边界划分和接口契约设计的必要前提。