基于有向图的任务编排

2023-09-14 10:02

杨晓琪 1278

我们平时开发当中，经常会遇到有些耗时的任务需要在后台执行，如果任务之间是无序的，那么我们可以把任务放到一个线程池里，这样多个任务就可以并行，提高执行效率。但线程的执行是无序的，在我们不干预的情况下，是无法保证顺序的，如果我们遇到需要严格控制执行顺序的任务时，例如以下几种情况：

任务A执行完，才能执行任务B
任务A、B都执行完，才能执行任务C
任务A执行完，才能执行任务B、C

这种任务的前后关系，使任务之间形成一个网状结构，因此我们可以用有向图来描述这种关系。

有向图是一幅具有方向性的图，由一组顶点和一组有方向的边组成，每条方向的边都连接着一对有序的顶点。

在了解了有向图的基本概念之后，我们需要用一种数据结构来存储有向图，即邻接矩阵。

邻接矩阵是表示定点之间相邻关系的矩阵。设图，其中顶点集，边集。用表示顶点与顶点之间的边数，可能取值为0,1,2,…,称所得矩阵为图G的邻接矩阵。

因此，上图 G1 和 G2 的邻接矩阵分别如下：

有了有向图的基本概念之后，我们就可以对任务进行数据建模了。

任务基础表：

("A", "任务A", 0),
("B", "任务B", 1),
("C", "任务C", 2),
("D", "任务D", 3);

任务关系表：

("A", "B")
("B", "C")
("B", "D")

task_no：任务的唯一编号
task_index：邻接矩阵的索引位置

代码实现

public class TaskGraph {
private int nodeCount;  // 节点数
private TaskNode[][] matrix;  // 邻接矩阵
public TaskGraph(int nodeCount) {
this.nodeCount = nodeCount;
this.matrix = new TaskNode[nodeCount][nodeCount];
}
/**
添加节点
@param start 起始位置
@param end   终止位置
@param node  节点
*/
public void addNode(int start, int end, TaskNode node) {
matrix[start][end] = node;
}
/**
显示图结构
*/
public void show() {
...
}

构建过程

1.创建任务有向图

TaskGraph graph = new TaskGraph();

2.创建任务实体

TaskNode node = new TaskNode();

3.在邻接矩阵对角线上放入任务实体

graph.addNode(i, i, node);

4.在有向边的位置放入任务实体

graph.addNode(i, j, node);

5.构建完成，输出结果

graph.show();
===========
| 0 0 X X |
| X 0 0 0 |
| X X 0 X |
| X X X 0 |
===========

结构说明

上面构建的任务有向图，与标准的邻接矩阵稍有区别：

X 表示没有任务
数字表示任务状态，0 表示未调度的任务
对角线表示任务自身
行表示任务的后续任务有哪些
列表示任务的前置任务有哪些

因此，从有向图上可以很直观地知道每个任务有哪些前置任务、哪些后续任务，以及任务的状态是什么。

扩展一下任务状态，有以下这些：

任务编排

有了以上数据模型的支撑，我们就可以对任务进行编排了。从构建完的数据模型开始：

0 0 X X
X 0 0 0
X X 0 X
X X X 0

首先，我们挑选没有任何依赖的任务，通过遍历邻接矩阵的每一列，可以看到 0 号任务不依赖任何其它任务，可以独立运行，而其它任务都有所依赖：

1 号任务依赖 0 号任务
2 号任务依赖 1 号任务
3 号任务依赖 1号任务

因此第一轮只有 0 号任务可以执行，其它任务等待，等 0 号任务完成之后，将第 0 行非 X 的值置为 8（任务完成状态）：

8 8 X X
X 0 0 0
X X 0 X
X X X 0

第二轮开始，已完成的任务列我们不再判断，直接跳过第 0 列。此时发现 1 号任务所依赖的任务已经完成，所以 1 号任务也进入执行态，而 2 和 3 号因为依赖 1 号任务而继续等待，等 1 号任务完成之后，邻接矩阵会变换为以下状态：

8 8 X X
X 8 8 8
X X 0 X
X X X 0

最后剩下的 2 个任务，现在的依赖任务也都已经完成，因此 3 和 4 号任务进入执行态，并且可以同时进行。最后邻接矩阵达到以下状态，则说明所有任务都已经执行完毕：

8 8 X X
X 8 8 8
X X 8 X
X X X 8

异常处理

循环依赖：

什么情况下会产生循环依赖？对于有向图来说，产生循环依赖，图上必定有环，但反过来，图上有环，不一定会产生循环依赖。我们通过两张图对比一下：

A -> B -> C -> D -> A：从顶点 A 出发，经过一条路径，最终又回到了顶点 A，这样就产生了循环依赖。当然 A 可以是任意顶点。

那么对于任务编排来说，循环依赖会导致任务陷入死循环，永远得不到执行，因此是一种很严重的异常，需要能够及时发现。幸好我们使用的任务编排算法，在第一轮过后就能发现循环依赖，即当邻接矩阵遍历完之后，如果没有可执行任务，则说明存在循环依赖，这时就可以抛出异常，让程序停止了。

任务失败：

任务执行过程中，总会遇到依赖的资源不可用的时候，因此我设计了任务的重试机制，当任务出错时，并不会直接进入“任务失败”状态，而是首先会进入“重试”状态，并且设置了一定的重试次数，等下一轮任务编排时，会让“重试”状态的任务再次执行。但如果超过了重试次数任务仍然没有执行成功，那么最终会进入“任务失败”状态，这时依赖该任务的其它任务将无法再得到执行的机会，这种情况就需要人工进行干预，排除依赖的资源不可用的情况，然后再让任务重新标记为可执行状态。

总的来说基于有向图的任务编排，主要有以下优点：

直观：可以从有向图上直接看出任务之间的依赖关系
简单：没有很复杂的数据结构和算法，便于理解
健壮：提供了容错处理，能及时发现不可执行的任务集
灵活：提供了灵活的任务编排手段，可以处理复杂的依赖关系
并行：只要没有依赖的任务，都可以同时执行
持久化：任务状态落库，可以直接将执行到一半的任务集从数据库中恢复并执行