張新洲， 周敏奇

（華東師范大學 軟件學院，上海 20062）

0 引 言

隨著大數(shù)據(jù)時代的到來，系統(tǒng)所需要承受的計算任務(wù)變得越來越復雜，因此系統(tǒng)在硬件技術(shù)以及軟件優(yōu)化方案上都有進一步的改善和提高.對于高性能計算機系統(tǒng)來說，為了應(yīng)對日益增長的數(shù)據(jù)量規(guī)模、逐漸增強的計算復雜度，需要添加越來越多的高性能組件.隨之帶來的結(jié)果是，長時間的運行分布式程序，由硬件失效造成的系統(tǒng)終端失效概率變大，此外，當一個系統(tǒng)應(yīng)用程序失敗時，會消耗更多的恢復成本，因為集群系統(tǒng)中會更多的計算結(jié)果都會隨之丟失.因此，分布式系統(tǒng)和并行系統(tǒng)雙方對于容錯機制的支持至關(guān)重要，以此來確保大規(guī)模計算環(huán)境的可用性.

本文專注于集群系統(tǒng)，以及在集群環(huán)境下運行的分布式應(yīng)用程序.集群系統(tǒng)是由大量相同的、集中管理的計算節(jié)點通過以太網(wǎng)或者萬兆網(wǎng)連接在一起的分布式系統(tǒng).節(jié)點間采用如MPI等軟件協(xié)助各個節(jié)點融入成為一個更大的、統(tǒng)一的集群系統(tǒng)；通常一些節(jié)點作為主節(jié)點用于管理和用戶交互.

在集群環(huán)境中，各個節(jié)點出現(xiàn)故障的概率較高.任何組件的任何計算節(jié)點都有可能出現(xiàn)失效，包括處理器，硬盤，存儲器網(wǎng)絡(luò)接口等硬件.一個節(jié)點上的硬件或者軟件故障都有可能會影響到整個系統(tǒng)的調(diào)度以及造成數(shù)據(jù)的丟失.第1節(jié)將概述這些故障的理論模型.

通常來說可能發(fā)生在集群系統(tǒng)中的故障主要有兩個基本類別.第1類是集中式的組件故障，例如一個存儲節(jié)點或者是一個管理軟件出現(xiàn)了硬件故障或者軟件錯誤最終導致系統(tǒng)失敗.冗余技術(shù)可以用于處理這一類故障，即將數(shù)據(jù)復制到多個節(jié)點上.一旦一個節(jié)點發(fā)生故障，備份的數(shù)據(jù)可以介入，接管主要的功能，從而保證系統(tǒng)可用性.第2節(jié)主要討論這一類的系統(tǒng)故障.

第2類故障是分布式應(yīng)用在集群中運行時某個節(jié)點突然崩潰或者掛起.這可能是由于應(yīng)用程序中的漏洞、該節(jié)點上的硬件故障，或者是操作系統(tǒng)的問題導致運行在該節(jié)點的應(yīng)用程序無法繼續(xù)正常工作.但是參加相同計算的其他節(jié)點可以繼續(xù)工作不受影響，不同的是它們不再從故障節(jié)點接受輸出.面對這樣的故障，通過設(shè)置程序的檢查點來定期檢查應(yīng)用程序的計算狀態(tài)，完成系統(tǒng)發(fā)生故障時的恢復.同時參與計算的其它節(jié)點可能需要回滾到較早之前的檢查點，使得所有的節(jié)點與出現(xiàn)故障的節(jié)點恢復的狀態(tài)是一致的.第3節(jié)提供了回滾恢復技術(shù)和防止故障發(fā)生的詳細細節(jié).在第4節(jié)對系統(tǒng)設(shè)計中的接口與封裝進行了闡述.

文章第5節(jié)和第6節(jié)分析了當前內(nèi)存計算環(huán)境下容錯技術(shù)面臨的機遇和挑戰(zhàn)，在利用內(nèi)存高效加載及高速計算的同時需要克服內(nèi)存的易失性.對Spark系統(tǒng)和Claims系統(tǒng)的容錯技術(shù)進行了分析.最后對全文進行總結(jié)，并對未來工作進行展望.

1 錯誤模型

面對大數(shù)據(jù)處理，集群環(huán)境出現(xiàn)失敗的情況數(shù)不勝數(shù)，通過故障在系統(tǒng)的行為方式中存在的抽象模型實現(xiàn)錯誤分類.容錯技術(shù)將針對不同的錯誤模型進行設(shè)計和實現(xiàn).本章討論3種最常見的故障模式.

1.1 隨機故障模型（拜占庭Byzantine模型）

