task-orchestration

使用DAG图描述任务依赖，实现控制xxl-job client端任务执行顺序

1、图

术语

• 图：是由顶点集合和能够将两个顶点相连的边集合构成

• 顶点：图中的一个点

• 边：连接两个顶点的线叫做边

• 相邻：一个边两头的顶点称为相邻的顶点

• 度数：由一个顶点出发，有几条边就称该顶点有几度，或者该顶点的度数是几，有向图可以细分为入度跟出度

• 路径：通过访问顶点的边，按某种顺序的从一个顶点到另一个顶点中间经过的顶点集合

• 简单路径：没有重复顶点的路径

• 环：存在起点和终点都是同一个顶点的路径

• 简单环：不含有重复顶点和边的环

• 连通的：当从一个顶点出发可以通过至少一条边到达另一个顶点，我们就说这两个顶点是连通的

• 连通图：如果一个图中，从任意顶点均存在一条边可以到达另一个任意顶点，我们就说这个图是个连通图

• 无环图：是一种不包含环的图

• 稀疏图：图中每个顶点的度数都不是很高

• 稠密图：图中的每个顶点的度数都很高

• 二分图：可以将图中所有顶点分为两部分的图

图的分类

• 无向图，顶点的简单连接，边没有方向
• 有向图，顶点的边有方向性，由一组顶点和有向边组成。
• 加权图，连接带有权值
• 加权有向图，连接既有方向性，又带有权值

有向图术语

• 出度：由一个顶点出发的边的总数

• 入度：指向一个顶点的边的总数

• 有向路径：图中的一组顶点可以满足从其中任意一个顶点出发，都存在一条有向边指向这组顶点中的另一个。

• 有向环：至少含有一条边的起点和终点都是同一个顶点的一条有向路径。

• 简单有向环：一条不含有重复顶点和边的环。

• 路径或环的长度就是他们包含的边数。

• 图的连通性在有向图中表现为可达性，由于边的方向性，可达性必须是通过顶点出发的边的正确方向，与另一个顶点可连通。

邻接表数组

可表示图的数据类型，意思就是如何通过一个具体的文件内容，来表示出一幅图的所有顶点，以及顶点间的边。

邻接表数组，以顶点为索引（注意顶点没有权值，只有顺序，因此是从0开始的顺序值），其中每个元素都是和该顶点相邻的顶点列表。

       3     4
        \    /
          2         5
       /    \   /
     6        1


6 vertices, 5 edges
1:
2: 6     1
3: 2
4: 2
5: 1
6:

有向无环图

不包含有向环的有向图就是有向无环图，DAG，Directed Acyclic Graph。

寻找有向环

如何监测有向图中没有有向环，也就是如何确定是否是一个DAG。

• 通过深度优先搜索算法进行拓扑排序，如果经过拓扑排序后没有入度大于0的顶点，说明没有环
• 对图中每一顶点按照边访问下游所有顶点，如果存在下游节点存在于前面遍历过的顶点，说明存在环

使用DAG图描述任务依赖

目标：

1. 定义DAG数据结构
   1. 图的基本能力-添加顶点与边
   2. 完整性检查（添加顶点边时，判断是否会形成有向环）
   3. 有向环检查（给定一个图，使用拓扑排序判断是否满足DAG约束）
   4. 获取起始节点、结束节点集合
   5. 获取顶点的上下游节点
2. 能使用DAG图进行描述任务依赖
3. 持久化DAG图以及任务信息
   1. 持久化DAG图，任务间关系
   2. 从DB加载DAG图
4. 依据DAG图分析任务依赖，以及依赖的上游任务进行判断是否可执行
   1. 上游任务全执行后触发执行(默认)
   2. 上游某一个任务执行后触发执行(手动执行)
   3. 上游执行后不触发下游执行(手动执行)
5. 任务执行完后，更新版本号，依赖的上游节点版本，执行日志等

设计思路

使用DAG图描述任务依赖，表设计

`task_id` varchar(64) NOT NULL COMMENT` '任务标识',
`task_group_id` varchar(50) NOT NULL COMMENT '任务分组标识',
`upstream_tasks` varchar(255) DEFAULT` '' COMMENT  '上游任务标识集合',

task_id+task_group_id唯一代表一个任务，task_group_id表示一个DAG图，task_id表示DAG图中的一个任务

upstream_tasks代表上游任务集合，也就是task_id集合，用","连接的字符串

xxl-job执行控制

使用xxl-job client XxlJobContext 传递执行上下文

控制流程

1. 普通任务

判定条件：a.任务没有上游可执行；b.任务上游全执行，则可执行

实现方式：

a) DAG图中没有上游的节点(也就是根节点)执行后，更新节点版本号。

b) 存在上游的节点判断上游节点版本号是否都执行过(跟上一次执行的依赖的上游版本号集合对比)，如果是则执行，并更新此次执行的版本号以及依赖的上游版本号

 `task_id` varchar(64) NOT NULL COMMENT '任务标识',
 `task_group_id` varchar(50) NOT NULL COMMENT '任务分组标识',
 `upstream_tasks` varchar(255) DEFAULT '' COMMENT '上游任务标识集合',
 `version`  int(11) NOT NULL DEFAULT 0 COMMENT '当前任务执行版本',
 `pre_version`  int(11) NOT NULL DEFAULT 0 COMMENT '任务上一个执行版本',
 `upstream_version` varchar(255) DEFAULT '' COMMENT '触发任务时<上游任务标识:上游版本集合>集合',

2. 补偿任务

方式1：手动触发任务执行，传入执行参数triggerType=2表示是一个补偿任务，这种场景下，直接执行，不判断上游节点情况。执行完成后，不更新版本号，分析下游所有的任务节点形成子DAG图，将下游任务写入补偿任务池，并记录补偿参数。

 `task_id` varchar(64) NOT NULL COMMENT '任务标识',
 `task_group_id` varchar(50) NOT NULL COMMENT '任务分组标识',
 `status`  int(11) NOT NULL DEFAULT 0 COMMENT '状态，1-待补偿；2-已补偿',
 `execute_params` varchar(1024) NOT NULL COMMENT '任务补偿使用的参数',

方式2：任务被定时触发，检查是否存在补偿任务，是的话补偿，不更新版本号。

3. 补偿任务（只补偿自身）

方式1：手动触发任务执行，传入执行参数triggerType=3表示是一个补偿（只补偿自身）任务，这种场景下，直接执行，不判断上游节点情况。执行完成后，不更新版本号，不做其他处理