本文關(guān)鍵詞：分布式圖計(jì)算系統(tǒng)的容錯(cuò)機(jī)制研究

  更多相關(guān)文章： 圖計(jì)算 容錯(cuò) 恢復(fù) 副本

【摘要】：現(xiàn)實(shí)世界中許多計(jì)算都涉及到大圖,例如社交網(wǎng)絡(luò)中朋友圈的分析工作。為了高效地分析圖結(jié)構(gòu)這類數(shù)據(jù),谷歌公司提出了“像頂點(diǎn)一樣思考”的圖計(jì)算。圖計(jì)算,憑借其強(qiáng)大的表達(dá)能力和高效的執(zhí)行效率,逐漸被廣泛用在網(wǎng)頁(yè)搜索、自然語(yǔ)言處理、推薦系統(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í)出現(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ù),它需要很長(zhǎng)的恢復(fù)時(shí)間。采用該機(jī)制的系統(tǒng),在平時(shí)執(zhí)行過程中,需要定期地將當(dāng)前計(jì)算的狀態(tài)記錄到分布式文件系統(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ì)算,這些副本擁有原頂點(diǎn)的許多的狀態(tài),可以很方便地被用來為系統(tǒng)提供容錯(cuò)支持�；谝陨嫌^察,本文提出了一個(gè)新的基于副本的容錯(cuò)機(jī)制Imitator。Imitator可以在引入很小執(zhí)行開銷的情況提供容錯(cuò)支持,同時(shí)它的恢復(fù)速度比較快。這是因?yàn)镮mitator采用了如下設(shè)計(jì):?Imitator盡可能地復(fù)用原有機(jī)制來降低執(zhí)行開銷,Imitator利用原有副本來備份頂點(diǎn)狀態(tài),同時(shí)它通過擴(kuò)展已有同步機(jī)制來保證副本頂點(diǎn)與原頂點(diǎn)的狀態(tài)是一致的;?Imitator利用整個(gè)集群的硬件資源進(jìn)行并行恢復(fù),Imitator通過選擇副本位置,在恢復(fù)過程中,它盡可能地將恢復(fù)工作均分到各個(gè)機(jī)器上,充分利用整個(gè)集群的硬件資源進(jìn)行恢復(fù)。測(cè)試表明,Imitator可以在引入很小執(zhí)行開銷的情況下(對(duì)于所有測(cè)試算法都小于5%)提供容錯(cuò)支持,同時(shí)它的恢復(fù)速度比較快,比基于分布式快照的容錯(cuò)機(jī)制快3.55～17.67倍。
【關(guān)鍵詞】：圖計(jì)算 容錯(cuò) 恢復(fù) 副本
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP302.8
【目錄】：