拜占庭故障模型代表系統(tǒng)失敗最敵對的模型.此故障模型允許失敗的節(jié)點繼續(xù)與系統(tǒng)的其余部分進行交互.節(jié)點間的行為可以是任意的和不一致的，并且失效的節(jié)點間允許進行通信繼續(xù)產(chǎn)生輸出.正確運行的節(jié)點不能自動檢測出已經(jīng)失效的節(jié)點，也不能得知當一個錯誤出現(xiàn)時哪些節(jié)點有可能會失效.這個模型可以被黑客表示為隨機系統(tǒng)故障以及惡意攻擊.它已經(jīng)被證明無法保證一個擁有3m＋1個節(jié)點的系統(tǒng)中其中m個節(jié)點正在經(jīng)歷拜占庭失效時還能夠正確運行.

1.2 故障－停止（Fail－stop）模型

故障停止故障模型比拜占庭模型要簡單.該模型允許任何節(jié)點在任何時間出現(xiàn)故障，但是，當發(fā)生故障時它停止產(chǎn)生輸出，與系統(tǒng)的其余部分交互.此外，所有其它節(jié)點自動地獲知該節(jié)點失敗狀態(tài).此故障模型表示是失敗的常見模式，如系統(tǒng)掛起或崩潰，但處理粒度不細致，如無法探測到隨機內(nèi)存損壞原因.

Fail－stop模型認為系統(tǒng)組件，如個別服務(wù)，節(jié)點，通信連接等，是通過簡單的停止而失敗的.部署的故障檢測機制僅僅對硬件錯誤或者災(zāi)難性的軟件錯誤做出反應(yīng).如果一個失敗的系統(tǒng)組件因軟件錯誤或者系統(tǒng)設(shè)計錯誤產(chǎn)生了錯誤的輸出而違背了這種假定，那么基于這種模型的冗余方案不能夠保證正確性.

1.3 Fail－stutter模型

上述兩種容錯模型中拜占庭模型是極其廣泛的，但不切實際，因此很難在實際中得到應(yīng)用；而故障停止模型更加常用也更加容易進行部署，但是它過于簡單，因為它未能表示出多種類型的現(xiàn)實世界失效.為了彌補這兩種極端情況的不足，F(xiàn)ail－stutter模型應(yīng)運而生.

Fail－stutter模型是故障停機模式的延伸.它試圖維持該模型的易處理性，同時擴展了真實世界中的各種故障集合.Fail－stutter模型覆蓋了故障停機模式的所有規(guī)則，同時它也允許性能故障.性能故障是指某個節(jié)點發(fā)生性能上的意外，此時處理性能急劇下降，但是仍然能夠輸出正確的結(jié)果.這個擴展允許模型包含諸如當遭遇非常大的流量負載時網(wǎng)絡(luò)交換機的高延遲性能故障.盡管Fail－stutter模型擁有以上優(yōu)勢，但是目前還沒有被社會廣泛的接受.

2 集中式容錯

集群系統(tǒng)依賴于大量集中式組件才能正常工作.主節(jié)點負責處理作業(yè)調(diào)度和節(jié)點監(jiān)控，存儲節(jié)點可以訪問大容量的磁盤陣列.而在某些系統(tǒng)中還有專門的節(jié)點負責與用戶進行交互，從而避免占用系統(tǒng)中其他節(jié)點的計算時間.這些關(guān)鍵的節(jié)點通常在集群中占用比較小的數(shù)量，但是它們對于整個系統(tǒng)至關(guān)重要，因此需要對于這些節(jié)點進行額外的關(guān)照，甚至可以提供額外的硬件支持來保證它們在遭遇系統(tǒng)故障時保持健壯性.

2.1 備份

對于集中式系統(tǒng)來說提供容錯最常見的方法是復制.復制通常可以采用以下兩種方式：

第1種是主動復制，第2臺機器接收所有來自主節(jié)點的輸入副本，并且通過所有必要的軟件獨立運行出一個相同的系統(tǒng)狀態(tài).此外，備份節(jié)點還會監(jiān)視主節(jié)點的不正確行為.同時，在這些不正確的行為發(fā)生（例如系統(tǒng)崩潰）時，備份節(jié)點自動提升自身的優(yōu)先狀態(tài)，并接管該系統(tǒng)的關(guān)鍵功能.由于備份節(jié)點的系統(tǒng)狀態(tài)已經(jīng)等同于優(yōu)先狀態(tài)，所以這種轉(zhuǎn)換所需要的時間是可以忽略掉的.這種備份的方式對于高性能并行計算集群來說是不可行的，因為這種系統(tǒng)需要增加一倍的節(jié)點數(shù)量開銷而并不提高系統(tǒng)的性能.

