如何构建一个DAG运行时

聊点技术，如何构建一个DAG运行时。

什么是DAG及其运行时

这是个有趣的话题，甚至可以认为绝大部分计算机问题都可以被转为DAG或某个Graph。考虑到DAG的本意是有向无环图，但很多问题是有环的，Graph这个词更准确。有时DAG在特定上下文中就是指Graph。这里，简单起见，我们就称Graph为DAG。

比如下图。

通常，图中的节点代表某个任务，可以是繁重的任务，或者是轻量级别的任务。如果是繁重的任务，一般而言，我们称为workflow工作流。

其实我们的一段程序都可以被描述为这样一个graph，包括IF条件，While循环等。

近年来，机器学习比较火，大家常提的TensorFlow就是个典型，GraphDef就是描述了这个图。即使是动态图Eager执行，也围绕着这个核心概念。

最近，一篇“类脑计算完备性”的文章登上了Nature(link)。文中给出的抽象描述，正是Graph。

图中的POG (programming operator graph)恰巧是我八月份同样的工作，并制作了一个完整的原型运行了起来。不同之处是POG如何近似转为EPG（execution primitive graph），即如何编译为硬件原语。这一点，原文也没有清晰的描述。

工作流也好，程序模型也好，深度学习计算框架也好，都可以用Graph来描述。

这个Graph可以具备如下特性。

• 动态
  • 条件判断，循环等，典型的比如RNN，LSTM，GRU这类模型需要他们。工作流中也很常见。
• 并行
  • 多个节点，只要条件具备，就可以并行执行。
• 异步
  • 每个节点，只要条件具备，可以各自以自己的节奏运行。
• 嵌套
  • 每个节点，都可能是一个子Graph。
• 数据流转
  • 数据的流转在小量持续数据情况下，可以以数据流动的方式。在大批量数据大粒度情况下，可以存储在公共区域，只索引传输存储位置信息。这些索引信息常被称为metadata。

如何执行

执行一个Graph，最简单的方式，拓扑排序，按序依次调度。然而，这不能很好的解决动态，并行和异步的问题。从设计角度，我们将这个问题分解为两部分。

• 一部分 A 负责从这个Graph的当前状态中获取可以执行的部分。
• 另一部分 B 负责具体执行特定任务并更新状态。

所以我们有了 A 和 B，他们相当于处理一个消息队列的消息。

A

消息队列中一个消息：某个Graph需要被处理。

A的工作就是去处理特定Graph。

• 查询当前Graph的最新信息
• 根据依赖关系，判断条件是否具备，并决定如下工作
  • 发现某个节点具备执行条件，执行这个节点。
    • 这个节点如果是个子Graph，给A的消息队列发送一个新消息。
    • 这个节点如果是个原子任务，给B的消息队列发送一个新消息。 A处理了“动态（条件，循环）”特性，A也处理了并行特性。

B

消息队列中一个消息：某个原子Node需要被处理。

B的工作就是去处理特定的原子Node。

• 查询当前Node的最新信息
• 如果没有执行，就去执行
• 如果失败或成功，就给A的消息队列发送消息，告知处理父级Graph
  • 这样A就继续执行下部分的工作
• “异步”问题也由B来负责。本质上B就是异步驱动的。所以只要特定条件具备，就给B的消息队列发送消息，以驱动异步执行。
  • 有可能是A发过来的
  • 也可能是B觉得条件不具备，给自己发送一个“延时”消息，一定时间后再次检测
  • 也可能是外部系统在特定条件具备时发送过来的

粒度

很显然，上述的基于消息队列的设计可以工作，功能完备。这样的设计尤其适合工作流性质的系统。简单起见，我称这类系统为“批处理系统”。

但是如果任务本身的粒度就不大，为了一点点任务，转这么一大圈，就是个没必要的开支。这种情况，更类似于流处理系统。典型的一个设计就是最近国人“老师木”发起的OneFlow项目，通过Actor模式，以很低的成本在多个Node间进行通讯。相当于固化graph的node为actor，然后进行消息的传递。所以，在和老师木交流后，确认了OneFlow的当前版本还不能很好支持RNN这类动态图模型，也就是本文中提到的“动态”特性。不过，很显然，通过外加一个或两个Actor，担任A的角色，仍然可以支持。

总结

这是我在带领那个开源项目时，给其设计的第二版，解决了动态，并行，异步，嵌套等核心问题，使命完成。考虑到利益冲突，我做的原型暂时就不拿出来了。这其实也是一个非常好的系统设计面试题，我会用它来考核一些候选人，好歹能想到拓扑排序这层吧。