分布式系統(tǒng)抽象

討論編程語(yǔ)言時(shí)，我們使用通用術(shù)語(yǔ)并用函數(shù)、運(yùn)算符、類、變量和指針來(lái)定義我們的程序。通用的詞匯可以幫助我們避免每次都為了描述某些東西而發(fā)明新詞。我們的定義越精確、越?jīng)]有歧異，聽(tīng)眾也就越容易理解。

在開(kāi)始學(xué)習(xí)算法之前，我們首先要了解分布式系統(tǒng)中的詞匯：這些定義你會(huì)經(jīng)常在演講、書(shū)籍和論文中遇到。

鏈路

網(wǎng)絡(luò)是不可靠的：消息會(huì)丟失、延遲或被打亂。記住這一點(diǎn)之后，我們來(lái)嘗試構(gòu)建幾種通信協(xié)議。我們從最不可靠的協(xié)議開(kāi)始，確定它們可能處于的狀態(tài)，然后找出可以為協(xié)議增加的東西使它提供更好的保證。

公平損失鏈路

我們可以從兩個(gè)進(jìn)程開(kāi)始，它們之間以鏈路相連。進(jìn)程可以相互發(fā)送消息，如圖2所示。任何通信介質(zhì)都是不完美的，消息可能丟失或延遲。

看看我們能得到什么樣的保證。消息M被發(fā)送之后（從發(fā)送方的角度來(lái)看），它可能處于以下?tīng)顟B(tài)之一：

• 還未送達(dá)進(jìn)程B（但會(huì)在某個(gè)時(shí)間點(diǎn)送達(dá)）

• 在途中丟失且不可恢復(fù)

• 成功送達(dá)遠(yuǎn)程進(jìn)程

圖8-2：最簡(jiǎn)單的不可靠通信形式

注意，發(fā)送方?jīng)]有任何方法確定消息是否已經(jīng)送達(dá)。在分布式系統(tǒng)的術(shù)語(yǔ)中，這種鏈路稱為公平損失（fair-loss）。這種鏈路具有以下屬性：

公平損失

        如果發(fā)送方和接收方都是正確的，且發(fā)送方無(wú)限多次重復(fù)發(fā)送，則消息最終會(huì)被送達(dá)注3。

有限重復(fù)

        發(fā)送的消息不會(huì)被送達(dá)無(wú)限次。

不會(huì)無(wú)中生有

        鏈路不會(huì)自己生成消息。換句話說(shuō)，它不會(huì)傳遞一個(gè)從未發(fā)送過(guò)的消息。

公平損失鏈路是一種很有用的抽象，它是構(gòu)建具有更強(qiáng)保證的通信協(xié)議的基石。我們可以假設(shè)該鏈路不會(huì)在通信雙方之間系統(tǒng)性地丟棄消息，也不會(huì)創(chuàng)建新消息。但與此同時(shí)，我們也不能完全依靠它。這可能讓你想起了用戶數(shù)據(jù)報(bào)協(xié)議（UDP），UDP允許我們從一個(gè)進(jìn)程發(fā)送消息到另一個(gè)進(jìn)程，但在協(xié)議層面上不提供可靠的傳輸語(yǔ)義。

消息確認(rèn)

為了改善這一情況、更清晰地獲得消息狀態(tài)，我們可以引入確認(rèn)（acknowledgment）機(jī)制：接收方通知發(fā)送方消息已送達(dá)。為此，我們需要雙向通信信道，并增加一些措施以區(qū)分不同的消息，例如序列號(hào)—單調(diào)遞增的唯一消息標(biāo)識(shí)符。

每個(gè)消息只要有唯一標(biāo)識(shí)符就足夠了。序列號(hào)只是唯一標(biāo)識(shí)符的一種特殊情況，即使用計(jì)數(shù)器來(lái)獲取標(biāo)識(shí)符，從而實(shí)現(xiàn)唯一性。當(dāng)使用哈希算法來(lái)唯一地標(biāo)識(shí)消息時(shí)，我們應(yīng)當(dāng)考慮可能的沖突，并確保能消除歧義。

現(xiàn)在，進(jìn)程A可以發(fā)送消息M(n)，其中n是單調(diào)遞增的消息計(jì)數(shù)器。B收到消息后立即向A發(fā)送確認(rèn)ACK(n)。圖8-3展示了這種通信形式。

圖3：發(fā)現(xiàn)消息并確認(rèn)

