[發明專利]一種基于Pyramid碼的局部性修復編碼方法

有效

• 申請號: 201710071734.2
• 申請日: 2017-02-09
• 公開（公告）號: CN106776112B
• 公開（公告）日: 2019-08-02
• 發明（設計）人: 王靜;張崇;楊洋
• 申請（專利權）人: 長安大學
• 主分類號: G06F11/10
• 分類號: G06F11/10;H04L29/08
• 代理公司: 西安恒泰知識產權代理事務所 61216
• 代理人: 李婷

1.一種基于Pyramid碼的局部性修復編碼方法，在分布式存儲系統中，所需存儲的文件系統中的每個文件，在存儲時被切分成若干個數據塊，每個數據塊都被存儲在分布式存儲系統的不同的存儲節點上，本方法是對包含n個存儲節點的分布式存儲系統進行局部性修復編碼，其中n為≥8的自然數；

其特征在于，包括以下步驟：

若n/8＝t為整數，文件系統被切分為4t個數據塊并存儲在t個局部修復組內的存儲節點上，每個局部修復組中存儲4個數據塊和4個校驗塊，

其中，每個所述局部修復組視為一個最小編碼結構C，所述最小編碼結構C由n個存儲節點中任意每8個存儲節點構成，所述校驗塊為數據塊經過生成矩陣G線性編碼生成，G表示生成C所需的生成矩陣，

其中g₁₂、g₁₃、g₂₁、g₂₄、g₃₁、g₃₄、g₄₂和g₄₃為Pyramid碼的編碼系數，各列之間編碼系數線性獨立，

所述最小編碼結構C＝D·G，D＝[d₁₁,d₁₂,...,d_ij,...,d_tj]，d_ij為第i個局部修復組存儲的j個數據塊，i表示第i個局部修復組，i≤t，j表示局部修復組內存儲的數據塊數目，1≤j≤4且為整數；

若n/8為非整數，文件系統被切分為4t+ε個數據塊，其中前t-1個局部修復組中每個局部修復組存儲4個數據塊，第t個局部修復組存儲4+ε個數據塊，其中，ε為n/8的余數個存儲節點中包含的數據塊個數，ε≤4且為整數，對第t個局部修復組采用MDS編碼方式進行編碼后存儲文件系統。

2.一種分布式存儲系統中存儲節點故障修復方法，其特征在于，包括以下步驟：

步驟一、采用權利要求1所述的方法對包含有n個存儲節點的分布式存儲系統進行局部性修復編碼；

步驟二，若第i個局部修復組內出現存儲節點故障，未出現故障的存儲節點為存活存儲節點，第i個局部修復組內存儲4個數據塊d_i1、d_i2、d_i3和d_i4以及4個校驗塊c_i1、c_i2、c_i3和c_i4，其中d_i1、d_i2、d_i3和d_i4是按照兩行兩列依次排列的數據塊，c_i1為d_i1和d_i2經過生成矩陣G線性編碼生成，c_i2為d_i3和d_i4經過生成矩陣G線性編碼生成，c_i3為d_i1和d_i3經過生成矩陣G線性編碼生成，c_i4為d_i2和d_i4經過生成矩陣G線性編碼生成；

(1)若第i個局部修復組內出現一個存儲節點故障：

若出現故障的存儲節點存儲的是d_i1、d_i2、d_i3和d_i4中的任意一個，則通過出現故障的存儲節點同行或者同列的存活存儲節點進行修復；

若出現故障的存儲節點存儲的是c_i1、c_i2、c_i3和c_i4中的任意一個，則通過生成故障的存儲節點存儲的校驗塊時對應的存活存儲節點進行修復；

(2)若第i個局部修復組內出現兩個存儲節點故障：

若出現故障的存儲節點存儲的是d_i1、d_i2、d_i3和d_i4中的兩個或c_i1、c_i2、c_i3和c_i4中的兩個：若所述d_i1、d_i2、d_i3和d_i4中的兩個或c_i1、c_i2、c_i3和c_i4中的兩個同行或同列，則分別通過所述d_i1、d_i2、d_i3和d_i4中的兩個或c_i1、c_i2、c_i3和c_i4中的兩個所在列或行的存活存儲節點進行修復；若所述d_i1、d_i2、d_i3和d_i4中的兩個或c_i1、c_i2、c_i3和c_i4中的兩個非同行或同列，則通過所述d_i1、d_i2、d_i3和d_i4中的兩個數據塊中的一個數據塊所在列和另一數據塊所在行的三個存活存儲節點進行修復；

若出現故障的存儲節點存儲的是d_i1、d_i2、d_i3和d_i4中的一個及c_i1、c_i2、c_i3和c_i4中的一個，則通過這個數據塊所在列和這個校驗塊所在行的三個存活存儲節點進行修復，或者通過這個數據塊所在行和這個校驗塊所在列的三個存活存儲節點進行修復。

3.權利要求2所述方法，其特征在于，步驟(2)所述若局部修復組內出現兩個存儲節點故障時，采用步驟(1)所述同時進行兩個存儲節點故障修復。