📚 课程目录第4章 DAG调度引擎

4、DAG调度引擎：有向无环图构建、拓扑排序、并行调度策略

聊到增量计算，DAG（有向无环图）调度引擎是核心中的核心。你可以把它想象成整个任务编排的“大脑”——它决定了哪些任务先跑，哪些可以并行，哪些必须等前面的兄弟干完活才能动。

我刚开始接触分布式调度时，总觉得DAG不就是画个图嘛，有啥难的？后来踩过几次坑才明白，图的构建质量、拓扑排序的效率、并行度的控制，每一个环节都能让你欲哭无泪。今天咱们就把这块掰开揉碎了讲。

4.1 有向无环图的构建：从任务依赖到数据结构

说白了，DAG就是一组节点（任务）和一组有向边（依赖关系）的组合。关键约束是——不能有环。一旦出现环，调度器就死循环了，任务永远跑不完。

我习惯用邻接表来存储DAG。为什么不用邻接矩阵？因为任务调度场景下，图通常是稀疏的，邻接表更省内存，遍历后继节点也更高效。

// 邻接表表示的DAG结构
class DAG {
    // 节点ID -> 节点元数据
    Map<String, TaskNode> nodes;
    // 节点ID -> 后继节点ID列表
    Map<String, List<String>> adjacencyList;
    // 节点ID -> 入度（有多少前置依赖）
    Map<String, Integer> inDegree;
}

构建DAG时，有几个坑我提醒你注意：

依赖传递性：A依赖B，B依赖C，那A其实也间接依赖C。但DAG里我们只存直接依赖，间接依赖靠拓扑排序自动推导。
重复依赖：同一个依赖关系被添加两次，入度会翻倍，导致调度器以为还有前置任务没完成。我遇到过这种bug，排查了一下午。
自环：任务依赖自己，这在代码里很容易写出来，但运行时就是死锁。

注意： 构建DAG时一定要做环检测。我建议在每次添加边之后，用DFS或拓扑排序验证一下。别等到运行时才发现，那时候任务已经卡死了。

4.2 拓扑排序：给任务排个队

拓扑排序就是把DAG里的节点排成一个线性序列，保证每个节点都在它的所有前置节点之后出现。说白了，就是告诉调度器：“按这个顺序跑，肯定没问题。”

最经典的算法是Kahn算法（基于入度）和DFS后序遍历。我个人更偏爱Kahn算法，因为它天然支持并行调度——每次入度为0的节点都可以同时执行。

// Kahn算法拓扑排序
List<String> topologicalSort(DAG dag) {
    Queue<String> readyQueue = new LinkedList<>();
    Map<String, Integer> inDegree = dag.getInDegree();
    
    // 初始化：入度为0的节点入队
    for (String nodeId : inDegree.keySet()) {
        if (inDegree.get(nodeId) == 0) {
            readyQueue.offer(nodeId);
        }
    }
    
    List<String> result = new ArrayList<>();
    while (!readyQueue.isEmpty()) {
        String current = readyQueue.poll();
        result.add(current);
        
        // 减少后继节点的入度
        for (String successor : dag.getSuccessors(current)) {
            int newDegree = inDegree.get(successor) - 1;
            inDegree.put(successor, newDegree);
            if (newDegree == 0) {
                readyQueue.offer(successor);
            }
        }
    }
    
    // 如果result长度不等于节点总数，说明有环
    if (result.size() != dag.size()) {
        throw new RuntimeException("DAG中存在环！");
    }
    return result;
}

这里有个细节：拓扑排序的结果不唯一。入度为0的节点可能有多个，你选哪个先处理，结果序列就不同。但没关系，只要保证依赖关系正确，任何合法拓扑序都能用。

4.3 并行调度策略：让任务飞起来

拓扑排序只是给了你一个可行的执行顺序，但真正的调度引擎要解决的是——如何最大化并行度。

你想想看，如果严格按照拓扑序一个一个跑，那跟串行有啥区别？DAG的价值就在于，那些没有依赖关系的任务可以同时跑。

我常用的并行调度策略是这样的：

维护一个“就绪队列”：所有入度为0的任务都在这个队列里。
从就绪队列中批量取出任务：根据系统资源（线程池大小、CPU核数、内存配额）决定一次取多少个。
并行执行：每个任务跑完后，更新其后继节点的入度。如果某个后继节点的入度变为0，就把它加入就绪队列。
重复直到所有任务完成。

核心思想： 并行调度 = 拓扑排序的“动态版本”。不是一次性排好序再执行，而是边执行边调度，让就绪任务随时可以开始。

这里有个性能关键点——就绪队列的并发安全。多个工作线程同时完成任务，同时更新入度，同时往就绪队列里加新任务。如果不用锁或者无锁队列，很容易出现数据竞争。

我曾经在一个项目里用ConcurrentLinkedQueue做就绪队列，配合AtomicInteger维护入度，性能还不错。但如果你的任务粒度特别细（每个任务执行时间不到1毫秒），那队列操作本身的开销就不可忽视了。

4.4 并行度控制：不是越多越好

很多人一听到“并行”，就觉得线程越多越快。其实不然。并行度受两个因素制约：

因素	说明	我的建议
硬件资源	CPU核数、内存带宽、IO通道	并行度不超过CPU核数的2倍（计算密集型）或更高（IO密集型）
任务依赖	DAG的宽度（同一层有多少个节点）	如果DAG很窄（比如一条链），并行度再高也没用

我见过一个案例：团队把并行度设成64，但DAG的宽度只有4，结果大部分线程都在空转，反而因为上下文切换拖慢了整体速度。后来改成动态并行度——根据就绪队列长度和系统负载实时调整，效果好了很多。

4.5 DAG调度引擎的整体架构

说了这么多，咱们用一张图把整个流程串起来：

4.6 避坑指南：我踩过的那些雷

最后分享几个实战中容易翻车的地方：

任务粒度过细：我曾经把一个计算任务拆成几百个微任务，每个就几毫秒。结果调度开销比任务执行本身还大。后来合并成粗粒度任务，整体吞吐反而提升了3倍。
忽略资源竞争：多个并行任务如果争抢同一个数据库连接池或文件锁，那并行就变成了串行。我建议在DAG里显式标注“共享资源”，调度器根据资源冲突自动调整并行度。
任务失败处理：并行任务中有一个失败了，其他任务怎么办？是全部取消还是继续跑？这取决于业务场景。我习惯的做法是：如果失败任务不影响其他任务的执行结果，就继续跑；否则立即终止整个DAG。

小技巧： 调试DAG调度时，可以先把并行度设为1，跑一遍确认逻辑正确。然后再逐步提高并行度，观察性能变化。这样能快速定位是逻辑问题还是并发问题。

嗯，DAG调度引擎这块内容不少，但核心就三件事：建好图、排好序、控好并行度。把这三点吃透了，大部分调度场景你都能应付。