確認(rèn)消息，就像原始消息一樣，也有可能在途中丟失。消息可能處于的狀態(tài)數(shù)會(huì)稍有變化。在A收到確認(rèn)之前，該消息仍處于我們前面提到的三種狀態(tài)之一，但是，一旦A收到確認(rèn)，就可以確信該消息已送達(dá)B。 

消息重傳

增加確認(rèn)機(jī)制仍不足以保證通信協(xié)議完全可靠：發(fā)送的消息仍可能會(huì)丟失，遠(yuǎn)程進(jìn)程也可能在確認(rèn)之前發(fā)生故障。為了解決該問(wèn)題并提供送達(dá)保證，我們可以嘗試重傳（retransmit）。重傳是指發(fā)送方重試可能失敗的操作。我們之所以說(shuō)可能失敗，是因?yàn)榘l(fā)送方并不能真的知道有沒(méi)有失敗，因?yàn)槲覀円懻摰逆溌凡皇褂么_認(rèn)機(jī)制。

進(jìn)程A發(fā)送消息M之后，它將等到超時(shí)T被觸發(fā)，然后嘗試再次發(fā)送同一條消息。假設(shè)進(jìn)程之間的鏈路完好無(wú)損，進(jìn)程間的網(wǎng)絡(luò)分區(qū)不會(huì)無(wú)限持續(xù)下去，并且并非所有數(shù)據(jù)包都丟失，我們可以認(rèn)為，從發(fā)送方的角度看，消息要么尚未送達(dá)進(jìn)程B，要么已經(jīng)成功送達(dá)。由于A一直在嘗試發(fā)送消息，可以認(rèn)為傳輸過(guò)程中不會(huì)發(fā)生不可恢復(fù)的消息丟失。

在分布式系統(tǒng)的術(shù)語(yǔ)中，這種抽象稱為頑固鏈路（stubborn link）。之所以稱為頑固，是因?yàn)榘l(fā)件人會(huì)無(wú)限期地反復(fù)發(fā)送消息，但是，由于這種抽象非常不切實(shí)際，因此我們需要將重試與確認(rèn)結(jié)合起來(lái)。

重傳的問(wèn)題

每當(dāng)我們發(fā)送消息時(shí)，在收到遠(yuǎn)程進(jìn)程的確認(rèn)之前，我們無(wú)從得知消息的狀態(tài)：可能已被處理，可能馬上就要處理，也可能已經(jīng)丟失，甚至可能在收到消息之前遠(yuǎn)程進(jìn)程就崩潰了—上述的任意狀態(tài)都是可能的。我們可以重試操作、再次發(fā)送消息，但這可能導(dǎo)致消息重復(fù)。只有當(dāng)我們要執(zhí)行的操作是冪等時(shí)，處理重復(fù)消息才是安全的。

冪等（idempotent）的操作可以執(zhí)行多次而產(chǎn)生相同的結(jié)果，且不會(huì)產(chǎn)生其他副作用。例如，服務(wù)器關(guān)機(jī)操作可以是冪等的，第一次調(diào)用將發(fā)起關(guān)機(jī)，而所有后續(xù)調(diào)用都不會(huì)產(chǎn)生任何其他影響。

如果每個(gè)操作都是冪等的，那我們可以少考慮一些傳遞語(yǔ)義，更多地依賴重傳來(lái)實(shí)現(xiàn)容錯(cuò)，并以完全反應(yīng)式的方式構(gòu)建系統(tǒng)：為某些信號(hào)觸發(fā)相應(yīng)的操作，而不會(huì)引起預(yù)期之外的副作用。但是，操作不一定是冪等的，簡(jiǎn)單地假設(shè)它們冪等可能會(huì)導(dǎo)致集群范圍的副作用。例如，向客戶的信用卡收費(fèi)不是冪等操作，絕對(duì)不可以重復(fù)收費(fèi)多次。

在存在部分故障和網(wǎng)絡(luò)分區(qū)的情況下，冪等性尤其重要，因?yàn)槲覀儫o(wú)法總是確定遠(yuǎn)程操作的確切狀態(tài)—是成功還是失敗，還是會(huì)馬上被執(zhí)行—我們只能等待更長(zhǎng)的時(shí)間。保證每個(gè)操作都是冪等的是不切實(shí)際的，因此我們需要在不改變實(shí)際操作語(yǔ)義的情況下，提供與冪等性等價(jià)的保證。為此，我們可以使用去重來(lái)避免多次處理消息。

