[發明專利]一種基于網絡編碼的分布式存儲方法及其裝置

有效

• 申請號: 201310219794.6
• 申請日: 2013-06-04
• 公開（公告）號: CN103336785A
• 公開（公告）日: 2013-10-02
• 發明（設計）人: 馮丹;李白;施展;柳青;焦田豐
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 方放

1.一種基于網絡編碼的分布式存儲方法，適用于分布式存儲系統，包括數據編碼步驟、數據解碼步驟和數據修復步驟，分布式存儲系統由一個名字節點NS和P個存儲節點{DS₁，DS₂，DS₃...DS_p}構成，P≥3，其中用于存儲文件分塊的存儲節點稱為數據節點，為n個，3≤n≤p；其特征在于：

(1)數據編碼步驟，包括下述子步驟：

(1.1)數據分塊：

將原始文件D分割為c塊等大小的原始數據塊D_g，g＝0，1...c-1，對于不足一塊原始數據塊大小的剩余原始數據D_B，先記下D_B的大小L_B，再將其使用零填充補足為原始數據塊大小，作為原始數據塊D_c；

c＝k×(d+1+i-k)-(i+1)×i/2，其中，k為恢復出原文件所需最少數據節點數目，2≤k＜n；d為修復一個損壞節點時可用數據節點的數目，k≤d＜n；i為編碼冗余參數，0≤i≤k-1；

(1.2)冗余編碼：

將c個原始數據塊D_a與編碼矩陣M_e進行有限域2^q內的運算，編碼為r個編碼數據塊C_b，q＝4、8、16、32或64；b＝0，2，...r-1；r＝(d+1+i-k)×n；

Cb=Σg=0c-1ab,gDg;]]>

其中，編碼矩陣M_e中的矩陣元素a_b，g為屬于有限域2^q的整數，0≤a_b，g≤2^q-1，編碼矩陣M_e為一個r行c列的范德蒙矩陣；每個C_b都是c個原始數據塊(D_g)_{g＝0，1...c-1}的線性組合，線性組合系數對應為編碼矩陣M_e第b行的行向量V_b，即每個C_b對應編碼矩陣M_e第b行的行向量V_b；

(1.3)生成元數據文件D_meta：

將編碼矩陣M_e以及參數n、k、d、i、q和L_B保存在元數據文件D_meta中；

(1.4)數據存儲：

將r個編碼數據塊C_b存放在n個數據節點d_f上，f＝0，1，...n-1，每個數據節點存儲α＝d+1+i-k個編碼數據塊，并存儲一份D_meta的副本；數據節點d_f存儲的數據塊為C_t，t＝f×α，f×α+1，...(f+1)α-1；

(2)數據解碼步驟，包括下述子步驟：

(2.1)獲取文件元數據信息：

下載原始文件D的元數據文件D_meta，得到編碼矩陣M_e以及參數n、k、d、i、q和L_B；

(2.2)下載可用數據塊：

判斷n個數據節點中可用數據節點數是否小于k個，是則數據讀取失敗，退出；否則任意選擇k個可用數據節點，k個數據節點中包含r_k＝k×α＝k×(d+1+i-k)個編碼數據塊，共對應編碼矩陣M_e中r_k個行向量：從編碼矩陣M_e這r_k個行向量中選擇c個行向量，要求這c個行向量組成的方陣M_e1可逆，然后下載這c個行向量所對應的c個編碼數據塊：C_b1，C_b2...C_bc；

(2.3)冗余解碼：

對所述方陣M_e1矩陣求逆，得到其逆矩陣M_e1^-1，逆矩陣M_e1^-1中元素記為b_gj，其中行數g＝0，1，...c-1，列數j＝0，1，...c-1；將逆矩陣M_e1^-1與下載的c個編碼數據塊做有限域2^q內的運算，得到c個原始數據塊D_g，

Dg=Σj=0c-1bgjCbj,]]>其中g＝0，1...c-1；

D_g為c個編碼數據塊C_b0，C_b1...C_b(c-1)的線性組合，線性組合的系數為逆矩陣M_e1^-1對應的行向量V_di；

(2.4)恢復數據：

將冗余解碼后得到的c個原始數據塊D_g按其下標的順序D₀，D₁...D_c-1依次寫入到恢復文件D0中，最后一塊原始數據塊D_c-1只寫其前L_B個字節到恢復文件D0中，形成恢復文件D0；

(3)數據修復步驟，當一個數據節點d_v損壞時，v為0、1、...或n-1，其存儲的編碼數據塊的修復包括下述子步驟：

(3.1)獲取文件元數據信息：

下載原始文件D的元數據文件D_meta，得到編碼矩陣M_e以及參數n、k、d、i、q和L_B；

設置下載數據塊數目變量γ的初值：

γ＝(2×c×d)/((2×k-i-1)×i+2×k×(d-k+1))；

(3.2)計算數據塊修復信息，包括下述過程：