對主服務(wù)器進行多個備份是主動復制的一個變體：所有備份機器接收全部的輸入，當產(chǎn)生輸出時，所有的副本投票決定什么是正確的輸出，最終根據(jù)拜占庭算法將結(jié)果進行比較，如果一個或多個節(jié)點生成超出閾值次數(shù)的不正確輸出，它們將被標記為故障并且忽略，直到它們可以通過維護程序進行修復.這種變體能夠處理拜占庭故障，而之前的主動復制只能容忍故障停機模式的錯誤.

第2種是被動復制，在被動復制中，“冷備”機始終作為主系統(tǒng)的完整備份.這個系統(tǒng)通常保持空閑狀態(tài)，但是它具有系統(tǒng)中所有軟件的備份.如果主設(shè)備發(fā)生故障，冷備機立即接管主要職責.這可能產(chǎn)生服務(wù)的暫時中斷，它取決于副本的空閑狀態(tài).如果在沒有設(shè)置檢查點機制的情況下，被動復制不適合用來維護復雜的難以恢復的系統(tǒng)內(nèi)部狀態(tài)，但是它適合用來維持小型的系統(tǒng)內(nèi)部組件，如子系統(tǒng)的完整備份.

另外，被動復制更加適合在更高級別上復制系統(tǒng)的某一部分組件而不是將整個系統(tǒng)進行完整的備份.通常在架構(gòu)整個系統(tǒng)時可以采用多個相同的內(nèi)部組件，例如，一臺機器裝備多個CPU、多個內(nèi)存以及多個主板等等，或者針對系統(tǒng)中最容易出現(xiàn)錯誤的組件準備多個備用組件.在系統(tǒng)運行中通過仔細監(jiān)視每個組件的正確性，一旦出現(xiàn)失效，則這個失敗的組件自動被禁用，用備份進行替換而不需要關(guān)閉系統(tǒng)，并且不中斷任何系統(tǒng)軟件.一旦正確的功能恢復正常，發(fā)生故障的組件可以后來進行熱交換使用新的副本.

2.2 可靠的通訊

如之前所述，當所有系統(tǒng)組件的副本所接收到的輸入完全相同的時候，系統(tǒng)組件的主動復制是可行的.雖然與集中式系統(tǒng)的節(jié)點進行通信可以采用多種組播通信協(xié)議來實現(xiàn)，但是沒有必要保證所有副本上的組播都是完全一致的.如果系統(tǒng)不提供這種一致性的保證，那么各個備份就可以在不一致的狀態(tài)下結(jié)束通信.

實際上存在多種可以提供可靠性，安全性的組播通信協(xié)議.組播通信將一個客戶或一個組成員發(fā)送的消息傳送給組內(nèi)的所有成員.不同的應(yīng)用程序要求系統(tǒng)中的組成員按照相應(yīng)的順序來接收和處理組播消息，以保證系統(tǒng)的正確運行.然而，在一個開放動態(tài)的分布系統(tǒng)中，網(wǎng)絡(luò)延遲、資源競爭等各種因素可能會導致各個成員接收消息的次序不同.為保證應(yīng)用的正常運行，組播通信需要解決消息次序問題.通常消息次序可以分為3種：FIFO序、因果序（Casual Order）、全序（Total Order）.FIFO序指一個組中所有的成員都按照相同的順序接收來自同一個客戶或者組成員的消息.FIFO序很容易實現(xiàn)，但它是實現(xiàn)其他通信方式的基礎(chǔ).因果序保證兩條具有因果關(guān)系的消息m1和m2按照其因果關(guān)系傳遞到組內(nèi)各個成員.這里因果關(guān)系是指一個成員先發(fā)送m1，然后才能發(fā)送m2，或者先接收m1，然后才能接收m2.因果序通常利用邏輯時鐘實現(xiàn)，如Lamport邏輯時鐘.

全序組通信，也被稱為原子組通信（Atomic Broadcast），它能夠保證一個通信組中所有的成員都按照相同的順序接收消息.全序組通信是分布式容錯系統(tǒng)中一個十分重要的問題，它是實現(xiàn)有限狀態(tài)機復制協(xié)議的基礎(chǔ).全序組通信在靜態(tài)和動態(tài)的組通信系統(tǒng)中的實現(xiàn)方式是不同的.在靜態(tài)系統(tǒng)中，全序組通信問題一般轉(zhuǎn)換成一致性（Consensus）問題，并直接利用不可靠失效檢測器來解決.在動態(tài)系統(tǒng)中，全序組通信需要利用組成員關(guān)系服務(wù)和虛擬同步通信原語來實現(xiàn).直觀而言，虛擬同步通信原語能夠保證在組視圖發(fā)生變化時，所有組成員接收的消息集合相等.

