分布式計算

分布式計算#

內容來自

極客時間專欄:《分布式技術原理與算法解析》

MapReduce 計算模式 (分冶法)#

分而冶之思想#

簡稱分冶法，就是將一個複雜的、難以直接解決的大問題，分割成一些規模較小的、可以比較簡單的或直接求解的子問題，這些子問題之間相互獨立且與原問題形式相同，遞歸地求解這些子問題，然後將子問題的解合併得到原問題的解

計算流程#

整個 MapReduce 的工作流程主要可以概括為 5 個階段，即：Input（輸入）、Splitting（拆分）、Mapping（映射）、Reducing（化簡）以及 Final Result（輸出）

Fork-Join 計算模式#

Fork-Join 是 Java 等語言或庫提供的原生多線程並行處理框架，採用線程級的分而治之計算模式。它充分利用多核 CPU 的優勢，以遞歸的方式把一個任務拆分成多個 “小任務”，把多個 “小任務” 放到多個處理器上並行執行，即 Fork 操作。當多個 “小任務” 執行完成之後，再將這些執行結果合併起來即可得到原始任務的結果，即 Join 操作

Fork-Join 不能大規模擴展，只適用於在單個 Java 虛擬機上運行，多個小任務雖然運行在不同的處理器上，但可以相互通信，甚至一個線程可以 “竊取” 其他線程上的子任務

Stream 計算模式#

MapReduce 模式下任務運行完成之後，整個任務進程就結束了，屬於短任務模式。但任務進程的啟動和停止是一件很耗時的事，因此針對流數據的處理，對處理延遲要求很高的實時性任務，往往利用的就是 Stream 流計算模型

Stream 工作原理#

流計算強調的是實時性，數據一旦產生就會被立即處理，當一條數據被處理完成後，會序列化存儲到緩存中，然後立刻通過網絡傳輸到下一個節點，由下一個節點繼續處理，而不是像 MapReduce 那樣，等到緩存寫滿才開始處理、傳輸。為了保證數據的實時性，在流計算中，不會存儲任何數據，就像水流一樣滾滾向前

計算步驟#

提交流式計算作業：對於流式計算作業，必須預先定義計算邏輯，且提交後在運行期間不可更改邏輯，只能重新提交運行
加載流式數據進行流計算：流式計算作業一旦啟動將一直處於等待事件觸發的狀態，一旦有小批量數據進入，系統會立刻執行計算邏輯並迅速得到結果
持續輸出計算結果：在得到小批量數據的計算結果後，可以立刻將結果數據寫入在線 / 批量系統，無需等待整體數據的計算結果，以進一步做到實時計算結果的實時展現

Actor 計算模式#

Actor 模型，代表一種分布式並行計算模型。這種模型有自己的一套規則，規定了 Actor 的內部計算邏輯，以及多個 Actor 之間的通信規則。在 Actor 模型裡，每個 Actor 相當於系統中的一個組件，都是基本的計算單元

Actor 模型的三要素是狀態、行為和消息，有一個很流行的等式：Actor 模型 =（狀態 + 行為）+ 消息

Actor 工作流程#

當 Actor A 和 Actor B 需要執行 Actor C 中的 Function 邏輯時，Actor A 和 Actor B 會將消息發送給 Actor C， Actor C 的消息隊列存儲著 Actor A 和 Actor B 的消息，然後根據消息的先後順序，執行 Function 即可

Actor 優缺點分析#

優點#