(3.2.1)置循環次數變量N1＝0，判斷n個數據節點中可用數據節點數是否小于d個，是則數據修復失敗，退出；否則進行過程(3.2.2)；

(3.2.2)從d個可用數據節點中隨機選擇γ個編碼數據塊，將它們對應的編碼矩陣M_e的γ個行向量V_h組合為γ行c列矩陣Vs，h＝1，2...γ；置N1＝N1+1；

(3.2.3)生成一個(d+1+i-k)行γ列的修復矩陣M_r＝[m_p，h]，其中每個元素m_p，h從有限域2^q內隨機取值，p＝1，2，...(d+1+i-k)，h＝1，2，...γ；

(3.2.4)建立r行c列的新編碼矩陣M_e’，M_e’由原有行向量和新行向量V′_p構成，原有行向量為可用數據節點所包括的編碼數據塊對應的編碼矩陣M_e中的行向量，按其在M_e中原有位置存在于M_e’中，做有限域2^q內的矩陣M_r與矩陣Vs乘法運算，得到新行向量V′_z：

Vp′=Σh=1γmp,hVh,]]>

用新行向量V′_p代替編碼矩陣M_e中損壞的數據節點d_v所存儲的α個編碼數據塊對應的行向量V_z，其中z＝v×α，v×α+1，...(v+1)×α-1；

(3.2.5)檢查所述新編碼矩陣M_e’是否滿足MDS性質，是則進行子步驟(3.3)，否則進行過程(3.2.6)；

(3.2.6)判斷是否N1≤L，是則轉過程(3.2.2)；否則置N1＝0，置γ＝γ+1，然后轉過程(3.2.2)，最大循環次數L＝1000～3000；

(3.3)更新元數據文件：

將元數據文件D_meta中的編碼矩陣M_e替換為新編碼矩陣M_e’，形成更新后的元數據文件D_meta’，將其拷貝到各個數據節點；

(3.4)修復數據塊：

下載(3.2.2)中所隨機選擇的γ個編碼數據塊(C_e1，C_e2，...C_eγ)，做有限域2^q內矩陣M_r與γ個編碼數據塊(C_e1，C_e2，...C_eγ)的運算，得到修復的數據塊C_p’：

Cp′=Σh=1γmp,hCeh;]]>

C_p’為γ個編碼數據塊(C_e1，C_e2，...C_eγ)的線性組合，線性組合的系數為修復矩陣M_r對應的行向量V_r；

(3.5)存儲數據塊：

將修復的數據塊C_p’存儲到一個新的可用數據節點上。

2.一種基于網絡編碼的分布式存儲裝置，適用于分布式存儲系統，包括數據編碼模塊、數據解碼模塊和數據修復模塊。分布式存儲系統由一個名字節點NS和P個存儲節點{DS₁，DS₂，DS₃...DS_p}構成，P≥3，其中用于存儲文件分塊的存儲節點稱為數據節點，為n個，3≤n≤p；其特征在于：

(1)數據編碼模塊，包括下述子模塊：

(1.1)數據分塊子模塊：

將原始文件D分割為c塊等大小的原始數據塊D_g，g＝0，1...c-1，對于不足一塊原始數據塊大小的剩余原始數據D_B，先記下D_B的大小L_B，再將其使用零填充補足為原始數據塊大小，作為原始數據塊D_c；

c＝k×(d+1+i-k)-(i+1)×i/2，其中，k為恢復出原文件所需最少數據節點數目，2≤k＜n；d為修復一個損壞節點時可用數據節點的數目，k≤d＜n；i為編碼冗余參數，0≤i≤k-1；

(1.2)冗余編碼子模塊：

將c個原始數據塊D_a與編碼矩陣M_e進行有限域2^q內的運算，編碼為r個編碼數據塊C_b，q＝4、8、16、32或64；b＝0，2，...r-1；r＝(d+1+i-k)×n；

Cb=Σg=0c-1ab,gDg;]]>

其中，編碼矩陣M_e中的矩陣元素a_b，g為屬于有限域2^q的整數，0≤a_b，g≤2^q-1，編碼矩陣M_e為一個r行c列的范德蒙矩陣；每個C_b都是c個原始數據塊(D_g)_{g＝0，1...c-1}的線性組合，線性組合系數對應為編碼矩陣M_e第b行的行向量V_b，即每個C_b對應編碼矩陣M_e第b行的行向量V_b；

(1.3)生成元數據文件D_meta子模塊：

將編碼矩陣M_e以及參數n、k、d、i、q和L_B保存在元數據文件D_meta中；

(1.4)數據存儲子模塊：

將r個編碼數據塊C_b存放在n個數據節點d_f上，f＝0，1，...n-1，每個數據節點存儲α＝d+1+i-k個編碼數據塊，并存儲一份D_meta的副本；數據節點d_f存儲的數據塊為C_t，t＝f×α，f×α+1，...(f+1)α-1；