2.3 監(jiān)控

對于一個系統(tǒng)來說，它必須監(jiān)測到主要的組件已經(jīng)失效才能夠自動激活備份副本.監(jiān)測的最基本形式是一個簡單的心跳系統(tǒng)，監(jiān)視器進程偵聽來自受監(jiān)視組件的周期性消息.該消息只是表示該組件正常工作，如果監(jiān)視器在預定時間內(nèi)沒有從組件收到消息，那么便認為該組件失效.這種形式的監(jiān)控適用于故障停機模式檢測故障.

復制組件之間的拜占庭模型是監(jiān)控的另一種形式.各個副本會根據(jù)正確的輸入輸出或者各個副本的各個操作進行投票.在發(fā)生分歧的情況下，少數(shù)被認為是錯誤的.這種方法允許拜占庭故障檢測機制，使得監(jiān)控更加的強壯.然而，拜占庭共識通信成本比心跳監(jiān)控的成本要高得多，因為在最壞情況下，所有節(jié)點都必須與所有其他節(jié)點通信.對于一個小規(guī)模副本，這可能是可以接受的.

當然，監(jiān)控也可以通過自一致性檢查的形式實現(xiàn).單個節(jié)點通過周期性的自我檢查來確定是否內(nèi)部組件正常運行.此外，系統(tǒng)中的其他節(jié)點可以確定一個集中式的服務(wù)器是否會出現(xiàn)問題來共享信息.也可以通過檢查從服務(wù)器丟失的或者格式不正確的消息進行錯誤檢查.倘若其他節(jié)點懷疑存在問題，也可以觸發(fā)服務(wù)器自診斷檢查.

2.4 軟件設(shè)計

管理軟件可以把容錯機能作為設(shè)計目的之一.細致的軟件工程可以設(shè)計出能夠抵抗系統(tǒng)故障的程序，并最大限度地減少停機時間，讓故障不影響系統(tǒng)功能.

重新啟動系統(tǒng)是處理各種故障的常見方式.但是它的缺點也顯而易見，它會大大增加系統(tǒng)的停機時間，并且產(chǎn)生很多不必要的開銷.例如重新啟動不僅會重啟失效的機器，正常工作的機器也會隨之重新啟動.因此，在架構(gòu)整個系統(tǒng)的初期就應(yīng)該設(shè)計好多層次結(jié)構(gòu)，使得各個功能組件盡可能的獨立.在某個層次出現(xiàn)失效的時候，只需要重啟與之緊密相關(guān)的系統(tǒng)，其他功能還能正常使用，從而避免不必要的開銷.

3 并行應(yīng)用程序的容錯

集群系統(tǒng)的真正價值并不在于軟件管理和操作執(zhí)行，而是將大規(guī)模的并行計算程序在串行的環(huán)境中有效的執(zhí)行并快速地輸出結(jié)果.因此，即使主節(jié)點可以抵抗任意類型的故障，系統(tǒng)還是需要保證分布式的應(yīng)用在集群中運行時受到保護，否則，針對硬件進行的容錯將毫無意義.

3.1 檢查點和回滾

并行應(yīng)用程序容錯的最基本形式是檢查點和回滾恢復.具有檢查點的恢復技術(shù)是在日志文件中增加一類新的記錄－－檢查點記錄（checkpoint），增加一個重新開始文件，并讓恢復子系統(tǒng)在登錄日志文件期間動態(tài)地維護日志.為了確保應(yīng)用的可靠性，系統(tǒng)需要保存應(yīng)用程序的狀態(tài)，用以保證系統(tǒng)計算的完整性.回滾恢復技術(shù)是保存系統(tǒng)狀態(tài)的一種常見形式.

并行檢查點設(shè)置和恢復技術(shù)包括兩部分：各進程狀態(tài)的保存和恢復，以及通信通道狀態(tài)的保存和恢復.前者與單進程檢查點內(nèi)容密切相關(guān)，而對后者的處理協(xié)議可分成兩大類：檢查點協(xié)議和日志協(xié)議.檢查點協(xié)議中，進程只記錄描述進程狀態(tài)信息的檢查點.日志協(xié)議中，進程不僅記錄檢查點，也記錄事件相關(guān)的日志信息.

回滾恢復技術(shù)可分為兩大類：基于檢查點的回滾以及基于日志的回滾.

（1）多米諾骨牌效應(yīng)

