2. 核心概念：DAG（有向无环图）定义、任务节点与依赖边、拓扑排序原理
在分布式任务调度领域，DAG（Directed Acyclic Graph，有向无环图）是描述任务依赖关系最严谨的数学模型。理解 DAG 的三个核心要素——节点、边与无环约束——是设计调度服务边界的前提。
2.1 DAG 的数学定义与工程映射
从图论角度，DAG 是一个由顶点集合 V 和有向边集合 E 构成的二元组 G=(V, E)，且不存在从某个顶点出发经过若干条有向边回到该顶点的路径。在任务调度场景中，这种抽象被直接映射为：
| 图论元素 | 调度领域映射 | 工程示例 |
|---|---|---|
| 顶点 (Vertex) | 任务节点 (Task Node) | 数据清洗、特征工程、模型训练 |
| 有向边 (Directed Edge) | 依赖关系 (Dependency) | “模型训练”依赖“特征工程”完成 |
| 无环约束 | 无循环依赖校验 | 禁止 A→B→C→A 的环形引用 |
| 入度 (In-degree) | 前置依赖数量 | 入度为 0 表示可立即调度 |
| 出度 (Out-degree) | 下游依赖数量 | 出度为 0 表示终端节点 |
架构要点： DAG 的无环特性是调度系统正确性的生命线。一旦出现环，拓扑排序将无法完成，调度器会陷入死锁。因此，边界服务必须在提交阶段进行环检测，而非等到运行时。
2.2 任务节点与依赖边的设计粒度
任务节点（Task Node）是 DAG 中最小的可调度单元。在领域驱动设计中，每个节点对应一个领域事件或命令的触发点。节点的属性设计直接影响调度服务的边界划分：
- 节点标识：全局唯一 ID，用于追踪和幂等。
- 执行类型：Shell 脚本、HTTP 调用、Spark 作业、子 DAG 等。
- 超时策略：硬超时与软超时，决定调度器的中断行为。
- 重试配置：最大重试次数、退避算法，属于调度服务的核心策略。
- 上下文数据：输入输出参数的 Schema，用于数据血缘追踪。
依赖边（Dependency Edge）则定义了节点间的时序与数据约束。常见的依赖类型包括：
| 依赖类型 | 语义 | 调度行为 |
|---|---|---|
| 硬依赖 (Hard) | 上游必须成功 | 上游失败则下游跳过或标记失败 |
| 软依赖 (Soft) | 上游完成即可（含失败） | 上游失败时下游仍可执行 |
| 数据依赖 | 上游输出作为下游输入 | 需传递数据路径或内存引用 |
| 信号依赖 | 仅等待上游完成信号 | 不关心上游执行结果数据 |
设计建议： 在限界上下文中，依赖边的类型应作为值对象（Value Object）封装在调度领域内部，而非暴露给外部调用方。这可以防止客户端错误地设置循环依赖或矛盾约束。
2.3 拓扑排序原理与调度顺序生成
拓扑排序（Topological Sorting）是 DAG 调度引擎的核心算法。它生成一个线性序列，使得对于每一条有向边 u→v，节点 u 在序列中都出现在节点 v 之前。调度器依据该序列决定任务的触发顺序。
最常用的算法是 Kahn 算法（基于入度），其步骤清晰且易于在分布式环境中实现：
- 初始化一个队列，将所有入度为 0 的节点入队。
- 从队列中取出一个节点，将其加入拓扑序列。
- 遍历该节点的所有出边，将目标节点的入度减 1。
- 若目标节点入度变为 0，则将其入队。
- 重复步骤 2-4，直到队列为空。
- 若最终序列长度小于节点总数，则说明图中存在环。
// Kahn 算法伪代码（调度服务核心逻辑）
function topologicalSort(graph):
inDegree = computeInDegree(graph)
queue = new Queue()
for node in graph.nodes:
if inDegree[node] == 0:
queue.enqueue(node)
sortedList = []
while queue is not empty:
node = queue.dequeue()
sortedList.append(node)
for neighbor in graph.getNeighbors(node):
inDegree[neighbor]--
if inDegree[neighbor] == 0:
queue.enqueue(neighbor)
if sortedList.length != graph.nodes.length:
throw new CyclicDependencyException("DAG contains a cycle")
return sortedList
架构陷阱： 在微服务架构中，拓扑排序不应在每次调度时都从零计算。建议将排序结果缓存为 DAG 的快照（Snapshot），仅在 DAG 结构变更时重新计算。这能显著降低调度延迟。
2.4 DAG 结构可视化：节点、边与拓扑顺序
下图展示了一个典型的 ETL 任务 DAG，包含 6 个任务节点和 7 条依赖边。拓扑排序结果为 [A, B, C, D, E, F]，调度器将按此顺序触发任务，同时利用并行度优化：
2.5 并行度与关键路径
拓扑排序仅保证依赖顺序，不直接决定并行度。调度器需要进一步分析 DAG 的关键路径（Critical Path）——从起点到终点的最长路径，它决定了整个 DAG 的最短完成时间。在架构设计中：
- 关键路径上的节点：应分配最高优先级资源，避免成为瓶颈。
- 非关键路径节点：可在资源空闲时延迟执行，或使用较低规格的 Worker。
- 并行度上限：由 DAG 的宽度（同一层级的节点数）决定，调度器需维护一个线程安全的就绪队列。
领域驱动视角： 关键路径计算属于调度引擎的领域服务（Domain Service），不应放在应用层或基础设施层。它依赖 DAG 的完整快照，输出一个有序的节点优先级列表，供资源分配模块消费。
下图展示了同一 DAG 的并行调度视图，其中 B 和 C 属于同一层级，可同时执行：