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

在審

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

1.一種分布式圖處理系統(tǒng)中加速無檢查點故障恢復的方法，其特征在于，若所述故障涉及無拓撲突變的圖算法，則應用感知分區(qū)的備份策略；若所述故障涉及拓撲突變的圖算法，則感知分區(qū)的備份策略及增量協(xié)議協(xié)同使用。

2.如權(quán)利要求1所述的方法，其特征在于，所述感知分區(qū)的備份策略的步驟具體包括：

步驟A1：在分布式圖處理系統(tǒng)正常執(zhí)行期間，當系統(tǒng)讀入輸入數(shù)據(jù)并完成shuffle過程后，系統(tǒng)要求所有節(jié)點將子圖備份至分布式文件系統(tǒng)；

步驟A2：一旦故障發(fā)生，系統(tǒng)利用子圖的備份來恢復故障節(jié)點的丟失子圖。

3.如權(quán)利要求2所述的方法，其特征在于，所述備份操作只在迭代數(shù)為0時進行。

4.如權(quán)利要求2所述的方法，其特征在于，步驟A1具體包括：

步驟A11：獲取當前迭代數(shù)，并判斷迭代數(shù)是否為0，如果為0則表示當前迭代為初始迭代，需要盡快寫入備份，之后進入步驟A12；如果當前迭代數(shù)不為0，則系統(tǒng)不進行任何備份操作；

步驟A12：系統(tǒng)要求所有節(jié)點將子圖上傳至分布式文件系統(tǒng)，每個節(jié)點在完成上傳后會通知系統(tǒng)；

步驟A13：等待所有節(jié)點完成上傳之后，系統(tǒng)在分布式文件系統(tǒng)上創(chuàng)建一個標識文件，用以標識備份可用。

5.如權(quán)利要求2所述的方法，其特征在于，步驟A2具體包括：

步驟A21：當故障發(fā)生時，系統(tǒng)首先檢查備份的可用情況，若備份可用則進入步驟A22，否則進入步驟A23；

步驟A22：故障節(jié)點從備份中讀取丟失的子圖，正常節(jié)點等待故障節(jié)點完成子圖的讀取，隨后進入步驟A24；

步驟A23：所有節(jié)點重新載入輸入數(shù)據(jù)，并通過shuffle來恢復故障節(jié)點的丟失子圖并進行讀取，隨后進入步驟A24；

步驟A24：在子圖讀取完成后，系統(tǒng)采用與無檢查點的恢復方式相同的做法來恢復丟失子圖上的頂點的值，即在丟失子圖上的頂點應用用戶自定義的補償方法，隨后系統(tǒng)繼續(xù)執(zhí)行計算過程。

6.如權(quán)利要求1所述的方法，其特征在于，所述增量協(xié)議的運行步驟具體包括：

步驟B1：在正常執(zhí)行期間，分布式圖處理系統(tǒng)將發(fā)生的圖拓撲突變寫入到位于分布式文件系統(tǒng)的日志中；

步驟B2：一旦故障發(fā)生，在通過感知分區(qū)的備份策略恢復故障節(jié)點的丟失子圖后，系統(tǒng)利用日志中記錄的拓撲突變信息將所有節(jié)點的拓撲恢復至某個迭代，之后系統(tǒng)將執(zhí)行用戶自定義的補償方法恢復丟失子圖的頂點的值，并重新開始進行計算，直到迭代中止。

7.如權(quán)利要求6所述的方法，其特征在于，步驟B1具體包括：

步驟B11：在每個迭代S_i，系統(tǒng)會監(jiān)控每個節(jié)點是否對圖的拓撲進行了修改，如果進行了修改則進入步驟B12；

步驟B12：一旦節(jié)點在迭代S_i對圖拓撲進行了修改，節(jié)點將生成對應的拓撲突變?nèi)罩荆懭氲轿挥诜植际轿募到y(tǒng)的日志文件中；

步驟B13：在所有修改了拓撲的節(jié)點將日志信息寫入到分布式文件系統(tǒng)后，系統(tǒng)將在分布式文件系統(tǒng)上創(chuàng)建一個以S_i命名的標志文件，用以表明系統(tǒng)已完整記錄發(fā)生在迭代S_i的拓撲突變信息。