消息順序

不可靠的網(wǎng)絡(luò)給我們帶來(lái)了兩個(gè)問(wèn)題：一是消息可能會(huì)亂序到達(dá)；二是由于重傳某些消息可能會(huì)多次送達(dá)。我們已經(jīng)引入了序列號(hào)，利用這些消息標(biāo)識(shí)符我們可以在接收方確保先進(jìn)先出（FIFO）的順序。由于每條消息都有一個(gè)序列號(hào)，因此接收方可以跟蹤下列信息：

• nconsecutive表示最大連續(xù)序列號(hào)：所有小于或等于該序列號(hào)的消息都已經(jīng)收到，這些消息可以按順序放到正確的位置上。

• nprocessed表示最大已處理序列號(hào)：所有小于或等于該序列號(hào)的消息都已經(jīng)按照原來(lái)的順序被處理。此序列號(hào)可以用于去重。

如果收到的消息序列號(hào)不連續(xù)，接收方會(huì)將其放入重新排序緩沖區(qū)。例如，它在接收到序列號(hào)為3的消息后收到消息5，那我們就知道4還是缺失的，因此我們將5放在一旁，直到4到來(lái)，然后就能構(gòu)造出原本的消息順序。由于通信構(gòu)建在公平損失鏈路之上，可以認(rèn)為nconsecutive和nmax_seen之間的消息最終一定會(huì)送達(dá)。

接收方可以安全地丟棄收到的序列號(hào)小于等于nconsecutive的消息，因?yàn)檫@些消息確定已經(jīng)送達(dá)了。

去重的工作原理是檢查帶有序列號(hào)n的消息是否已被處理（已被傳給網(wǎng)絡(luò)棧的更上層），丟棄已處理的消息。

在分布式系統(tǒng)的術(shù)語(yǔ)中，這種類型的鏈路稱為完美鏈路，它提供以下保證[CACHIN11]：

可靠傳遞

正確的進(jìn)程A發(fā)送一次到正確的進(jìn)程B的每個(gè)消息最終都會(huì)被傳遞。

沒(méi)有重復(fù)

消息不會(huì)被傳送多次。

不會(huì)無(wú)中生有

與其他種類的鏈路一樣，它只能傳遞實(shí)際由發(fā)送者發(fā)送過(guò)的消息。

這可能會(huì)讓你想起TCP注4協(xié)議（但是，TCP僅在單個(gè)會(huì)話內(nèi)保證可靠傳遞）。當(dāng)然，上述模型僅僅是一種用于說(shuō)明原理的簡(jiǎn)化表示。TCP中處理消息確認(rèn)的模型更為復(fù)雜，它按組進(jìn)行確認(rèn)以減少協(xié)議層面的開(kāi)銷。另外，TCP具有選擇性確認(rèn)、流控、擁塞控制、錯(cuò)誤檢測(cè)等很多其他功能，這些不在我們的討論范圍之內(nèi)。

嚴(yán)格一次傳遞

分布式系統(tǒng)中只有兩個(gè)難題：1）保證消息順序；2）嚴(yán)格一次傳遞。 

                                                                                                      —Mathias Verraes

關(guān)于是否可以做到嚴(yán)格一次傳遞（exactly-once delivery）這個(gè)問(wèn)題已經(jīng)有很多討論。這里，語(yǔ)義和精確的措辭非常重要。由于鏈路故障可能導(dǎo)致傳遞消息的第一次嘗試無(wú)法成功，因此大多數(shù)實(shí)際的系統(tǒng)都采用至少一次傳遞（at-least-once delivery），它確保了發(fā)送方將重試直到收到確認(rèn)為止，否則就認(rèn)為對(duì)方?jīng)]有收到該消息。還有一種傳遞語(yǔ)義是最多一次（at-most-once）：發(fā)送方僅僅發(fā)送消息而不期待得到任何確認(rèn)。

TCP協(xié)議的原理是將消息分成數(shù)據(jù)包，一個(gè)一個(gè)傳輸，然后在接收端將它們拼接到一起。TCP可能會(huì)嘗試重傳某些數(shù)據(jù)包，并且可能有不止一次的傳輸會(huì)成功。由于TCP用序列號(hào)標(biāo)記每個(gè)數(shù)據(jù)包，即使某些數(shù)據(jù)包被發(fā)送多次，它也可以對(duì)其進(jìn)行去重，確保接收方只會(huì)看到并處理一次該消息。在TCP中，此保證僅對(duì)單個(gè)會(huì)話有效：如果消息被確認(rèn)并處理，但是發(fā)送方在收到確認(rèn)消息前連接就中斷了，則應(yīng)用程序并不知道此傳遞成功，取決于其邏輯，它可能會(huì)嘗試再次發(fā)送消息。

