【转】分布式数据流的轻量级异步快照

本篇翻译自论文：Lightweight Asynchronous Snapshots for Distributed Dataflows，Flink的容错快照模型即来源于该论文。原文地址：https://arxiv.org/pdf/1506.08603.pdf

分布式数据流的轻量级异步快照

摘要

分布式有状态的流处理使得大规模持续计算能够部署在云端，它的目标是低延迟和高吞吐。其最基本的挑战之一是提供潜在失败可能性下对处理的保证。现有的方法都依赖用于故障恢复的周期性全局状态快照。这些方法有两个主要缺点。首先，它们经常停止（拖延）全部的计算，这会影响摄取。其次，它们热衷于保持运行过程中的所有状态，导致快照比所需的要大。在我们这项工作中，我们提出了异步屏障快照Asynchronous Barrier Snapshotting (ABS)，这是一个的、适用于现代数据流执行引擎的、将空间占用最小化的轻量级算法。ABS仅仅在非循环执行拓扑上保留Operator的状态，同时在循环的数据流上保留最小化的record日志。我们在Apache Flink（一个支持有状态的分布式流处理分析引擎）中实现了ABS。我们的评估表名，我们的算法对执行没有很重的影响，并且保持了线性的扩展以及在频繁快照的情况下表现良好。

关键词 容错, 分布式计算, 流处理, 数据流, 云计算, 状态管理

1. 介绍

分布式数据流处理是一种新出现的允许持续计算的数据密集型计算范例，目标是端到端的低延迟同时保证高吞吐量。一些对时间要求严格的应用可以从诸如Apache Flink和Naiad这样的数据流处理系统受益，尤其是实时分析领域（eg. 预测分析和复杂事件处理）。容错在这类系统中至关重要，因为绝大多数真实世界的用例是不能提供错误的。目前已知的，在有状态的处理系统上能够保证exactly-once语义的方法，依赖于执行状态的全局一致快照。然而，这里有两个主要缺点会使得它们的应用对于实时流处理而言效率低下。同步快照技术会停止分布式计算的整体执行来获得整体状态的一致视图。此外，据我们所知，已知的所有分布式快照算法会包含正在通道中传输的记录或者未处理的信息作为快照的一部分，大多数情况下，包含的状态会比需要的大。

在这项工作中，我们专注于提供轻量级的快照，专门针对分布式有状态的数据流系统，在性能上影响很小。我们的解决方案提供异步的低空间成本状态快照，它仅仅包含了Operator在非循环执行拓扑上的状态。另外，我们通过在拓扑的选中部分应用下游备份，同时保持快照状态在最小值，来覆盖循环执行图的case。我们的技术不会停止流操作，它只会引入很小的运行开销。这篇论文的主要贡献可以归纳如下：

• 我们提出并且实现了一个异步快照算法，它在非循环执行图上实现了最小化的快照。
• 我们描述并实现了用于循环执行图上的算法的概论。
• 我们展示了我们的方法相比于使用Apache Flink Streaming作为基础系统的最新技术的优势。

论文的剩余篇幅组织如下：第2部分概述了有状态数据流系统中分布式全局快照的现有方法；第3部分提供了Apache Flink的处理处理和执行模型，接着第4部分我们详细描述了全局快照的主要方法。我们的恢复方案会在第5部分有个简要介绍。第6部分总结了我们的实现，第7部分是我们的测试评估，未来工作和结论在第8部分。

2. 相关工作

在过去十年间，（业界）为做持续处理的系统提出过几种恢复机制[4,11][4,11]。将持续处理模拟为无状态分布式批处理计算（如离散化流和Comet[6，15][6，15]）的系统依赖于状态重新计算。另一方面，有状态的数据流系统，如Naiad、SDGs、Piccolo和SEEP[3、5、11、12][3、5、11、12]（它们也是我们在这项工作中的主要关注点），使用checkpoint检查点获取故障恢复的全局执行的一致快照。Chandy和Lamport[4][4]提出的分布式环境中的一致全局快照问题在过去几十年中得到了广泛的研究[4,7,8][4,7,8]。全局快照理论上反映了执行的整体状态，或者在其操作的特定实例上可能的状态。Naiad [11][11]采用的一种简单但成本高昂的方法是分三步同步快照：第一步是暂停执行图的整体计算，第二步是执行快照，最后一步是指示每个task在全局快照完成后继续其操作。这个方法对吞吐量和空间使用都有着很大的影响，因为需要阻塞整个计算，同时还依赖上游备份，该备份记录生产者端发送的records。另外一种流行的方法，最初由Chandy和Lamport提出，现在已经部署在很多系统中，是在做上游备份的时候异步执行快照[4,5,10][4,5,10]。这是通过在整个执行图中分布标记来实现的，这些标记会触发Operator和通道状态的持久性。但是，由于需要上游备份，并且由于对备份记录的重新处理导致恢复时间延长，这种方法仍然存在额外的空间需求。我们的方法扩展了Chandy和Lamport最初的异步快照思想，但是，它不考虑非循环图记录的备份日志记录，同时在循环执行图上保留非常有选择性的备份记录。

