2. DAG（有向无环图）原理：DAG的定义、节点与边的含义、拓扑排序的概念、环检测的重要性

聊任务依赖，绕不开 DAG。说白了，DAG 就是一张图，图里的箭头表示「谁先谁后」，而且不能有循环依赖。我当年第一次接触工作流引擎时，就被 DAG 这个概念卡了很久——总觉得它太抽象。后来亲手画了几张图，才明白它其实特别直观。

2.1 DAG 的定义

DAG，全称 Directed Acyclic Graph，中文叫「有向无环图」。拆开来看：

• 有向（Directed）：每条边都有方向，从 A 指向 B，表示 A 必须在 B 之前完成。
• 无环（Acyclic）：沿着箭头走，永远回不到起点。不存在 A→B→C→A 这种死循环。
• 图（Graph）：由节点和边组成的数据结构。

举个例子。你想想看，一个软件构建流程：编译 → 链接 → 打包 → 部署。编译完了才能链接，链接完了才能打包，打包完了才能部署。这就是一个典型的 DAG。如果编译又依赖部署的结果，那就成环了，整个流程就卡死了。

2.2 节点与边的含义

在任务调度场景下，DAG 的两个基本元素有明确的业务含义：

元素	符号	含义	举例
节点（Node）	V（Vertex）	一个具体的任务或步骤	数据清洗、模型训练、报表生成
边（Edge）	E（Edge）	任务间的依赖关系	「数据清洗」→「模型训练」

我个人习惯把节点想象成「要做的事」，把边想象成「做完这个才能做那个」。每个节点可以有多个入边（依赖多个前置任务）和多个出边（被多个后续任务依赖）。

2.3 拓扑排序的概念

拓扑排序，就是把 DAG 里的所有节点排成一个线性序列，保证每个节点都在它的所有依赖节点之后出现。说白了，就是「先干谁，后干谁」的最终答案。

算法很简单，两步走：

1. 从图中找一个入度为 0 的节点（没有前置依赖的任务），输出它。
2. 把这个节点从图中删掉，同时删掉它所有的出边。重复第一步，直到所有节点都被输出。

如果图里有环，那第二步就会卡住——永远找不到入度为 0 的节点。这就是环检测的用武之地。

下面是一个简单的拓扑排序代码示例，用 Python 写的：

def topological_sort(graph):
    # graph: dict, key=节点, value=依赖列表
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for dep in graph[node]:
            in_degree[dep] = in_degree.get(dep, 0) + 1

    queue = [node for node in graph if in_degree[node] == 0]
    result = []

    while queue:
        node = queue.pop(0)
        result.append(node)
        for dep in graph.get(node, []):
            in_degree[dep] -= 1
            if in_degree[dep] == 0:
                queue.append(dep)

    if len(result) != len(graph):
        raise ValueError("图中存在环，无法拓扑排序")
    return result

这段代码我用了很多年，核心逻辑没变过。你注意看最后那个环检测——如果输出的节点数不等于总节点数，说明有环。嗯，这里要特别留意。

2.4 环检测的重要性

环检测为什么重要？我曾经在一个数据管道项目里吃过亏。当时系统跑得好好的，突然某天凌晨任务全部卡死。排查了一整夜，最后发现是某个同事不小心加了一条反向依赖，形成了一个环。从那以后，我每次提交 DAG 配置前，都会先跑一遍环检测。

环带来的问题很直接：

• 死锁：任务互相等待，谁也跑不了。
• 资源浪费：调度器反复重试，CPU 和内存被白白消耗。
• 数据不一致：部分任务执行了，部分没执行，中间状态不可控。

环检测的常用方法有两种：

方法	原理	复杂度	适用场景
DFS（深度优先搜索）	遍历时标记节点状态，遇到已访问的节点即发现环	O(V+E)	小规模 DAG，实时检测
拓扑排序（Kahn 算法）	统计入度，逐步移除入度为 0 的节点	O(V+E)	大规模 DAG，批量检测

我个人更推荐拓扑排序法。原因很简单：它不仅能检测环，还能直接给出一个可执行的顺序。一举两得。

2.5 DAG 核心逻辑图

下面这张图展示了 DAG 的核心概念和它们之间的关系。我画这张图时，特意把节点、边、拓扑排序和环检测放在一起，方便你理解整体脉络。

从这张图你可以看到，DAG 是基础，节点和边是它的构成要素，拓扑排序是它的输出方式，环检测是它的安全阀。四者缺一不可。

2.6 避坑指南

最后，分享几个我踩过的坑：

• 别把 DAG 设计得太复杂：节点超过 1000 个时，拓扑排序和环检测的性能会明显下降。我建议按业务域拆分 DAG，每个 DAG 控制在 200 个节点以内。
• 环检测不能只做一次：DAG 是动态的，任务配置可能随时变更。每次变更后都要重新检测。我曾经因为忽略了这一点，导致线上事故。
• 注意隐式环：有些环不是直接 A→B→A，而是 A→B→C→D→A，绕了一大圈。拓扑排序法能自动发现这种隐式环，DFS 需要额外处理。