這意味著嚴(yán)格一次處理是個(gè)有趣的問(wèn)題，因?yàn)橹貜?fù)的傳送（或數(shù)據(jù)包傳輸）沒(méi)有副作用，僅僅是鏈路盡力而為的產(chǎn)物。舉個(gè)例子，如果數(shù)據(jù)庫(kù)節(jié)點(diǎn)僅接收到記錄但還沒(méi)將它持久化。在這種情況下傳遞已經(jīng)完成了，但除非該記錄可以被查到（換句話說(shuō)，除非消息被傳遞并且處理了），否則這次傳遞毫無(wú)用處。

為了確保嚴(yán)格一次傳遞，各節(jié)點(diǎn)需要一個(gè)共同知識(shí)[HALPERN90]：每個(gè)節(jié)點(diǎn)都知道某件事，每個(gè)節(jié)點(diǎn)都知道其他所有節(jié)點(diǎn)也都知道這件事。用簡(jiǎn)化的術(shù)語(yǔ)來(lái)說(shuō)，節(jié)點(diǎn)必須在記錄狀態(tài)上達(dá)成共識(shí)：兩個(gè)節(jié)點(diǎn)都認(rèn)為該記錄已經(jīng)或者還未被持久化。正如本章之后會(huì)說(shuō)的，這在理論上是不可能的，但在實(shí)踐中，我們?nèi)酝ㄟ^(guò)放寬協(xié)調(diào)的要求來(lái)使用這一概念。

各種關(guān)于是否是嚴(yán)格一次發(fā)送的誤解，大多是因?yàn)閺牟煌瑓f(xié)議和抽象層次上考慮該問(wèn)題，以及對(duì)“傳遞”的不同定義。要想建立可靠的鏈路，不可能不重復(fù)傳送某些消息。但是，我們可以通過(guò)僅處理每個(gè)消息一次并忽略重復(fù)消息，使得從發(fā)送方的角度來(lái)看是嚴(yán)格一次發(fā)送。

現(xiàn)在，在建立了實(shí)現(xiàn)可靠通信的方法之后，我們可以繼續(xù)前進(jìn)，探尋實(shí)現(xiàn)分布式系統(tǒng)中進(jìn)程間一致性和共識(shí)的方法。

4 兩將軍問(wèn)題

一個(gè)被廣泛稱為兩將軍問(wèn)題的思想實(shí)驗(yàn)，是對(duì)分布式系統(tǒng)一致性的最著名的描述之一。

這個(gè)思想實(shí)驗(yàn)表明，如果鏈路可能發(fā)生故障并且通信是異步的，則不可能在通信的雙方之間達(dá)成共識(shí)。盡管TCP具有完美鏈路的性質(zhì)，但是務(wù)必記住：完美鏈路盡管被稱為完美鏈路，并不能保證完美的傳遞。它們也不能保證參與方一直活著，而只關(guān)心傳輸本身。

想象現(xiàn)在有兩支軍隊(duì)，分別由兩位將軍領(lǐng)導(dǎo)，準(zhǔn)備進(jìn)攻一座要塞城市。兩支軍隊(duì)分別位于城市的兩側(cè)，只有在同時(shí)進(jìn)攻的情況下才能獲勝。

兩位將軍通過(guò)信使進(jìn)行通信。他們已經(jīng)制定了攻擊計(jì)劃，現(xiàn)在唯一需要達(dá)成共識(shí)的就是是否執(zhí)行計(jì)劃。該問(wèn)題的變體包括：其中一位將軍的級(jí)別較高，但需要確保攻擊是有協(xié)調(diào)的；或者兩位將軍需要就確切時(shí)間達(dá)成共識(shí)。這些細(xì)節(jié)不會(huì)改變問(wèn)題的定義：將軍們需要達(dá)成一項(xiàng)共識(shí)。

將軍們只需要對(duì)“他們都會(huì)發(fā)起進(jìn)攻”這一事實(shí)達(dá)成共識(shí)。否則，攻擊將無(wú)法成功。將軍A發(fā)出一條消息MSG(N)，表明如果對(duì)方也同意的話，就在指定的時(shí)間發(fā)起進(jìn)攻。

