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

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

【摘要】：現(xiàn)實世界中許多計算都涉及到大圖,例如社交網(wǎng)絡(luò)中朋友圈的分析工作。為了高效地分析圖結(jié)構(gòu)這類數(shù)據(jù),谷歌公司提出了“像頂點一樣思考”的圖計算。圖計算,憑借其強大的表達能力和高效的執(zhí)行效率,逐漸被廣泛用在網(wǎng)頁搜索、自然語言處理、推薦系統(tǒng)等各個領(lǐng)域。為了應(yīng)對現(xiàn)實世界中越來越復(fù)雜的算法和越來越大的數(shù)據(jù)集,現(xiàn)有的圖計算系統(tǒng)大多設(shè)計為分布式系統(tǒng)。例如,谷歌公司已經(jīng)用成百上千臺機器來運行相關(guān)數(shù)據(jù)挖掘算法。由于運行在分布式環(huán)境下,圖計算在運行過程中可能隨時出現(xiàn)宕機、斷電等異常情況,圖計算系統(tǒng)需要提供機制來容忍這些異常的發(fā)生。本文的主要貢獻如下:第一,通過實驗詳細分析了圖計算現(xiàn)有的容錯機制所存在的問題由于頂點上復(fù)雜的計算和頂點間復(fù)雜的依賴關(guān)系,現(xiàn)有的圖計算系統(tǒng)主要采用為整個系統(tǒng)記錄快照的方式進行容錯。該機制存在兩個問題:對于平時執(zhí)行,它會引入很大的執(zhí)行開銷;對于故障恢復(fù),它需要很長的恢復(fù)時間。采用該機制的系統(tǒng),在平時執(zhí)行過程中,需要定期地將當前計算的狀態(tài)記錄到分布式文件系統(tǒng)中。當有故障發(fā)生后,系統(tǒng)會從最近的快照中恢復(fù)出計算狀態(tài),然后重新開始計算。由于記錄快照和從快照中恢復(fù)計算狀態(tài)的過程涉及許多費時的網(wǎng)絡(luò)請求,基于分布式快照的容錯機制的執(zhí)行開銷比較大,恢復(fù)速度卻比較慢。由于上述兩個原因,在圖計算真實運行中,即使系統(tǒng)提供了該容錯機制,它也往往不被使用。第二,提出并實現(xiàn)了一個全新的利用頂點副本進行容錯的機制分布式圖計算系統(tǒng)會為一個頂點建立副本來服務(wù)其遠端鄰居的計算,這些副本擁有原頂點的許多的狀態(tài),可以很方便地被用來為系統(tǒng)提供容錯支持�；谝陨嫌^察,本文提出了一個新的基于副本的容錯機制Imitator。Imitator可以在引入很小執(zhí)行開銷的情況提供容錯支持,同時它的恢復(fù)速度比較快。這是因為Imitator采用了如下設(shè)計:?Imitator盡可能地復(fù)用原有機制來降低執(zhí)行開銷,Imitator利用原有副本來備份頂點狀態(tài),同時它通過擴展已有同步機制來保證副本頂點與原頂點的狀態(tài)是一致的;?Imitator利用整個集群的硬件資源進行并行恢復(fù),Imitator通過選擇副本位置,在恢復(fù)過程中,它盡可能地將恢復(fù)工作均分到各個機器上,充分利用整個集群的硬件資源進行恢復(fù)。測試表明,Imitator可以在引入很小執(zhí)行開銷的情況下(對于所有測試算法都小于5%)提供容錯支持,同時它的恢復(fù)速度比較快,比基于分布式快照的容錯機制快3.55～17.67倍。
【關(guān)鍵詞】：圖計算 容錯 恢復(fù) 副本
【學位授予單位】：上海交通大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP302.8
【目錄】：

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

【共引文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：675704