• 摘要3-5
• abstract5-14
• 第一章 緒論14-20
• 1.1 研究背景14-15
• 1.2 研究目標(biāo)15-16
• 1.3 本文工作16-17
• 1.4 全文結(jié)構(gòu)17-20
• 第二章 背景介紹與相關(guān)研究工作20-32
• 2.1 圖計(jì)算20-24
• 2.1.1 系統(tǒng)架構(gòu)20-21
• 2.1.2 計(jì)算模型21-22
• 2.1.3 數(shù)據(jù)模型22
• 2.1.4 以頂點(diǎn)為中心的計(jì)算22-23
• 2.1.5 副本模型23-24
• 2.2 相關(guān)系統(tǒng)及其容錯(cuò)技術(shù)24-28
• 2.2.1 Map Reduce及其容錯(cuò)技術(shù)24-25
• 2.2.2 Spark及其容錯(cuò)技術(shù)25-27
• 2.2.3 數(shù)據(jù)庫(kù)的容錯(cuò)技術(shù)27-28
• 2.2.4 基于副本的容錯(cuò)技術(shù)28
• 2.3 圖計(jì)算現(xiàn)有的容錯(cuò)技術(shù)28-31
• 2.3.1 快照記錄29-30
• 2.3.2 故障恢復(fù)30-31
• 2.4 小結(jié)31-32
• 第三章 圖計(jì)算容錯(cuò)技術(shù)的問題分析32-40
• 3.1 Imitator-CKPT32
• 3.2 基于分布式快照容錯(cuò)機(jī)制所存在的問題32-35
• 3.2.1 執(zhí)行開銷32-34
• 3.2.2 故障恢復(fù)34-35
• 3.3 利用副本容錯(cuò)的機(jī)遇35-38
• 3.3.1 低執(zhí)行開銷36-37
• 3.3.2 快速恢復(fù)37-38
• 3.4 小結(jié)38-40
• 第四章 基于副本容錯(cuò)機(jī)制的設(shè)計(jì)40-54
• 4.1 利用副本容錯(cuò)的整體設(shè)計(jì)40-43
• 4.1.1 正常工作流程40-42
• 4.1.2 故障恢復(fù)流程42-43
• 4.2 副本管理43-46
• 4.2.1 容錯(cuò)副本43-44
• 4.2.2 鏡像副本44-45
• 4.2.3 自私頂點(diǎn)的優(yōu)化45-46
• 4.3 利用副本容錯(cuò)的恢復(fù)46-52
• 4.3.1 重生46-50
• 4.3.2 遷移50-52
• 4.4 更多故障模型52-53
• 4.4.1 多機(jī)故障52
• 4.4.2 其他故障52-53
• 4.5 小結(jié)53-54
• 第五章 基于副本容錯(cuò)機(jī)制的實(shí)現(xiàn)54-62
• 5.1 系統(tǒng)組織架構(gòu)54-55
• 5.2 故障檢測(cè)55-57
• 5.2.1 故障發(fā)現(xiàn)55-56
• 5.2.2 柵欄實(shí)現(xiàn)56-57
• 5.3 并行恢復(fù)57-58
• 5.4 Imitator基準(zhǔn)系統(tǒng)58-60
• 5.5 小結(jié)60-62
• 第六章 實(shí)驗(yàn)與評(píng)測(cè)62-72
• 6.1 測(cè)試環(huán)境62-63
• 6.2 算法簡(jiǎn)介63-64
• 6.3 執(zhí)行開銷64-65
• 6.4 執(zhí)行開銷分析65
• 6.5 恢復(fù)情況65-66
• 6.6 恢復(fù)的可伸縮性66-67
• 6.7 劃分算法的影響67-68
• 6.8 多機(jī)故障68-69
• 6.9 內(nèi)存使用情況69-70
• 6.10案例分析70-71
• 6.11小結(jié)71-72
• 第七章 總結(jié)與展望72-74
• 7.1 工作總結(jié)72
• 7.2 工作展望72-74
• 參考文獻(xiàn)74-82
• 致謝82-84
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄84-86

