第十章故障恢復與系統(tǒng)容錯

基于事務型的服務比較適合于維護長期存在的共享數(shù)據(jù)，但并非適合于所有的分布式應用程序。基于事務型的服務在正常工作時將數(shù)據(jù)項存儲在恢復文件中，一旦發(fā)生故障，可馬上進行恢復。對服務進行恢復的通常方法是通過重啟，利用恢復文件進行數(shù)據(jù)項的恢復，但這種方式對某些應用程序來說速度太慢。利用運行于不同計算機中的服務副本可大大提高恢復速度，若能夠保證相互間的一致性，則可瞬時完成單一故障的恢復工作。但使用多個活躍的副本，對計算機資源又是極大的浪費。折衷方案是使用一臺主服務器和若干臺備份服務器，系統(tǒng)正常工作時由主服務器處理客戶要求，當主服務器發(fā)生故障時，啟動某臺備份服務器，接管主服務器還沒有完成的操作。目前一頁\總數(shù)三十一頁\編于七點10．2事務恢復事務的原子化特征可以用耐久性和錯誤原子化來描述。耐久性要求將數(shù)據(jù)項保存到永久存儲器中并可隨時使用，因此承認客戶的提交請求意味著該事務的所有影響不僅記錄在服務器的數(shù)據(jù)項中，而且記錄在永久存儲器中。所謂錯誤原子化，是指即使服務器發(fā)生故障，事務對數(shù)據(jù)項的影響也是原子化的。若某事務需具有恢復功能，則必須保證服務器的數(shù)據(jù)項具有耐久性，并且服務也應提供錯誤原子化功能。雖然文件服務器和數(shù)據(jù)庫服務器都將數(shù)據(jù)保存在永久存儲器中，但其他的服務器并不是這樣的，除非要求此服務器具有恢復功能。在本章中假定：服務器運行時將所有的數(shù)據(jù)項都保存在易失性存儲器中，并把所有已提交的數(shù)據(jù)記錄到恢復文件或文件中。這樣恢復工作就是把數(shù)據(jù)項的最新提交版本從永久存儲器中恢復到服務器上。由于數(shù)據(jù)庫通常需要處理大量數(shù)據(jù)，所以它們通常通過高速緩存把數(shù)據(jù)項從易失性存儲器轉(zhuǎn)移到磁盤永九存儲器中。

目前二頁\總數(shù)三十一頁\編于七點

耐久性和錯誤原子化并不是相互獨立的，它們可由恢復處理程序這個單一機制來統(tǒng)一完成。恢復處理程序的主要任務是：(1)對于已提交的事務，將其數(shù)據(jù)項保存到永久存儲器中(恢復文件中)；(2)發(fā)生故障后，對服務器數(shù)據(jù)項進行恢復；(3)通過重新組織恢復文件以提高恢復工作的效率；(4)回收存儲空間(在恢復文件中)。在有些情況下要求恢復處理程序處理介質(zhì)故障即恢復文件本身的故障。這時可使用一種稱為穩(wěn)定存儲器的技術(shù)進行恢復文件復制，從而不僅可以使發(fā)生介質(zhì)故障的可能性大大減少，而且當系統(tǒng)在進行寫操作發(fā)生故障時，可保證寫操作是原子化的。

目前三頁\總數(shù)三十一頁\編于七點意向表：任何提供事務的服務器需要對客戶事務所存取的數(shù)據(jù)項進行監(jiān)控。當客戶打開一個事務時，與之發(fā)生聯(lián)系的第一臺服務器提供一個新的事務標識符并將它返回給客戶。這以后，事務中的每個客戶請求(包括提交請求和異常終止請求)，都應包含此標識符。在事務的執(zhí)行過程中，應將更新操作作用于該事務數(shù)據(jù)項一系列的私有臨時版本上。服務器記錄所有當前活躍事務的意向表，表中包含事務名以及由事務修改的數(shù)據(jù)項的值；提交事務時，服務器利用事務意向表識別該事務所影響的數(shù)據(jù)項，并用此事務所產(chǎn)生的每個數(shù)據(jù)項的臨時版本代替原提交版本，然后將新的值寫到服務器的恢復文件中。事務異常終止時，服務器通過意向表來刪除所有由該事務所產(chǎn)生的數(shù)據(jù)項的臨時版本。目前四頁\總數(shù)三十一頁\編于七點

