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 变得如此容易。说实话,最得益的还是程序员自己,感谢开源!
转自:包子铺里聊IT