3、DAG依赖模型：有向无环图原理、为什么用DAG、节点与边的定义、依赖关系的数学表达

聊到任务调度，绕不开一个核心概念——DAG。说白了，DAG就是一张图，图里的节点代表任务，边代表依赖关系，而且整个图里不能有环。为什么不能有环？你想想看，如果任务A依赖B，B依赖C，C又依赖A，那这三个任务谁先跑？谁也跑不了。这就是死锁。

我在项目中遇到过好几次这样的问题。有一次是数据管道，开发同学把依赖配反了，结果整个DAG提交上去就卡死，调度器直接报循环依赖错误。排查了半天，最后发现是配置里写了个环。从那以后，我养成了一个习惯：每次提交DAG之前，先手动检查一遍有没有环。

3.1 有向无环图的基本原理

DAG，全称Directed Acyclic Graph。拆开来看：

• 有向（Directed）：每条边都有方向，从上游指向下游。任务A → 任务B，表示A完成后才能跑B。
• 无环（Acyclic）：从任意节点出发，沿着边的方向走，永远回不到起点。没有闭环。
• 图（Graph）：由节点和边组成的结构。

嗯，这里要注意：DAG不要求图是连通的。你可以有多个独立的子图，每个子图内部没有环就行。比如你同时跑两个互不依赖的数据管道，它们就是两个独立的DAG。

3.2 为什么用DAG？

我刚开始做调度系统时，也想过：直接用列表不行吗？按顺序执行不就完了？后来发现，现实世界的任务依赖远没那么简单。

举个例子：你有一个数据报表任务，它依赖三个上游数据源。这三个数据源之间没有依赖关系，可以并行跑。如果用列表，你只能写成串行，白白浪费资源。用DAG，这三个上游节点可以同时执行，等它们都跑完了，再触发下游的报表任务。

DAG的好处，我总结了几点：

• 并行执行：没有依赖关系的节点可以同时跑，大幅缩短整体执行时间。
• 容错性：某个节点失败，只影响它的下游，不会波及整个流程。
• 可观测性：每个节点的状态一目了然，方便定位问题。
• 灵活性：可以动态增删节点，只要不破坏无环性质。

3.3 节点与边的定义

在DAG里，节点和边是最基本的元素。咱们来细说一下。

节点（Vertex）

节点代表一个具体的任务。每个节点通常包含以下信息：

属性	说明	示例
ID	节点的唯一标识	task_001
名称	任务的可读名称	数据清洗
类型	任务的具体操作类型	Shell、Spark、Python
状态	当前执行状态	等待中、运行中、成功、失败
超时时间	任务最长执行时间	3600秒
重试次数	失败后自动重试的次数	3

边（Edge）

边代表节点之间的依赖关系。一条边从上游节点指向下游节点，表示上游完成后下游才能开始。

边的类型通常有两种：

• 硬依赖：上游必须成功，下游才能执行。如果上游失败，下游直接跳过或等待。
• 软依赖：上游执行完成后，下游可以开始，不要求上游必须成功。这种场景比较少见，但某些监控或补偿任务会用到。

3.4 依赖关系的数学表达

从数学角度看，DAG可以用一个二元组来表示：G = (V, E)。

• V：节点的集合，V = {v₁, v₂, ..., vₙ}
• E：边的集合，E ⊆ V × V

每条边 (u, v) 表示从节点u到节点v的有向边，u是v的前驱，v是u的后继。

依赖关系可以用邻接矩阵或邻接表来表示。咱们看个简单的例子：

// 邻接矩阵表示法
// 行表示上游，列表示下游
// 1 表示存在依赖关系
// 0 表示没有依赖

     A  B  C  D
A    0  1  1  0
B    0  0  0  1
C    0  0  0  1
D    0  0  0  0

// 这个矩阵表示：
// A → B, A → C, B → D, C → D

在实际系统中，我更推荐用邻接表。为什么呢？因为大多数DAG是稀疏的，节点很多但边相对较少。邻接表节省空间，遍历也快。

// 邻接表表示法
// 每个节点记录它的后继节点列表

A: [B, C]
B: [D]
C: [D]
D: []

拓扑排序是DAG的核心算法。它的作用是把所有节点排成一个线性序列，保证每个节点都在它的所有前驱之后出现。常用的算法有两种：

• Kahn算法：基于入度，每次取出入度为0的节点。
• DFS后序遍历：深度优先遍历，按完成时间逆序输出。

我个人习惯用Kahn算法，因为它直观，而且能顺便检测环——如果最后还有节点没处理完，说明有环。

3.5 DAG的核心结构图

下面这张图展示了一个典型的DAG结构。你可以看到节点之间的依赖关系，以及拓扑排序后的执行顺序。

3.6 实际应用中的DAG设计

在真实项目中，DAG的设计有几个要点需要注意：

• 节点粒度：每个节点应该是一个原子操作。不要把一个复杂的ETL流程塞进一个节点里。
• 依赖深度：DAG的层级不要太深。我见过一个DAG有20多层，每次出问题排查起来特别痛苦。建议控制在5-7层以内。
• 并行度控制：虽然DAG支持并行，但也要考虑资源限制。如果同时跑100个任务，集群可能扛不住。可以加个全局并行度限制。
• 循环依赖检测：每次提交DAG时，一定要做环检测。我习惯用Kahn算法，时间复杂度O(V+E)，效率很高。

3.7 依赖关系的数学性质

最后，咱们聊聊依赖关系的数学性质。这些性质虽然抽象，但理解之后对设计调度系统很有帮助。

• 自反性：一个任务不依赖自己。DAG中不允许自环。
• 反对称性：如果A依赖B，那么B不能依赖A。否则就成环了。
• 传递性：如果A依赖B，B依赖C，那么A间接依赖C。在调度时，C必须先于A执行。

这些性质保证了DAG的偏序关系。说白了，就是任务之间有一个明确的先后顺序，不会出现循环等待的情况。