DAG 基础理论：有向无环图的调度基石
聊任务调度，绕不开 DAG。说白了，DAG 就是一张图，图里的边有方向，而且整个图里没有环路。我刚开始接触分布式调度时，总觉得这概念太理论，后来被线上一个死循环任务坑过一次，才真正明白 DAG 为什么是调度的基石。
有向无环图的定义
DAG 的全称是 Directed Acyclic Graph。拆开来看：
- 有向（Directed）：每条边都有方向，从 A 指向 B，表示 A 完成后才能开始 B。
- 无环（Acyclic）：从任意节点出发，沿着边的方向走，永远回不到起点。
- 图（Graph）：由节点（Vertex）和边（Edge）组成的数据结构。
举个例子，你想想看，一个数据管道：采集 → 清洗 → 聚合 → 输出。这就是典型的 DAG。采集指向清洗，清洗指向聚合，聚合指向输出，没有回头路。
核心要点：DAG 保证了任务之间只有单向依赖，不会出现 A 等 B、B 等 A 的死锁情况。这是它能用于调度的根本原因。
DAG 在调度中的角色
DAG 在调度系统里扮演什么角色？我个人的理解是——依赖关系的骨架。
具体来说，DAG 帮我们解决了三个核心问题：
- 执行顺序：哪些任务必须先跑，哪些可以并行。
- 资源规划：根据 DAG 的层级，提前分配计算资源。
- 故障恢复：某个节点挂了，只需要重跑它的上游，下游不受影响。
我记得在做一个实时数仓项目时，业务方要求每天凌晨 3 点前必须产出报表。我们用 DAG 把 200 多个任务串起来，哪个环节慢了，一眼就能看出瓶颈在哪。没有 DAG，这种规模的调度根本没法管理。
个人经验：设计 DAG 时，尽量让每个节点的粒度适中。太细了，图会变得臃肿，调度开销大；太粗了，并行度不够，资源利用率低。我一般控制在每个节点执行 5-15 分钟为宜。
DAG 的拓扑排序原理
拓扑排序，就是把 DAG 里的所有节点排成一个线性序列，保证每个节点都在它的所有依赖节点之后出现。说白了，就是给任务排个队，谁先谁后，清清楚楚。
算法其实不复杂，我常用的方法是 Kahn 算法：
// 伪代码：Kahn 拓扑排序
function topologicalSort(graph):
inDegree = 计算每个节点的入度
queue = 所有入度为 0 的节点
while queue 不为空:
node = queue.dequeue()
result.append(node)
for neighbor in graph[node]:
inDegree[neighbor]--
if inDegree[neighbor] == 0:
queue.enqueue(neighbor)
if result.length != graph.nodes.length:
return "存在环，无法拓扑排序"
return result这个算法的核心思想很简单：先处理没有依赖的任务，然后逐步释放下游。每处理完一个节点，就把它的出边删掉，看有没有新的节点变成「无依赖」状态。
你可能会问，为什么入度为 0 就能执行？因为入度表示有多少个前置任务。入度为 0，说明所有前置都跑完了，当前任务可以放心启动。
避坑指南：我曾经在线上遇到过一个问题——拓扑排序结果不唯一。两个没有依赖关系的任务，谁先谁后？这会影响资源分配和最终结果吗？答案是：如果任务之间没有共享状态，顺序无所谓；如果有共享资源，需要额外加锁或依赖约束。
DAG 的合法性校验
合法性校验，说白了就是检查你画的 DAG 是不是真的「无环」。环是调度系统的头号杀手，一旦出现环，任务就会无限循环，资源被吃光，系统直接瘫痪。
校验方法主要有三种：
| 方法 | 原理 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| DFS 染色法 | 深度遍历，标记节点状态（未访问/访问中/已访问），遇到「访问中」即存在环 | O(V+E) | 小规模 DAG，需要精确定位环的路径 |
| Kahn 算法 | 拓扑排序，如果最终排序节点数少于总节点数，说明有环 | O(V+E) | 大规模 DAG，只需要判断是否有环 |
| 并查集 | 合并节点集合，如果两个节点已经在同一集合中，说明有环 | O(V·α(V)) | 动态添加边时实时校验 |
我个人最常用的是 Kahn 算法，原因很简单：它不仅能检测环，还能顺便给出拓扑排序结果，一举两得。DFS 染色法虽然能定位环的具体路径，但实现起来稍微复杂一些。
关键点：合法性校验不能只在提交 DAG 时做一次。运行时也要做，因为某些调度系统支持动态添加任务。我见过一个案例，运维同学手动补数据时加了一条边，结果形成了环，整个集群卡了半小时。
下面这张图展示了 DAG 的核心概念和校验流程：
工程建议：生产环境中，我建议把 DAG 校验做成一个独立的服务。每次提交 DAG 时，先调这个服务做合法性检查，通过后再写入存储。这样即使调度系统重启，校验逻辑也不会丢失。
嗯，DAG 的基础理论就这些。理解清楚定义、角色、拓扑排序和合法性校验，后面讲具体调度算法时，你会觉得顺滑很多。