DAG、Workflow 系统设计、Airflow 与开源的那些事儿

DAG (Directed Acyclic Graph) 是一个非常有用、也有很有意思的数据结构。如果说数组、链表、二叉树这类数据结构是学习中的基础，那么 DAG 绝对算得上工作中常常会听到、用到的实践知识。工作中两个 SDE 讨论技术问题，DAG 和 Array/Linkedlist/Tree 算的上是同一级的词汇、知识，默认彼此都懂。

下面我们详细讲讲原因：有向无环图 (DAG)，结合拓扑排序（topolocial sort）的确是解决存在依赖关系的一类问题的利器。

举个例子，Excel 中的单元格 (Cell) 支持引用和公式，假设 Cell 1 = 10, Cell 2 可以直接引用 Cell 1 即 Cell 2 = $ Cell 1; Cell 3 甚至可以使用公式进行引用，比如 Cell 3 = $ Cell 2 * 10;

• 由于当前 Cell 1 = 10, 所以引用之后的 Cell 2 显示为 10，Cell 3 显示为 100;
• 当 Cell 1 的值从 10 变为 100 时，由于存在引用关系，Excel 会马上自动更新， Cell 2 显示为 100， Cell 3 显示为 1000.

更新的逻辑看起来简单，但仔细想想，类似的依赖关系可能呈复杂的网状结构，一个 Cell 的更新，可能联动更新 N 多 Cell, 然后产生更多的联动更新，直到所有相关依赖的 Cell 都被更新才结束。

这类问题我们喜欢归类为依赖问题的解决（resolve dependency problem). 直接尝试暴力解决很难，但是把依赖关系的问题建模成 DAG, 依赖关系成为 Graph 中的 Directed Edge, 然后通过拓扑排序，不断遍历和剔除无依赖的接点，可以达到快速 Resolve dependency 的目的。

今天我们就不展开讲解拓扑排序，有兴趣的朋友可以自行搜索。

任何 Workflow 系统都是 DAG 的典型应用。在一个 Workflow 系统中，任务间往往存在复杂的依赖关系。常见的有：

• Task A can’t start until Task B succeeds;
• Task A can’t start until Task B, C, D all succeed;
• Task A can’t start until any of Task B C D succeeds;
• Task A only executes when Task B output is X; …

Workflow 系统的作用就是保证任务可以按照他们所设置的依赖关系有序进行。想想看，是不是和 Update Excel Cell 有点类似？

当然，解决 DAG 中的依赖关系并不复杂，甚至是刷题中少见的可以直接照搬进工作的算法。如果在面试中被问到如何设计一个 Workflow 系统？难点在哪里呢？

首先，如何设计 Scheduler / Worker?

有同学表示这是一个白痴问题，每次看到一个能做的 Task 直接 Run 不就行了？干嘛需要什么 Scheduler / Worker?

如果每一个 Task 是一个简单可以快速结束的函数，这么做似乎没问题。问题是，绝大部分（如果不是所有）工作需要 Workflow 来管理的 Task 都相对复杂，并通常要和其他 Service 打交道，比如 Task 需要跑一个非常大的 Query, 跑完之后把结果存到某个地方，然后再做检索等。没有全面考虑的 Scheduler / Worker 设计，这类问题难以解决。

老实说，系统设计面试的失败往往并非算法/逻辑错误，而是尝试解决一个错误的、甚至不存在的问题。

其次，如何设计处理 Failure Case?

Workflow 的核心是状态管理，一个 Task 究竟是 Succeed? Fail? Running? State 如果错了，那么这个系统一定是懵逼的。

有同学表示这是一个白痴问题，把 State 存在数据库里，需要的时候读一读不就可以了?

大部分的情况下没错。但是，如果还没来得及保存 State 的时候 Process 被 Kill 了怎么办？Host 被 Shutdown 了怎么办？这真不是鸡蛋里挑骨头，不能正确的处理各类异常的系统是根本不能上线的。

再次，如何 Scale Scheduler / Worker?

当一个 Workflow 系统处理越来越多的 Tasks, 总有一天会达到单机能够处理的极限。怎么办？

有同学表示这是一个白痴问题，多加几个 Host 不就行了?

没错，但这句话等于没说。关键是怎么加 Host? Host 之间如何 Communicate? 是 Master-Slave 结构还是 Peer-Peer? 怎么处理网络间的异常？

更多深入的细节思考、而不是夸夸其他的将概念，可以给你的系统设计面试大大加分。

在 Google 中搜索 Airflow，看到的可能是

但今天我们想谈的是 Airbnb 开源的 Airflow, Github 上两千星的项目，一个挺不错的 Workflow 实现。

具体的技术简单说两句：Airflow 使用 Python 写的，支持 Python 2/3 两个版本。

传统 Workflow 通常使用 Text Files (json, xml / etc) 来定义 DAG, 然后 Scheduler 解析这些 DAG 文件形成具体的 Task Object 执行；Airflow 没这么干，它直接用 Python 写 DAG definition, 一下子突破了文本文件表达能力的局限，定义 DAG 变得简单。

另外，Airflow 的权限设计、限流设计、以及 Hook/Plugin 的设计都挺有意思，功能性、扩展性良好。当然，项目里的代码质量感觉比较一般，很多地方函数名和实现不太一致，造成理解障碍；也有很多 Flag 和重复出现的定义，显然是当初没有设计好、后面没有精力 Refactor 转而 Hack 的结果。但总体上，可读性中上，系统的扩展性非常好。

但我们想说的是，Airflow 真的是一个可以拿来即用、而且相当好用的东西。坊间传闻说，Airflow 作者当初在 FB 的时候搞过非常类似的系统，跳槽之后，可能觉得重来一遍没啥意思，顺手开源。于是社区欢欣鼓舞，“不花钱，还能用上比 FB 里面还好用的 Workflow System, 真是 Why Not 啊”.

近几年，开源社区真的是赶上了好日子。一方面，Google Facebook 们对于开源的态度和贡献远远大于那些老头们（不点名了），另一方面像 Github 这样的存在也让 Social Coding 变得如此容易。说实话，最得益的还是程序员自己，感谢开源！