當服務器準備提交某事務時，它必須把該事務的意向表以及意向表中的數(shù)據(jù)項保存到恢復文件中，這樣即使服務器臨時發(fā)生故障也可以在以后執(zhí)行提交操作。當某事務所涉及的所有服務器全部同意提交該事務時，協(xié)調(diào)程序就會通知客戶并發(fā)送消息到各參與服務器以執(zhí)行提交操作。一旦已通知客戶可進行提交，則相關服務器的恢復文件中必須包括足夠多的信息，這樣即使有服務器在準備提交或提交過程中發(fā)生故障，所有服務器也可提交該事務。

恢復文件表目：為了使服務器上的分布式事務具有恢復功能，恢復文件中除了保存數(shù)據(jù)項外還應保存更多的信息。這些信息包括每個事務的狀態(tài)：提交、異常終止、準備提交。通過把意向表保存到恢復文件中可使恢復文件中的每個數(shù)據(jù)項與一個特定的事務相聯(lián)系，恢復文件中包含的項目如表101所示。目前五頁\總數(shù)三十一頁\編于七點目前六頁\總數(shù)三十一頁\編于七點10．2．1登錄登錄技術(shù)是一種恢復文件的方法。在登錄技術(shù)中，恢復文件代表某服務器所執(zhí)行的所有事務的歷史記錄，其中包括數(shù)據(jù)項的值、事務狀態(tài)表目以及意向表。在登錄中表目的順序反映了該服務器上事務準備提交、提交或異常終止的順序。在服務器正常工作時，若準備提交、提交或異常終止某事務，則需調(diào)用恢復處理程序；當服務器準備提交某事務時，恢復處理程序就將意向表中的所有數(shù)據(jù)項、意向表本身以及事務當前狀態(tài)(準備)添加到恢復文件中；當事務最終真正提交或異常終止時，恢復處理程序再將相應的事務狀態(tài)添加到恢復文件中?；謴吞幚沓绦驗槊總€數(shù)據(jù)項分配一個標識符，從而使得恢復文件中數(shù)據(jù)項的成功版本與服務器中的數(shù)據(jù)項保持一致。目前七頁\總數(shù)三十一頁\編于七點

圖101說明了銀行服務事務T和u的登錄機制。在事務T和U開始執(zhí)行之前重新組織登錄，圖中左邊表示A、B、C值的快照。在本圖中將A、B、C作為數(shù)據(jù)項的標識符。圖中顯示了事務T已提交而事務U準備提交但尚未提交的狀態(tài)。當事務T準備提交時，將數(shù)據(jù)項A和B的值寫入到登錄中的P1和P2位置，然后寫入T的準備事務狀態(tài)表目及它的意向表中[(A，P1)，(B，P2)]；當提交事務時，將T的提交事務狀態(tài)表目寫人到P4位置；類似的，當事務U準備提交時，將數(shù)據(jù)項C和B的值寫入到登錄中的P5和P6位置，然后寫入U的準備事務狀態(tài)表目及它的意向表[(c，P5)，(B，P6)]中。

每一個事務狀態(tài)表目都包含一個指針指向前一個事務狀態(tài)表目，從而使恢復處理程序可以反向跟蹤恢復文件中的事務狀態(tài)表目，事務狀態(tài)表目的最后一個指針指向一個檢查點(checkpoint)。目前八頁\總數(shù)三十一頁\編于七點