當回滾之后，一個進程根據(jù)發(fā)件人的狀態(tài)記錄了尚未發(fā)送的消息記錄，隨后便出現(xiàn)多米諾骨牌效應(yīng).在這種情況下，收件人的狀態(tài)必須回滾到收到消息之前的狀態(tài).這種效果會產(chǎn)生級聯(lián)效應(yīng)，使得系統(tǒng)無限期回滾，導致巨大計算量的損失.這種效應(yīng)也迫使每個進程維護多個檢查點，在多米諾骨牌效應(yīng)回滾的情況下存在這樣的后備選項.

（2）基于檢查點的回滾恢復

一般情況下，以檢查點為基礎(chǔ)的回滾恢復協(xié)議周期性地保存每個計算中涉及的進程當前計算狀態(tài).當創(chuàng)建檢查點被激活時，系統(tǒng)會記錄該進程的內(nèi)存狀態(tài).這樣，在進程出現(xiàn)故障的時候，進程可以根據(jù)一個中間狀態(tài)進行重建.

通常來說，有3個類別的檢查點作為恢復協(xié)議：協(xié)作式檢查點，獨立式檢查點和通信引導式檢查點.

在協(xié)作式（同步）檢查點中，要求強制多個線程協(xié)調(diào)記錄檢查點用以獲得一致的全局狀態(tài)，只需要每個進程在穩(wěn)定存儲上維護一個永久性檢查點，降低存儲開銷以及避免垃圾回收操作.它的缺點是在向外界提交輸出任何結(jié)果時需要協(xié)調(diào)記錄全局的檢查點，導致提交輸出操作有較大延遲.

獨立式檢查點方法中，進程具有極大的自主性來決定記錄檢查點的時機，例如在進程狀態(tài)信息量小的時候記錄.它的缺點是：1）容易產(chǎn)生Domino效應(yīng)；2）進程可能會記錄不屬于全局一致狀態(tài)的無用檢查點，導致不必要的開銷；3）每個進程要維護多個檢查點，必須周期性的激活垃圾回收刪除不再使用的檢查點；4）不適合與外界交互頻繁的應(yīng)用，因為向外界輸出時需要全局的協(xié)調(diào)操作，導致開銷的增加.

在這種方法中，進程要記錄2種檢查點，一種是進程各自獨立記錄的，稱為局部檢查點，另一種是進程被強制記錄的，稱為強制檢查點.進程根據(jù)接收到的其它進程消息捎帶來的信息決定是否記錄強制檢查點.和協(xié)作式檢查點相比，這種方法不需要交換專門的消息.

（3）基于日志的回滾恢復

日志協(xié)議把進程的執(zhí)行看成非確定狀態(tài)區(qū)間序列，每個區(qū)間以非確定事件的執(zhí)行開始.協(xié)議假定所有的非確定事件都可以被識別，同時事件相關(guān)的信息都可以記錄到穩(wěn)定存儲上.另外，進程也記錄檢查點.一個進程的狀態(tài)依賴于非確定事件，但是該事件在恢復階段不能重新生成，這樣的進程稱為孤立進程（orphan process）.產(chǎn)生孤立進程將導致系統(tǒng)的不一致狀態(tài).日志協(xié)議可保證在執(zhí)行恢復操作時不產(chǎn)生孤立進程從而獲得一致的全局狀態(tài).日志協(xié)議分為3種：悲觀日志、樂觀日志和因果日志.

悲觀日志假定任何非確定事件之后都可能發(fā)生故障.最直接的實現(xiàn)方式是在事件影響計算結(jié)果之前，事件日志信息都已經(jīng)存到穩(wěn)定存儲上.悲觀日志導致很高的開銷.可以采用特殊的硬件降低開銷.例如，采用非易失性內(nèi)存作為穩(wěn)定存儲，另外一種形式是采用專門的總線記錄日志消息.也可以不采用硬件，如基于發(fā)送方消息日志把消息記錄在發(fā)送方動態(tài)內(nèi)存內(nèi).

樂觀日志中事件日志信息以易失性日志的形式臨時保存，然后周期地存放到穩(wěn)定存儲.它樂觀地假設(shè)在發(fā)生故障之前能記錄完日志.因此，應(yīng)用可繼續(xù)執(zhí)行，不必阻塞等待日志保存到穩(wěn)定存儲.和悲觀日志相比，樂觀日志必須記錄多個檢查點導致垃圾回收算法相對復雜.另外可能產(chǎn)生孤立進程.

因果日志協(xié)議結(jié)合了樂觀日志和悲觀日志兩者的優(yōu)點.一方面，它避免了同步訪問穩(wěn)定存儲的操作；另一方面，它允許每個進程獨立地提交輸出操作而不產(chǎn)生孤立進程.另外，在恢復時能保證進程回滾到最近的存放在穩(wěn)定存儲上的檢查點.但這些優(yōu)勢的獲得是以復雜的恢復協(xié)議為代價的.