3. Apache Flink

我们当前的工作以Apache Flink Streaming的容错需求为指导，Apache Flink Streaming是一个分布式流分析系统，是Apache Flink Stack（前身Stratosphere [2][2]）的一部分。 Apache Flink围绕通用的Runtime引擎进行架构，统一处理有状态并且互连的task组成的批处理和流工作。 Flink中的分析作业被编译为任务的有向图。 数据元素从外部源获取，并以管道方式通过任务图进行路由。 task根据收到的输入持续操纵其内部状态，并产生新的输出。

3.1 流式编程模型

Apache Flink的流式处理API允许通过暴露无界有分区的数据流（部分排序的record序列）作为其核心的数据抽象（称为DataStream）来组合复杂的流分析job。DataStream可以从外部数据源创立（如消息队列，Socket流，自定义Generator）或者通过在其他DataStream上调用操作。DataStream以高阶函数的形式支持多种operator如map、filter、reduce，这些函数在每条记录上都应用，生成新的DataStream。下面代码示例1展示了如何在Apache Flink实现一个增量的WordCount。在这个程序里，单词从文本读入，每个单词的count打印到标准输出。这是一个有状态的流程序，因为数据源需要留意当前单词在文件的偏移量，计数器叶鏊维持当前的每个单词的计数作为它们的内部状态。

图1：增量的WordCount执行图

示例1：增量的WordCount程序

3.2 分布式数据流执行

当用户执行一个应用，所有的DataStream operator会编译成一个执行图，原则上是一个有向图G = (T, E)，顶点T代表Task，边E代表task之间的数据通道，这和Naiad相似。上图1描绘了一个增量WordCount示例程序的执行图。如图所示，每个operator实例都被封装到相关task上。 当没有输入通道时，task可以更进一步被分类为数据源，没有输出通道时，task可以下沉。此外，M表示在并行执行期间所有通过task传输的record的集合，每个task t∈Tt∈T 封装了一个独立执行的operator实例，并且由以下部分组成：（1）输入输出通道的集合：It,Ot⊆EIt,Ot⊆E；（2）一个operator的状态stst和（3）用户自定义函数（UDF）ftft。数据接收是基于拉取（pull-based）的：在执行期间，每个task消耗其input records，更新其operator状态并根据其用户自定义函数生成新记录。更具体地说，对于一个task t∈Tt∈T接收的每个record r∈Mr∈M，一个新的状态s、tst、会随着根据UDF ft:st,r−>[s、t,D]ft:st,r−>[st、,D] 得到的输出records集合 D⊆MD⊆M产生。

4. 异步屏障快照（Asynchronous Barrier Snapshotting， ABS）

为了提供持续的输入，分布式处理系统需要对故障task有弹性（容忍）。一个提供弹性的方式是周期性地抓取执行图的快照，这样就可以用来稍后从故障中恢复。一个快照是一个执行图的全局状态，抓取所有必须的信息来从特定的执行状态重启计算。

4.1 问题定义

我们定义了一个执行图G=(T,E)G=(T,E)的全局快照Gx=(Tx,Ex)Gx=(Tx,Ex)作为一个所有task和edge的状态集合，TxTx和ExEx分别地。更详细地说，TxTx由所有operator的状态sxt∈Tx,∀t∈Tstx∈Tx,∀t∈T组成，ExEx是通道状态的集合ex∈Exex∈Ex，而exex由在e中传输的records组成。

我们需要为每个快照G∗G∗保留某些属性，为了保证恢复的正确结果如Tel所描述的终止（Termination）和可行性（Feasibility）[14][14]。

终止（Termination）保证了一个快照算法在所有进程alive的情况下最终能在有限的时间内完成。可行性（Feasibility）表示快照是有意义的的，即在快照过程中没有丢失有关计算的信息。从形式上讲，这意味着快照中维护了因果顺序，这样task中传递的records也是从快照的角度发送的。