1．數(shù)據(jù)項恢復當服務器重啟時，首先設置數(shù)據(jù)項的初始默認值，然后將控制權(quán)交給恢復處理程序?；謴吞幚沓绦蜇撠熁謴头掌魃系臄?shù)據(jù)項，它必須恢復所有已提交的事務對數(shù)據(jù)項的影響，并撤銷所有未提交或異常終止的事務對數(shù)據(jù)項的影響。事務的晟新信息保存在登錄的最后，因此恢復處理程序采用從后向前讀取恢復文件的方式恢復服務器上的數(shù)據(jù)項。它利用具有提交狀態(tài)的事務來恢復相應數(shù)據(jù)項，直到服務器上所有數(shù)據(jù)項都已恢復。為了恢復事務對數(shù)據(jù)項的影響，恢復處理程序從恢復文件中讀取相應的意向表，而意向表中包含該事務所影響的所有數(shù)據(jù)項的值在恢復文件中的位置及其標識符。例：如果服務器在圖10.1以后發(fā)生故障，則恢復處理程序?qū)匆韵路绞交謴蛿?shù)據(jù)項：讀取登錄中最后一條事務狀態(tài)表目，發(fā)現(xiàn)事務U沒有提交，故應撤銷其影響，則移動到登錄的前一個事務狀態(tài)表目P4位置；發(fā)現(xiàn)事務T已提交，故應恢復事務T對數(shù)據(jù)項的影響，即移動到登錄的前一個事務狀態(tài)表目P3位置找到事務T的意向表[(A，P1)，(B，P2)]，然后從P1和P2位置恢復數(shù)據(jù)項A、B。由于沒有恢復數(shù)據(jù)項c，所以還應移動到檢查點即P0點恢復C。

目前九頁\總數(shù)三十一頁\編于七點2．恢復文件的重新組織恢復處理程序負責恢復文件的重新組織以加快恢復過程并減少文件所占的存儲空間。如果沒有對恢復文件進行重新組織，那么恢復處理程序必須從后向前掃描恢復文件直到找出所有數(shù)據(jù)項的值。用checkpointing來表示將當前已提交的數(shù)據(jù)項值以及未完成事務的意向表和事務狀態(tài)表目寫入到某個新恢復文件中的過程。檢查點表示由checkpointing過程所存儲的信息。這樣做的目的是減少恢復過程中需要處理的事務數(shù)目并回收文件空間?？稍诨謴屯瓿梢院笕魏问聞臻_始之前立即執(zhí)行checkpointing

過程。雖然恢復工作并非經(jīng)常進行，但是需要在服務器正常工作時經(jīng)常執(zhí)行checkpointing過程。具有恢復能力的系統(tǒng)可通過刪除舊的恢復文件來回收存儲空間。在恢復過程中，若恢復處理程序移動到恢復文件中的檢查點，則可立即從檢查點中恢復相關的所有數(shù)據(jù)項。目前十頁\總數(shù)三十一頁\編于七點10．2．2影子版本影子版本技術(shù)是另一種組織恢復文件的方式。它通過一張地圖對保存于稱為版本存儲文件中的數(shù)據(jù)項版本進行定位。地圖將服務器數(shù)據(jù)項標識符與它們在版本存儲文件中當前版本的位置聯(lián)系起來，由事務寫入的版本作為以前已提交版本的影子，將事務狀態(tài)表目與意向表分開處理。這里首先介紹影子版本。當準備提交一個事務時，將所有由該事務所修改的數(shù)據(jù)項添加到版本存儲文件中，并保持相應的提交版本不變，這些新的臨時版本稱為影子版本。當事務提交時，通過復制原來的地圖并進入影子版本位置的方式構(gòu)造新的地圖。提交完成后，用新地圖代替原來的地圖。當服務器重新啟動時，恢復處理程序讀取地圖并利用地圖中的信息對版本存儲文件中的數(shù)據(jù)項進行定位，然后就可以恢復相應的數(shù)據(jù)項。

目前十一頁\總數(shù)三十一頁\編于七點這里還是用事務T和u這個例子來說明這個技術(shù)。圖10.2第一列表示在事務T和u開始執(zhí)行之前A、B、C的存款分別是100美元、200美元和300美元，第二列表示事務T提交后的狀況。圖102所示的版本存儲文件中包含一個檢查點,P3位置和P4位置表示事務T提交后A和B的版本情況，文件中還包含事務u準備提交時B和C的影子版本。目前十二頁\總數(shù)三十一頁\編于七點

