因?yàn)榉植际较到y(tǒng)的網(wǎng)絡(luò)模型和故障模型在我的博客中可能會(huì)經(jīng)常被引用, 所以我寫了本文作為一個(gè)引用文章.
分布式系統(tǒng)中的網(wǎng)絡(luò)模型
- 同步網(wǎng)絡(luò)(synchronous network): 這里的同步網(wǎng)絡(luò)和編程中的同步阻塞io和異步非阻塞io是兩回事, 不要弄混了. 同步網(wǎng)絡(luò)是指i). 所有節(jié)點(diǎn)的時(shí)鐘漂移有上限, ii). 網(wǎng)絡(luò)的傳輸時(shí)間有上限, iii). 所有節(jié)點(diǎn)的計(jì)算速度一樣. 這意味著整個(gè)網(wǎng)絡(luò)按照round運(yùn)行, 每個(gè)round中任何節(jié)點(diǎn)都要執(zhí)行完本地計(jì)算并且可以完成一個(gè)任意大小消息的傳輸. 一個(gè)發(fā)出的消息如果在一個(gè)round內(nèi)沒有到達(dá), 那么一定是網(wǎng)絡(luò)中斷造成的, 這個(gè)消息會(huì)丟失, 不會(huì)延遲到第二個(gè)round到達(dá). 在現(xiàn)實(shí)生活中這種網(wǎng)絡(luò)比較少, 盡管很少, 同步網(wǎng)絡(luò)仍然是在計(jì)算機(jī)科學(xué)中是不可缺少的一個(gè)分析模型, 在這種模型下可以解決一些問題, 比如拜占庭式故障. 但我們每天打交道的網(wǎng)絡(luò)大多都是異步網(wǎng)絡(luò).
- 異步網(wǎng)絡(luò)(asynchornous network): 和同步網(wǎng)絡(luò)相反, 節(jié)點(diǎn)的時(shí)鐘漂移無上限, 消息的傳輸延遲無上限, 節(jié)點(diǎn)計(jì)算的速度不可預(yù)料. 這就是我們打交道的網(wǎng)絡(luò)類型. 在異步網(wǎng)絡(luò)中, 有些故障非常難解決, 比如當(dāng)你發(fā)給一個(gè)節(jié)點(diǎn)一個(gè)消息之后幾秒鐘都沒有收到他的應(yīng)答, 有可能這個(gè)節(jié)點(diǎn)計(jì)算非常慢, 但是也可能是節(jié)點(diǎn)crash或者網(wǎng)絡(luò)延遲造成的, 你很難判斷到底是發(fā)生了什么樣的故障.
fault, error and failure
這不是繞口令, 你一定要區(qū)分他們的關(guān)系. 過去很多時(shí)候這些詞匯混用導(dǎo)致很多問題, 后來統(tǒng)一了這幾個(gè)詞的定義: Fault: 在系統(tǒng)中某一個(gè)步驟偏離正確的執(zhí)行叫做一個(gè)fault, 比如內(nèi)存寫入錯(cuò)誤, 但是如果內(nèi)存是ECC的那么這個(gè)fault可以立刻被修復(fù), 就不會(huì)導(dǎo)致error. Error: 如果一個(gè)fault沒能在結(jié)果影響到整個(gè)系統(tǒng)狀態(tài)之前被修復(fù), 結(jié)果導(dǎo)致系統(tǒng)的狀態(tài)錯(cuò)誤, 那么這就是一個(gè)error, 比如不帶ECC的內(nèi)存導(dǎo)致一個(gè)計(jì)算結(jié)果錯(cuò)誤. Failure: 如果一個(gè)系統(tǒng)的error沒能在錯(cuò)誤狀態(tài)傳遞給其它節(jié)點(diǎn)之前被修復(fù), 換句話說error被擴(kuò)散出去, 這就是一個(gè)failure.
所以他們的關(guān)系是fault導(dǎo)致error, error導(dǎo)致failure. 在分布式系統(tǒng)中, 每個(gè)節(jié)點(diǎn)很難確定其它節(jié)點(diǎn)內(nèi)部的狀態(tài), 通常只能通過和其他節(jié)點(diǎn)的交互監(jiān)測到failure. 接下來我們所說的故障一般都是指failure.
分布式系統(tǒng)中的故障模型
在分布式系統(tǒng)中, 故障可能發(fā)生在節(jié)點(diǎn)或者通信鏈路上, 下面我們按照從最廣泛最難的到最特定最簡單的順序列出故障類型:
- byzantine failures: 這是最難處理的情況, 一個(gè)節(jié)點(diǎn)壓根就不按照程序邏輯執(zhí)行, 對(duì)它的調(diào)用會(huì)返回給你隨意或者混亂的結(jié)果. 要解決拜占庭式故障需要有同步網(wǎng)絡(luò), 并且故障節(jié)點(diǎn)必須小于1/3或者消息傳遞過程中不可篡改，通常只有某些特定領(lǐng)域才會(huì)考慮這種情況通過高冗余來消除故障. 關(guān)于拜占庭式故障你現(xiàn)在只要知道這是最難的情況, 稍后我們會(huì)更詳細(xì)的介紹它.
- crash-recovery failures: 它比byzantine類故障加了一個(gè)限制, 那就是節(jié)點(diǎn)總是按照程序邏輯執(zhí)行, 結(jié)果是正確的. 但是不保證消息返回的時(shí)間. 原因可能是crash后重啟了, 網(wǎng)絡(luò)中斷了, 異步網(wǎng)絡(luò)中的高延遲. 對(duì)于crash的情況還要分健忘(amnesia)和非健忘的兩種情況. 對(duì)于健忘的情況, 是指這個(gè)crash的節(jié)點(diǎn)重啟后沒有完整的保存crash之前的狀態(tài)信息, 非健忘是指這個(gè)節(jié)點(diǎn)crash之前能把狀態(tài)完整的保存在持久存儲(chǔ)上, 啟動(dòng)之后可以再次按照以前的狀態(tài)繼續(xù)執(zhí)行和通信.
- omission failures: 比crash-recovery多了一個(gè)限制, 就是一定要非健忘. 有些算法要求必須是非健忘的. 比如最基本版本的Paxos要求節(jié)點(diǎn)必須把ballot number記錄到持久存儲(chǔ)中, 一旦crash, 修復(fù)之后必須繼續(xù)記住之前的ballot number.
- crash-stop failures: 也叫做crash failure或者fail-stop failures, 它比omission failure多了一個(gè)故障發(fā)生后要停止響應(yīng)的要求. 比如一個(gè)節(jié)點(diǎn)出現(xiàn)故障后立即停止接受和發(fā)送所有消息, 或者網(wǎng)絡(luò)發(fā)生了故障無法進(jìn)行任何通信, 并且這些故障不會(huì)恢復(fù). 簡單講, 一旦發(fā)生故障, 這個(gè)節(jié)點(diǎn) 就不會(huì)再和其它節(jié)點(diǎn)有任何交互. 就像他的名字描述的那樣, crash and stop.
分布式系統(tǒng)中的故障類型還有其他的分類方法, 有些分類會(huì)把omission去掉, 有些會(huì)加入performance failures, 有些會(huì)把crash-stop和fail-stop根據(jù)故障檢測能力區(qū)分開, 此處介紹的是使用較為廣泛的一種分類方法. 他們的關(guān)系如下:
這四種故障中, 拜占庭式故障是非常難以解決的, Leslie Lamport證明在同步網(wǎng)絡(luò)下,有辦法驗(yàn)證消息真?zhèn)位蛘吖收瞎?jié)點(diǎn)不超過1/3的情況下才有可能解決, 在現(xiàn)實(shí)中, 這類問題解決成本非常高, 只有在非常關(guān)鍵的領(lǐng)域才會(huì)考慮使用BFT(Byzantine Fault Tolerance)的設(shè)計(jì). 比如NASA的航天飛機(jī)有5臺(tái)可以抵抗各種射線影響的AP-101系列計(jì)算機(jī), 其中四臺(tái)使用同樣的軟件運(yùn)行, 另外一臺(tái)獨(dú)立運(yùn)行另外一個(gè)獨(dú)立編寫版本的軟件. 空客A320有7臺(tái)計(jì)算機(jī), 分別是三種硬件上運(yùn)行的三套獨(dú)立編寫的軟件. 美國海軍的海狼級(jí)核動(dòng)力攻擊型潛水艇(SSN-21)也采用了多組計(jì)算機(jī)控制. 絕大多數(shù)應(yīng)用是不太考慮重力加速度和射線輻射對(duì)硬件的影響的. 大多數(shù)分布式應(yīng)用主要是關(guān)注crash-recovery的情況, 而crash-stop是一種過于理想化的情況, 比如3PC的故障模型是基于crash-stop的, 但是在真實(shí)環(huán)境中crash-recovery會(huì)導(dǎo)致3PC的結(jié)果不一致.
