3. DAG调度核心概念：有向无环图、任务依赖、拓扑排序
在分布式任务调度系统中，DAG（有向无环图）是描述任务执行顺序与依赖关系的核心数学模型。理解DAG的三个基本要素——有向无环图、任务依赖与拓扑排序，是构建可靠、高效调度系统的基础。本节将逐一拆解这些概念，并说明它们在Docker Compose环境下的实际映射。
3.1 有向无环图（DAG）
DAG由一组顶点（Vertex）和一组有向边（Directed Edge）组成，且图中不存在任何环路。在任务调度场景中：
- 顶点：代表一个具体的任务单元（如数据清洗、模型训练、结果推送）。
- 有向边：代表任务间的执行顺序约束，方向从前置任务指向后置任务。
- 无环：保证任务不会形成循环依赖，避免死锁或无限执行。
关键特性：DAG保证了任务图的可执行性——只要图是无环的，就一定存在至少一种合法的执行顺序。
下图展示了一个典型的DAG任务调度结构，包含5个任务节点及其依赖关系：
3.2 任务依赖关系
任务依赖定义了DAG中边的语义。在分布式调度中，常见的依赖类型包括：
| 依赖类型 | 语义 | Docker Compose场景示例 |
|---|---|---|
| 顺序依赖 | 任务B必须在任务A完成后才能启动 | 数据清洗容器必须在数据采集容器退出后启动 |
| 数据依赖 | 任务B需要任务A产生的输出文件或数据集 | 模型训练容器需要特征工程容器生成的共享卷数据 |
| 资源依赖 | 任务B需要任务A释放的端口、锁或连接池 | API网关容器需要等待认证服务容器释放端口 |
| 条件依赖 | 任务B仅在任务A的返回状态为成功时才执行 | 失败通知容器仅在主任务容器返回非零退出码时触发 |
实践建议：在Docker Compose编排中，顺序依赖通常通过
depends_on 实现，但该指令仅控制容器启动顺序，不保证任务内部逻辑完成。对于严格的任务级依赖，应使用健康检查（healthcheck）或外部调度器（如Airflow、Argo Workflows）来确保任务实际完成。
3.3 拓扑排序
拓扑排序是将DAG中所有顶点排成一个线性序列，使得对于每一条有向边 (u → v)，顶点 u 在序列中都出现在顶点 v 之前。这是调度系统确定任务执行顺序的核心算法。
3.3.1 算法原理
最常用的拓扑排序算法是Kahn算法（基于入度），其步骤如下：
- 计算每个顶点的入度（指向该顶点的边数）。
- 将所有入度为0的顶点加入队列（这些顶点没有前置依赖，可以立即执行）。
- 从队列中取出一个顶点，将其加入拓扑序列，并移除所有从该顶点出发的边（即减少目标顶点的入度）。
- 如果某个目标顶点的入度变为0，则将其加入队列。
- 重复步骤3-4，直到队列为空。
- 如果最终拓扑序列中的顶点数小于总顶点数，说明图中存在环。
时间复杂度：O(V + E)，其中V为顶点数，E为边数。Kahn算法在分布式调度中非常高效，适合动态生成执行计划。
3.3.2 拓扑排序在调度中的实际应用
下图展示了Kahn算法对上述DAG进行拓扑排序的过程，以及最终生成的执行计划：
3.4 在Docker Compose中的映射
将DAG调度概念映射到Docker Compose编排中，需要理解以下对应关系：
| DAG概念 | Docker Compose实现 | 说明 |
|---|---|---|
| 顶点（任务） | services 中的每个容器服务 |
每个服务对应一个任务单元，可独立启动、停止、扩缩 |
| 有向边（依赖） | depends_on 指令 |
声明服务间的启动顺序，但需配合健康检查确保任务完成 |
| 无环约束 | Compose文件解析时的循环依赖检测 | Docker Compose v2+ 会在启动前检测并报错 |
| 拓扑排序 | Compose引擎内部的启动顺序计算 | 引擎自动按依赖关系排序，用户无需手动实现 |
| 并行执行 | 无依赖关系的服务可同时启动 | 利用多核CPU和网络带宽，缩短整体调度时间 |
注意：
depends_on 仅保证容器启动顺序，不保证容器内任务完成。对于严格的任务级DAG调度，建议使用专门的DAG调度框架（如Apache Airflow、Prefect、Argo Workflows）来管理任务依赖，而将Docker Compose作为容器编排层使用。
3.5 拓扑排序在调度优化中的价值
理解拓扑排序对网络通信优化有直接帮助：
- 减少等待时间：通过拓扑排序识别可并行执行的任务，在Docker Compose中利用多服务并发启动，减少整体调度时间。
- 优化网络带宽：将数据密集型任务（如大文件传输）安排在非高峰时段或独立网络路径上，避免与关键任务争抢带宽。
- 降低连接冲突：拓扑排序可提前暴露端口依赖关系，避免多个容器同时竞争同一端口或连接池。
- 提升故障恢复速度：当某个任务失败时，拓扑排序可快速计算出受影响的下游任务范围，实现精准的重启或回滚。
优化思路：在Docker Compose编排中，可以结合
depends_on 与自定义健康检查脚本，实现任务级别的依赖感知。例如，数据清洗服务在完成处理后写入一个标记文件，下游服务通过卷挂载检测该文件是否存在，从而实现精确的任务级DAG调度。