從舊地圖轉(zhuǎn)換到新地圖必須在一個單一的原子化步驟內(nèi)完成，因此需要利用穩(wěn)定存儲器來保存地圖，這樣即使在文件寫操作過程中出了故障也可以保證地圖的正確性。影子版本技術(shù)的恢復速度比登錄技術(shù)快，這是因為在影子版本技術(shù)中，當前已提交數(shù)據(jù)項的位置記錄在地圖中，而登錄技術(shù)需要掃描整個登錄文件。系統(tǒng)正常工作時，登錄技術(shù)的速度比影子版本技術(shù)快，這是因為登錄技術(shù)僅僅需要將一系列操作添加到相同的文件中，而影子版本技術(shù)需要額外的穩(wěn)定存儲器寫操作(涉及到兩個獨立的磁盤塊)。對服務器而言，僅有影子版本是不夠的，還必須將事務狀態(tài)表目和意向表保存在事務狀態(tài)文件中。意向表代表事務提交后對地圖的修改。事務狀態(tài)文件可組織成登錄形式。目前十三頁\總數(shù)三十一頁\編于七點圖10.3表示提交事務T和準備提交事務U時地圖及事務狀態(tài)文件的相應情形.目前十四頁\總數(shù)三十一頁\編于七點10．2．3恢復文件中的事務狀態(tài)表及意向表表目對分布式事務而言，必須在恢復文件中增加事務狀態(tài)表目及意向表，理由如下：(1)某些恢復處理程序在假定事務正常提交的情況下會提前將數(shù)據(jù)項寫入恢復文件。(2)在事務使用了大量大數(shù)據(jù)項的情況下，由于要將數(shù)據(jù)項連續(xù)地寫入恢復文件中，這將使服務器的設計復雜化。(3)在時間段定序并發(fā)控制中，服務器有時可以確定某事務可最終提交并確認客戶，這時再將數(shù)據(jù)項寫人到恢復文件中，以確保數(shù)據(jù)項的永久性，但是，該事務必須等待以前事務的提交。在這種情況下，恢復文件中相應的事務狀態(tài)表目為等待提交，然后進行提交以保證恢復文件中已提交事務的時間段定序?；謴瓦^程中允許提交任何等待提交事務，因為該事務所等待的事務要么已經(jīng)提交，要么由于服務器出故障而異常終止。

目前十五頁\總數(shù)三十一頁\編于七點1．對兩階段提交協(xié)議的恢復在分布式事務中，各臺服務器保存自身的恢復文件。當服務器出故障時，恢復處理程序必須可對執(zhí)行兩階段提交協(xié)議的事務進行有效恢復。在恢復處理程序中用到另外兩個狀態(tài)值done和uncertain。協(xié)調(diào)程序使用提交狀態(tài)以表示表決的結(jié)果是Yes，并使用done狀態(tài)表示兩階段提交協(xié)議執(zhí)行完畢。工作者使用uncertain狀態(tài)表示自身表決為Yes但還不知道最終結(jié)果。協(xié)調(diào)程序表目記錄相應的工作者，工作者表目記錄相應的協(xié)調(diào)程序，如表10.2所示。目前十六頁\總數(shù)三十一頁\編于七點

在協(xié)調(diào)的第一階段，當協(xié)調(diào)程序準備提交時(即已將準備狀態(tài)表目添加到恢復文件中)，恢復處理程序?qū)f(xié)調(diào)程序表目添加到恢復文件中。在工作者表決Yes之前，該事務必須已經(jīng)準備提交(即已把準備狀態(tài)表目添加到恢復文件中)。當工作者表決Yes時，恢復處理程序?qū)ぷ髡弑砟孔飨鄳涗洸ncertain狀態(tài)添加到恢復文件中。當工作者表決No時，恢復處理程序?qū)bort事務狀態(tài)表目添加到恢復文件中。在協(xié)議的第二階段，與協(xié)調(diào)程序相應的恢復處理程序根據(jù)不同情況將提交或異常終止事務狀態(tài)添加到自身的恢復文件中，與工作者相應的恢復處理程序根據(jù)協(xié)調(diào)程序發(fā)送來的消息，將提交或異常終止事務狀態(tài)添加到各自的恢復文件中。當協(xié)調(diào)程序收到所有工作者的確認消息后，其恢復處理程序?qū)one事務狀態(tài)添加到恢復文件中。done狀態(tài)表目并不是協(xié)議的一部分，但在重新組織恢復文件時要用到它。如圖10.4所示.目前十七頁\總數(shù)三十一頁\編于七點

