[發(fā)明專利]一種分布式圖處理系統(tǒng)中加速無檢查點故障恢復(fù)的方法

在審

• 申請?zhí)枺?/td>: 202210031284.5
• 申請日: 2022-01-12
• 公開（公告）號: CN114780507A
• 公開（公告）日: 2022-07-22
• 發(fā)明（設(shè)計）人: 徐辰;楊溢;楊振華;潘青峰;錢衛(wèi)寧;周傲英
• 申請（專利權(quán)）人: 華東師范大學(xué)
• 主分類號: G06F16/18
• 分類號: G06F16/18;G06F16/901;G06F11/14
• 代理公司: 上海德禾翰通律師事務(wù)所 31319
• 代理人: 夏思秋

本發(fā)明公開了一種分布式圖處理系統(tǒng)中加速無檢查點故障恢復(fù)的方法，包括感知分區(qū)的備份策略以及增量協(xié)議。若所述故障涉及無拓撲突變的圖算法，則應(yīng)用感知分區(qū)的備份策略；若所述故障涉及拓撲突變的圖算法，則感知分區(qū)的備份策略及增量協(xié)議協(xié)同使用。感知分區(qū)的備份策略在正常執(zhí)行期間將系統(tǒng)中各個節(jié)點的子圖進行備份，并在恢復(fù)期間直接通過備份恢復(fù)故障節(jié)點上的丟失子圖，從而減少了無檢查點的恢復(fù)方式在恢復(fù)期間引入的附加開銷。增量協(xié)議在正常期間將涉及拓撲突變的信息作為日志記錄下來，并在恢復(fù)期間利用這些日志將系統(tǒng)中所有節(jié)點的拓撲恢復(fù)至故障發(fā)生前的某個時刻，避免了無檢查點的恢復(fù)方式在處理涉及拓撲突變的故障時導(dǎo)致結(jié)果不精確的問題。

技術(shù)領(lǐng)域

本發(fā)明屬于分布式圖處理技術(shù)領(lǐng)域，涉及一種應(yīng)用于分布式圖處理系統(tǒng)中的容錯技術(shù)，在分布式圖處理系統(tǒng)中加速無檢查點故障恢復(fù)的方法。

背景技術(shù)

在處理以圖結(jié)構(gòu)表示的數(shù)據(jù)時，分布式圖處理系統(tǒng)一般都是迭代執(zhí)行的，且執(zhí)行時間長。在此過程中，系統(tǒng)中節(jié)點出現(xiàn)故障是常見的現(xiàn)象。通常，許多分布式圖處理系統(tǒng)都利用檢查點來處理故障。在正常執(zhí)行期間，系統(tǒng)周期性地寫入檢查點。一旦故障發(fā)生，系統(tǒng)讀取最新的檢查點并進行回退。然后，系統(tǒng)從檢查點開始重新計算。顯然，在沒有故障發(fā)生的情況下，這種基于檢查點的恢復(fù)方式帶來了顯著的運行時開銷。

與基于檢查點的恢復(fù)方式不同，無檢查點的恢復(fù)方式并不要求系統(tǒng)在正常執(zhí)行期間寫入任何檢查點。一旦發(fā)生故障，無檢查點的恢復(fù)方式將重新載入輸入數(shù)據(jù)，以恢復(fù)故障節(jié)點上的丟失子圖。在這之后，無檢查點的恢復(fù)方式使用一個用戶自定義的補償方法來恢復(fù)丟失子圖上的頂點的值，并繼續(xù)進行計算。特別地，這種方式并不會回滾頂點的值，并重復(fù)故障之前的計算，而是利用圖算法的特性來設(shè)置頂點的值，從而減少重復(fù)計算帶來的開銷。

圖1和圖2以計算最大值的圖算法為例來說明無檢查點的恢復(fù)方式的工作過程。這里，圖作業(yè)執(zhí)行在由N₁和N₂兩個節(jié)點組成的集群上。特別地，該作業(yè)由四個迭代組成，從迭代S0執(zhí)行到S3。如圖1所示，在執(zhí)行迭代S0前，N₁和N₂會分別從輸入數(shù)據(jù)的文件分片1和分片2中加載子圖。然而，根據(jù)分區(qū)函數(shù)，分片1的子圖上的頂點C并不屬于N₁。類似地，頂點A也不屬于N₂。因此，N₁和N₂在加載期間會相互交換頂點，即shuffle。在這之后，作業(yè)將執(zhí)行從S0到S3的計算。在計算期間，無檢查點的恢復(fù)方式實現(xiàn)了零開銷，因為它并不寫入任何檢查點。一旦N₂在迭代S₂發(fā)生故障，如圖2所示，由頂點C和D組成的子圖會丟失。為了恢復(fù)丟失的子圖，無檢查點的恢復(fù)方式將要求N₁和N₂重新從分片1和分片2中載入子圖。之后，無檢查點的恢復(fù)方式將頂點C和D的值補償為最小值，即0。這避免了將頂點D的值再次更新為3的重計算開銷。在補償之后，作業(yè)繼續(xù)進行計算，并在迭代S₅終止計算。

無檢查點的恢復(fù)方式有效地處理故障，然而這種方式在恢復(fù)時會引入顯著的恢復(fù)開銷。一旦故障發(fā)生，無檢查點的恢復(fù)方式不得不重新讀取輸入數(shù)據(jù)的文件分片并執(zhí)行分區(qū)操作。然而，分區(qū)操作需要通過網(wǎng)絡(luò)進行shuffle，這帶來了附加的開銷。以圖2為例，一旦N₂在S₂處發(fā)生故障，無檢查點的恢復(fù)方式將要求N₁和N₂載入輸入數(shù)據(jù)。之后，N₂通過shuffle恢復(fù)頂點C，即N₁在從分片1中讀取C后通過網(wǎng)絡(luò)將C發(fā)送給N₂。顯然，如果N₂能直接讀取頂點C，那么無檢查點的恢復(fù)方式將避免由shuffle帶來的附加開銷。