分布式系統(tǒng)中只有兩個(gè)難題
分布式系統(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)摯感謝
免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn),不代表本平臺(tái)立場(chǎng),如有問(wèn)題,請(qǐng)聯(lián)系我們,謝謝!