[發(fā)明專利]一種分布式存儲中的糾刪碼的編解碼方法

有效

• 申請?zhí)枺?/td>: 202110572519.7
• 申請日: 2021-05-25
• 公開（公告）號: CN113391946B
• 公開（公告）日: 2022-06-17
• 發(fā)明（設(shè)計）人: 宋罡;徐欣;張權(quán)
• 申請（專利權(quán)）人: 杭州電子科技大學(xué)
• 主分類號: G06F11/10
• 分類號: G06F11/10
• 代理公司: 杭州君度專利代理事務(wù)所(特殊普通合伙) 33240
• 代理人: 朱亞冠

1.一種分布式存儲中的糾刪碼的編解碼方法，包括編碼方法和解碼方法；其特征在于：該方法首先對糾刪碼進(jìn)行截短操作，將長度為n、包含k個信息位及n-k個校驗位的糾刪碼母碼(n,k)刪除t個信息位，得到截短碼(n-t,k-t)；截短碼與母碼具有相同的校驗位；

所述的編碼方法具體是：

(1)設(shè)定整體上稀疏的二進(jìn)制矩陣組成的編碼矩陣其中，I_k×k是k×k的單位矩陣，φ_(n-k)×k為(n-k)×k的校驗矩陣，對應(yīng)Ψ_n×k第i行的編碼向量為Ψ_i，i＝1,2,…,n；截短后的編碼矩陣其中，Q_k×k由I_k×k將任意兩行全部置零后得到；

(2)分布式系統(tǒng)中n個節(jié)點存儲的碼字表示為一個n×1的矩陣C，利用截短后的編碼矩陣Ψ′_n×k以及信息矩陣M得到編碼后的編碼塊矩陣C＝Ψ′_n×k×M；信息矩陣M為k×1的列向量，其中，數(shù)據(jù)塊d_j為一維數(shù)組，j＝1,2,…,k；

編碼后的編碼塊矩陣C包括數(shù)據(jù)塊矩陣C₁和校驗塊矩陣C₂，數(shù)據(jù)塊矩陣C₁為k×1的列向量，C₁＝Q_k×k×M，校驗塊矩陣C₂為(n-k)×1的列向量，C₂＝φ_(n-k)×k×M；

編碼塊矩陣C的第i行的數(shù)據(jù)c_i為第i個節(jié)點存儲的數(shù)據(jù)c_i＝Ψ′_i×M，Ψ′_i為對應(yīng)Ψ′_n×k第i行的編碼向量；

所述的解碼方法即數(shù)據(jù)重建，當(dāng)用戶需要讀取數(shù)據(jù)時，數(shù)據(jù)收集者提取數(shù)據(jù)塊矩陣C₁中的所有數(shù)據(jù)，以及從校驗塊矩陣C₂中提取兩個校驗塊，用于恢復(fù)出截短的數(shù)據(jù)塊；具體是：

(3)數(shù)據(jù)收集者將提取到的數(shù)據(jù)塊和校驗塊按矩陣形式排列成重建編碼矩陣B_k×1，其中校驗塊置于數(shù)據(jù)塊之下，重建編碼矩陣B_k×1為k×1的列向量；

(4)將Q_k×k中全部置零的兩行刪除，將提取的兩個校驗塊對應(yīng)的兩行行向量加入Q_k×k中，置于最后兩行，構(gòu)成k×k的重建矩陣R_k×k；

(5)對重建矩陣R_k×k求逆，得到逆矩陣R′_k×k；

(6)將逆矩陣R′_k×k與重建編碼矩陣B_k×1相乘，即恢復(fù)出包含截短數(shù)據(jù)塊的信息矩陣M，M＝R′_k×k×B_k×1；

(7)數(shù)據(jù)收集者將所有數(shù)據(jù)塊并發(fā)送給用戶組合成原數(shù)據(jù)，完成數(shù)據(jù)重建。

2.如權(quán)利要求1所述的一種分布式存儲中的糾刪碼的編解碼方法，其特征在于：

分布式存儲系統(tǒng)中節(jié)點間通過通信探測彼此存活狀態(tài)，解碼過程中，如發(fā)生節(jié)點失效，即該節(jié)點存儲的數(shù)據(jù)塊丟失，其他節(jié)點探測到該失效節(jié)點后，分布式存儲系統(tǒng)生成新生節(jié)點N用于代替失效節(jié)點進(jìn)行數(shù)據(jù)存儲；

新生節(jié)點N首先生成k×k的單位矩陣I_k×k，并將對應(yīng)失效節(jié)點的行向量移除，加入兩個校驗塊中的任意一個對應(yīng)的行向量，置于I_k×k的最下一行，得到修復(fù)矩陣H_k×k；驗證加入的行是否能使修復(fù)矩陣H_k×k滿秩，如果不滿秩，更換另一個校驗塊；

對修復(fù)矩陣H_k×k求逆，得到逆矩陣H′_k×k；取出H′_k×k中對應(yīng)失效節(jié)點的行向量，得到修復(fù)該失效節(jié)點所需的數(shù)據(jù)塊，發(fā)送至 新生節(jié)點N；

新生節(jié)點N將接收到的數(shù)據(jù)塊進(jìn)行異或運算，即得到丟失的數(shù)據(jù)塊，完成修復(fù)。