將軍A送出信使之后，他不知道信使是否已經(jīng)到達(dá)：信使可能會(huì)被抓而無(wú)法傳達(dá)消息。當(dāng)將軍B收到消息時(shí)，他必須發(fā)送確認(rèn)ACK(MSG(N))。圖8-4展示了一條消息由一方發(fā)送并由另一方確認(rèn)。

圖4：兩將軍問(wèn)題示意圖

傳遞確認(rèn)消息的信使也可能會(huì)被抓而無(wú)法傳達(dá)消息。B無(wú)從得知信使是否已成功送達(dá)確認(rèn)消息。

為了確認(rèn)這一點(diǎn)，B必須等待ACK(ACK(MSG(N)))，一個(gè)二階的確認(rèn)，用于確認(rèn)A收到了確認(rèn)。

無(wú)論將軍們互相發(fā)送多少確認(rèn)，他們始終距離安全地發(fā)起攻擊還差一個(gè)ACK。將軍們注定要懷疑最后一個(gè)確認(rèn)消息是否已送達(dá)目的地。

注意我們沒(méi)有做任何時(shí)序上的假設(shè)：將軍間的通信是完全異步的。并沒(méi)有一個(gè)上限約束將軍必須在多長(zhǎng)時(shí)間內(nèi)做出回應(yīng)。

5 FLP不可能定理

Fisher、Lynch和Paterson在論文中描述了一個(gè)著名的問(wèn)題：FLP不可能問(wèn)題[FISCHER85]（FLP是作者姓氏的首字母），論文討論了一種共識(shí)形式：各進(jìn)程啟動(dòng)時(shí)有一個(gè)初始值，并嘗試就新值達(dá)成共識(shí)。算法完成后，所有正常進(jìn)程上的新值必須相同。

如果網(wǎng)絡(luò)完全可靠，很容易對(duì)特定值達(dá)成共識(shí)。但實(shí)際上，系統(tǒng)容易出現(xiàn)各式各樣的故障，例如消息丟失、重復(fù)、網(wǎng)絡(luò)分區(qū)，以及進(jìn)程緩慢或崩潰。

共識(shí)協(xié)議描述了這樣一個(gè)系統(tǒng)：給定初始狀態(tài)的多個(gè)進(jìn)程，它將所有進(jìn)程帶入決定狀態(tài)。一個(gè)正確的共識(shí)協(xié)議必須具備以下三個(gè)屬性：

一致性

    協(xié)議達(dá)成的決定必須是一致的：每個(gè)進(jìn)程都做出了決定且所有進(jìn)程決定的值是相同的。否則我們就尚未達(dá)成共識(shí)。

有效性

    達(dá)成共識(shí)的值必須由某一個(gè)參與者提出，這意味著系統(tǒng)本身不能“提出”值。這也意味著這個(gè)值不是無(wú)關(guān)緊要（trivial）的：進(jìn)程不能總是決定某個(gè)預(yù)定義的默認(rèn)值。

終止性

    只有當(dāng)所有進(jìn)程都達(dá)到?jīng)Q定狀態(tài)時(shí)，協(xié)議才算完成。

文獻(xiàn)[FISCHER85]假定處理過(guò)程是完全異步的，進(jìn)程之間沒(méi)有共享的時(shí)間概念。這樣的系統(tǒng)中的算法不能基于超時(shí)，并且一個(gè)進(jìn)程無(wú)法確定另一個(gè)進(jìn)程是崩潰了還是僅僅運(yùn)行太慢。論文表明，在這些假設(shè)下，不存在任何協(xié)議能保證在有限時(shí)間內(nèi)達(dá)成共識(shí)。完全異步的共識(shí)算法甚至無(wú)法容忍一個(gè)遠(yuǎn)程進(jìn)程無(wú)通知地突然崩潰。

如果我們不給進(jìn)程完成算法步驟設(shè)定一個(gè)時(shí)間上限，那么就無(wú)法可靠地檢測(cè)出進(jìn)程故障，也不存在確定性的共識(shí)算法。

但是，F(xiàn)LP不可能定理并不意味著我們要收拾東西回家（由于達(dá)成共識(shí)是不可能的）。它僅僅意味著我們不能總是在有限的時(shí)間內(nèi)在一個(gè)異步系統(tǒng)中達(dá)成共識(shí)。實(shí)踐中，系統(tǒng)至少會(huì)表現(xiàn)出一定程度的同步性，而要想解決共識(shí)問(wèn)題還需要一個(gè)更完善的模型。

