分布式圖計算的快速故障恢復方案

1、分布式圖計算的快速故障恢復方案技術創(chuàng)新，變革未來匯報提綱研究背景問題的定義總體架構與技術方案實驗評價總結圖計算是大數(shù)據(jù)計算的類重要計算模式大數(shù)據(jù)計算批計算流計算迭代計算交互式計算數(shù)據(jù)層社交網絡基因圖系統(tǒng)層應用層圖計算能做什么？分布式圖計算系統(tǒng)Google PregelGiraph GraphXGraphlabPregelixPowerGraphPageRank各類算法庫SimRank 最短路徑聚類Semi-clustering頻繁子圖挖掘圖數(shù)據(jù)庫關系數(shù)據(jù)庫各種類型的圖數(shù)據(jù)Web圖譜知識圖譜交通圖HDFS圖計算系統(tǒng)的運行原理圖 的 劃 分計算節(jié)點1計算節(jié)點2計算節(jié)點3圖數(shù)據(jù)庫HDFS 圖 的 存

2、 儲ZookeeperMaster節(jié)點圖數(shù)據(jù)存儲在圖數(shù)據(jù)庫、HDFS、或本地文件系統(tǒng)根據(jù)圖的劃分策略，圖的 分片被加載到不同的計算 節(jié)點計算節(jié)點負責圖分片的計 算計算是迭代式的可以是同步或異步的計算Master負責協(xié)調和任務分配Zookeeper負責控制流的共 享和同步計算節(jié)點負責計算和節(jié)點間 的數(shù)據(jù)傳輸圖計算系統(tǒng)的運行原理次迭代計算節(jié)點1計算節(jié)點2 計算節(jié)點3本 地 計 算數(shù) 據(jù) 通 信同 步計算節(jié)點112341234Compute 函數(shù)輸入：頂點值、上個迭 代收到的消息執(zhí)行：compute函數(shù)輸出：給其他頂點發(fā)送消 息，更新頂點值圖計算與容錯容錯設計的必要性故障率# of failures

3、 per unit of time1/200(hours)Exponential failure probability圖數(shù)據(jù)規(guī)模持續(xù) 增加需要更多的計算 資源增加節(jié)點故障的 數(shù)量0.80.70.60.50.40.30.20.10141664256# of compute nodesFailure probability when avg. failure time of a compute node is -200 hours現(xiàn)有解決方案及挑戰(zhàn)圖的算法經常需要數(shù)百次的迭代旦出現(xiàn)故障，就要從頭開始執(zhí)行，之前的計算都白費了直觀的故障恢復策略 定期檢查點機制每隔若干個迭代（比如10次迭代）做次檢查

4、點操作執(zhí)行故障恢復時恢復到最近的檢查點某個（或多個）節(jié)點出現(xiàn)故障，找個（或多個）節(jié)點代替現(xiàn)有解決方案及挑戰(zhàn)寫檢查點FSFS迭代 1迭代 10迭代 12讀檢查點迭代 10FS重做丟失狀態(tài)圖數(shù)據(jù)所需的消息 丟失，因此需要重新計算全部圖 數(shù)據(jù)，來重構這些消息。面臨的問題：A 需要重做全部數(shù)據(jù) B 計算資源浪費C 遞歸故障死循環(huán) 匯報提綱研究背景問題的定義總體架構與技術方案實驗評價總結例子假設每隔10個迭代，做次checkpoint圖的作業(yè)執(zhí)行到第12步，節(jié)點N1 failsSf (v):故障發(fā)生后v的狀態(tài)Sf*(v):故障恢復前v的狀態(tài)問題定義給定故障F(Nf, sf), recover verte

5、x states from Sf to Sf*問題定義BAGHJcFED !#SfSf*A-F: 10; G-J: 12A-J: 12匯報提綱研究背景問題的定義總體架構與技術方案實驗評價總結什么是正確的故障恢復寫檢查點HDFSHDFS迭代10 日志 本地消息日志 本地消息日志 本地消息HDFS迭代 1迭代 2迭代 3迭代 10迭代 12迭代 11日志 本地消息日志 本地消息檢查點日志（框架）故障恢復的正確性理論如何做到快速的故障恢復無需計算所有圖數(shù)據(jù)。故障節(jié)點中的圖數(shù)據(jù)需要Redo健康節(jié)點 僅僅負責重新發(fā)送消息（注意消息維護在 每個節(jié)點的本地磁盤）充分利用計算資源。主要思想 故障恢復的并行化計

6、算故障節(jié)點中的圖數(shù)據(jù)分配到其他健康的節(jié)點健康節(jié)點 發(fā)送消息計算故障的并行化恢復機制計算節(jié)點1計算節(jié)點2計算節(jié)點3計算節(jié)點2計算節(jié)點3新計算節(jié)點1 新計算節(jié)點1計算節(jié)點2計算節(jié)點312將所有丟失狀態(tài) 的圖節(jié)點均勻分 配到計算節(jié)點進 行計算，雖然CPU時間短但是通信代價高。按照圖結構設計 啟發(fā)式的分配策 略，兼顧負載均 衡和通信代價。平均分配根據(jù)CostModel分配壓縮與Lazydecompression技術寫檢查點HDFSHDFS迭代10 日志 本地消息日志 本地消息日志 本地消息HDFS迭代 1迭代 2迭代 3迭代 10迭代 12迭代 11日志 本地消息日志 本地消息寫Logs時通過壓縮技

7、術減小1/0代價計算節(jié)點讀取壓縮后 的log日志，并直接 發(fā)送到接收端，然后 再在接收端進行解壓，減小通信代價匯報提綱研究背景問題的定義總體架構與技術方案實驗評價總結實驗設置在Giraph上集成了我們提出的故障恢復框架；實驗環(huán)境 在42個節(jié)點構成的集群上部署了Giraph,每個計算節(jié) 點只允許啟動個Task,使用內存限制為4G。測試數(shù)據(jù)與算法 k-means (k=100) semi-clustering PageRank寫LOG日志代價PageRankK-meansSemi-clustering故障恢復速度測試PageRank故障恢復速度測試故障恢復速度測試Semi-clustering通信

8、代價測試PageRank通信代價測試Semi-clustering并行恢復的彈性計算總結圖計算系統(tǒng)的運行原理探討了圖計算系統(tǒng)的節(jié)點故障的必然性故障恢復的正確性機制檢查點日志優(yōu)化數(shù)據(jù)壓縮技術故障的并行化恢復機制實驗驗證參考論文Yanyan Shen, Gang Chen, H.V. Jagadish, Wei Lu, Beng Chin Ooi, Bogdan Marius Tudor, Fast Failure Recovery in Distributed Graph Processing Systems, VLDB 2015Wei Lu, Yanyan Shen,Tongtong Wang, Meih