[發明專利]修復多節點失效的MDS陣列碼編碼以及解碼方法

有效

• 申請號: 201710156631.6
• 申請日: 2017-03-16
• 公開（公告）號: CN107086870B
• 公開（公告）日: 2019-10-22
• 發明（設計）人: 侯韓旭;韓永祥;周清峰
• 申請（專利權）人: 東莞理工學院
• 主分類號: H03M7/04
• 分類號: H03M7/04;H03M13/03;G06F3/06;H04L29/08
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙) 44248
• 代理人: 孫偉

本發明涉及數據處理領域，其公開了一種修復多節點失效的MDS陣列碼編碼，其組成部分為C（k，r，p）碼，通過構建一個(p?1)*(k+r)的矩陣來存儲原始信息數據塊和冗余塊，其中p為質數，且p大于k和r，k和r小于為小于p大于0的任意整數；k列稱為信息列，其對應為k個數據塊；r列為冗余列，其對應為r個冗余塊，C（k，r，p）碼中的加法和減法運算均為異或運算。本發明的有益效果是：能修復任意n?k個節點失效且編解碼計算復雜度較低的新Cauchy陣列碼，提高了系統的容錯性。通過二進制異或運算實現了新Cauchy陣列碼的編解碼，與CRS碼相比，編解碼過程的計算復雜度更低。

【技術領域】

本發明涉及數據處理領域，尤其涉及一種修復多節點失效的MDS陣列碼編碼以及解碼方法。

【背景技術】

隨著計算機網絡應用的迅速發展，網絡信息數據量變得越來越大，海量信息存儲變得尤為重要，持續增長的數據存儲壓力推動著整個存儲市場的快速發展。分布式存儲以其高性價比、低初期投資、按需付費等優越的特點日益成為當今大數據存儲的主流技術。

當前，分布式存儲系統的存儲節點失效已經成為一種常態。當系統所部署的存儲節點變得不可靠時，必須引入冗余來提高節點失效時的可靠性。引入冗余最簡單的方法就是對原始數據直接備份，直接備份雖然簡單但是其存儲效率和系統可靠性不高，而通過編碼引入冗余的方法可以提高其存儲效率，增強系統的可靠性。因此分布式存儲的高概率可用性、可靠性以及安全性等均是分布式存儲系統的關鍵技術問題。

在目前的存儲系統中，編碼方法一般采用MDS碼，MDS碼可以達到存儲空間效率的最優化，一個(n,k)MDS碼需要將一個原始數據文件分成k個大小相等的數據塊，通過線性編碼生成n個互不相關的編碼塊，并由n個節點存儲n個編碼塊。若n個編碼塊中包含原始的k個數據塊，其它n-k個編碼塊稱為冗余塊，包含k個數據塊的MDS碼稱為系統MDS碼。MDS碼滿足MDS屬性：即從n個編碼塊中取任意k個即可解碼出原始的k個數據塊。這種編碼技術在提供有效的網絡存儲編碼中占有重要的地位，特別適合應用于存儲大的文件以及檔案數據備份。

在分布式存儲系統中，把數據按某種方式編碼，并把編碼結果存儲在n個存儲節點中，這一過程稱為編碼過程。數據接收者只需連接并下載n個存儲節點中的任意k個存儲節點的數據即可恢復出原始數據，這一過程稱為數據重建過程或解碼過程。

不同的MDS碼有不同的編碼、解碼計算復雜度。復雜度越高，計算量越大，計算時所消耗的時間就越長。設計出一種好的MDS碼，能夠降低計算量，縮短工作時間，減少資源的消耗，節省系統運行時需要的成本，使得運算和存儲更加靈活。MDS陣列碼是MDS碼的一種，其特征是編解碼過程中僅僅用到簡單的二進制異或操作，因此可以很容易且高效的在系統中實現。本發明即是一種能容納任意n-k個編碼塊的丟失，編碼、解碼計算復雜度低的二進制系統MDS陣列碼。

EVENODD碼，引自論文[M.Blaum,J.Brady,J.Bruck,and J.Menon,“EVENODD:Anefficient scheme for tolerating double disk fai lures in RAID architectures,”IEEE Transactions on Computers,vol.44,no.2,pp.192–202,1995]。