【轉】分散式數據流的輕量級非同步快照

• 2019 年 10 月 4 日
• 筆記

本篇翻譯自論文：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/