? ? 分布式任务调度系统设计 详解Go实现任务编排与工作流 ? ? 贺鹏?目前就职某互联网金融公司负责架构及开发管理工作，在分布式领域和风控领域深入研究。 I.内容提要 定时调度系统（定时任务、定时执行）算是工作中经常依赖的中间件系统，简单使用操作系统的 crontab，或基于 Quartz，xxl-job 来搭建任务调度平台，行业有很多优秀的开源产品和中间件。了解其工作和设计原理，有助于我们完善或定制一套适合公司业务场景的任务调度中间件，之前写了两篇文章介绍了调度负载均衡和定时延时任务的内容，可以参考。 分布式调度分发负载均衡及服务保持 分布式调度延时任务实现原理 今天我们探讨另一话题，对调度任务的依赖关系及编排展开分析，实现一套工作流，来满足任务间的复杂依赖的场景。本章内容提要： 任务调度依赖 & 工作流 图相关知识 golang 并发相关 II.任务调度依赖 什么是任务依赖？比如 “任务?a” 执行的前提是 “任务?b”?先执行完成，“任务b” 又依赖于 “任务?c” 先执行，那么就形成如下依赖关系。 这个还比较简单，如果复杂点的如下图所示，形成一个工作流，Azkaban 大数据调度器就实现了工作流模式调度依赖，这是一个典型的图应用案例。 III.图数据结构 提到图数据结构，大部分人既熟悉又陌生，因为大学基本都学过，但一般工作场景都不会用到，这里就先简单回顾一下图相关的知识。 图 graph?，图中的元素称为顶点 vertex。图中任一顶点可以与其他顶点建立连线关系，叫做边 edge。 上面图叫 “无向图”，如果边有 “方向” ，那么就是 “有向图” 了。 无向图中，顶点有几条边就叫几度；有向图中，顶点有入度，表示有多少边指向此顶点，顶点的出度表示该顶点有多少边指向 “远方” 。 上图中 a 指向 b，b 指向 d，d 又指向 a， a、b、d 之间形成一个环，如果将顶点比作调度的任务，那么任务 a 完成必须依赖任务 b，任务 b 又依赖任务 d，任务 d 又依赖任务 a，那么最终肯定无法完成，因此调度问题使用的是有向无环图 （DAG），比如我们最早那张图。 了解了图的基本概念，那么图结构如何用代码表示出来？这里涉及到图的两种存储方式：邻接矩阵、邻接表。 邻接矩阵底层为二维数据，如果有一条边顶点为 x 和 y，对无向图来说，对应的数据 Array[x][y] 和 Array[y][x] 标记为 1；对有向图 x->y ，只将 Array[x][y] 标记为 1 即可，下图为使用邻接矩阵表示的无向图和有向图。 对于无向图来说，邻接矩阵沿着红色对角线两边是对称的，如果图的顶点连线比较少，这种叫稀疏图，将存储大量的 0 ，浪费存储空间，这时候可以选择使用邻接表表示，相对稀疏图的叫稠密图，使用邻接矩阵可以更好地查询连通性，其原理也是用空间换时间。下图为使用邻接表表示的无向图和有向图。 最后说下图的遍历，和遍历树一样分为广度优先 BFS?和?深度优先 DFS，但图如果存在成环的情况，访问的节点要做记录，同时可用辅助队列存放待访问的邻接节点。 拓扑排序，对有向无环图的顶点进行遍历，将所有顶点形成一个线性序列，可以用数组（切片）或链表存储，如下图。 IV.golang 代码实现 回顾了图的相关知识，那么回到最开始的任务依赖工作流中，将每个任务看成图的顶点，任务 a 依赖 任务 b，使用一条有向线从 a 指向 b，最后将所有任务顶点连线形成一个图，这个图是一个有向无环图 DAG，对 DAG 进行拓扑排序，形成一个任务执行链表，反向执行即可解决依赖问题。 首先定义一个图结构体，这里使用邻接矩阵方式存储，图的顶点结构体存储 Key 和 Value 代表任务的相关执行信息。 //图结构 type DAG struct { Vertexs []*Vertex } //顶点 type Vertex struct { Key string Value interface{} Parents []*Vertex Children []*Vertex } 为图添加顶点和添加边，这里是有向图，from 代表边的起始顶点， to 代表边的终止顶点。 //添加顶点 func (dag *DAG) AddVertex(v *Vertex) { dag.Vertexs = append(dag.Vertexs, v) } //添加边 func (dag *DAG) AddEdge(from, to *Vertex) { from.Children = append(from.Children, to) to.Parents = append(to.Parents, f