本文轉自：https://zhuanlan.zhihu.com/p/47838090.
本站轉載已經過作者授權。如需轉載，請和原作者聯系。
最近兩年流式計算又開始逐漸火了起來，說到流式計算主要分兩種：continuous-based 和 micro-batch。最近在使用基于 micro-batch 模式的 Spark Streaming，正好結合論文介紹一下。這裡說的論文是 2013 年釋出的 《Discretized Streams: Fault-Tolerant Streaming Computation at Scale》，雖然是 2013 年發表的論文，但是系統的核心邏輯基本沒怎麼變化，對于了解 Spark Streaming 的系統設計、工作方式還是很有幫助的。注：Spark 在 2016 年推出了 Structured Streaming，後來逐漸演變成 continuous based，基于 micro-batch 這種模式的 Spark Streaming 可能将逐漸淡出吧。
0. abstract
目前（2013 年）分布式流式系統的主要問題在于錯誤恢複的代價非常高：熱備份或者恢複時間長，而且不處理 straggler，這裡的 straggler 是分布式系統某一個成員/成分運作滞後于其他組成部分，比如某個 task 節點的運作時間要明顯長于其他節點。相比之下，DStream (Spark Streaming 的流式處理模式，全稱 discretized streams) 錯誤恢複更快，而且會處理 straggler。除此之外，還有其他優點包括：提供豐富的算子、高吞吐、可以線性擴充到 100 個節點的叢集規模、亞秒級延遲和壓秒級故障恢複。最後，DStream 還可以和批處理、互動式查詢結合使用。
1. Overview
分布式計算主要分兩種：批（batch）處理和流式（streaming）計算，流式計算的主要優勢在于其時效性和低延遲。而大規模流式計算系統設計的兩個主要問題是錯誤處理和 straggler 處理。由于流式系統的實時性，錯誤之後如何快速恢複顯得極其重要。
不幸的是，現存的流式系統在這兩個點的設計上都不夠好。比如 Storm 和 TimeStream 等（這個時候 flink 還沒有大規模流行起來） 都是基于 continuous operator 模式，由一個持續運作、有狀态的節點負責接收和處理資料。在這種模式下的錯誤恢複主要由兩個方式：一個是 replication，也就是每個 operator 節點有一個 replication 節點；另一個是上遊在某個節點失敗之後對新的節點提供 replay。在大規模叢集模式下，這兩種方式都不太可取：replication 會耗費一倍的資源；上遊 replay 會耗費一定時間。而且這兩種模式都沒處理 straggler: 第一種模式會由于 straggler 的存在導緻 replication 的過程變慢；第二種模式會将 straggler 當成失敗節點，然後進行恢複，代價比較大。
Spark Streaming 的模式是 discretized streams (D-Streams)，這種模式不存在一直運作的 operator，而是将每一個時間間隔的資料通過一系列無狀态、确定性（deterministic）的批處理來處理。比如對每一秒的資料通過 MapReduce 計算 count。類似的，也可以疊加計算多個批次的資料的 count。簡而言之，DStream 模式下，一旦 input 給定，輸出狀态就是确定的；下面我們會詳細說明為什麼 DStream 的失敗恢複模式要優于前面兩種模式。
DStream 的實作難點主要由兩個：低延遲和快速錯誤恢複（包括 straggler）。傳統的批處理系統，比如 Hadoop，一般運作的比較慢，主要是因為中間結果要進行持久化（注：這種也代表容錯性比較好）。DStream 使用彈性分布式資料集（Resilient Distributed Datasets），也就是 RDD，來進行批處理（注：RDD 可以将資料儲存到記憶體中，然後通過 RDD 之間的依賴關系快速計算）。這個過程一般是亞秒級的，對于大部分場景都是可以滿足的。
快速錯誤恢複主要是通過 DStream 的确定性來提供一種新的恢複機制：par- allel recovery。當一個節點失敗之後，我們通過叢集的其他節點來一起快速重建出失敗節點的 RDD 資料。這種恢複模式相比之前的 replication 和 upstream replay 都要快。這裡 straggler 的處理因為我們可以擷取到一個批處理 task 的運作時間，是以我們可以通過推測 task 的運作時間判斷是不是 straggler。
DStream 的實作系統是 Spark Streaming，基于 Spark 引擎。這個系統可以在 100 個節點的叢集上每秒處理 6kw 條資料，并保證亞秒級的延遲，錯誤恢複也可以保證在亞秒級。當然這些評測資料都是 2013 年，也就是 5 年前。論文繼續列舉了一些對比資料，這裡就不贅述了，總之結論就是 Spark Streaming 的吞吐和線性擴充要優于時下的其他流式計算系統。
最後值得一提的是，因為 Spark Streaming 使用的 RDD model 和批處理相同，是以使用者可以将 Spark Streaming 和批處理和互動式出現結合起來。或者将曆史 RDD 資料結合 Spark Streaming 一起來用（注：這裡的一個場景是線下訓練模型，然後通過 Spark Streaming 運用到實時資料上）。
2. Backgroud
很多分布式流式計算系統使用的是 continuous operator 模式，這種模式下會有多個持續運作的 operator，每個 operator 接收自己的資料然後并更新狀态。盡管這種方式可以減小延遲，但是因為 operator 本身是有狀态的，導緻錯誤恢複起來特别麻煩，如前所述，要麼通過 replication，要麼通過 upstream backup 和 replay。而這兩種方式的缺點也很明顯：資源浪費；恢複時間長。
replication 除了成本問題還有資料一緻性的問題，如何保證兩個節點收到的資料是一緻，是以還需要引入分布式協定，比如 Flux 或者 Borealis’s DPC。
upstream backup 模式下，當某個 operator 節點 fail 之後，upstream 将之前發送給失敗 operator 節點的資料從某個 checkpoint 重新發送給新的替代節點，這樣就會導緻恢複時間比較長。論文這裡沒有說 operator 的狀态儲存問題，實際上 operator 的狀态也是要儲存的，而且 checkpoint 要和 upstream 的 checkpoint 一緻。
除此之後，straggler 不管在 replication 模式還是 upstream backup 模式都不能很好的處理。
3. DStream
如上所述，DStream 通過一系列小的批處理作業來代替 operator 進而達到快速錯誤恢複的目的。
3.1 computation model
DStream 将批處理分解成多個一定時間間隔的批處理。在每個時間間隔的資料會被存儲成一系列的 RDD，然後通過一系列的算子，比如 map, reduce, group 等進行并行計算，最後将結果輸出成新的 RDD 或者輸出到系統外（比如 stdout, 檔案系統，網絡等）。
論文給了一個計算網站 pv 的例子，僞代碼如下
pageViews = readStream("http://...", "1s")
ones = pageViews.map(event => (event.url, 1))
counts = ones.runningReduce((a, b) => a + b)
對應的資料流如下圖
執行過程簡單描述如下：
- Spark Streaming 持續不斷接收 http url 的 view 資料 pageViews
- 将 pageViews 按 1s 間隔拆分成一系列的 RDD 資料（每個時間間隔也會包含多個 RDD 資料）
- 對 2 中的資料進行 map, reduce 等處理。
系統錯誤處理通過 DStream 和 RDD 的依賴關系來恢複。依賴關系的次元是 partition，也就是說每個 RDD 可能會分成多個 partition 然後分布在叢集的不同機器上，這樣當某個機器上的 RDD 資料丢失的時候就可以通過 RDD 的依賴關系從多個機器上來并行的回複資料了。上圖中的 DStream 就表示有 3 個 partition。除此之後，如果各個時間間隔沒有時序關系，那麼每個時間間隔的 RDD 資料也可并行恢複。這正是 DStream 快速錯誤恢複的關鍵所在。
3.2 Consistency Semantics
基于 continuous operator 的流處理系統當多個 operator 由于各自的負載不同可能導緻某些 operator 滞後，這樣整個系統的某個時間點的 snapshot 資料就是不準确的。針對這個問題，Borealis 對不同節點進行同步來避免這個問題；而 storm 直接忽略這個問題。
對于 DStream，由于時間被自然的離散化，而每個時間 interval 對應的 RDDs 都是容錯不可變且計算确定性的，是以 DStream 是滿足 exactly-once 語義的。
感覺這裡有一個前提，論文沒有點出來，就是 upstream 的資料是可靠的。
4. System Architecture
系統架構的主題變化不大，但是實作細節再讨論感覺意義不大。Spark Streaming 主要包括三個部分：
- master: 負責記錄 DStream 的依賴圖（lineage graph）和 task 的排程。我們現在也叫 driver。
- worker: 負責接收資料，存儲資料以及執行 task。我們現在也叫 executor。
- client library。
-
[轉載] Spark Streaming 設計原理
Spark Streaming 的無狀态的 task 可以運作在任意節點，相比于傳統的流式系統的固定拓撲結構（注：不太确定目前還是不是都是這樣），擴充起來會更加的容易。
Spark Streaming 的所有狀态都存儲在 RDD 中，同時 RDD 的 partition 可以存儲到任意節點或者通過多個節點計算。task 計算會考慮資料局部性，比如處理 parition A 的 task 會優先配置設定到 partition A 所在的節點運作。
下面的實作的一些細節部分不再讨論。
5. Fault and Straggler Recovery
Parallel Recovery 前面已經說過了，這裡就不贅述了。這裡在補充一下 straggler 的處理。
straggler 的判斷非常簡單，由于很多 task 都是很快結束，如果一個 task 明顯比其他 task 長就可以認為是 straggler。straggler 可以進行遷移，也就是将 task 遷移到其他機器上。
這篇論文雖然很久了，但是對于了解 Spark Streaming 的設計初衷或者設計思路還是很有幫助的。最後，對于論文中其他部分，或者略顯陳舊，或者啟發意義不大，這裡就不再贅述了。對于文章中有失偏頗的地方，還希望多多指教。