6 系統(tǒng)同步性

從FLP不可能定理中可以看出時(shí)序假設(shè)是分布式系統(tǒng)的關(guān)鍵特征之一。在異步系統(tǒng)中，我們不知道進(jìn)程運(yùn)行的相對(duì)速度，也不能保證在有限時(shí)間內(nèi)或以特定順序傳遞消息。進(jìn)程可能要花無(wú)限長(zhǎng)的時(shí)間來(lái)響應(yīng)，而且無(wú)法總是可靠地檢測(cè)到進(jìn)程故障。

對(duì)異步系統(tǒng)的主要批評(píng)在于上述假設(shè)不切實(shí)際：進(jìn)程不可能具有任意不同的處理速度，鏈路傳遞消息的時(shí)間也不會(huì)無(wú)限長(zhǎng)。依賴時(shí)間能夠簡(jiǎn)化推理，并提供時(shí)間上限的保證。

在異步模型中不一定能解決共識(shí)問(wèn)題[FISCHER85]。而且，不一定能設(shè)計(jì)出高效的異步算法。對(duì)于某些任務(wù)，切實(shí)可行的解決方案很可能需要依賴時(shí)間[ARJOMANDI83]。

我們可以放寬一些假設(shè)，認(rèn)為系統(tǒng)是同步的。為此我們引入了時(shí)間的概念。在同步模型下對(duì)系統(tǒng)進(jìn)行推理要容易得多。它假定各進(jìn)程的處理速度相近、傳輸延遲是有限的，并且消息傳遞不會(huì)花任意長(zhǎng)的時(shí)間。

同步系統(tǒng)也可以表示為同步的進(jìn)程本地時(shí)鐘：兩個(gè)進(jìn)程本地時(shí)間源之間的時(shí)間差存在上限[CACHIN11]。

在同步模型中設(shè)計(jì)系統(tǒng)可以使用超時(shí)機(jī)制。我們可以構(gòu)建更復(fù)雜的抽象，例如領(lǐng)導(dǎo)者選舉、共識(shí)、故障檢測(cè)以及基于它們的其他抽象。這使得最佳情況的場(chǎng)景更加健壯，但是如果時(shí)序假設(shè)不成立則可能導(dǎo)致故障。例如：Raft共識(shí)算法（參見(jiàn)14.4節(jié)）中，可能最終有多個(gè)進(jìn)程認(rèn)為它們是領(lǐng)導(dǎo)者，為了解決該問(wèn)題，我們強(qiáng)制滯后的進(jìn)程接受其他進(jìn)程成為領(lǐng)導(dǎo)者；故障檢測(cè)算法（參見(jiàn)第9章）可能會(huì)錯(cuò)誤地將活動(dòng)進(jìn)程標(biāo)記為故障，反之亦然。設(shè)計(jì)系統(tǒng)時(shí)，我們必須考慮這些可能性。

異步和同步模型的性質(zhì)可以組合使用，我們可以將系統(tǒng)視為部分同步的。部分同步的系統(tǒng)具有同步系統(tǒng)的某些屬性，但是消息傳遞、時(shí)鐘漂移和相對(duì)處理速度的邊界范圍可能并不精確，并且僅在大多數(shù)時(shí)候成立[DWORK88]。

同步是分布式系統(tǒng)的基本屬性：它對(duì)性能、擴(kuò)展性和一般可解性有影響，并且有許多對(duì)系統(tǒng)正常工作來(lái)說(shuō)是必要的因素。本書(shū)中討論的一些算法就工作在同步系統(tǒng)的假設(shè)下。

7 故障模型

我們一直在提到故障這個(gè)詞，但到目前為止，它還是一個(gè)十分寬泛的概念，可能包含多種含義。就像我們可以做出不同的時(shí)序假設(shè)那樣，我們也可以假設(shè)存在不同種類的故障。故障模型準(zhǔn)確地描述了分布式系統(tǒng)中的進(jìn)程可能以怎樣的方式崩潰，并基于這些假設(shè)來(lái)開(kāi)發(fā)算法。例如，我們可以假設(shè)進(jìn)程可能崩潰并且永遠(yuǎn)無(wú)法恢復(fù)，或者可以預(yù)期它將在一段時(shí)間后恢復(fù)，或者它可能會(huì)失控并且產(chǎn)生錯(cuò)誤的值。