4.2 非循环数据流的ABS

执行被拆分成stages的情况下，不保存通道状态就做快照是可行的。Stages将注入的数据流和所有相关的计算拆分为一系列可能的执行（executions），在这些执行中，所有先前的输入和生成的输出都已经被安全处理。一个stage结束时的operator状态的集合反映了整个执行的历史。因此，它可以单独用于快照。我们算法的核心思想是在保持持续数据流入的同时，使用阶段性（分阶段）快照创建相同的快照。

在我们的方法中，stage在持续数据流执行中被特殊的屏障标记所模拟，这些屏障标记被数据流周期性地注入，也在整个执行图中被推送到下游接收。随着每个task接收指示执行阶段的屏障，逐步构建全局快照。 我们进一步对我们的算法做出以下假设：

图2：非循环图的异步屏障快照（ABS）

算法1：非循环执行图的异步屏障快照

 1: upon event do
 2: state := init_state; blocked_inputs := ϕϕ;
 3: inputs := input_channels;
 4: outputs := output_channels; udf := fun;
 5:
 6: upon event > do
 7: if input ≠≠ Nil then
 8: blocked_inputs := blocked_inputs ∪∪ {input};
 9: trigger ;
 10: if blocked_inputs = inputs then
 11: blocked_inputs := ϕϕ;
 12: broadcast >;
 13: trigger ;
 14: for each inputs as input
 15: trigger ;
 16:
 17:
 18: upon event do
 19: {state ‘‘, out_records}:=udf(msg,state);
 20: state:=state‘‘;
 21: for each out_records as {out_put,out_record}
 22: *trigger ;
 23:
 
网络信道是准可靠的，遵守FIFO传送次序，可以被阻止（blocked）和解除阻止（unblock）。
 当通道被阻止（blocked）时，所有消息（msg）都被缓冲但在解除阻塞（unblock）之前不会继续传递。

• Task可以在它们的通道（channel）组件触发（trigger）操作如阻止（blocked）、解除阻止（unblock）和发送（send）消息。广播（broadcast）消息也是在输出通道（output_channel）上支持的。
• 在源头task上注入的消息（msg），即消息屏障，被解析为“Nil”输入通道（input_channel）。

译者注：这段确实有点晦涩难懂，我来解释一下。

1. 首先说图，可以看到图上黑色加粗的线标记的是barrier屏障，屏障存在于每个通道上，可以看做一个特殊的record，在其前面的record叫preshot records，在其后面的record叫postshot records，当preshot records都被传递到途中的count算子后，src->count的通道上只剩postshot records，这时候通道会block，按照前文的说法，block的channel上的record都会在缓存里。当连接至某个算子的全部输入信道（如图中b所示的count-1 task的两条输入通道src-1->count-1和src-2->count-1通道）都已经block以后，对该task做快照，同理图中c所示的count-2 task也一样。
2. 然后说算法，首先要明确一下，算法中的input和output其实都是指通道。
   • 第一个方法很好理解，一个初始化方法，此时block的输入通道是空集，也就是没有被block的通道。
   • 第二个和第三个方法其实都是receive的方法，上面我在解释图的时候说过，可以把barrier当作一个特殊的record来考虑。所以，第二个方法是接收到barrier，第三个方法是接收到正常的有msg的record。那我们先来说第二个，当task接收到barrier屏障时，首先是个常规的空值判断，如果input不为空，那么就把触发该input通道的block。并且该task的block的input通道的集合为当前已经block的通道和参数input通道的并集。如果block的input通道等于所有input通道，也就是所有input通道都已经被block了，此时触发该task的快照操作，并且把屏障往后广播（即对所有output通道加上这个屏障），然后对所有input通道解除block。
   • 第三个方法，传入msg，通过UDF计算出结果record和结果状态，并且把结果状态赋值给当前状态，并且把所有结果record往后发送（结果集的每个record对应的output通道不一定是同一个，只逐个往对应的output通道发送）。

下文也会有官方解释，更进一步了解该算法。↓↓↓↓