實現了更高級的抽象。Actor 與 OOP 對象類似，封裝了狀態和行為。但是，Actor 之間是異步通信的，多個 Actor 可以獨立運行且不會被干擾，解決了 OOP 存在的競爭問題。
非阻塞性。在 Actor 模型中，Actor 之間是異步通信的，所以當一個 Actor 發送信息給另外一個 Actor 之後，無需等待響應，發送完信息之後可以在本地繼續運行其他任務。也就是說，Actor 模型通過引入消息傳遞機制，從而避免了阻塞。
無需使用鎖。Actor 從 MailBox 中一次只能讀取一個消息，也就是說，Actor 內部只能同時處理一個消息，是一個天然的互斥鎖，所以無需額外對代碼加鎖。
並發度高。每個 Actor 只需處理本地 MailBox 的消息，因此多個 Actor 可以並行地工作，從而提高整個分布式系統的並行處理能力。
易擴展。每個 Actor 都可以創建多個 Actor，從而減輕單個 Actor 的工作負載。當本地 Actor 處理不過來的時候，可以在遠程節點上啟動 Actor 然後轉發消息過去

缺點#

Actor 提供了模塊和封裝，但缺少繼承和分層，這使得即使多個 Actor 之間有公共邏輯或代碼部分，都必須在每個 Actor 中重寫這部分代碼，也就是說重用性小，業務邏輯的改變會導致整體代碼的重寫
Actor 可以動態創建多個 Actor，使得整個 Actor 模型的行為不斷變化，因此在工程中不易實現 Actor 模型。此外，增加 Actor 的同時，也會增加系統開銷。
Actor 模型不適用於對消息處理順序有嚴格要求的系統。因為在 Actor 模型中，消息均為異步消息，無法確定每個消息的執行順序。雖然可以通過阻塞 Actor 去解決順序問題，但顯然，會嚴重影響 Actor 模型的任務處理效率

Actor 模型的應用#

Akka
Quasar (Java)
Erlang/OTP

Actor 模型總結：

Pipeline 流水線計算模式#

計算機中的流水線（Pipeline）技術是一種將每條指令拆分為多個步驟，多條指令的不同步驟重疊操作，從而實現幾條指令並行處理的技術。現代 CPU 指令採用了流水線設計，將一條 CPU 指令分為取指（IF）、譯碼（ID）、執行（EX）、訪存（MEM）、回寫（WB）五級流水線來執行。在分布式領域中，流水線計算模式也類似，它是將一個大任務拆分為多個步驟執行，不同的步驟可以採用不同的進程執行

計算流程#

以機器學習中的數據預處理為例，假設現在有 5 個樣本數據，每個樣本數據進行數據預處理的流程，包括數據去重、數據缺失值處理、數據歸一化 3 個步驟，且需要按照順序執行。也就是說，數據預處理這個任務可拆分為數據去重 —> 數據缺失值處理 —> 數據歸一化 3 個子任務。如果現在有 3 個節點，節點 1 執行數據去重，節點 2 執行數據缺失值處理，節點 3 執行數據歸一化。那么，節點 1 處理完樣本 1 的數據，將處理後的數據發送節點 2 後，則節點 1 可以繼續處理樣本 2 的數據，同時節點 2 處理樣本 1 的數據，以此類推，就實現了多任務的並行執行

流水線計算模式應用#

機器學習流水線任務，比如 TensorFlow
Apache Beam (沒具體研究過，看介紹是基於流水線處理思想)

總結拓展#

流計算和批量計算的區別#

流水線模式和 MapReduce 模式中，都有將大任務拆分為多個子任務，兩者的區別是什麼？#

MapReduce 以任務為粒度，將大的任務劃分成多個小任務，每個任務都需要執行完整的、相同的步驟，同一任務能被並行執行，可以說是任務並行的一種計算模式；
而流水線計算模式以步驟為粒度，一個任務拆分為多個步驟，每個步驟執行的是不同的邏輯，多個同類型任務通過步驟重疊以實現不同任務的並行計算，可說是數據並行的一種模式

此外，它們的子任務（步驟）間的關係不同：

在 MapReduce 中，各個子任務可以獨立執行，互不干擾，多個子任務執行完後，進行結果合併得到整個任務的結果，因此要求子任務之間是沒有依賴關係的；
在流水線模式中，多個子任務之間是具有依賴關係的，前一個子任務的輸出是後一個子任務的輸入。

綜合來講，MapReduce 計算模式適合任務並行的場景，而流水線計算模式適合同類型任務數據並行處理的場景