分布式系統(tǒng)中，進(jìn)程互相依賴以共同執(zhí)行算法，因此故障可能導(dǎo)致整個(gè)系統(tǒng)的執(zhí)行錯(cuò)誤。

我們將討論分布式系統(tǒng)中現(xiàn)有的多種故障模型，例如崩潰、遺漏和任意故障。這個(gè)列表并非面面俱到，但它涵蓋了在實(shí)際中的大多數(shù)重要場(chǎng)景。

7.1 崩潰故障

通常，我們期望進(jìn)程正確執(zhí)行算法的所有步驟。最簡(jiǎn)單的崩潰方式是進(jìn)程停止執(zhí)行接下來(lái)的算法步驟，并且不再發(fā)送任何消息給其他進(jìn)程。換句話說(shuō)，該進(jìn)程崩潰了。大多數(shù)情況下，我們使用崩潰–停止（crash-stop）進(jìn)程抽象的假設(shè)，它規(guī)定一旦進(jìn)程崩潰就會(huì)保持這種狀態(tài)。

該模型不假定該進(jìn)程無(wú)法恢復(fù)，也不阻攔或試圖阻止恢復(fù)。這僅僅意味著該算法的正確性或活動(dòng)性不依賴于恢復(fù)過(guò)程。實(shí)際上，并沒(méi)有什么東西會(huì)去阻止進(jìn)程恢復(fù)、追上系統(tǒng)狀態(tài)以及參與下一次的算法執(zhí)行。

失敗的進(jìn)程無(wú)法再繼續(xù)參與當(dāng)前這一輪的協(xié)作。為恢復(fù)的進(jìn)程分配一個(gè)新的、不同的ID不會(huì)使模型等價(jià)于崩潰–恢復(fù)模型（之后會(huì)討論），因?yàn)榇蠖鄶?shù)算法使用預(yù)定義的進(jìn)程列表，并且依據(jù)最多可容忍的故障數(shù)明確定義了故障的語(yǔ)義[CACHIN11]。

崩潰–恢復(fù)（crash-recovery）是另一種的進(jìn)程抽象。在這個(gè)抽象中，進(jìn)程停止執(zhí)行算法步驟，但會(huì)在稍后恢復(fù)并嘗試執(zhí)行剩下的步驟。要想讓恢復(fù)成為可能，需要在系統(tǒng)中引入持久狀態(tài)以及恢復(fù)協(xié)議[SKEEN83]。允許崩潰–恢復(fù)的算法需要考慮所有可能的恢復(fù)狀態(tài)，因?yàn)榛謴?fù)的進(jìn)程會(huì)嘗試從最后一個(gè)已知的步驟開(kāi)始繼續(xù)執(zhí)行。

想利用恢復(fù)的算法必須同時(shí)考慮狀態(tài)和進(jìn)程ID。在這種情況下，崩潰恢復(fù)也可以看作是遺漏故障的一種特殊情況，因?yàn)閺牧硪粋€(gè)進(jìn)程的角度看，不可達(dá)的進(jìn)程與崩潰再恢復(fù)的進(jìn)程沒(méi)什么區(qū)別。

7.2 遺漏故障

另一個(gè)故障模式是遺漏故障（omission fault）。該模型假設(shè)故障進(jìn)程跳過(guò)了某些算法步驟，或者無(wú)法執(zhí)行這些步驟，或者執(zhí)行過(guò)程對(duì)其他參與者不可見(jiàn)，或者無(wú)法與其他參與者通信。遺漏故障中包含了由于網(wǎng)絡(luò)鏈路故障、交換機(jī)故障或網(wǎng)絡(luò)擁塞而導(dǎo)致的網(wǎng)絡(luò)分區(qū)。網(wǎng)絡(luò)分區(qū)可以表示為單個(gè)進(jìn)程或進(jìn)程組之間的消息遺漏。進(jìn)程崩潰可以模擬為遺漏所有該進(jìn)程收發(fā)的消息。

如果進(jìn)程的運(yùn)行速度慢于其他參與者，發(fā)送響應(yīng)比預(yù)期遲得多，那么對(duì)于系統(tǒng)的其余部分來(lái)說(shuō)，這個(gè)節(jié)點(diǎn)看起來(lái)丟三落四的。慢節(jié)點(diǎn)沒(méi)有完全停止，而是發(fā)送結(jié)果太慢，常常與其他節(jié)點(diǎn)不同步。

