[發明專利]基于完全圖的對稱部分重復碼構造及故障節點修復方法

有效

• 申請號: 201910930888.1
• 申請日: 2019-09-29
• 公開（公告）號: CN110781025B
• 公開（公告）日: 2023-02-28
• 發明（設計）人: 王靜;王秘;余春雷;劉艷
• 申請（專利權）人: 長安大學
• 主分類號: G06F11/10
• 分類號: G06F11/10
• 代理公司: 西安恒泰知識產權代理事務所 61216
• 代理人: 王芳

本發明屬于計算機領域，公開了一種基于完全圖的對稱部分重復碼構造及故障節點修復方法。本方法主要是根據n階完全圖中頂點之間的對稱關系，構造對稱部分重復碼。所構造的對稱部分重復碼不但能快速高效修復單故障節點或任意兩個故障節點，而且在修復節點修復過程中節點的修復局部性較小。單故障節點和不連續的兩個節點故障有多種修復度為2的修復方案，當兩個連續節點發生故障也存在節點的修復度為2的修復方案。相比于傳統的部分重復碼，節點修復時磁盤I/O開銷相對較小，冗余編碼塊少，且該碼構造過程簡單，極易推廣，可操作性強。

技術領域

本發明屬于計算機領域，具體涉及一種基于完全圖的對稱部分重復碼構造及故障節點修復方法。

背景技術

由于信息技術的快速發展，數據量呈爆炸性增長，大數據對存儲系統提出了嚴峻的挑戰。分布式存儲系統以其高效的存儲性能成為主流存儲系統。在分布式存儲系統中，通常利用存儲冗余數據來確保數據存儲的可靠性，但需要存儲多個副本，使得系統存儲開銷過大；糾刪碼策略有效降低了存儲開銷，但是在修復故障節點時需要下載整個文件大小的數據量，導致了修復帶寬開銷過大。結合網絡編碼的思想，Dimakis等人提出了再生碼，通過傳送多個數據的線性組合從而減少了修復帶寬開銷。然而，再生碼在修復故障節點時，磁盤I/O開銷大，計算復雜度較高。部分重復碼融合了復制和再生碼技術，使得修復故障節點時只需從部分存活節點下載少量數據塊，并將下載的數據塊傳輸給新節點無需其他運算操作即可完成故障節點的修復，修復復雜度低。由于存儲系統中存儲的數據量大，存儲節點數增多，若采用Steiner系、射影幾何及可分解設計構造部分重復碼，不但碼的構造過程復雜，而且單節點出現故障時，故障節點修復方案單一且節點的修復局部性較大，修復過程中的磁盤I/O開銷較大，同時系統的容錯能力較低。

發明內容

本發明的目的在于提供一種基于完全圖的對稱部分重復碼構造及故障節點修復方法，用以解決現有技術中的部分重復碼構造方法復雜、節點修復過程中修復局部性大，容錯能力小和節點修復選擇性小等問題。

為了實現上述任務，本發明采用以下技術方案：

基于完全圖的對稱部分重復碼構造方法，包括如下步驟：

步驟1：將原始文件分成k個原始數據塊，對k個原始數據塊進行(n,k)MDS 編碼，得到n個編碼塊C₁、C₂、…、C_n，其中n≥4且n、k為正整數；

步驟2：建立正n邊形，將正n邊形的每個頂點分別和除自身之外的n-1 個頂點用線段連接，得到n階完全圖，對n階完全圖的n個頂點按順時針方向分別用1、2、…、n進行編號，所述n階完全圖中包括n個由頂點和該頂點左右兩側分別相鄰的頂點構成的三角形，所述n個三角形的頂點與n個頂點依次對應；

步驟3：令n階完全圖的1至n個頂點依次對應1至n個節點，每個節點存有三個編碼塊，所述每個節點存有的三個編碼塊的編號為當前節點對應三角形的三個頂點的編號，完成對稱部分重復碼的構造。

進一步的，步驟3中n個節點存儲的編碼塊分別為：

節點v₁存儲的編碼塊為：C_n、C₁和C₂；

節點v_i存儲的編碼塊為：C_i-1、C_i和C _i+1，其中i為正整數且i＝2，3，4，...， n-1；

節點v_n存儲的編碼塊為：C_n-1、C_n和C₁。

故障節點修復方法，按照上述的任一種基于完全圖構造的對稱部分重復碼的構造方法，，將包含n個編碼塊的原始文件存儲到分布式存儲系統的n個節點中，令每個節點存儲3個編碼塊；