【共引文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 張德軍;何發(fā)智;;基于建模歷史一致性的協(xié)同CAD并發(fā)控制方法[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2015年05期

2 羅軍;王宏;李文生;;基于向量時(shí)鐘模型的NoSQL最終一致性的研究[J];計(jì)算機(jī)工程與應(yīng)用;2013年23期

3 張晶;潘有順;;嵌入式系統(tǒng)同步進(jìn)程的競(jìng)態(tài)條件分析與推理學(xué)習(xí)方法[J];計(jì)算機(jī)科學(xué);2014年02期

4 劉恒;李美安;蘇萌;;基于重復(fù)數(shù)的最短循環(huán)請(qǐng)求集生成算法[J];計(jì)算機(jī)應(yīng)用;2014年05期

5 張展;左德承;黃友富;何輝;;一種基于準(zhǔn)同步檢查點(diǎn)的虛擬機(jī)卷回恢復(fù)算法[J];計(jì)算機(jī)科學(xué);2014年05期

6 林菲;孫勇;丁宏;任一支;;自穩(wěn)定的分布式事務(wù)內(nèi)存模型及算法[J];計(jì)算機(jī)研究與發(fā)展;2014年09期

7 周歡;樊秋實(shí);胡華梁;;OceanBase一致性與可用性分析[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年05期

8 劉雨辰;王佳;陳云霽;焦帥;;計(jì)算機(jī)系統(tǒng)模擬器研究綜述[J];計(jì)算機(jī)研究與發(fā)展;2015年01期

9 禹振;蘇小紅;王甜甜;馬培軍;;虛擬時(shí)間及其在數(shù)據(jù)競(jìng)爭(zhēng)檢測(cè)中的應(yīng)用[J];哈爾濱工業(yè)大學(xué)學(xué)報(bào);2015年01期

10 曾珊;文杰;;分布式系統(tǒng)一致性研究與案例分析[J];計(jì)算機(jī)與數(shù)字工程;2015年07期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前1條

1 張宇輝;褚慶昕;李迪;;基于時(shí)間誤差的網(wǎng)絡(luò)控制系統(tǒng)的穩(wěn)定性分析[A];2015年第五屆全國(guó)地方機(jī)械工程學(xué)會(huì)學(xué)術(shù)年會(huì)暨中國(guó)制造2025發(fā)展論壇論文集[C];2015年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前7條

1 朱素霞;面向多核處理器確定性重演的內(nèi)存競(jìng)爭(zhēng)記錄機(jī)制研究[D];哈爾濱工業(yè)大學(xué);2013年

2 毛華堅(jiān);云環(huán)境中的移動(dòng)文件存儲(chǔ)和時(shí)空數(shù)據(jù)分析關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

3 劉光輝;高效處理器容錯(cuò)技術(shù)研究與實(shí)現(xiàn)[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

4 楊哲a\;Java語(yǔ)言的程序漏洞檢測(cè)與診斷技術(shù)[D];復(fù)旦大學(xué);2012年

5 王濤;任務(wù)關(guān)鍵系統(tǒng)的軟件行為建模與檢測(cè)技術(shù)研究[D];燕山大學(xué);2014年

6 陳艷文;分布式系統(tǒng)的時(shí)間化通信行為模型[D];華東師范大學(xué);2014年

7 張揚(yáng);基于操作語(yǔ)義的弱內(nèi)存模型描述及程序邏輯研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 顧飛;基于SPARC架構(gòu)面向確定性重演的多核訪存競(jìng)爭(zhēng)記錄方法的研究[D];哈爾濱工業(yè)大學(xué);2013年

2 王勇;動(dòng)態(tài)可重構(gòu)的DSM語(yǔ)義研究[D];哈爾濱工業(yè)大學(xué);2012年

3 王文苑;分布式緩存可用性相關(guān)問題研究[D];華中科技大學(xué);2013年

4 孫建良;分布式存儲(chǔ)系統(tǒng)可用性與一致性研究[D];華中科技大學(xué);2013年

5 曹粟;基于非即停調(diào)試模式的嵌入式應(yīng)用級(jí)調(diào)試系統(tǒng)[D];華中科技大學(xué);2013年

6 林嵐;基于銀行家算法的分布式互斥請(qǐng)求集生成算法研究[D];內(nèi)蒙古農(nóng)業(yè)大學(xué);2012年

7 陳志黨;對(duì)分布式互斥請(qǐng)求集生成算法的進(jìn)一步探索[D];內(nèi)蒙古農(nóng)業(yè)大學(xué);2012年

8 林浩泓;云平臺(tái)下可擴(kuò)展分布式協(xié)調(diào)服務(wù)研究[D];華中科技大學(xué);2013年

9 王君君;網(wǎng)絡(luò)文件的分布式存儲(chǔ)設(shè)計(jì)與實(shí)現(xiàn)[D];山東大學(xué);2014年

10 王丁賢;一個(gè)大規(guī)模數(shù)據(jù)下的語(yǔ)義實(shí)體挖掘與語(yǔ)義實(shí)體關(guān)系歸并的新框架[D];華東師范大學(xué);2014年

，

本文編號(hào)：675704