第十章故障恢復與系統容錯詳解演示文稿

第十章故障恢復與系統容錯詳解演示文稿目前一頁\總數三十頁\編于七點優(yōu)選第十章故障恢復與系統容錯目前二頁\總數三十頁\編于七點10．2事務恢復事務的原子化特征可以用耐久性和錯誤原子化來描述。耐久性要求將數據項保存到永久存儲器中并可隨時使用，因此承認客戶的提交請求意味著該事務的所有影響不僅記錄在服務器的數據項中，而且記錄在永久存儲器中。所謂錯誤原子化，是指即使服務器發(fā)生故障，事務對數據項的影響也是原子化的。若某事務需具有恢復功能，則必須保證服務器的數據項具有耐久性，并且服務也應提供錯誤原子化功能。雖然文件服務器和數據庫服務器都將數據保存在永久存儲器中，但其他的服務器并不是這樣的，除非要求此服務器具有恢復功能。在本章中假定：服務器運行時將所有的數據項都保存在易失性存儲器中，并把所有已提交的數據記錄到恢復文件或文件中。這樣恢復工作就是把數據項的最新提交版本從永久存儲器中恢復到服務器上。由于數據庫通常需要處理大量數據，所以它們通常通過高速緩存把數據項從易失性存儲器轉移到磁盤永九存儲器中。

目前三頁\總數三十頁\編于七點

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

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

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

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

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

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

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

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

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

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

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

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

在協調的第一階段，當協調程序準備提交時(即已將準備狀態(tài)表目添加到恢復文件中)，恢復處理程序將協調程序表目添加到恢復文件中。在工作者表決Yes之前，該事務必須已經準備提交(即已把準備狀態(tài)表目添加到恢復文件中)。當工作者表決Yes時，恢復處理程序對工作者表目作相應記錄并將uncertain狀態(tài)添加到恢復文件中。當工作者表決No時，恢復處理程序將abort事務狀態(tài)表目添加到恢復文件中。在協議的第二階段，與協調程序相應的恢復處理程序根據不同情況將提交或異常終止事務狀態(tài)添加到自身的恢復文件中，與工作者相應的恢復處理程序根據協調程序發(fā)送來的消息，將提交或異常終止事務狀態(tài)添加到各自的恢復文件中。當協調程序收到所有工作者的確認消息后，其恢復處理程序將done事務狀態(tài)添加到恢復文件中。done狀態(tài)表目并不是協議的一部分，但在重新組織恢復文件時要用到它。如圖10.4所示.目前十八頁\總數三十頁\編于七點

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

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

目前二十六頁\總數三十頁\編于七點

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

目前二十八頁\總數三十頁\編于七點

Byzantine協議算法要發(fā)送更多的消息，使用更多的活躍服務器。算法的任務是將相同的消息發(fā)送到所有服務器上，從而使得正常的服務器在特定的時間限制內產生相同的響應。它等價于原子化多點傳送，即使某些有故障的服務器發(fā)生了同步故障而導致不確定的響應延遲，算法仍可正常工作。每臺服務器都使用相同的方法將自己的表決與其他服務器的表決進行組合，在此過程中可能發(fā)生值故障或遺漏故障。如圖10.6(a)所示，有A、B、C三臺服務器(兩臺正常，一臺不正常)，正常的服務器表決Yes，不正常的服務器向一臺正常的服務器發(fā)送Yes，而向另一臺正常的服務器發(fā)送No。服務器A接收到的消息為{Yes，Yes，Yes}，服務器B接收到的消息為{Yes，Yes，Nn}，由于在這兩種情況下表決的主體是Yes，故正常服務器的表決結果是Yes，這表明兩臺正常服務器可對一臺不正常服務器的故障進行容錯。一般而言，若可保持接收者的消息不