ABS算法也如图2所示：一个中心协调器会周期性地给所有source注入stage屏障。当一个source收到了屏障，它就会给当前状态做一个快照，然后广播屏障到所有输出通道（如图2的a）。当一个非source的task收到了其input通道里的某个发送过来的屏障，它会block该input通道直到它收到了所有input通道的屏障（算法第9行，图2的b），然后该task就会生成其当前状态的快照并且广播屏障给所有output通道（算法第12-13行，图2的c）。接下来，该task会解除所有input通道的block继续计算（算法第15行，图2的d）。最终的全局快照Gx=(Tx,Ex)Gx=(Tx,Ex)是完全由所有Ex=ϕEx=ϕ的operator的状态T∗T∗组成的。

证明简述：正如之前提到的，一个快照算法需要保证终止（Termination）和可行性（Feasibility）。 终止（Termination）是由通道和非循环执行图的属性保证的。通道的可靠性保证了只要task存活，最终将收到之前发送的每个屏障。 此外，由于始终存在来自源的路径，因此有向无环图（DAG）拓扑中的每个任务task都会从其所有输入通道接收到屏障并生成快照。 至于可行性（Feasibility），它足以表明全局快照中的operator的状态只反映到最后一个stage处理的records的历史。这是由先入先出顺序（FIFO）和屏障上input通道的block来保证的，它确保在快照生成之前没有post-shot记录会被处理。

4.3 循环数据流的ABS

在执行图存在有向循环的情况下，前面提出的ABS算法不会终止，这就会导致死锁，因为循环中的task将无限等待接收来自其所有输入的屏障。此外，在循环内任意传输的records不会包含在快照中，违反了可行性。因此，需要一致地将一个周期内生成的所有记录包括在快照中，以便于可行性，并在恢复时将这些记录放回传输中。我们处理循环图的方法扩展了基本算法，而不会引入任何额外的通道阻塞，如下算法2所示。首先，我们通过静态分析，在执行图的循环中定义back-edges L。根据控制流图理论，在一个有向图中，一个back-edge是一个指向已经在深度优先搜索（depth-first search）中被访问过的顶点（vertex）的边（edge）。定义执行图 G(T, E \ L) 是一个包含拓扑中所有task的有向无环图（DAG）。从这个DAG的角度来看，该算法和以前一样工作，不过，我们在快照期间还使用从已定义的back-edges接收的记录的下游备份。这是由每个task t 实现的，back-edges的一个消费者Lt⊆It,LtLt⊆It,Lt产生一个从LtLt转发屏障到接收屏障们回LtLt的备份日志。屏障会push所有在循环中的records进入下游的日志，所以它们在连续不断的快照中只会存在一次。

图3：循环图的异步屏障快照（ABS）

算法2：非循环执行图的异步屏障快照

 1: upon event do
 2: state := init_state; marked := ϕϕ;
 3: inputs := input_channels; logging := False
 4: outputs := output_channels; udf := fun;
 5: loop_inputs := backedge_channels;
 6: state_copy := Nil; backup_log := [];
 7:
 8: upon event > do
 9: marked := marked ∪∪ {input}
 10: regular := inputs \ loop_inputs;
 11: if input ≠≠ Nil AND input ∉∉ loop_inputs then
 12: trigger ;
 13: if !logging AND marked = regular then
 14: state_copy := state; logging := True;
 15: broadcast >;
 16: for each inputs as input
 17: trigger ;
 18:
 19: if marked = input_channels then
 20: trigger ;
 21: marked := ϕϕ; logging := False;
 22: state_copy := Nil; backup_log := [];
 23:
 24: upon event do
 25: if logging AND node ∈∈ loop_inputs then
 26: backup_log := backup_log :: [input];
 27: {state ‘‘, out_records}:=udf(msg,state);
 28: state:=state‘‘;
 29: for each out_records as {out_put,out_record}
 30: *trigger ;
 31:
 

译者注：这个算法跟上一个算法不一样的地方在于，把循环过的input边当作back-edge，其余边当作regular，除掉循环的DAG依然还是按之前的做法处理，然后有back-edge的边的task，在接收到屏障的时候需要把其state做一个备份，并且接受它的back-edge中在屏障之前的pre-shot record作为log。

更详细解释下ABS算法2（图3所示）：有着back-edge作为输入通道的task，一旦它们的常规通道（e∉Le∉L）都接收到了屏障，该task就会产生了一个其状态的本地备份（算法的14行，图3的b）。接下来，从这一点开始，它们记录从back-edges收到的所有record，直到它们收到来自它们的stage屏障（算法第26行）。这就允许，像图3（c）中看到的，所有在循环中的pre-shot record，都会包含在当前快照中。注意，最后的全局快照Gx=(Tx,Lx)Gx=(Tx,Lx) 包含了所有task的状态TxTx和在传输中Lx⊂ExLx⊂Ex仅仅back-edge中的记录。