如果本應(yīng)執(zhí)行某些步驟的算法跳過(guò)了這些步驟或者執(zhí)行結(jié)果不可見(jiàn)時(shí)，就發(fā)生了遺漏故障。例如，消息在送往接收方的途中丟失，而發(fā)送方就像消息發(fā)送成功時(shí)那樣，沒(méi)有再次發(fā)送而是繼續(xù)運(yùn)行，即使消息已經(jīng)不可恢復(fù)地丟失了。遺漏故障也可能是由間歇性停頓、網(wǎng)絡(luò)過(guò)載、隊(duì)列滿等引起的。

7.3 任意故障

最難以解決的故障種類是任意故障或拜占庭故障（Byzantine fault）：進(jìn)程繼續(xù)執(zhí)行算法步驟，但是以與違背算法的方式（例如，共識(shí)算法中的進(jìn)程決定一個(gè)從未由任何參與者提出過(guò)的值）。

此類故障可能是由于軟件bug或運(yùn)行不同版本算法的進(jìn)程，在這種情況下，故障很容易被發(fā)現(xiàn)和理解。如果我們無(wú)法控制所有進(jìn)程，并且其中一個(gè)進(jìn)程有意地誤導(dǎo)其他進(jìn)程，則發(fā)現(xiàn)和理解故障會(huì)變得非常困難。

你可能在航空航天工業(yè)中聽(tīng)說(shuō)過(guò)拜占庭式的容錯(cuò)：飛機(jī)和航天器的系統(tǒng)不會(huì)直接使用子部件傳來(lái)的值，而是會(huì)對(duì)結(jié)果進(jìn)行交叉驗(yàn)證。另一個(gè)廣泛的應(yīng)用是加密貨幣[GILAD17]，那里沒(méi)有中央權(quán)威，節(jié)點(diǎn)被多方控制，并且敵對(duì)的參與者有強(qiáng)烈的動(dòng)機(jī)通過(guò)提供錯(cuò)誤響應(yīng)來(lái)欺騙系統(tǒng)。

7.4 故障處理

我們可以通過(guò)構(gòu)成進(jìn)程組、在算法中引入冗余來(lái)掩蓋故障：即使其中一個(gè)進(jìn)程發(fā)生故障，用戶也不會(huì)注意到[CHRISTIAN91]。

故障可能會(huì)帶來(lái)一些性能損失：正常的執(zhí)行依賴于進(jìn)程可響應(yīng)，而且系統(tǒng)必須回退到較慢的執(zhí)行路徑來(lái)處理故障和糾正錯(cuò)誤。故障往往可以通過(guò)一些方式來(lái)避免，例如：代碼審查、廣泛的測(cè)試、引入超時(shí)重試機(jī)制確保消息送達(dá)，以及確保各算法步驟在本地按順序執(zhí)行。

我們這里介紹的大多數(shù)算法都基于崩潰-故障模型，并通過(guò)引入冗余來(lái)解決故障。這些假設(shè)幫助我們創(chuàng)造性能更好、更易于理解和實(shí)現(xiàn)的算法。

8 小結(jié)

我們討論了一些分布式系統(tǒng)的術(shù)語(yǔ)，并介紹了一些基本概念。我們討論了分布式系統(tǒng)的固有困難和復(fù)雜性，這是由于系統(tǒng)組件不可靠性導(dǎo)致的：鏈路可能無(wú)法傳遞消息、進(jìn)程可能崩潰、網(wǎng)絡(luò)可能發(fā)生分區(qū)。

這些術(shù)語(yǔ)應(yīng)該足夠讓我們繼續(xù)討論。本書(shū)的剩余部分將討論分布式系統(tǒng)中常見(jiàn)的解決方案：我們將先回想下哪些地方可能會(huì)出問(wèn)題，然后看看有哪些可用的選項(xiàng)。

更多閱讀

如果你想了解更多本章中提到的概念，可以參考以下來(lái)源：

• 分布式系統(tǒng)抽象、故障模型和時(shí)序假設(shè)

• Lynch, Nancy A. 1996. Distributed Algorithms. San Francisco: Morgan Kaufmann.

• Tanenbaum, Andrew S. and Maarten van Steen. 2006. Distributed Systems: Principles and Paradigms (2nd Ed). Boston: Pearson.

• Cachin, Christian, Rachid Guerraoui, and Lus Rodrigues. 2011. Introduction to Reliable and Secure Distributed Programming (2nd Ed.). New York: Springer.

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：

長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