第4章：有向无环图（DAG）构建方法

聊到CI并行任务调度，核心就一个字——依赖。没有依赖关系，你大可以一股脑全丢给机器跑；有了依赖，就必须排个先后顺序。怎么排？靠的就是有向无环图，也就是DAG。

DAG这东西，说简单也简单，说复杂也复杂。简单在于它就是个图，节点是任务，边是依赖。复杂在于你一旦构建错了，轻则任务卡死，重则整个pipeline崩溃。我见过太多团队上来就写个拓扑排序，结果跑起来一团乱麻。今天咱们就掰开揉碎，把DAG的构建方法讲明白。

4.1 为什么非要用DAG？

你想想看，CI里任务之间天然就有前后关系。编译必须在测试之前，测试又必须在部署之前。这种关系用树形结构也勉强能描述，但树不允许交叉依赖——而项目里很多场景恰恰需要交叉。

举个例子：你有一个单元测试任务，它依赖于编译任务A和编译任务B的产物。树形结构没法表达“两个爹一个娃”的关系，但DAG可以。

我记得早期在一个微服务项目中，团队用了一个简单的列表来硬编码执行顺序。后来服务数量从10个涨到50个，那个列表变成了噩梦——每次加一个服务都得手动调整几百行的执行顺序。后来我引入了DAG，整个流程自动化了。说白了，DAG不只是技术选择，更是工程管理的必然产物。

4.2 DAG的两种构建策略

构建DAG，我习惯把它分成两种思路：自顶向下和自底向上。不同的项目规模、不同的团队习惯，适合不同的策略。

策略	适用场景	优点	缺点
自顶向下	单仓库、模块间依赖清晰	逻辑直观，容易理解	依赖关系定义容易遗漏
自底向上	多仓库、服务架构	从底层模块开始，避免循环依赖	构建过程需要更细致的分析

4.2.1 自顶向下构建法

这种方式，说白了就是你先画出整个流程的>顶层任务，然后逐层拆解。比如一个典型的CI流程：代码提交 → 编译 → 单元测试 → 打包 → 部署。顶层节点就是这些大任务，再展开每个大任务下的子任务。

具体步骤：

1. 列出所有任务节点（每个节点对应一个CI任务）。
2. 确定每个节点的直接前置任务（依赖什么）。
3. 检查是否有孤立节点（没有依赖也没有被依赖）。
4. 检查是否有循环依赖（A依赖B，B依赖C，C依赖A —— 不行）。
5. 生成有向边列表。

我曾经在一个项目里用这种思路，但忽略了“编译产出”这个任务居然被两个不同模块依赖。还好在测试阶段捕获到了，不然部署的时候还要重新编译一遍。嗯，这里要注意：自顶向下容易遗漏隐式依赖，比如共享产物、共享环境变量等。

4.2.2 自底向上构建法

这种方法更适合微服务或monorepo。你先找出哪些任务没有前置依赖——这些就是“叶子节点”，或者说最基础的底层任务。然后一步步往上推，直到所有任务都被包含。

举个例子，一个Java项目里有三个模块：common、service-a、service-b。service-a依赖common，service-b也依赖common。用自底向上，你先把common的编译和测试作为底层，然后service-a和service-b在它的基础上并行执行。

4.3 DAG构建的核心数据结构

DAG在内存里怎么存？常用两种：邻接矩阵和邻接表。CI场景里任务数通常几十到几百，我推荐用邻接表——节省空间，遍历也快。

一个简单的邻接表示例：

# 定义节点
nodes = ["compile", "unit_test", "integration_test", "package", "deploy"]

# 定义依赖（有向边）
edges = {
    "unit_test": ["compile"],
    "integration_test": ["compile"],
    "package": ["unit_test", "integration_test"],
    "deploy": ["package"]
}

注意：compile没有在edges的key中，说明它是入度为0的节点。拓扑排序就从这里开始跑的。

4.4 如何检测循环依赖？

构建DAG时，最怕的就是出现环。一旦有环，拓扑排序就无解了。我见过一个团队把整个CI跑死，就是因为A→B→C→A这种循环。

检测方法很简单——用DFS。每个节点标记三种状态：未访问、访问中、已访问。如果DFS过程中再次遇到“访问中”的节点，说明有环。

伪代码如下：

function has_cycle(graph):
    WHITE = 0   # 未访问
    GRAY = 1    # 访问中
    BLACK = 2   # 已访问

    color = {node: WHITE for node in graph.nodes}

    def dfs(node):
        if color[node] == GRAY:
            return True  # 发现环
        if color[node] == BLACK:
            return False
        color[node] = GRAY
        for neighbor in graph.neighbors(node):
            if dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    for node in graph.nodes:
        if dfs(node):
            return True
    return False

我曾经在一个大型monorepo里因为依赖关系写了几个自动生成的脚本，结果某次整合时引入了循环。那个检测脚本救了我——在CI的pre-check阶段就报错了，避免了把错误提交推送到远程。

4.5 DAG的响应式构建流程

实际项目中，DAG往往是动态的。比如：编译任务运行后，如果失败了，后面依赖它的测试任务就不该运行。这需要支持修剪——根据运行结果动态移除下游节点。

我习惯把DAG构建分成三个阶段：

1. 静态构建：解析配置文件，生成全量DAG。
2. 动态修剪：根据上游任务的运行状态（成功/失败/跳过），裁剪不可达节点。
3. 调度执行：使用拓扑排序生成可并行执行的批次，交给执行器。

三个阶段对应的数据变化：

阶段	输入	输出
静态构建	依赖描述文件（yaml/json）	初始DAG（所有节点+边）
动态修剪	初始DAG + 上游任务状态	子DAG（可达节点）
调度执行	子DAG	批次列表（每批可并行）

下面这张图展示了从依赖描述到可执行批次的全流程：

4.6 构建DAG时的常见陷阱

我见过很多新手在构建DAG时踩的坑，这里列几个最典型的：

• 遗漏隐式依赖：比如两个任务都使用同一个共享目录，但没有显式声明依赖。哦豁，并发写入导致数据错乱。
• 过度依赖：把所有任务都串成一个链，明明可以并行却搞成了串行。调度效率打折扣。
• 忽略资源竞争：即使任务之间没有数据依赖，但它们可能竞争同一台机器的CPU或内存。DAG只能管逻辑依赖，管不了资源依赖——这块交给调度器去处理。
• 超大DAG导致内存爆炸：如果你在一个monorepo里把每个文件变更都作为一个节点，DAG可能上万个节点。注意做粒度控制，我通常把粒度控制在“模块”级别，而不是“文件”级别。

4.7 小结

DAG构建是CI并行调度的基石。记住三个要点：

1. 明确依赖关系，用邻接表存储。
2. 自动化检测循环依赖，不要靠人肉。
3. 区分静态构建和动态修剪，支持失败情况下的任务裁剪。