基于DAG的任务依赖调度

DAG叫做有向无环图(Directed Acyclic Graph, DAG),读过数据结构的应该都有点印象。

DAG可以用来实现依赖管理,比如:执行A任务之前,必须先完成B任务,因为A任务的输入是B任务的输出。

当整个依赖关系继续变多的时候,就催生出了依赖管理的需求,而A对B的依赖可以描述为图中的一条边。

项目地址

https://github.com/owenliang/task_schedule

DAG

掌握DAG是实现依赖调度的先决条件,DAG有3部分内容需要掌握:

  • DAG数据结构
  • DAG拓扑排序(基于入度)
  • DAG逆拓扑序列(基于出度)

推荐读一下这篇博客温习DAG数据结构,拓扑排序的含义与算法:【图论】有向无环图的拓扑排序

任务依赖

A任务依赖B与C任务,那么就需要建立一条A->B的边、一条A->C的边。

我们需要先执行那些依赖已经执行OK或者压根没有依赖的任务,在这里也就是先执行B和C,最后执行A。

所以,我们需要基于”出度=0″这个条件作为执行条件,任何满足”出度=0″的任务均可以立即执行;在上述例子中,B和C没有依赖其他任务,它们从一开始出度就为0,所以可以立即执行。

任务调度

每次从DAG中找出”出度=0″且”尚未执行”的任务列表,逐个或者并发的执行它们;每当1个任务完成时,就从DAG图中删除这个任务,并发现更多”出度=0″的任务,放入待执行的任务集合中去。

调度过程,就是不断执行依赖完备的任务,并不断发现更多依赖完备的新任务的过程。

构建DAG

这样一个依赖关系,JOB1依赖JOB2、JOB3、JOB5;JOB2依赖JOB4;JOB3依赖JOB4;

我们通过代码控制,建立这个DAG图:

调度任务

每次从DAG中找到”出度=0″且”尚未执行”的任务,放入todo数组。

这些任务之间必然没有依赖关系,可以完全并行化处理,并行度由程序灵活控制;在这里为了简化问题,我采用了串行执行任务的方式。

每完成一个任务,更新DAG图标记任务完成,这将使一些依赖该任务的任务变成可执行状态,从而在下一次调度时可以获取到这些新任务。

打印DAG

这个过程会打印每一个任务当前依赖哪些任务,以及被哪些任务依赖,方便我调试代码。

TaskNode表示DAG中的一个节点,而TaskNode.outEdge表示这个节点指向了哪些节点,TaskNode.inEdge表示这个节点被哪些节点指向。

上述2个集合随着任务的完成被更新,从而可以随时获知最新的任务依赖关系。

任务调度日志

下面是完整执行日志,展现了整个调度过程中,每个任务依赖与被依赖的关系,以及任务之间的并行关系:

最后

基于该demo,可以演化出一个任务调度系统。

用户向系统提交一个DAG拓扑,大概长这样:

拓扑名:hadoop挖掘任务

任务列表:

  • JOB1
    • 依赖:JOB2,JOB3
  • JOB2:
    • 依赖:JOB3

系统根据上述配置,创建对应的DAG图,并启动线程/协程完成调度。

 

发表评论

电子邮件地址不会被公开。