【IT168 技術】長期以來學習掌握分布式系統的知識非常龐雜混亂，本文將分布式算法歸納為幾種：計時模型timing model; 進程間通訊interprocess communication和失敗模型failure model。

　　計時模型timing model

　　計時模型分同步 異步和部分同步三種，這幾種模型都有時間計時這個共同特點。

　　同步模型是直接調用執(zhí)行，組件之間同時按步驟執(zhí)行，這個模型的問題是無法反映現實情況，甚至在分布式情況下很少有真正同步，比如過去RPC(遠程過程調用)等都是兩個服務器之間的代碼方法直接相互調用，這種問題帶來相互堵塞各種服務器進程，現在服務器之間都是通過發(fā)送消息實現通訊，讓發(fā)送消息變成同步幾乎很難。同步模型好處是能完成理論上測試結果，比如，因為同步模型有時間上的保證，我們可以看看一個問題在同步模型下是否能夠解決，如果在有時間保證的機制下都不能解決，意味著在沒有時間保證的機制也是不可能解決的。

　　異步模型有點復雜，組件之間的動作是按照它們自己的順序要求進行的，也不提供任何關于采取這些行動的時間上與速度的保證，這個模型更接近于現實情況，但是也不是完美的，比如一個進程會需要無限循環(huán)來響應一個請求，在真實項目中，我們可能會強加一個計時timeout，一旦超過這個timeout，將會退出這個請求的處理，這就帶來了問題，如果確保一個進程活躍的條件?也就是說，如何知道一個進程是需要無限循環(huán)活躍的，而其他進程則是不需要，需要timeout去中斷的，這里面哪個是業(yè)務需要，哪個是因為故障導致的呢?

　　在部分同步模型中大部分訪問同步時鐘，有關于傳遞消息有多長的限制，有一個進程執(zhí)行一個步驟需要多長時間的限制。

　　進程間通訊

　　進程之間是如何通訊的，這里有消息傳遞模型和共享內存模型，前者是通過消息發(fā)送通訊，后者是訪問內存中共享變量共享數據進行通訊。這里進程有服務器 節(jié)點的意思，一個進程可能代表分布式場景的一臺服務器。

　　消息傳遞最難的是不能發(fā)送重復消息，每次只能精確一次傳遞，這里有很多設計，比如Perfect Links抽象可以保證，但是它不能正常反映現實世界，雖然不真實，但是有用，我們可以使用Perfect Links證明一個問題不可能被解決，然后我們就知道其他相關問題也沒有答案。消息傳遞總是可以被想象為FIFO之類隊列或堆棧。

　　共享內存是我們編程常用的方式，需要在一臺服務器內才能完成。我們可以使用消息傳遞算法完成分布式情況下的內存共享對象，比如讀寫注冊器，調用一個服務之間需要查詢這個服務在哪個服務器上，負載平衡器也是一個讀寫注冊器，是一個全局共享的內存。

　　失敗模型

　　分布式模型總是必須考慮進程失敗的情況，在crash-stop失敗模型中，一個進程假設為一直是正確，直至它崩潰，一旦它崩潰，就永遠不會恢復;也有crash-recovery 模型，進程能夠在失敗以后恢復，在這種情況下，一些算法來保證進程恢復到其失敗之前的狀態(tài)，這可以通過從持久層讀取狀態(tài)完成，或者通過和一個集群小組中的其他進程通訊方式完成。注意這里有不同集群組算法，一個進程崩潰后，恢復其狀態(tài)的進程不會再被認為是之前同樣的進程，這取決于動態(tài)組還是固定組這兩種算法。

　　失敗模型也包括：一個進程如果無法接受和發(fā)送消息，被稱為遺漏omission failure mode，遺漏模型也有不同種類，一個進程無法接受和發(fā)送消息很重要嗎?想象一組進程實現一個分布式緩存，如果一個進程無法回復同一組的其他進程，即使能夠接受來自它們的請求，這也意味著這個進程能夠接受外部消息更新自己的狀態(tài)，其實也就意味著它能回復來自客戶端的讀請求，也就是說，雖然它自己不能主動回復客戶端的請求，但是可以接受客戶端的主動讀取請求。

　　一個復雜失敗模型是拜占庭Byzantine 或稱為任意失敗模型，進程會發(fā)送錯誤信息到對方，它們會模仿發(fā)送正確數據，但是實際已經篡改了本地數據庫的內容。

　　設計分布式系統時，我們需要對付這些失敗模型。

　　失敗探測

