DAG多任务编排驱动设计

       有向无环图应用DAG(Directed Acyclic Graph)是图论中重要的概念，运用场景广泛。首先举一个日常案例，下图使用有向无环图体现将不同的课程之间的依赖进行表示。

        在软件设计方面，有向无环图被大量运用，如在数据存储、版本控制方面非常著名的使用场景——Git。Git采用了Merkle Tree + DAG作为一个组合的数据结构Merkle DAG，来实现了分布式的的版本控制。在 Excel 的设计中，函数功能是一个非常重要的部分，函数的依赖关系符合 DAG 图的特性，采用有向无环图来存储表格内所有函数之间的依赖关系，称为表格的依赖图。

       任务编排(Scheduling)、数据处理（Data processing networks）也离不开有向无环图，如Spark等。

       有向无环图能够很好的表示复杂多变量系统，基于有向无环图的算法模型也很丰富，如贝叶斯网络（典型案例——学生网络（student network））。

        在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG, Directed Acyclic Graph）。

2.2.1 检测有否有环

• 拓扑排序(Topological Sort)
  

       循环执行以下两步：(1) 选择一个入度为0的顶点，输出；(2) 从图中删除此顶点以及所有的出边。循环结束后，若输出的顶点数小于网中的顶点数，则说明有回路。

• 遍历方法

       使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。

2.2.2 遍历

• 深度优先（Depth First Search，DFS）

        基本思想：首先访问起始顶点 v，接着由 v 出发，依次访问 v 的各个未访问过的邻接顶点 w1, w2 , … ,wi ，然后依次访问 w1, w2 , … , w~i~ 的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问过的顶点作为起始点，重复上述过程，直至图中所有的顶点都被访问到为止。

• 广度优先（Breadth First Search，BFS）
  

        基本思想：首先访问图中某一起始顶点 v，然后由 v 出发，访问与 v 邻接且未被访问过的任一顶点 w1，再访问与 w1 邻接且未被访问的任一顶点 w2 …… 重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

        本文提出一个基于有向无环图的任务编排驱动方案，对多任务并行、依赖关系复杂的场景进行处理。下图为该方案的核心模型，由JOB, STAGE, TASK三部分构成。

3.1.1 JOB

        JOB一个由多个并行/串行的任务组STAGE构成，每一个JOB即为一张有向无环图。

3.1.2 STAGE

        每个JOB被拆分成更小的被称作STAGE(阶段)的TASK(任务)组, 每一个STAGE是有向无环图的节点，STAGE彼此之间存在相互依赖, 各个STAGE会按照依赖关系依次执行。

3.1.3 TASK

        TASK是STAGE的一个任务执行单元，在具体执行的时候TASK被发送到processor中的进行执行。

        业务方在使用时，首先完成业务场景(business_code)的配置，该配置为一行或者多行config记录构成，这些记录构成该业务场景的“配置有向无环图”，即每一行为该配置图的一个节点，并由config_code进行标记。

       在正式发起JOB请求时，每一个STAGE由其相应的config_code进行标记，每一个STAGE为JOB有向无环图的节点。即每一个STAGE节点通过配置有向无环图映射为一个有向无环图，存储模型如下。

        任务驱动，基于mq+事件驱动机制，对图进行广度优先遍历驱动各个节点执行。

3.1 STAGE执行条件

• STAGE父节点为空 & 当前STAGE节点满足业务条件

• STAGE父节全部成功 & 当前STAGE节点满足业务条件

• 当前STAGE为成功或者为空， 则发送当前节点所在配置的子节点配置驱动消息，对子节点尝试执行。
  

3.2 驱动消息

        驱动消息由构成如下，系统消费驱动消息后尝试执行相应STAGE的任务，满足3.1所述的条件的STAGE将被执行，不满足条件的驱动消息会被直接丢弃，由定时任务补偿驱动消息。

3.3 事件机制

        本文中设计的系统通过EventBus机制对job、stage、task状态变化做出响应。

• TaskEvent

        通知业务调用方task成功。

• StageEvent

        通知业务调用方stage成功；尝试触发其子节点stage执行相应的task；判断当前job下其他stage的状态，必要时触发job事件。

• JobEvent

       更改job状态；通知业务调用方job状态。

4.1 演示

4.2 源码解析

• https://github.com/damaohongtu/dag-demo（更新中）
  
  

[1] https://en.wikipedia.org/wiki/Directed_acyclic_graph

[2] Machine Learning with Graphs http://web.stanford.edu/class/cs224w/

[3] https://github.com/alibaba/butterfly