2. DAG基础：有向无环图定义、顶点与边、拓扑排序、关键路径
在分布式任务调度系统中，DAG（有向无环图）是描述任务依赖关系的核心数学模型。理解DAG的基本概念是设计高效调度算法与数据传输机制的前提。本节将从定义、结构、排序与路径四个维度，系统梳理DAG的基础知识。
2.1 有向无环图定义
有向无环图（Directed Acyclic Graph, DAG）是一种特殊的图结构，由一组顶点和一组有向边组成，且图中不存在任何有向环。形式化定义如下：
- 顶点集 V：表示任务或计算单元，记为 \( V = \{v_1, v_2, ..., v_n\} \)。
- 边集 E：表示任务间的依赖关系，记为 \( E \subseteq V \times V \)。
- 无环约束：不存在从某个顶点出发，经过若干条有向边后回到该顶点的路径。
调度视角理解： DAG中的“无环”特性保证了任务调度不会出现循环等待或死锁。在分布式系统中，若任务A依赖任务B，任务B又依赖任务A，则系统无法确定执行顺序，调度将陷入死局。DAG天然规避了这一问题。
2.2 顶点与边
在DAG任务调度场景中，顶点和边被赋予了具体的业务语义：
| 元素 | 符号 | 调度语义 | 典型属性 |
|---|---|---|---|
| 顶点 | \( v_i \) | 一个独立的任务单元 | 计算量、数据量、执行时间、优先级 |
| 有向边 | \( e_{ij} = (v_i, v_j) \) | 任务 \( v_i \) 必须在 \( v_j \) 之前完成 | 数据传输量、传输延迟、带宽需求 |
| 入度 | \( indeg(v) \) | 指向该顶点的边数，即前置依赖数 | 调度就绪条件 |
| 出度 | \( outdeg(v) \) | 从该顶点出发的边数，即后继任务数 | 数据分发扇出 |
数据传输设计要点： 边上的数据传输量是调度决策的关键参数。在服务边界视角下，跨节点边意味着网络传输，其成本远高于节点内边。因此，DAG中边的“位置属性”（本地/远程）直接影响调度策略。
2.3 拓扑排序
拓扑排序是将DAG中所有顶点排成一个线性序列，使得对于每条有向边 \( (v_i, v_j) \)，顶点 \( v_i \) 在序列中都出现在 \( v_j \) 之前。拓扑排序是任务调度顺序生成的基础算法。
2.3.1 Kahn算法（基于入度）
Kahn算法通过维护入度为零的顶点集合，逐步剥离无依赖任务，是工程中最常用的拓扑排序实现：
// Kahn算法伪代码
function topologicalSortKahn(graph):
inDegree = computeInDegree(graph) // 计算所有顶点入度
queue = emptyQueue()
for each vertex v in graph:
if inDegree[v] == 0:
queue.enqueue(v) // 入度为0的顶点入队
result = []
while queue is not empty:
v = queue.dequeue()
result.append(v)
for each neighbor u of v:
inDegree[u] -= 1
if inDegree[u] == 0:
queue.enqueue(u)
if result.length != graph.vertexCount:
return error("图中存在环，无法拓扑排序")
return result2.3.2 拓扑排序在调度中的意义
| 应用场景 | 说明 |
|---|---|
| 任务执行顺序生成 | 拓扑序列直接作为任务提交的顺序基准，保证依赖满足 |
| 并行度识别 | 同一拓扑层级中无依赖关系的任务可以并行执行 |
| 数据传输规划 | 根据拓扑顺序预判数据产生与消费的时间窗口，优化传输策略 |
| 环检测 | 若拓扑排序无法覆盖所有顶点，则说明DAG中存在环，需报错 |
工程陷阱： 拓扑排序结果不唯一。当多个任务入度同时为零时，不同的出队顺序会产生不同的拓扑序列。调度系统需要结合任务优先级、数据局部性等策略，从多个合法拓扑序列中选择最优调度顺序。
2.4 关键路径
关键路径（Critical Path）是DAG中从源点到汇点具有最长路径长度的路径。在任务调度中，关键路径决定了整个作业的最短完成时间（makespan），路径上的任务称为关键任务，任何延迟都会直接导致整体工期延长。
2.4.1 关键路径相关参数
| 参数 | 符号 | 定义 | 计算公式 |
|---|---|---|---|
| 最早开始时间 | EST(v) | 任务可以开始的最早时刻 | EST(v) = max{ EFT(u) | u ∈ pred(v) } |
| 最早完成时间 | EFT(v) | 任务可以完成的最早时刻 | EFT(v) = EST(v) + duration(v) |
| 最晚开始时间 | LST(v) | 任务必须开始的最晚时刻，否则影响工期 | LST(v) = LFT(v) - duration(v) |
| 最晚完成时间 | LFT(v) | 任务必须完成的最晚时刻 | LFT(v) = min{ LST(w) | w ∈ succ(v) } |
| 浮动时间 | Slack(v) | 任务可延迟的最大时间 | Slack(v) = LST(v) - EST(v) |
2.4.2 关键路径在数据传输设计中的应用
- 数据预取策略： 关键路径上的数据传输必须优先保障带宽和低延迟，避免因数据未到导致关键任务等待。
- 数据副本放置： 非关键路径上的任务具有浮动时间，其数据可以延迟传输或使用较低优先级通道，节省网络资源。
- 传输超时设置： 关键路径上的数据传输超时应设置更短，以便快速失败并触发重试或备用路径。
- 调度与传输协同： 将关键路径上的任务调度到同一节点或相邻节点，减少跨节点数据传输开销。
服务边界视角： 在微服务架构中，关键路径上的任务往往对应核心业务链路。数据传输机制需要为这些链路提供专用通道、QoS保障和故障隔离，而非关键路径上的数据可以使用批量传输或异步队列，以降低系统整体负载。
2.5 本章小结
DAG作为任务调度的基础模型，其核心要素可归纳如下：
- 定义与结构： DAG由顶点（任务）和有向边（依赖关系）组成，无环约束保证了调度的可行性。
- 拓扑排序： 将DAG转化为线性执行序列，是调度顺序生成的基础算法，Kahn算法是工程首选。
- 关键路径： 决定作业最短完成时间，关键任务的数据传输需要最高优先级保障。
- 服务边界关联： 顶点对应微服务实例，边对应服务间调用与数据传输，拓扑排序对应服务编排顺序，关键路径对应核心业务链路。