[發(fā)明專利]基于部分重復碼的局部性修復編碼及節(jié)點故障修復方法

有效

• 申請?zhí)枺?/td>: 201810115623.1
• 申請日: 2018-02-06
• 公開（公告）號: CN108540520B
• 公開（公告）日: 2020-09-11
• 發(fā)明（設計）人: 王靜;王甜甜;段宗濤;王淑霞;張雪飛
• 申請（專利權）人: 長安大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L12/24;H04L1/00
• 代理公司: 西安恒泰知識產(chǎn)權代理事務所 61216
• 代理人: 李婷;周春霞

1.一種基于部分重復碼的局部性修復編碼方法，該方法基于FR碼的編碼結構,用于將原文件B存儲到節(jié)點中，其特征在于，包括以下步驟：

步驟1，將分布式存儲系統(tǒng)的節(jié)點進行分組，得到多個局部修復組；分布式存儲系統(tǒng)的節(jié)點總數(shù)為N；具體分組方法如下：

若分布式存儲系統(tǒng)的節(jié)點的總數(shù)N能夠被FR碼的編碼結構所需節(jié)點數(shù)n整除，即N＝tn，則得到t個局部修復組，每個局部修復組內的節(jié)點數(shù)為n；

若分布式存儲系統(tǒng)的節(jié)點的總數(shù)N不能夠被FR碼的編碼結構所需節(jié)點數(shù)n整除，即N＝tn+λ，則得到t個局部修復組，前t-1個局部修復組中每個局部修復組內的節(jié)點數(shù)為n，第t個局部修復組內的節(jié)點數(shù)為n+λ；

步驟2，若分布式存儲系統(tǒng)的節(jié)點的總數(shù)N能夠被FR碼的編碼結構所需節(jié)點數(shù)n整除，則將原文件B分成t個子文件，每個子文件包括j個數(shù)據(jù)塊，每個局部修復組包括一個子文件，對每個局部修復組內的子文件包括的j個數(shù)據(jù)塊采用FR碼進行編碼，得到多個編碼塊；將該多個編碼塊存儲到該局部修復組中的n個節(jié)點中；

若分布式存儲系統(tǒng)的節(jié)點的總數(shù)N不能夠被FR碼的編碼結構所需節(jié)點數(shù)n整除，則將原文件B分成t個子文件，前t-1個子文件中每個子文件包括j個數(shù)據(jù)塊，最后一個子文件包括j+ε個數(shù)據(jù)塊，1≤ε≤j-1，每個局部修復組包括一個子文件，對前t-1個局部修復組中每個局部修復組內的子文件包括的j個數(shù)據(jù)塊采用FR碼進行編碼，得到多個編碼塊，將該多個編碼塊存儲到該局部修復組中的n個節(jié)點中；對最后一個局部修復組內的子文件包括的j+ε個數(shù)據(jù)塊采用MDS碼進行編碼，得到多個編碼塊，將該多個編碼塊存儲到最后一個局部修復組內的n+λ個節(jié)點中。

2.如權利要求1所述的基于部分重復碼的局部性修復編碼方法，其特征在于，所述步驟2中的對每個局部修復組內的子文件包括的j個數(shù)據(jù)塊采用FR碼進行編碼，得到多個編碼塊；將該多個編碼塊存儲到該局部修復組中的n個節(jié)點中；具體包括以下步驟：

對j個數(shù)據(jù)塊進行RS編碼，生成i個不同的編碼塊，將生成的i個不同的編碼塊復制ρ次，得到iρ個編碼塊；當ρ＝2時，按照正則圖得到的排布矩陣，或當ρ≥3時，按照Fano平面得到的排布矩陣，將復制后的iρ個編碼塊存儲在局部修復組內的n個節(jié)點中，每個節(jié)點存儲d個編碼塊，即iρ＝nd。

3.如權利要求1所述的基于部分重復碼的局部性修復編碼方法，其特征在于，所述步驟2中的對前t-1個局部修復組中每個局部修復組內的子文件包括的j個數(shù)據(jù)塊采用FR碼進行編碼，得到多個編碼塊，將該多個編碼塊存儲到該局部修復組中的n個節(jié)點中；具體包括以下步驟：

對j個數(shù)據(jù)塊進行RS編碼，生成i個不同的編碼塊，將生成的i個不同的編碼塊復制ρ次，得到iρ個編碼塊；按照正則圖或Fano平面得到的排布矩陣，將復制后的iρ個編碼塊存儲在局部修復組內的n個節(jié)點中，每個節(jié)點存儲d個編碼塊，即iρ＝nd；

所述步驟2中的對最后一個局部修復組內的子文件包括的j+ε個數(shù)據(jù)塊采用MDS碼進行編碼，得到多個編碼塊，將該多個編碼塊存儲到最后一個局部修復組內的n+λ個節(jié)點中，具體包括以下步驟：

對j+ε個數(shù)據(jù)塊采用MDS碼編碼方式進行編碼，生成(λ+n)d個編碼塊，將這(λ+n)d個編碼塊存儲在最后一個局部修復組內的n+λ個節(jié)點中，每個節(jié)點存儲d個編碼塊。

4.一種節(jié)點故障修復方法，其特征在于，包括以下步驟：

按照權利要求1-3中任一權利要求所述的基于部分重復碼的局部性修復編碼方法將原文件B存儲到節(jié)點中；

若單個節(jié)點發(fā)生故障，則修復方法如下：

(1)若發(fā)生故障的節(jié)點中存儲的編碼塊為采用FR碼進行編碼得到的，則通過正則圖，找到與該發(fā)生故障的節(jié)點相連的多個存活節(jié)點，或者通過Fano平面找到與該發(fā)生故障的節(jié)點中編碼塊相連的多個存活節(jié)點，并從這些存活節(jié)點直接下載發(fā)生故障的節(jié)點丟失的數(shù)據(jù)，即可修復該發(fā)生故障的節(jié)點；

(2)若發(fā)生故障的節(jié)點中存儲的編碼塊為采用MDS碼進行編碼得到的，則根據(jù)MDS碼故障節(jié)點修復性質，從多個存活節(jié)點下載j+ε個不同的編碼塊，對這些編碼塊進行MDS編碼操作，即可修復該發(fā)生故障的節(jié)點；

若兩個節(jié)點同時發(fā)生故障，且兩個節(jié)點屬于同一個局部修復組，則修復方法如下：

(1)若發(fā)生故障的節(jié)點中存儲的編碼塊為采用FR碼進行編碼得到的，當復制次數(shù)ρ＝2時，根據(jù)正則圖，從存活節(jié)點下載j個不同的編碼塊，對上述編碼塊進行異或操作，即可恢復故障節(jié)點；當復制次數(shù)ρ≥3時，根據(jù)Fano平面，找到與該發(fā)生故障的節(jié)點中編碼塊相連的多個存活節(jié)點，并從這些存活節(jié)點直接下載發(fā)生故障的節(jié)點丟失的數(shù)據(jù)，即可修復該發(fā)生故障的節(jié)點；

(2)若發(fā)生故障的節(jié)點中存儲的編碼塊為采用MDS碼進行編碼得到的，根據(jù)MDS碼故障節(jié)點修復性質，從存活節(jié)點下載j+ε個不同編碼塊，對上述編碼塊進行MDS編碼操作，即可修復發(fā)生故障的節(jié)點。