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

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

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

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

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