3.2 虛擬線程

虛擬線程允許并行程序以超過物理處理器個數(shù)的線程數(shù)進行執(zhí)行.在這樣的系統(tǒng)中，每一個虛擬線程映射到一個物理處理器，而每一個物理處理器處理一個或多個虛擬線程的任務(wù).虛擬線程可以從一個物理處理器遷移到另外一個物理處理器而不需要關(guān)閉整個應(yīng)用進程.這項技術(shù)主要應(yīng)用于負載均衡、網(wǎng)格計算以及系統(tǒng)容錯.

容錯應(yīng)用使用這項技術(shù)的關(guān)鍵是遷移功能.如果一個節(jié)點出現(xiàn)故障，虛擬線程可以遷移到操作可正常執(zhí)行的其他節(jié)點上繼續(xù)運行.雖然在遷移之后，系統(tǒng)整體的執(zhí)行速度可能會有所下降，但這是一種比系統(tǒng)完全失效或者暫停更優(yōu)的方案.

為了處理失敗停機類故障，虛擬處理器技術(shù)可與處理器復制或檢查點相結(jié)合，允許在一個幸存的物理節(jié)點上對已經(jīng)丟失的虛擬線程進行實時恢復.在實踐中，通常使用協(xié)同檢查點技術(shù)，針對大型應(yīng)用程序使用磁盤中的檢查點，針對小型應(yīng)用程序使用內(nèi)存中的檢查點.

此外，虛擬處理器可以主動或被動地復制，以提供可在發(fā)生故障時接管的備份實例.系統(tǒng)中的應(yīng)用程序根據(jù)功能的不同可以被分配給每個處理器，并且處理器可以被復制到不同程度，具體程度取決于需要保護該組件的重要級別.

4 接口與封裝

雖然容錯技術(shù)具有很高的學術(shù)研究價值，但是只有通過系統(tǒng)部署才能產(chǎn)生真正的價值.顯然容錯技術(shù)可以由程序開發(fā)人員直接實現(xiàn)，但是一個簡單易用的軟件包可以大大降低學習成本，因此從接口到合成系統(tǒng)是區(qū)分各種容錯方案的一個關(guān)鍵因素.

最常見的封裝容錯技術(shù)是以提供軟件庫形式來實現(xiàn)相關(guān)應(yīng)用程序的編程接口（API）.開發(fā)者調(diào)用特定的API函數(shù)便可以實現(xiàn)軟件開發(fā)中容錯的高效移植.目前比較成熟的容錯軟件接口大多采用面向?qū)ο蟮乃枷?因此在容錯中可以建立容錯的編程語言，從而簡化開發(fā)人員根據(jù)分布式特性進行分布式程序開發(fā)的步驟，減少編程錯誤導致運行的錯誤.此外，容錯還可以在操作系統(tǒng)級別實現(xiàn).理想的情況下，應(yīng)用程序?qū)柚到y(tǒng)自行運行的能力進行實時容錯.

另一種可能的方法是部署中間件系統(tǒng)，利用系統(tǒng)守護進程進行系統(tǒng)監(jiān)控以及應(yīng)用程序支持.這類似于系統(tǒng)級別的集中式容錯理念，它并不需要特殊的主機操作系統(tǒng)，而是利用系統(tǒng)級別的守護進程在后臺持續(xù)運行.這些后臺程序可以被配置成監(jiān)視所有的應(yīng)用程序并提供容錯功能.

提供容錯技術(shù)的最后一個方法是使用預處理器針對源代碼自動生成必要的修改代碼.這樣做可以簡化復雜的代碼，不需要程序員添加額外的代碼來指定某一部分作為系統(tǒng)的容錯代碼，通過自動執(zhí)行預處理代碼從而減少內(nèi)存開銷和資源浪費.

5 內(nèi)存計算環(huán)境下的容錯技術(shù)

隨著硬件進一步發(fā)展，超大規(guī)模計算已經(jīng)發(fā)展到內(nèi)存計算，即將所有需要的數(shù)據(jù)全部加載到內(nèi)存中然后再進行計算，充分利用內(nèi)存計算的高效性.這一發(fā)展給容錯又帶來了前所未有的挑戰(zhàn)，因為在享受內(nèi)存高效的同時還需要解決易失性的缺點.在支持內(nèi)存計算的系統(tǒng)中，通常需要將系統(tǒng)執(zhí)行過程中的操作進行記錄，通過階段性的切分，將數(shù)據(jù)自適應(yīng)地組織成一個完整的鏈條，通過這個鏈條對整個操作流程進行完整的備份.目前在這方面較為出色的是Berkeley的Spark系統(tǒng).

