[發明專利]一種基于二進制域里德所羅門碼的數據編解碼方法

有效

• 申請號: 201480038232.4
• 申請日: 2014-12-16
• 公開（公告）號: CN105518996B
• 公開（公告）日: 2019-07-23
• 發明（設計）人: 李揮;侯韓旭;陳俊;朱兵;李碩彥
• 申請（專利權）人: 深圳賽思鵬科技發展有限公司
• 主分類號: H03M13/15
• 分類號: H03M13/15;H04L29/08
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙) 44248
• 代理人: 黃曉笛

本發明涉及分布式存儲系統領域，尤其涉及一種基于二進制域里德所羅門碼(Binary Reed?Solomon Code,簡為BRS碼)的數據編解碼方法，包括以下步驟：(A)原始數據構建二進制域里德所羅門碼；(B)更新二進制域里德所羅門碼；(C)重構二進制域里德所羅門碼；所述步驟(A)、步驟(B)以及步驟(C)中的運算均采用異或運算。本發明的有益效果是：通過該方法大大提高了數據上傳和下載的速率，很大程度上減少了系統操作復雜度(如元數據更新、更新后的數據廣播等)；在實際的分布式存儲系統中具有很高的應用價值和發展潛力。

【技術領域】

本發明涉及分布式存儲系統領域，尤其涉及一種基于二進制域里德所羅門碼的數據編解碼方法。

【背景技術】

隨著計算機網絡應用的迅速發展，網絡信息數據量變得越來越大，海量信息存儲變得尤為重要，持續增長的數據存儲壓力帶動著整個存儲市場的快速發展；分布式存儲以其高性價比、低初期投資、按需付費等優越的特點日益成為當今大數據存儲的主流技術。分布式存儲系統的存儲結點失效已經成為一種常態,當系統所部署的存儲結點變得不可靠時，必須引入冗余來提高結點失效時的可靠性,引入冗余最簡單的方法就是對原始數據直接備份，直接備份雖然簡單但是其存儲效率和系統可靠性不高，而通過編碼引入冗余的方法可以提高其存儲效率；因此分布式存儲的高概率可用性、可靠性以及安全性等均是分布式存儲系統的關鍵技術問題。在目前的存儲系統中，編碼方法一般采用MDS碼，MDS碼可以達到存儲空間效率的最佳，一個(n,k)MDS糾刪碼需要將一個原始文件分成k個大小相等的模塊，并通過線性編碼生成n個互不相關的編碼模塊，由n個結點存儲不同的模塊，并滿足MDS屬性(n個編碼模塊中任意k個就可重構原始文件)。

當存儲系統中的存儲結點失效時，為了保持存儲系統的冗余量，需要恢復該失效結點存儲的數據并將該數據存儲在新結點中，該過程稱為修復過程。在修復過程中，里德所羅門碼首先需要下載k個存儲結點的數據并恢復出原始數據，之后為新結點編碼出失效結點的存儲數據。而當原始數據出現改動時，為了維持數據的一致，需要對冗余的校驗數據塊進行更改，這個過程稱為更新過程。

RDP碼，全稱RowDiagonal Parity Code,是一種簡單的糾刪碼(引自論文References P.Corbett et al.“Row diagonal parity for double disk failurecorrection,”4th Usenix Conf.on File and Storage Tech.,San Francisco,2004)。它不需要使用有限域或者生成矩陣，只是按行和按泛對角線進行異或計算，生成兩個校驗數據塊，構成了一種帶有2個校驗數據塊的糾刪碼；但是RDP碼更新復雜度偏高和不可拓展。

論文[James S.Plank,Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Network Storage ApplicationsNetwork Computing and Applications,2006.]提出的柯西里德所羅門碼(CauchyReed-Solomon Code，簡稱CRS碼)是當前最常用的里德所羅門編碼之一，已經被廣泛用于分布式存儲系統中，例如在HDFS中就提供了一套基于CRS編碼的分布式存儲系統。但是CRS依然存在著一些缺陷，首先，使用0-1生成矩陣，雖然能大大降低編解碼復雜度，但實際上，它的解碼復雜度卻不是最優的，還存在許多糾刪碼，比如DRP編碼，它們的解碼復雜度要優于CRS。其次，它用于編解碼的有限域二進制矩陣還是比較復雜，散亂無章的0和1使得編解碼難以更進一步優化。然后，也是因為編碼復雜度目前還比較高，使得數據更新時，需要分析各種不同的情況，也使得編碼復雜度比較高。

【發明內容】