[發明專利]一種修復二進制碼生成矩陣構造方法及修復方法

在審

• 申請號: 201810905992.0
• 申請日: 2018-08-09
• 公開（公告）號: CN109257050A
• 公開（公告）日: 2019-01-22
• 發明（設計）人: 侯韓旭;韓永祥;李揮;周清峰;李勇;周豐豐;范立生
• 申請（專利權）人: 東莞理工學院
• 主分類號: H03M13/15
• 分類號: H03M13/15
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙) 44248
• 代理人: 李利

本發明適用于數字處理技術改進領域，提供了一種修復二進制碼生成矩陣構造方法，所述修復二進制碼生成矩陣構造方法包括：設構造碼C₁(k，r，d，p)，其中η＝d?k+1，k≥3，r≥3是一個奇數，d＝k+(r?1)/2和τ＝(d?k+1)^k?2，構造矩陣P_k×r；其計算公式：。再生碼的產品矩陣結構仍在商環下工作，計算復雜度較低，以更大的容錯度減少修復帶寬。

技術領域

本發明屬于數字處理技術改進領域，尤其涉及一種修復二進制碼生成矩陣構造方法及修復方法。

背景技術

現代分布式存儲系統部署擦除代碼來維護數據可用性，以防止存儲節點的故障.二進制最大距離可分(MDS)陣列編碼是一種特殊的擦除碼，它可以實現最小存儲冗余和低計算復雜度的容錯.特別地，二進制數組代碼由 k+r列組成，每個列中都有L位.在k+r列中，k信息列存儲信息位r奇偶列存儲冗余位.每個列中的L位都存儲在相同的存儲節點中.我們將磁盤作為一個列或一個存儲節點，并將數組中的一個條目作為一個比特.當一個節點發生故障時，數組代碼的相應列被認為是一個擦除.如果k+r列中的任何k都可以重構所有k信息列(即：它可以容忍任何r失敗的列)，這樣的編碼稱作MDS碼. 二進制MDS陣列碼的示例包括雙容錯代碼(即r＝2)如x-code[2]，RDP碼[3] 和EVENODD碼[4]，以及三重容錯碼(即r＝3)如：STAR碼[5]，廣義RDP碼[6]，和TIP碼[7]。

當一個節點在分布式存儲系統中出現故障時，應該通過從d健康節點中下載片段來修復故障節點，其中k≤d≤k+r-1.最小化修復帶寬，定義為在修復過程中下載的比特數量，對于加快修復操作和最小化漏洞的窗口是至關重要的，特別是在分布式存儲中，網絡傳輸是瓶頸.修復問題是由Dimakis等人[8]基于信息流動圖的概念制定的.最小存儲冗余的最小修復帶寬在[8]中進行了陳述，也稱為最小存儲再生(MSR)點，是由下式表示：

雖然最小的修復帶寬是可以達到的，在一個足夠大的有限域上，但是如何構造二進制的MDS陣列碼來實現最小的修復帶寬仍然是一個挑戰。

一種傳統的方法是從任何k幸存的列中下載所有的位元來重新生成故障列中的位元.因此，用于修復故障列的比特數的總數是故障位的k倍.在二進制MDS陣列代碼中，有研究減少了單個失敗列的修復帶寬.一些方法最小化了RDP代碼[10]的磁盤讀取和d＝k+1的x-code[11]，但是它們的修復帶寬是次優的，比d＝k+1時(1)的最小值大50％.MDR碼[12]，[13]和ButterFly碼 [14]，[15]是二進制的MDS陣列編碼，達到最優修復；然而，它們只提供了雙重容錯(即r＝2).如何用最優修復和更好的容錯(即r＞2)來構造二進制MDS陣列碼仍然是一個開放的問題.這樣的結構將有利于在故障易發的分布式存儲系統中維護數據可用性。

基于專利【二進制陣列碼編碼框架】，本文通過選取合適的生成矩陣，提出了一種新的設計二進制MDS陣列編碼的方法，該方法可以容忍r≥3 個磁盤故障。我們表明，當d足夠大時，對于任何單個信息列故障的最小修復帶寬(1)都可以漸進地實現.通過利用循環結構的商環和選擇精心設計的編碼矩陣，我們的結構最小化了修復帶寬，這樣在修復操作中訪問的位元就會盡可能多地交叉。