分布式圖計算系統(tǒng)的容錯機制研究.pdf

1、現(xiàn)實世界中許多計算都涉及到大圖，例如社交網(wǎng)絡中朋友圈的分析工作。為了高效地分析圖結構這類數(shù)據(jù)，谷歌公司提出了“像頂點一樣思考”的圖計算。圖計算，憑借其強大的表達能力和高效的執(zhí)行效率，逐漸被廣泛用在網(wǎng)頁搜索、自然語言處理、推薦系統(tǒng)等各個領域。為了應對現(xiàn)實世界中越來越復雜的算法和越來越大的數(shù)據(jù)集，現(xiàn)有的圖計算系統(tǒng)大多設計為分布式系統(tǒng)。例如，谷歌公司已經用成百上千臺機器來運行相關數(shù)據(jù)挖掘算法。由于運行在分布式環(huán)境下，圖計算在運行過程中可能隨時

2、出現(xiàn)宕機、斷電等異常情況，圖計算系統(tǒng)需要提供機制來容忍這些異常的發(fā)生。本文的主要貢獻如下：
　　第一，通過實驗詳細分析了圖計算現(xiàn)有的容錯機制所存在的問題
　　由于頂點上復雜的計算和頂點間復雜的依賴關系，現(xiàn)有的圖計算系統(tǒng)主要采用為整個系統(tǒng)記錄快照的方式進行容錯。該機制存在兩個問題：對于平時執(zhí)行，它會引入很大的執(zhí)行開銷；對于故障恢復，它需要很長的恢復時間。采用該機制的系統(tǒng)，在平時執(zhí)行過程中，需要定期地將當前計算的狀態(tài)記錄到分布式

3、文件系統(tǒng)中。當有故障發(fā)生后，系統(tǒng)會從最近的快照中恢復出計算狀態(tài)，然后重新開始計算。由于記錄快照和從快照中恢復計算狀態(tài)的過程涉及許多費時的網(wǎng)絡請求，基于分布式快照的容錯機制的執(zhí)行開銷比較大，恢復速度卻比較慢。由于上述兩個原因，在圖計算真實運行中，即使系統(tǒng)提供了該容錯機制，它也往往不被使用。
　　第二，提出并實現(xiàn)了一個全新的利用頂點副本進行容錯的機制
　　分布式圖計算系統(tǒng)會為一個頂點建立副本來服務其遠端鄰居的計算，這些副本擁有原

4、頂點的許多的狀態(tài)，可以很方便地被用來為系統(tǒng)提供容錯支持?；谝陨嫌^察，本文提出了一個新的基于副本的容錯機制 Imitator。Imitator可以在引入很小執(zhí)行開銷的情況提供容錯支持，同時它的恢復速度比較快。這是因為Imitator采用了如下設計：
　　1.Imitator盡可能地復用原有機制來降低執(zhí)行開銷，Imitator利用原有副本來備份頂點狀態(tài)，同時它通過擴展已有同步機制來保證副本頂點與原頂點的狀態(tài)是一致的；
　　2.