论文阅读：分布式数据流计算的执行引擎 CIEL

CIEL 分布式执行引擎

• 分布式执行引擎，用于执行具有任意数据依赖的控制流的程序。主要动机是运行时动态生成任务图，从而自然地支持迭代算法。

• 论文核心在第三、四、五节，分别介绍了 CIEL 系统的核心动态任务图，描述任务的 Skywriting 语言，以及实现上的细节问题。其中前后两者具有普遍性，领域特定语言比较凑数，意义不大。

动态任务图

CIEL 引擎包括三个基础概念，对象（Objects）、引用（References）和任务（Tasks）。

对象是无结构的定长字节序列。每个对象有唯一的名字，换个角度说，同名对象的内容相同。一旦对象构造完成，它就是不可变的。

引用由对象的名字和存储该对象的位置集合组成。如果位置集合为空，表明该对象还未构造完成，否则成为具体的引用。引用主要用于在不拷贝和处理对象内容的情况下逻辑上代表一个对象。

任务是非阻塞的原子计算单位，任务的一次执行不会跨越机器。任务可以定义若干个依赖，依赖由引用表示，仅当所有依赖均就位时可执行此任务。任务依赖的计算应当是确定性的。任务可以具有若干个输出，输出可以由此任务自己构造，也可以代理到另一个任务构造。

任务可以执行两个外部可见的动作。一个是通过创建引用来发布若干个对象，这可能会导致其他作业观察到这个对象从而可以被执行。另一个是创建一个新任务，新的任务能够执行新的计算。这两个动作的限制如下。

1. 对于每一个具体的输出，任务要么发布它的一个具体的引用，要么创建一个子任务，子任务代为产生这个输出。这个限制保证依赖当前任务输出的任务在当前任务及其子任务全部完成后总能被允许执行。

2. 子任务只能依赖具体的引用（即已经构造完成的对象）或者已有任务的输出（即明确会被发布的对象）。这个限制保证任务依赖不会发生死锁。

任务执行的两种模型

1. 立即求值。从前面的限制我们可以推断出任务之间的依赖可以表示为一个有向无环图，从而可以拓扑排序并依次执行。这种执行模型称为立即求值。

2. 惰性求值。相比而言，如果仅在需要某个对象的值时，从产生它的任务出发，逐步请求执行依赖任务，这样的执行模型称为惰性求值。

CIEL 引擎采用惰性求值的执行模型。

系统架构

Object Table

Object ID Produced By Locations 对象唯一名字 产生该对象的任务（若初始时就有该对象，即为初始数据，该项为空） 对象当前位置

Task Table

Task ID Dependencies Expected Outputs 任务唯一名字 任务依赖的对象 任务产生的对象

错误处理

CIEL 引擎将错误处理分为三个方面，Client 的错误处理、Worker 的错误处理以及 Master 的错误处理。

Client 在 CIEL 引擎的执行模型中只负责向 Master 提交作业，因此它的容错不在 CIEL 引擎的处理范围之内。不过，如果是单个作业，重复提交或者首先向 Master 按名请求作业结果即可；如果是多个作业，则需要 Client 实现诸如 Apache Airflow 一类的机制。CIEL 引擎提供了 Skywriting DSL 支持简单的作业依赖描述，解放了后一种情况所需的负担。

Worker 的错误处理比较直白，重做任务或在级联失败的情况下递归地重做任务。这种方案是批处理本位的处理，因为在流计算中，完全重做任务通常是不可接受的，有时是不可能的。

Master 的错误处理是 CIEL 引擎主要需要讨论的内容，因为 CIEL 引擎主要的特点就在于 Master 维护了特殊的元数据。总的来说，错误处理还是批处理本位的，即假定作业在有限时间内可以完成且完全重做任务是可接受的。在此基础上，通过三种具体的技术提升错误处理的体验。

1. 持久化日志。在创建作业时，Master 同时为作业创建一个日志文件，并同步地将根任务（即种子任务）的描述符写到日志中。日志文件可以写在本地或者分布式文件系统上。当新的任务被创建时，其描述符被异步地追加到日志中。当作业完成时，对应结果的具体引用被写到日志中。在重启的时候，通过回放日志来重新构建 Master 的状态。

2. 次要主节点。这种方法也就是常见的 Standby 机制，论文中没有详细讨论在极端失败场景下的错误处理问题，例如次要主节点错误的认为 Master 失败的集群双主问题等。

3. 动态作业图重建。这种方法以 Worker 为出发点，当 Master 失败后，Worker 尝试重新连接同一个（网络）位置的 Master，并在重连成功后将自己的状态即存储对象表发送给 Master，以期 Master 能够从中恢复状态。

这三种技术中，第二种跟第一第三种是不排斥的，实际起作用的可以认为是第一第三两种之一。这两种思路的差别在于作业状态以 Master 为准或者以 Worker 为准，实际情况可以根据引擎的特点进行选择。论文中只是简单罗列了可能性，由于不是重点内容，并未做出详尽的讨论。

流式计算的支持

前面提到任务依赖的对象必须被构造之后，当前任务才被允许执行，并且对象被构造后就不可变。这要求对象的构造是可以完成的动作，而流式计算中任务的输出可能是无界的数据集。同时，批处理任务也可以采用流的形式描述，从而得到持续处理输出而不是等待批次再一并处理的效果。

因此，CIEL 引擎提供了 stream reference 和 stream consumers 等抽象。它们与此前提到的 reference 和 task 大同小异，区别在于对象是一个可追加数据的管道，当有数据产生时，对象就存在，依赖它的任务因此不再被它所阻塞。这一块论文中说得不多，具体调度是在有一个依赖构建完管道时就调度起来还是所有依赖构建完管道后再调度是一个开放问题。