(2)數據解碼模塊，包括下述子模塊：

(2.1)獲取文件元數據信息子模塊：

下載原始文件D的元數據文件D_meta，得到編碼矩陣M_e以及參數n、k、d、i、q和L_B；

(2.2)下載可用數據塊子模塊：

判斷n個數據節點中可用數據節點數是否小于k個，是則數據讀取失敗，退出；否則任意選擇k個可用數據節點，k個數據節點中包含r_k＝k×α＝k×(d+1+i-k)個編碼數據塊，共對應編碼矩陣M_e中r_k個行向量：從編碼矩陣M_e這r_k個行向量中選擇c個行向量，要求這c個行向量組成的方陣M_e1可逆，然后下載這c個行向量所對應的c個編碼數據塊：C_b1，C_b2...C_bc；

(2.3)冗余解碼子模塊：

對所述方陣M_e1矩陣求逆，得到其逆矩陣M_e1^-1，逆矩陣M_e1^-1中元素記為b_gj，其中行數g＝0，1，...c-1，列數j＝0，1，...c-1；將逆矩陣M_e1^-1與下載的c個編碼數據塊做有限域2^q內的乘法運算，得到c個原始數據塊D_g，

Dg=Σj=0c-1bgjCbj,]]>其中g＝0，1...c-1；

D_g為c個編碼數據塊C_b0，C_b1...C_b(c-1)的線性組合，線性組合的系數為逆矩陣M_e1^-1對應的行向量V_di；

(2.4)恢復數據子模塊：

將冗余解碼后得到的c個原始數據塊D_g按其下標的順序d₀，D₁...D_c-1依次寫入到恢復文件D0中，最后一塊原始數據塊D_c-1只寫其前L_B個字節到恢復文件D0中，形成恢復文件D0；

(3)數據修復模塊，當一個數據節點d_v損壞時，v為0、1、...或n-1，其存儲的編碼數據塊的修復包括下述子模塊：

(3.1)獲取文件元數據信息子模塊：

下載原始文件D的元數據文件D_meta，得到編碼矩陣M_e以及參數n、k、d、i、q和L_B；

設置下載數據塊數目變量γ的初值：

γ＝(2×c×d)/((2×k-i-1)×i+2×k×(d-k+1))；

(3.2)計算數據塊修復信息子模塊，包括下述單元：

單元(3.2.1)，置循環次數變量N1＝0，判斷n個數據節點中可用數據節點數是否小于d個，是則數據修復失敗，退出；否則轉單元(3.2.2)；

單元(3.2.2)，從d個可用數據節點中隨機選擇γ個編碼數據塊，將它們對應的編碼矩陣M_e的γ個行向量V_h組合為γ行c列矩陣Vs，h＝1，2...γ；置N1＝N1+1；

單元(3.2.3)，生成一個(d+1+i-k)行γ列的修復矩陣M_r＝[m_p，h]，其中每個元素m_p，h從有限域2^q內隨機取值，p＝1，2，...(d+1+i-k)，h＝1，2，...γ；

單元(3.2.4)，建立r行c列的新編碼矩陣M_e’，M_e’由原有行向量和新行向量V′_p構成，原有行向量為可用數據節點所包括的編碼數據塊對應的編碼矩陣M_e中的行向量，按其在M_e中原有位置存在于M_e’中，做有限域2^q內的矩陣M_r與矩陣Vs乘法運算，得到新行向量V′_z：

Vp′=Σh=1γmp,hVh,]]>

用新行向量V′_p代替編碼矩陣M_e中損壞的數據節點d_v所存儲的α個編碼數據塊對應的行向量V_z，其中z＝v×α，v×α+1，...(v+1)×+α-1；

單元(3.2.5)，檢查所述新編碼矩陣M_e’是否滿足MDS性質，是則轉子模塊(3.3)，否則轉單元(3.2.6)；

單元(3.2.6)，判斷是否N1≤L，是則轉單元(3.2.2)；否則置N1＝0，置γ＝γ+1，然后轉單元(3.2.2)，最大循環次數L＝1000～3000；

(3.3)更新元數據文件子模塊：

將元數據文件D_meta中的編碼矩陣M_e替換為新編碼矩陣M_e’，形成更新后的元數據文件D_meta’，將其拷貝到各個數據節點；

(3.4)修復數據塊子模塊：

下載(3.2.2)中所隨機選擇的γ個編碼數據塊(C_e1，C_e2，...C_eγ)，做有限域2^q內矩陣M_r與γ個編碼數據塊(C_e1，C_e2，...C_eγ)的運算，得到修復的數據塊C_p’：

Cp′=Σh=1γmp,hCeh;]]>

C_p’為γ個編碼數據塊(C_e1，C_e2，...C_eγ)的線性組合，線性組合的系數為修復矩陣M_r對應的行向量V_r；

(3.5)存儲數據塊子模塊：

將修復的數據塊C_vp存儲到一個新的可用數據節點上。