3 分布式系統抽象
討論編程語言時，我們使用通用術語并用函數、運算符、類、變量和指針來定義我們的程序。通用的詞匯可以幫助我們避免每次都為了描述某些東西而發明新詞。我們的定義越精確、越沒有歧異，聽眾也就越容易理解。
在開始學習算法之前，我們首先要了解分布式系統中的詞匯：這些定義你會經常在演講、書籍和論文中遇到。
鏈路
網絡是不可靠的：消息會丟失、延遲或被打亂。記住這一點之后，我們來嘗試構建幾種通信協議。我們從最不可靠的協議開始，確定它們可能處于的狀態，然后找出可以為協議增加的東西使它提供更好的保證。
公平損失鏈路
我們可以從兩個進程開始，它們之間以鏈路相連。進程可以相互發送消息，如圖2所示。任何通信介質都是不完美的，消息可能丟失或延遲。
看看我們能得到什么樣的保證。消息M被發送之后（從發送方的角度來看），它可能處于以下狀態之一：
- 還未送達進程B（但會在某個時間點送達）
- 在途中丟失且不可恢復
- 成功送達遠程進程
圖8-2：最簡單的不可靠通信形式
注意，發送方沒有任何方法確定消息是否已經送達。在分布式系統的術語中，這種鏈路稱為公平損失（fair-loss）。這種鏈路具有以下屬性：
公平損失
如果發送方和接收方都是正確的，且發送方無限多次重復發送，則消息最終會被送達注3。
有限重復
發送的消息不會被送達無限次。
不會無中生有
鏈路不會自己生成消息。換句話說，它不會傳遞一個從未發送過的消息。
公平損失鏈路是一種很有用的抽象，它是構建具有更強保證的通信協議的基石。我們可以假設該鏈路不會在通信雙方之間系統性地丟棄消息，也不會創建新消息。但與此同時，我們也不能完全依靠它。這可能讓你想起了用戶數據報協議（UDP），UDP允許我們從一個進程發送消息到另一個進程，但在協議層面上不提供可靠的傳輸語義。
消息確認
為了改善這一情況、更清晰地獲得消息狀態，我們可以引入確認（acknowledgment）機制：接收方通知發送方消息已送達。為此，我們需要雙向通信信道，并增加一些措施以區分不同的消息，例如序列號—單調遞增的唯一消息標識符。
每個消息只要有唯一標識符就足夠了。序列號只是唯一標識符的一種特殊情況，即使用計數器來獲取標識符，從而實現唯一性。當使用哈希算法來唯一地標識消息時，我們應當考慮可能的沖突，并確保能消除歧義。
現在，進程A可以發送消息M(n)，其中n是單調遞增的消息計數器。B收到消息后立即向A發送確認ACK(n)。圖8-3展示了這種通信形式。
圖3：發現消息并確認
確認消息，就像原始消息一樣，也有可能在途中丟失。消息可能處于的狀態數會稍有變化。在A收到確認之前，該消息仍處于我們前面提到的三種狀態之一，但是，一旦A收到確認，就可以確信該消息已送達B。
消息重傳
增加確認機制仍不足以保證通信協議完全可靠：發送的消息仍可能會丟失，遠程進程也可能在確認之前發生故障。為了解決該問題并提供送達保證，我們可以嘗試重傳（retransmit）。重傳是指發送方重試可能失敗的操作。我們之所以說可能失敗，是因為發送方并不能真的知道有沒有失敗，因為我們要討論的鏈路不使用確認機制。
進程A發送消息M之后，它將等到超時T被觸發，然后嘗試再次發送同一條消息。假設進程之間的鏈路完好無損，進程間的網絡分區不會無限持續下去，并且并非所有數據包都丟失，我們可以認為，從發送方的角度看，消息要么尚未送達進程B，要么已經成功送達。由于A一直在嘗試發送消息，可以認為傳輸過程中不會發生不可恢復的消息丟失。
在分布式系統的術語中，這種抽象稱為頑固鏈路（stubborn link）。之所以稱為頑固，是因為發件人會無限期地反復發送消息，但是，由于這種抽象非常不切實際，因此我們需要將重試與確認結合起來。
重傳的問題
每當我們發送消息時，在收到遠程進程的確認之前，我們無從得知消息的狀態：可能已被處理，可能馬上就要處理，也可能已經丟失，甚至可能在收到消息之前遠程進程就崩潰了—上述的任意狀態都是可能的。我們可以重試操作、再次發送消息，但這可能導致消息重復。只有當我們要執行的操作是冪等時，處理重復消息才是安全的。
冪等（idempotent）的操作可以執行多次而產生相同的結果，且不會產生其他副作用。例如，服務器關機操作可以是冪等的，第一次調用將發起關機，而所有后續調用都不會產生任何其他影響。
如果每個操作都是冪等的，那我們可以少考慮一些傳遞語義，更多地依賴重傳來實現容錯，并以完全反應式的方式構建系統：為某些信號觸發相應的操作，而不會引起預期之外的副作用。但是，操作不一定是冪等的，簡單地假設它們冪等可能會導致集群范圍的副作用。例如，向客戶的信用卡收費不是冪等操作，絕對不可以重復收費多次。
在存在部分故障和網絡分區的情況下，冪等性尤其重要，因為我們無法總是確定遠程操作的確切狀態—是成功還是失敗，還是會馬上被執行—我們只能等待更長的時間。保證每個操作都是冪等的是不切實際的，因此我們需要在不改變實際操作語義的情況下，提供與冪等性等價的保證。為此，我們可以使用去重來避免多次處理消息。
消息順序
不可靠的網絡給我們帶來了兩個問題：一是消息可能會亂序到達；二是由于重傳某些消息可能會多次送達。我們已經引入了序列號，利用這些消息標識符我們可以在接收方確保先進先出（FIFO）的順序。由于每條消息都有一個序列號，因此接收方可以跟蹤下列信息：
- nconsecutive表示最大連續序列號：所有小于或等于該序列號的消息都已經收到，這些消息可以按順序放到正確的位置上。
- nprocessed表示最大已處理序列號：所有小于或等于該序列號的消息都已經按照原來的順序被處理。此序列號可以用于去重。
如果收到的消息序列號不連續，接收方會將其放入重新排序緩沖區。例如，它在接收到序列號為3的消息后收到消息5，那我們就知道4還是缺失的，因此我們將5放在一旁，直到4到來，然后就能構造出原本的消息順序。由于通信構建在公平損失鏈路之上，可以認為nconsecutive和nmax_seen之間的消息最終一定會送達。
接收方可以安全地丟棄收到的序列號小于等于nconsecutive的消息，因為這些消息確定已經送達了。
去重的工作原理是檢查帶有序列號n的消息是否已被處理（已被傳給網絡棧的更上層），丟棄已處理的消息。
在分布式系統的術語中，這種類型的鏈路稱為完美鏈路，它提供以下保證[CACHIN11]：
可靠傳遞
正確的進程A發送一次到正確的進程B的每個消息最終都會被傳遞。
沒有重復
消息不會被傳送多次。
不會無中生有
與其他種類的鏈路一樣，它只能傳遞實際由發送者發送過的消息。
這可能會讓你想起TCP注4協議（但是，TCP僅在單個會話內保證可靠傳遞）。當然，上述模型僅僅是一種用于說明原理的簡化表示。TCP中處理消息確認的模型更為復雜，它按組進行確認以減少協議層面的開銷。另外，TCP具有選擇性確認、流控、擁塞控制、錯誤檢測等很多其他功能，這些不在我們的討論范圍之內。
嚴格一次傳遞
分布式系統中只有兩個難題：1）保證消息順序；2）嚴格一次傳遞。
—Mathias Verraes
關于是否可以做到嚴格一次傳遞（exactly-once delivery）這個問題已經有很多討論。這里，語義和精確的措辭非常重要。由于鏈路故障可能導致傳遞消息的第一次嘗試無法成功，因此大多數實際的系統都采用至少一次傳遞（at-least-once delivery），它確保了發送方將重試直到收到確認為止，否則就認為對方沒有收到該消息。還有一種傳遞語義是最多一次（at-most-once）：發送方僅僅發送消息而不期待得到任何確認。
TCP協議的原理是將消息分成數據包，一個一個傳輸，然后在接收端將它們拼接到一起。TCP可能會嘗試重傳某些數據包，并且可能有不止一次的傳輸會成功。由于TCP用序列號標記每個數據包，即使某些數據包被發送多次，它也可以對其進行去重，確保接收方只會看到并處理一次該消息。在TCP中，此保證僅對單個會話有效：如果消息被確認并處理，但是發送方在收到確認消息前連接就中斷了，則應用程序并不知道此傳遞成功，取決于其邏輯，它可能會嘗試再次發送消息。
這意味著嚴格一次處理是個有趣的問題，因為重復的傳送（或數據包傳輸）沒有副作用，僅僅是鏈路盡力而為的產物。舉個例子，如果數據庫節點僅接收到記錄但還沒將它持久化。在這種情況下傳遞已經完成了，但除非該記錄可以被查到（換句話說，除非消息被傳遞并且處理了），否則這次傳遞毫無用處。
為了確保嚴格一次傳遞，各節點需要一個共同知識[HALPERN90]：每個節點都知道某件事，每個節點都知道其他所有節點也都知道這件事。用簡化的術語來說，節點必須在記錄狀態上達成共識：兩個節點都認為該記錄已經或者還未被持久化。正如本章之后會說的，這在理論上是不可能的，但在實踐中，我們仍通過放寬協調的要求來使用這一概念。
各種關于是否是嚴格一次發送的誤解，大多是因為從不同協議和抽象層次上考慮該問題，以及對“傳遞”的不同定義。要想建立可靠的鏈路，不可能不重復傳送某些消息。但是，我們可以通過僅處理每個消息一次并忽略重復消息，使得從發送方的角度來看是嚴格一次發送。
現在，在建立了實現可靠通信的方法之后，我們可以繼續前進，探尋實現分布式系統中進程間一致性和共識的方法。
4 兩將軍問題
一個被廣泛稱為兩將軍問題的思想實驗，是對分布式系統一致性的最著名的描述之一。
這個思想實驗表明，如果鏈路可能發生故障并且通信是異步的，則不可能在通信的雙方之間達成共識。盡管TCP具有完美鏈路的性質，但是務必記住：完美鏈路盡管被稱為完美鏈路，并不能保證完美的傳遞。它們也不能保證參與方一直活著，而只關心傳輸本身。
想象現在有兩支軍隊，分別由兩位將軍領導，準備進攻一座要塞城市。兩支軍隊分別位于城市的兩側，只有在同時進攻的情況下才能獲勝。
兩位將軍通過信使進行通信。他們已經制定了攻擊計劃，現在唯一需要達成共識的就是是否執行計劃。該問題的變體包括：其中一位將軍的級別較高，但需要確保攻擊是有協調的；或者兩位將軍需要就確切時間達成共識。這些細節不會改變問題的定義：將軍們需要達成一項共識。
將軍們只需要對“他們都會發起進攻”這一事實達成共識。否則，攻擊將無法成功。將軍A發出一條消息MSG(N)，表明如果對方也同意的話，就在指定的時間發起進攻。
將軍A送出信使之后，他不知道信使是否已經到達：信使可能會被抓而無法傳達消息。當將軍B收到消息時，他必須發送確認ACK(MSG(N))。圖8-4展示了一條消息由一方發送并由另一方確認。
圖4：兩將軍問題示意圖
傳遞確認消息的信使也可能會被抓而無法傳達消息。B無從得知信使是否已成功送達確認消息。
為了確認這一點，B必須等待ACK(ACK(MSG(N)))，一個二階的確認，用于確認A收到了確認。
無論將軍們互相發送多少確認，他們始終距離安全地發起攻擊還差一個ACK。將軍們注定要懷疑最后一個確認消息是否已送達目的地。
注意我們沒有做任何時序上的假設：將軍間的通信是完全異步的。并沒有一個上限約束將軍必須在多長時間內做出回應。
5 FLP不可能定理
Fisher、Lynch和Paterson在論文中描述了一個著名的問題：FLP不可能問題[FISCHER85]（FLP是作者姓氏的首字母），論文討論了一種共識形式：各進程啟動時有一個初始值，并嘗試就新值達成共識。算法完成后，所有正常進程上的新值必須相同。
如果網絡完全可靠，很容易對特定值達成共識。但實際上，系統容易出現各式各樣的故障，例如消息丟失、重復、網絡分區，以及進程緩慢或崩潰。
共識協議描述了這樣一個系統：給定初始狀態的多個進程，它將所有進程帶入決定狀態。一個正確的共識協議必須具備以下三個屬性：
一致性
協議達成的決定必須是一致的：每個進程都做出了決定且所有進程決定的值是相同的。否則我們就尚未達成共識。
有效性
達成共識的值必須由某一個參與者提出，這意味著系統本身不能“提出”值。這也意味著這個值不是無關緊要（trivial）的：進程不能總是決定某個預定義的默認值。
終止性
只有當所有進程都達到決定狀態時，協議才算完成。
文獻[FISCHER85]假定處理過程是完全異步的，進程之間沒有共享的時間概念。這樣的系統中的算法不能基于超時，并且一個進程無法確定另一個進程是崩潰了還是僅僅運行太慢。論文表明，在這些假設下，不存在任何協議能保證在有限時間內達成共識。完全異步的共識算法甚至無法容忍一個遠程進程無通知地突然崩潰。
如果我們不給進程完成算法步驟設定一個時間上限，那么就無法可靠地檢測出進程故障，也不存在確定性的共識算法。
但是，FLP不可能定理并不意味著我們要收拾東西回家（由于達成共識是不可能的）。它僅僅意味著我們不能總是在有限的時間內在一個異步系統中達成共識。實踐中，系統至少會表現出一定程度的同步性，而要想解決共識問題還需要一個更完善的模型。
6 系統同步性
從FLP不可能定理中可以看出時序假設是分布式系統的關鍵特征之一。在異步系統中，我們不知道進程運行的相對速度，也不能保證在有限時間內或以特定順序傳遞消息。進程可能要花無限長的時間來響應，而且無法總是可靠地檢測到進程故障。
對異步系統的主要批評在于上述假設不切實際：進程不可能具有任意不同的處理速度，鏈路傳遞消息的時間也不會無限長。依賴時間能夠簡化推理，并提供時間上限的保證。
在異步模型中不一定能解決共識問題[FISCHER85]。而且，不一定能設計出高效的異步算法。對于某些任務，切實可行的解決方案很可能需要依賴時間[ARJOMANDI83]。
我們可以放寬一些假設，認為系統是同步的。為此我們引入了時間的概念。在同步模型下對系統進行推理要容易得多。它假定各進程的處理速度相近、傳輸延遲是有限的，并且消息傳遞不會花任意長的時間。
同步系統也可以表示為同步的進程本地時鐘：兩個進程本地時間源之間的時間差存在上限[CACHIN11]。
在同步模型中設計系統可以使用超時機制。我們可以構建更復雜的抽象，例如領導者選舉、共識、故障檢測以及基于它們的其他抽象。這使得最佳情況的場景更加健壯，但是如果時序假設不成立則可能導致故障。例如：Raft共識算法（參見14.4節）中，可能最終有多個進程認為它們是領導者，為了解決該問題，我們強制滯后的進程接受其他進程成為領導者；故障檢測算法（參見第9章）可能會錯誤地將活動進程標記為故障，反之亦然。設計系統時，我們必須考慮這些可能性。
異步和同步模型的性質可以組合使用，我們可以將系統視為部分同步的。部分同步的系統具有同步系統的某些屬性，但是消息傳遞、時鐘漂移和相對處理速度的邊界范圍可能并不精確，并且僅在大多數時候成立[DWORK88]。
同步是分布式系統的基本屬性：它對性能、擴展性和一般可解性有影響，并且有許多對系統正常工作來說是必要的因素。本書中討論的一些算法就工作在同步系統的假設下。
7 故障模型
我們一直在提到故障這個詞，但到目前為止，它還是一個十分寬泛的概念，可能包含多種含義。就像我們可以做出不同的時序假設那樣，我們也可以假設存在不同種類的故障。故障模型準確地描述了分布式系統中的進程可能以怎樣的方式崩潰，并基于這些假設來開發算法。例如，我們可以假設進程可能崩潰并且永遠無法恢復，或者可以預期它將在一段時間后恢復，或者它可能會失控并且產生錯誤的值。
分布式系統中，進程互相依賴以共同執行算法，因此故障可能導致整個系統的執行錯誤。
我們將討論分布式系統中現有的多種故障模型，例如崩潰、遺漏和任意故障。這個列表并非面面俱到，但它涵蓋了在實際中的大多數重要場景。
7.1 崩潰故障
通常，我們期望進程正確執行算法的所有步驟。最簡單的崩潰方式是進程停止執行接下來的算法步驟，并且不再發送任何消息給其他進程。換句話說，該進程崩潰了。大多數情況下，我們使用崩潰–停止（crash-stop）進程抽象的假設，它規定一旦進程崩潰就會保持這種狀態。
該模型不假定該進程無法恢復，也不阻攔或試圖阻止恢復。這僅僅意味著該算法的正確性或活動性不依賴于恢復過程。實際上，并沒有什么東西會去阻止進程恢復、追上系統狀態以及參與下一次的算法執行。
失敗的進程無法再繼續參與當前這一輪的協作。為恢復的進程分配一個新的、不同的ID不會使模型等價于崩潰–恢復模型（之后會討論），因為大多數算法使用預定義的進程列表，并且依據最多可容忍的故障數明確定義了故障的語義[CACHIN11]。
崩潰–恢復（crash-recovery）是另一種的進程抽象。在這個抽象中，進程停止執行算法步驟，但會在稍后恢復并嘗試執行剩下的步驟。要想讓恢復成為可能，需要在系統中引入持久狀態以及恢復協議[SKEEN83]。允許崩潰–恢復的算法需要考慮所有可能的恢復狀態，因為恢復的進程會嘗試從最后一個已知的步驟開始繼續執行。
想利用恢復的算法必須同時考慮狀態和進程ID。在這種情況下，崩潰恢復也可以看作是遺漏故障的一種特殊情況，因為從另一個進程的角度看，不可達的進程與崩潰再恢復的進程沒什么區別。
7.2 遺漏故障
另一個故障模式是遺漏故障（omission fault）。該模型假設故障進程跳過了某些算法步驟，或者無法執行這些步驟，或者執行過程對其他參與者不可見，或者無法與其他參與者通信。遺漏故障中包含了由于網絡鏈路故障、交換機故障或網絡擁塞而導致的網絡分區。網絡分區可以表示為單個進程或進程組之間的消息遺漏。進程崩潰可以模擬為遺漏所有該進程收發的消息。
如果進程的運行速度慢于其他參與者，發送響應比預期遲得多，那么對于系統的其余部分來說，這個節點看起來丟三落四的。慢節點沒有完全停止，而是發送結果太慢，常常與其他節點不同步。
如果本應執行某些步驟的算法跳過了這些步驟或者執行結果不可見時，就發生了遺漏故障。例如，消息在送往接收方的途中丟失，而發送方就像消息發送成功時那樣，沒有再次發送而是繼續運行，即使消息已經不可恢復地丟失了。遺漏故障也可能是由間歇性停頓、網絡過載、隊列滿等引起的。
7.3 任意故障
最難以解決的故障種類是任意故障或拜占庭故障（Byzantine fault）：進程繼續執行算法步驟，但是以與違背算法的方式（例如，共識算法中的進程決定一個從未由任何參與者提出過的值）。
此類故障可能是由于軟件bug或運行不同版本算法的進程，在這種情況下，故障很容易被發現和理解。如果我們無法控制所有進程，并且其中一個進程有意地誤導其他進程，則發現和理解故障會變得非常困難。
你可能在航空航天工業中聽說過拜占庭式的容錯：飛機和航天器的系統不會直接使用子部件傳來的值，而是會對結果進行交叉驗證。另一個廣泛的應用是加密貨幣[GILAD17]，那里沒有中央權威，節點被多方控制，并且敵對的參與者有強烈的動機通過提供錯誤響應來欺騙系統。
7.4 故障處理
我們可以通過構成進程組、在算法中引入冗余來掩蓋故障：即使其中一個進程發生故障，用戶也不會注意到[CHRISTIAN91]。
故障可能會帶來一些性能損失：正常的執行依賴于進程可響應，而且系統必須回退到較慢的執行路徑來處理故障和糾正錯誤。故障往往可以通過一些方式來避免，例如：代碼審查、廣泛的測試、引入超時重試機制確保消息送達，以及確保各算法步驟在本地按順序執行。
我們這里介紹的大多數算法都基于崩潰-故障模型，并通過引入冗余來解決故障。這些假設幫助我們創造性能更好、更易于理解和實現的算法。
8 小結
我們討論了一些分布式系統的術語，并介紹了一些基本概念。我們討論了分布式系統的固有困難和復雜性，這是由于系統組件不可靠性導致的：鏈路可能無法傳遞消息、進程可能崩潰、網絡可能發生分區。