當服務器重新啟動時，恢復處理程序必須恢復數(shù)據(jù)項并處理兩階段提交協(xié)議。充當協(xié)調(diào)程序的事務必須找到協(xié)調(diào)程序表目和一系列事務狀態(tài)表目，充當工作者的事務必須找到工作者表目及一系列事務狀態(tài)表目。無論是哪種情況，都由最當前(最接近登錄末尾)的事務狀態(tài)表目確定出故障時事務的狀態(tài)。若恢復處理程序執(zhí)行兩階段提交協(xié)議，則其行為取決于相應服務器是充當協(xié)調(diào)程序還是充當工作者，以及故障發(fā)生時服務器的狀態(tài)。其具體情況如表10.3所示。目前十八頁\總數(shù)三十一頁\編于七點目前十九頁\總數(shù)三十一頁\編于七點2．恢復處理程序的重新組織執(zhí)行checkpointing時必須保證：若某事務的狀態(tài)不是done，則與之相應的協(xié)調(diào)程序表目不能從恢復文件中刪除，直到所有工作都確認已完成相應事務?？蓪顟B(tài)為done的表目進行刪除，但若某事務的狀態(tài)為uncertain，則相應的工作者表目必須保留。3.嵌套事務的恢復在設計嵌套事務的恢復系統(tǒng)時假定每個事務可以在獨立的一臺服務器上運行。例如，在圖10.5中，事務T1、T11、T12、T2可存取相同的數(shù)據(jù)項A，但是存取過程有一定順序。子事務的臨時版本基于父事務的臨時版本，當某子事務提交時，相應的父事務繼承它臨時提交的臨時版本。當某子事務異常終止時，丟棄它的臨時版本。分層中最頂層的事務最終提交時，它的版本成為新的提交版本。在最頂層事務提交或異常終止以前，臨時提交的臨時版本代表相應子事務，并將它寫入服務器的恢復文件中。在對最頂層事務進行處理以前，必須先完成準備提交子事務的上述過程。最頂層事務的兩階段提交協(xié)議作為協(xié)凋程序決定了這些臨時版本在恢復文件中的最終狀態(tài)。目前二十頁\總數(shù)三十一頁\編于七點10．2．4事務的故障模型Lampson(1981)提出了一種可解釋為磁盤、服務器和通信故障的分布式事務故障模型。在這種模型中，若發(fā)生的故障是可預測的，則可以保證算法正確運行，否則不能保證算法可正確運行。這種模型還是可能發(fā)生故障，但可以在任何不正確的情況發(fā)生以前通過算法進行檢測以發(fā)現(xiàn)和處理該故障。這種模型描述如下：(1)向永久存儲器進行寫操作時可能發(fā)生故障，例如可能沒有寫入或?qū)懭脲e誤數(shù)據(jù)。另外寫入錯誤塊是災難性錯誤，文件存儲器也可能遭到破壞，可以通過對永久存儲器進行讀操作的方式來檢測數(shù)據(jù)塊是否遭到破壞(例如，通過校驗和方法)。(2)服務器隨時可能發(fā)生故障，當重新啟動時，服務器的易失性存儲器丟失了故障發(fā)生前的所有數(shù)據(jù)(如數(shù)據(jù)項)，因此，必須進行重新設置。當處理器發(fā)生故障時，必須使之失效以防止發(fā)送錯誤消息或?qū)㈠e誤數(shù)據(jù)寫入永久存儲器中。處理器利用永久存儲器和其他處理機的信息來恢復自身數(shù)據(jù)項的值。故障可能在任何時候發(fā)生，在對故障進行恢復時可能再次發(fā)生故障。(3)在消息到達目的地之前可能有一個隨機延遲。消息可能丟失，被復制或被破壞，接收者應能對遭到破壞的消息進行檢測(通過校驗和方法)，偽造的消息或已遭破壞但役有檢測出來的消息是災難性錯誤?？衫眠@種故障模型設計穩(wěn)定系統(tǒng)，該系統(tǒng)各部件中可對任何單一故障進行容錯處理。當發(fā)生單一的寫操作故障或單一的進程故障時，穩(wěn)定存儲器可提供原子寫操作。發(fā)生故障后，穩(wěn)定處理器可利用穩(wěn)定存儲器來恢復數(shù)據(jù)項，并可通過一個可靠的遠程過程調(diào)用機制屏蔽通信故障。目前二十一頁\總數(shù)三十一頁\編于七點10．3容錯計算機的各個部件都是由若干軟件和硬件組合而成的，它們隨時可能發(fā)生故障。分布式系統(tǒng)是由并發(fā)運行于不同計算機上的處理器組成的，它通過通信子系統(tǒng)進行通信轉(zhuǎn)換，相對于計算機而言，通信子系統(tǒng)的行為相對較慢，也相對不可靠，這就導致了在設計正確的服務時相互對立的兩個方面：(1)分布式系統(tǒng)中某個服務操作常常依靠運行于其他計算機上的其他服務操作。但是由于計算機可能出故障，通信也不可能完全可靠，這就會導致后者響應失敗。另外，服務器本身很難檢測出其他相關計算機是否發(fā)生故障，其他服務器是否超載等。(2)可將運行于不同計算機上的一系列服務器聯(lián)合起來，服務器的聯(lián)合執(zhí)行相對于任何單個的服務器而言，其發(fā)生故障的概率更小。例如，可利用多臺服務器復制同一服務的數(shù)據(jù)，這樣即使某些服務器發(fā)生故障，仍可繼續(xù)執(zhí)行此服務。第(1)點表示分布式系統(tǒng)的服務設計者必須考慮到自己使用的其他服務器可能由于多種原因發(fā)生故障；第(2)點表示分布式系統(tǒng)設計者可利用多臺計算機的優(yōu)勢屏蔽所設計的服務中可能存在的潛在錯誤。目前二十二頁\總數(shù)三十一頁\編于七點