证明简述：再次地，我们需要证明终止（Termination）和可行性（Feasibility）。与4.2中终止（Termination）被保证一样，因为每个task最终都会接收到所有输入通道（包括后端）的屏障。通过从所有常规输入接收屏障后立即广播屏障，我们避免了前面提到的死锁条件。

FIFO的属性仍适用于back-edge，以下属性证明了可行性。（1）快照中包含的每个task状态，是在处理常规输入接收的post-shot record之前所执行的各自task的状态副本。 （2）快照中包含的下游日志是完整的，由于FIFO保证，包含back-edge接收的所有屏障之前的所有pending的post-shot record。

5. 故障恢复

虽然不是这项工作的主要焦点，但故障恢复方案是我们应用快照方法的动机。因此，我们在这里简要说明了它的操作。有几种故障恢复方案可以使用这种持续快照。在最简单的形式中，整个执行图可以从上一个全局快照重新启动，如下所示：每个任务t（1）从持久化存储中检索其快照stst的关联状态并将其设置为其初始状态，（2）恢复其备份日志并处理所有其中包含的records，（3）开始从其输入通道中摄取records。类似于TimeStream [13]，部分图恢复方案也是可行的，通过仅重新安排上游依赖task（输出通道连接失败task的task）以及它们各自的上游任务直到源。 示例恢复计划如图4所示。为了提供exactly-once语义，应在所有下游节点中忽略重复记录以避免重新计算。 为了实现这一目标，我们可以遵循与SDG类似的方案[5]，使用来自源的序列号标记记录，因此，每个下游节点都可以丢弃序列号小于已处理的记录的记录。

图4：示例恢复计划

6. 实现

我们为Apache Flink贡献了ABS算法的实现，以便为流运行时提供精确的一次处理语义。在我们当前的实现中，阻塞通道将所有传入记录存储在磁盘上，而不是将它们保留在内存中以提高可伸缩性。虽然这种技术确保了鲁棒性，但它增加了ABS算法的运行时间影响。

为了从数据中区分operator状态，我们引入了一个显式的OperatorState接口，该接口包含更新和检查状态的方法。 我们为Apache Flink支持的有状态的运行时operator提供了OperatorState实现，例如基于偏移量的源或聚合。

快照协调是作为JobManager上的参与者进程实现的，它为单个job的执行图保留全局状态。协调器定期向执行图的所有源注入阶段屏障。重新配置后，最后一个全局快照状态将从分布式in-memory的持久化存储中恢复到operator上。

7. 评估

我们评估的目标是将ABS的运行时开销与Naiad [11]中采用的全局同步快照算法进行比较，并测试该算法在大量节点上的可扩展性。

7.1 Setup

用于评估的执行拓扑（图5）由6个不同的运算符组成，并行度等于集群节点的数量，Task点的数量是6倍的集群节点数量。该执行包含了3个shuffle，以强调ABS中通道阻塞的可能影响。 源生成总共10亿条记录，这些记录统一分布在源实例之间。拓扑中的operator的状态是每个key的聚合和源偏移。 实验在Amazon EC2集群上运行，使用多达40台 m3.medium实例。

图5：用于评估的执行拓扑

我们测量了在不同快照方案下运行的评估作业的运行时开销，即ABS和具有不同快照间隔的同步快照[11]。 我们在Apache Flink上实现了Naiad [11]中使用的同步快照算法，以便为比较提供相同的执行后端。 该实验使用10节点集群运行。 为了评估算法的可扩展性，我们处理了固定数量的输入记录（10亿），同时将拓扑的并行性从5个增加到40个节点。

7.2 结论

在图6中，我们描述了两种算法对基线的运行时影响（没有容错）。当快照间隔很小时，同步快照的巨大性能影响尤为明显。这是因为系统花费更多时间不处理任何数据，以获得全局快照。 ABS对运行时的影响要小得多，因为它在不阻塞整体执行的情况下连续运行，同时保持相当稳定的吞吐率。对于较大的快照间隔，同步算法的影响不太重要，因为它是突然执行的（在我们的实验中为1-2秒），同时让系统在其余执行期间以其正常吞吐量运行。然而，就许多临界环境应用（如入侵检测管道）的实时保证而言，突发事件通常会违反SLA。因此，这些应用将通过ABS的性能进一步受益。在图7中，我们将运行ABS的拓扑的可扩展性与基线的3秒快照间隔进行比较（没有容错）。很明显，基线工作和ABS都实现了线性可扩展性。

