任务依赖关系与 DAG

聊到并行调度，有个东西绕不过去——任务之间的依赖关系。

说白了，就是哪个任务必须先跑完，哪个才能开始。比如，编译没完成，单元测试就没法跑。这是个很朴素的逻辑，但一旦任务多了、流水线复杂了，靠人脑去记谁先谁后就变得不现实了。

所以，我们得用一种图结构来描述它。我个人最常用，也是业界最通用的，就是有向无环图，简称 DAG（Directed Acyclic Graph）。

在实际项目中，我见过团队把任务依赖写成了一团乱麻，结果调度器卡住了。排查了半天，发现是人为加了个环形依赖。嗯，这事后来我专门写了个脚本，每次提交流水线定义文件时就做一次环路检测。

DAG 的基本元素

咱们拆开来看，一个 DAG 主要由两部分组成：节点和边。

元素	代表什么	举个例子
节点（Vertex）	一个 CI 任务	编译、测试、打包、部署
边（Edge）	任务间的依赖	测试必须在编译之后

节点里存的是任务信息，比如任务名、执行脚本、超时时间、资源需求等。边则是用来连接这些节点的箭头。

为什么叫“有向”？你想想看，箭头是有方向的。如果说“测试依赖编译”，那箭头就是从编译指向测试。反着来，就不对。

任务依赖的几种常见类型

不是所有依赖关系都一样。根据我的经验，可以分成这么几类：

• 线性依赖：任务一个接一个，串行执行。比如 A→B→C。这是最简单的，但也是最慢的。
• 扇出依赖：一个任务完成，触发多个并行任务。比如编译完，同时跑单元测试和静态分析。
• 扇入依赖：多个任务都完成后，才能触发下一个任务。比如所有单元测试都跑完了，才能进行集成测试。
• 混合依赖：上述几种的组合。在实际项目中，大部分 DAG 都是混合的。

我记得有个项目，光单元测试就分了 8 组，每个组跑不同的模块。如果全串行跑，要 40 分钟。但只要把它们的依赖关系理清楚，做成扇出结构，8 组并行跑，时间就缩短到 5 分多钟。效果非常明显。

给大家看一个简单的 DAG 示例，这是用 Python 的 networkx 库画出来的结构，你也可以在代码中定义它：

# 一个简单的 DAG 定义示例
# 节点：编译、单元测试、集成测试、打包、部署
# 依赖关系：
# 编译 -> 单元测试
# 编译 -> 集成测试
# 单元测试 -> 打包
# 集成测试 -> 打包
# 打包 -> 部署

tasks = {
    "编译": [],
    "单元测试": ["编译"],
    "集成测试": ["编译"],
    "打包": ["单元测试", "集成测试"],
    "部署": ["打包"]
}

你看，这个依赖已经形成了扇出（编译到两个测试）和扇入（打包等待两个测试都完成）。

如何把 CI 流程映射为 DAG

我一直在强调，DAG 不是凭空产生的，它是你 CI 流程的抽象。怎么把你的 Jenkinsfile 或 .gitlab-ci.yml 变成一张图？

1. 列任务：把流水线里所有独立的任务列出来。
2. 找依赖：问自己，“这个任务需要上游的什么产出？比如编译产物、测试结果、代码仓库版本。” 这才是依赖的本质。
3. 画箭头：根据依赖关系，把箭头画出来。
4. 检查环路：从头到尾走一遍，确认没有循环依赖。

我曾经遇到过一个团队，他们把“代码检查”和“编译”搞成了互相依赖。代码检查需要编译后的二进制去跑一些规则检查，编译又要等代码检查通过才能触发。你看，这就形成了一个环。在那个场景下，我们最后把代码检查拆成了两个阶段，才解决了问题。

下面这张图，用一个简单的例子总结了一下任务依赖关系和 DAG 的映射过程。

DAG 的设计原则

画 DAG 看起来简单，但设计好并不容易。我给自己定过几个小规矩：

• 保持 DAG 扁平：不要让依赖链太长。过长的链意味着串行步骤多，并行度被浪费了。
• 叶子节点尽早合并：多个并行任务结束后，尽快合并到下一阶段。合并得越早，资源回收得越快。
• 适度粒度：任务拆得太细，DAG 会变得很复杂，调度开销会增加。拆得太粗，并行度又不够。我一般建议一个任务控制在 2-10 分钟之间。

DAG 是并行调度的基础。你把依赖关系梳理清楚了，调度器才能高效地工作。否则，你连让任务并行跑的资格都没有。