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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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