图6：两种算法对基线的运行时影响（没有容错）

图7：与基线的3秒快照间隔进行比较（没有容错）

8. 未来的工作和结论

在未来的工作中，我们计划通过解耦快照状态和运行状态来探索进一步降低ABS影响的可能性。 这允许纯粹的异步状态管理，因为任务可以在持久化快照的同时连续处理记录。 在这种方案中，还需要将pre-shot和post-shot记录与相应的状态同步，这可以通过根据它们所属的快照标记记录来解决。 由于这种方法会增加算法的计算，空间和网络I/O要求，我们计划将其性能与我们当前的ABS实现进行比较。 最后，我们计划研究不同的恢复技术，这些技术只维护exactly-once语义，同时通过在每个任务粒度上操作来最小化重新配置的需要。

综上所述，我们重点研究了分布式数据流系统中周期性全局快照的问题，介绍了一种新的快照技术ABS，它可以获得良好的吞吐量。ABS是第一个考虑非循环执行拓扑可能的最小化的状态的算法。此外，我们还扩展了ABS来处理循环执行图，只存储恢复时需要重新处理的记录。我们在ApacheFlink上实现了ABS，并跟同步快照作对比，测试评估了我们的方法。在此早期阶段，ABS显示出良好的效果，对整体执行吞吐量的影响很小，具有线性可扩展性。

参考文献

[1] Apache flink. https://flink.apache.org/.

[2] A. Alexandrov, R. Bergmann, S. Ewen, J.-C. Freytag, F. Hueske, A. Heise, O. Kao, M. Leich, U. Leser, V. Markl, et al. The stratosphere platform for big data analytics. The VLDB JournalThe International Journal on Very Large Data Bases, 23(6):939–964, 2014.

[3] R. Castro Fernandez, M. Migliavacca, E. Kalyvianaki, and P. Pietzuch. Integrating scale out and fault tolerance in stream processing using operator state management. In Proceedings of the 2013 ACM SIGMOD international conference on Management of data, pages 725–736. ACM, 2013.

[4] K. M. Chandy and L. Lamport. Distributed snapshots: determining global states of distributed systems. ACM Transactions on Computer Systems (TOCS), 3(1):63–75, 1985.

[5] R. C. Fernandez, M. Migliavacca, E. Kalyvianaki, and P. Pietzuch. Making state explicit for imperative big data processing. In USENIX ATC, 2014.

[6] B. He, M. Yang, Z. Guo, R. Chen, B. Su, W. Lin, and L. Zhou. Comet: batched stream processing for data intensive distributed computing. In Proceedings of the 1st ACM symposium on Cloud computing, pages 63–74. ACM, 2010.

[7] A. D. Kshemkalyani, M. Raynal, and M. Singhal. An introduction to snapshot algorithms in distributed computing. Distributed systems engineering, 2(4):224, 1995.

[8] T. H. Lai and T. H. Yang. On distributed snapshots. Information Processing Letters, 25(3):153–158, 1987.

[9] L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, 1978.

[10] Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein. Distributed graphlab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 5(8):716–727, 2012.

[11] D. G. Murray, F. McSherry, R. Isaacs, M. Isard, P. Barham, and M. Abadi. Naiad: a timely dataflow system. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 439–455. ACM, 2013.

[12] R. Power and J. Li. Piccolo: Building fast, distributed programs with partitioned tables. In OSDI, volume 10, pages 1–14, 2010.

[13] Z. Qian, Y. He, C. Su, Z. Wu, H. Zhu, T. Zhang, L. Zhou, Y. Yu, and Z. Zhang. Timestream: Reliable stream computation in the cloud. In Proceedings of the 8th ACM European Conference on Computer Systems, pages 1–14. ACM, 2013.

[14] G. Tel. Introduction to distributed algorithms. Cambridge university press, 2000.

[15] M. Zaharia, T. Das, H. Li, S. Shenker, and I. Stoica. Discretized streams: an efficient and fault-tolerant model for stream processing on large clusters. In Proceedings of the 4th USENIX conference on Hot Topics in Cloud Ccomputing, pages 10–10. USENIX Association, 2012.

【原文】http://blog.orisonchan.cc/2019/04/04/51/