不論何種情況，設計者都應了解服務發(fā)生故障的可能性，這意味著設計者不僅要詳細說明正確運行的情況，而且要詳細說明發(fā)生故障的不同方式。對服務器發(fā)生故障的方式進行討論稱為故障語義學。服務器的故障語義學知識能使設計的服務屏蔽服務故障。例如，由于IP協(xié)議所提供的數(shù)據(jù)報服務不可靠，所以必須提出TCP協(xié)議以提供可靠的流通信服務。容錯系統(tǒng)可以檢測出故障的存在，并在此基礎上預測所發(fā)生的故障或進行故障屏蔽。具有容錯能力的服務器所依賴的其他服務器發(fā)生故障時，本故障通過一系列的規(guī)范進行操作。容錯的這種意義允許具有容錯能力的服務器發(fā)生故障語義學允許的故障。服務器在屏蔽服務故障時，要么將故障整個隱藏起來，要么將之轉(zhuǎn)換為允許發(fā)生的故障。在后一種情況下，通常將低層服務器的故障轉(zhuǎn)換成高層服務器的故障類型。目前二十三頁\總數(shù)三十一頁\編于七點10．3．1故障特征為了規(guī)范說明服務器的故障語義學，可以使用一套對故障進行描述的方法。Cristian(1991)提出了一種非常有效的故障分類方法。服務器請求可以改變服務器資源狀況并為用戶產(chǎn)生一個結(jié)果。為了服務器的正確運行，Cristian分類法假定對服務器資源的影響以及客戶響應必須正確。具體的分類情況如表10.4所示。目前二十四頁\總數(shù)三十一頁\編于七點1．同步故障Cristian分類法中提出了同步故障，它是指在特定的時間間隔內(nèi)對客戶無效的任何響應。同步故障可描述為響應太遲(即執(zhí)行故障)或太早。例如某超載的服務器的響應可能過遲到達。設計實時操作系統(tǒng)必須避免同步故障，相對于其他沒有實時限制的操作系統(tǒng)(如UNIX)而言，設計實時操作系統(tǒng)更為復雜并需要更多的硬件資源。2．服務器失效故障Cristian將服務器失效故障定義為遺漏故障重復發(fā)生。大多數(shù)服務器故障使得服務器停止發(fā)送消息，在客戶眼里，服務器巳停止工作?？蛻舨荒軐Ψ掌鞴收?、服務器響應過慢和服務器通信失敗這三者進行確切區(qū)分?？梢岳贸瑫r和重新傳遞請求消息的方法檢測服務器故障，即與處理器進行通信的次數(shù)超過一定數(shù)目后處理器仍無應答，則認為處理器巳發(fā)生故障。這種檢測服務器故障的方法是基于對服務器的可能響應時間及丟失消息的可能性進行設定，因此出錯的可能性很小。

目前二十五頁\總數(shù)三十一頁\編于七點