Spark的核心概念是RDD（resilient distributed dataset），將數(shù)據(jù)定義為一個只讀的，可分區(qū)的分布式數(shù)據(jù)集，這個數(shù)據(jù)集可以全部或者部分緩存在內(nèi)存中，并且可以在多次計算之間重用.

容錯方面，Spark采用Lineage機制，結(jié)合利用內(nèi)存加快數(shù)據(jù)加載，提出了一套區(qū)別于其他系統(tǒng)在分布式環(huán)境下使用的容錯方案，解決了節(jié)點實效和數(shù)據(jù)丟失的問題.為了保證系統(tǒng)中RDD數(shù)據(jù)魯棒性，RDD數(shù)據(jù)集通過血統(tǒng)關(guān)系（Lineage）記錄整個數(shù)據(jù)集演變的過程.相比于其它系統(tǒng)的細粒度的內(nèi)存數(shù)據(jù)，RDD的Lineage記錄粗粒度的特定數(shù)據(jù)變換操作，例如，filter，map，join等操作.當RDD中部分分區(qū)的數(shù)據(jù)丟失時，系統(tǒng)可以通過Lineage獲取足夠的信息來重新運算和恢復丟失的數(shù)據(jù)分區(qū).同時，Spark將整個操作的并行過程按照不同節(jié)點之間是否交換數(shù)據(jù)（shuffle）劃分成不同的Stage，當系統(tǒng)發(fā)生故障時，會自動回溯到最后一個執(zhí)行成功的Stage，重新執(zhí)行該Stage之后的所有操作.通過這種方式，以較小的性能代價保證了數(shù)據(jù)的魯棒性，大大提高了系統(tǒng)容錯的性能.

6 分布式容錯＠CLAIMS

隨著大數(shù)據(jù)時代到來，海量數(shù)據(jù)的多樣性、實時性在給信息科技帶來更多便利與機遇的同時也給數(shù)據(jù)分析研究領(lǐng)域帶來前所未有的挑戰(zhàn).當今單臺服務(wù)器節(jié)點的性能可以達到非常高的標準，不論是處理器的個數(shù)還是內(nèi)存容量的大小都已經(jīng)達到了前所未有的高度，如果我們依然按照傳統(tǒng)的思維繼續(xù)發(fā)展單機上的內(nèi)存數(shù)據(jù)庫，其性能必將受到極大的制約.因此，將內(nèi)存數(shù)據(jù)庫向分布式方向發(fā)展顯得尤為重要.

當前，還沒有較為成熟的分布式內(nèi)存數(shù)據(jù)庫系統(tǒng)以及基于這樣的系統(tǒng)的一整套容錯系統(tǒng)和機制.在這方面，華東師范大學數(shù)據(jù)科學與工程學院已經(jīng)開展了近兩年時間的研究，致力于開發(fā)集群感知的基于內(nèi)存的分布式數(shù)據(jù)庫系統(tǒng)（Cluster－Aware In－Memory System，CLAIMS），并且已經(jīng)取得了不錯的成果（http：／／github.com／wangli1426／Claims）.該系統(tǒng)設(shè)計了針對內(nèi)存數(shù)據(jù)的分布式容錯系統(tǒng)，結(jié)合hdfs的優(yōu)勢最大地降低了容錯恢復的成本.在數(shù)據(jù)的存儲端，主要是用基于日志的恢復技術(shù)，利用hdfs自身多備份的特性有效地提高存儲系統(tǒng)的穩(wěn)定性.同時，在并行內(nèi)存計算的過程中加入監(jiān)視線程并記錄檢查點，通過基于檢查點的回滾機制最大限度的提高容錯的效率，提升總體性能.

7 小 結(jié)

本文綜述大規(guī)模高性能集群計算系統(tǒng)的容錯技術(shù).這些技術(shù)可以分為2類：保護集群管理的硬件和軟件基礎(chǔ)設(shè)施，保護計算節(jié)點確保應(yīng)用程序長期穩(wěn)定運行.

集群管理硬件和軟件容錯通常利用冗余，由數(shù)量相對較少的部件進行復制.當一個組件發(fā)生故障時，冗余組件接管故障部分的責任.冗余可以因此通過比較每個副本產(chǎn)生的產(chǎn)出和尋找差異可用于故障檢測.

系統(tǒng)集群發(fā)生故障之后，使用檢查點和回滾恢復技術(shù)處理故障.在應(yīng)用程序中每個組件定期記錄其狀態(tài)形式存儲檢查點文件.在進行錯誤恢復的時候，應(yīng)用程序從最新的一組檢查點進行恢復.目前已有多種協(xié)議確保系統(tǒng)使用最高效的方式恢復到正常狀態(tài).