　　我們希望在進程崩潰失敗時及時發(fā)現，比如crash-stop失敗模型加上同步系統，我們能夠使用timeout;如果我們定期讓進程ping到一個專門的失敗探測器，我們就能精確知道那個進程是否正常，如果過了timeout時間沒有Ping訪問，那么我們就可以認為那臺進程服務器崩潰了。

　　更真實情況是，假設一個消息到達目標需要確定的時間，確定好一個進程執(zhí)行一個步驟需要多長時間，那么就可以使用timeout進行衡量計算。

　　失敗模型探測有兩個屬性策略：

　　1. Strong Completeness強完整性：每個失敗的進程會永久被其他正確進程懷疑。

　　2.Eventual Strong Accuracy最終強精確度，沒有一個進程被任何正確的進程懷疑。

　　當一個進程被其他進程懷疑時，這些進程就不可能達成共識consensus ，而在分布式系統中使用異步模型是必須要達成共識，也就是每個進程內部狀態(tài)通過異步消息傳遞后，最終其他進程的狀態(tài)會和最初發(fā)送消息的那個進程內部狀態(tài)一致，這稱為達成共識，但是因為有進程存在失敗崩潰的可能，所以，在這個達成共識的消息傳遞過程中，如何確保進程之間的信任，不懷疑對方，從而確保消息傳遞成功，那么引入失敗探測器是可以規(guī)避這個問題的。

　　領導人選舉LEADER ELECTION

　　這是通過決定某個進程沒有崩潰失敗，能夠正常工作，那么這個進程就可以被網絡中其他進程信任，它就可以被認為是領導人，負責協調分布式動作，這種協議有Raft和Zab兩種。

　　這種機制會導致瓶頸集中在領導人那里，而且之前還需要領導人選舉，這些多余過程可能是我們不需要的。

　　一致共識CONSENSUS

　　共識是在獨立進程之間達成一致的統一意見，這些進程會就某個問題建議一個數值，基于這個推薦的值會同意采取一致行動，比如，一個轎車有各種傳感器提供制動器溫度的信息，依賴于傳感器的精度，會有不同變化的數值，但是ABS計算機需要知道施加多大壓力到制動器上，這種共識問題每天生活中都發(fā)生。

　　一個進程實現共識是通過暴露帶有推薦和決定功能的API實現的，一個進程會推薦數值，由此開始共識，然后它得基于一個數值決定，這個數值是在整個系統中被推薦了的，這些算法包括：Termination, Validity, Integrity 和Agreement.

　　1.Termination: 每個正確的進程最終會決定某個數值。

　　2.Validity: 如果一個進程決定了v，那么v會被其他進程推薦。

　　3.Integrity: 沒有進程能夠決定兩次

　　4.Agreement: 沒有兩個正確進程有不同的決定。

　　法定人數QUORUMS

　　Quorums 是一個設計失敗容錯分布式系統的工具，當系統存在crash-failure模型時，總是有一個法定人數代表大多數意見從而進行決策的，因為崩潰失敗的總是少數。

　　比如有N個進程服務器，假設崩潰的進程是少數，比如N/2-1個進程崩潰，也就是49%的進程崩潰，我們還是有51%的會投贊成票。Raft協議使用的是這種大多數策略，根據提交到系統的日志來判斷，

　　分布式系統的時間

　　理解時間和其導致的因果是分布式系統的大問題，我們通常用事件這個概念代表生活中發(fā)生的那些事實，使用happened before順序約束定義這些事件，但是我們有很多進程交換信息，共同訪問共享資源等等，我們如何告訴某個進程事件的happened before策略呢?也就是誰在前誰在后的順序呢?為了回答這個問題，進程需要共享一個同步的時鐘，精確知道它在網絡間移動花費多長時間?包括CPU調度任務的時間等等，顯然這在真實世界是不可能實現的。

　　Time, Clocks, and the Ordering of Events in a Distributed System引入了邏輯時鐘概念，邏輯時鐘是一個分配一個數字給事件的方式，也就是說，這些數字不是和實際時間有關，但是和一個節(jié)點的進程事件有關。

　　有各種邏輯時鐘，比如 Vector Clocks向量時鐘或 Interval Tree Clocks.

　　理解分布式時間問題，必須理解一個重要概念：同時性這個想法有時我們必須放棄(The idea of simultaneity is something we have to let go.)，這是有關“絕對知識”等舊哲學信條的問題，他們認為絕對知識是可以到達的，其實人的認識是相對，永遠不可能到達真正事物本質，你以為的同時性并不是真正同時性，光線也是有速度的，即使最快的光線也是需要時間才從一個地方到達另外一個地方?？梢奍nventing the Enemy發(fā)明敵人 一書中的“絕對與相對”。