失憶故障相對于重復的遺漏故障而言危害更大，因為在這種情況下服務器丟失了自身的狀態(tài)(如數(shù)據(jù)項的值)?？梢岳没謴蜋C制避免服務器出故障時發(fā)生失憶故障行為。利用恢復機制避免失憶故障時，由于需提供新的服務，從而增加了開銷。目前二十六頁\總數(shù)三十一頁\編于七點10．3．2Byzantine故障Cristian使用隨機故障語義學這個詞來表示服務器可能發(fā)生上述所有的故障語義學，即失效故障、同步故障、響應故障和遺漏故障。利用Byzantine故障這個詞表示在最壞情況下服務器的故障語義學。Lamport等人(1982)使用臨界生存系統(tǒng)使Byzantine問題一般化。在本系統(tǒng)中設定了一個環(huán)境模型，在此環(huán)境模型中，大多數(shù)計算機正常工作而其他一些有故障的計算機在盡可能惡劣的條件下工作。有故障的計算機可能對不同的接收者發(fā)送相互矛盾的消息，也可能相互冒充。這種考慮最壞情況的觀點使設計的系統(tǒng)可以出現(xiàn)最壞情況，從而使得系統(tǒng)是超可靠的。Byzantine協(xié)議可應用于有特定響應時間限制的環(huán)境及能正確運行于有故障硬件能力的環(huán)境中。

目前二十七頁\總數(shù)三十一頁\編于七點

Byzantine協(xié)議算法要發(fā)送更多的消息，使用更多的活躍服務器。算法的任務是將相同的消息發(fā)送到所有服務器上，從而使得正常的服務器在特定的時間限制內(nèi)產(chǎn)生相同的響應。它等價于原子化多點傳送，即使某些有故障的服務器發(fā)生了同步故障而導致不確定的響應延遲，算法仍可正常工作。每臺服務器都使用相同的方法將自己的表決與其他服務器的表決進行組合，在此過程中可能發(fā)生值故障或遺漏故障。如圖10.6(a)所示，有A、B、C三臺服務器(兩臺正常，一臺不正常)，正常的服務器表決Yes，不正常的服務器向一臺正常的服務器發(fā)送Yes，而向另一臺正常的服務器發(fā)送No。服務器A接收到的消息為{Yes，Yes，Yes}，服務器B接收到的消息為{Yes，Yes，Nn}，由于在這兩種情況下表決的主體是Yes，故正常服務器的表決結(jié)果是Yes，這表明兩臺正常服務器可對一臺不正常服務器的故障進行容錯。一般而言，若可保持接收者的消息不會遭到破壞，并可鑒定發(fā)送者身份，則2n+1臺服務器可以屏蔽n臺故障服務器的故障，因為正常的服務器占表決多數(shù)。在圖10.6(b)所示情況下，正常服務器A表決Yes，不正常服務器C卻宣布A表決No，由于服務器B從A接收到兩個完全相反的表決，故B不能確定A的表決到底是什么。若不能鑒定消息發(fā)送者身份，則需要三臺正常服務器來屏蔽一臺服務器的故障。理論上的Byzantine模型需要三臺正常服務器處理一臺不正常服務器的故障行為。在實際應用中可以假定消息不會遭到破壞并且可以鑒定發(fā)送者身份，這種模型有時稱作Byzantine鑒定將軍模型，其故障語義學包括響應故障(值故障、狀態(tài)轉(zhuǎn)換故障)、遺漏故障和同步故障。目前二十八頁\總數(shù)三十一頁\編于七點10．4分層故障屏蔽和成組故障屏蔽Cristian提出了分層故障屏蔽和成組故障屏蔽兩種故障屏蔽方法。10．4．1分層屏蔽分層故障屏蔽是指服務器依靠低層服務的情況，高層次服務器屏蔽低層次故障。某些情況下服務器故障可能完全隱藏，例如請求---應答協(xié)議通過重新發(fā)送請求消息的方式屏蔽消息傳送服務中的遺漏故障。當不能屏蔽某低層故障時，可將它轉(zhuǎn)換成一個高層異常。例如請求一應答協(xié)議通過向客戶報告異常來屏蔽服務器失效故障。一般而言，在每個層次上，故障要么完全隱藏，要么轉(zhuǎn)換為高層異常，從而在高層上試圖屏蔽該故障。當最終到達用戶界面層次時，大多數(shù)故障已經(jīng)得到屏蔽。此時若還有故障不能屏蔽，則必須將故障報告給用戶。對用戶而言，