容錯性的解決方案可以通過各種形式來實現(xiàn).這包括軟件庫，特殊的編程語言，編譯器或預處理器修改，操作系統(tǒng)的擴展和系統(tǒng)中間件的實現(xiàn).每種方法都在高效性和易用性方面有自己的優(yōu)勢.

隨著分布式計算的擴展性持續(xù)的增長，系統(tǒng)的可靠性變得至關(guān)重要，系統(tǒng)故障的預測和糾錯機制在提高系統(tǒng)穩(wěn)定性方面扮演著極其重要的角色.分布式計算變得更加的靈活和復雜.目前為了在分布式系統(tǒng)中及時發(fā)現(xiàn)故障，恢復故障，已經(jīng)有各種各樣的技術(shù)被提出.一旦有故障被發(fā)現(xiàn)，系統(tǒng)會自動找到故障的根源.

本篇綜述通過客觀的方式來描述整個分布式計算的容錯領(lǐng)域，但是關(guān)于這方面的研究還有很多工作需要完善.

［1］ CHRISTIAN F.Understanding fault－tolerant distributed systems［J］.Communications of the ACM，1991，34（2）：58－78.

［2］ BARTLETT J，BARTLETT W，CARR R，et al.Fault tolerance in tandem computer systems［J］.Technical Report 90.5，1990.

［3］ SISTLA A P，WELCH J L.Efficient distributed recovery using message logging［C］／／Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing，1989：223－238.

［4］ TIAN D，WU K，LI X.A Novel Adaptive Failure Detector for Distributed Systems.In Proceedings of the 2008 International Conference on Networking Architecture and Storage（2008）ISBN：978－0－7695－3187－8.

［5］ KOLA G，KOSAR T，LIVNY M.Faults in large distributed systems and what we can do about them （2005）.

［6］ AFFAN M，ANSARI M A.Distributed fault management for computational grids［C］／／Fifth International Conference on Grid and Cooperative Computing，2006：363－368.

［7］ JALOTR P.Fault Tolerance in Distributed Systems［M］.New Jersey：Prentice Hall，1994.

［8］ HWANG S，KESSELMAN C.A flexible framework for fault tolerance in the grid［J］.Journal of Grid Computing，2003，1（3）：251－272.

［9］ WIESMANN M，PEDONE F，SCHIPER A，et al.Understanding replication in databases and distributed systems［C］／／20th IEEE International Conference on Distributed Computing Systems，2000：464－474.

［10］ SHUKRI A，NOOR M，DERIS M M.Extended Heartbeat Mechanism for Fault Detection Serrice Methodology［C］／／Grid and Distributed Computing，2009，63：88－95.

［11］ HERLIHY M，WING J.Linearizability：a correctness condition for concurrent objects［J］.ACM Transactions.on Programming.Languages and Systems，1990，12（3）：463－492.

［12］ SHYE A，BLOMSTEDT J，MOSELEY T，et al.PLR：A software approach to transient fault tolerance for multicore architectures［C］／／IEEE Transactions on Dependable and Secure Computing，2009，6（2）：135－148.

［13］ WALTERS J，CHANDHARY T.Replication－based fault tolerance for MPI applications，Ieee Transactions On Parallel and Distributed Systems，2009，20（7）：997－1010.

［14］ GORENDER S，RAYNAL M.An adaptive programming model for fault－tolerant distributed computing［C］／／IEEET Transactions on Dependable and Secure Computing，2007，4（1）：18－31.

［15］ OSRAEL J，F(xiàn)ROIHOFER L，GOESCHKA K M，et al.A system architecture for enhanced availability of tightly coupled distributed systems［C］／／Proceedings.of 1st International.Conference.on Availability，Reliability and Security，2006.

［16］ XIONG N，CAO M，HE J.et al.A survey on fault－tolerance in distributed network systems［C］／／International Conference on Computational Science and Engineering，2009：1065－1070.

［17］ TIAN D，WU K，LI X.A novel adaptive failure detector for distributed systems［C］／／Proceedings of the 2008International Conference on Networking，Architecture，and Storage.2008：215－221.

［18］ 懷特T著Hadoop權(quán)威指南.周敏奇，王曉玲，金澈清，等譯，周傲英 審校.2版.北京：清華出版社，2011.

［19］ 宮學慶，金澈清，王曉玲，等.數(shù)據(jù)密集型科學與工程：需求和挑戰(zhàn)［J］.計算機學報，2012，35（8）：1563－1578.