北京大學的一個研究團隊提出了可以降低存儲編碼計算復雜度的編碼方法，一種改良的RS 碼，即基于GF（2）域的RS碼——BRS碼，實現了以簡單的編解碼方式獲得最快速的編解碼速度。

互聯網、移動設備和點對點通信的發展導致數據不斷增長。2010年，全球線上和線下數據第一次超過1澤字節（1021字節），從此我們步入了澤字節的時代。而IDC的報告顯示，預計到2020年，全球數據總量將超過40澤字節（相當于4萬億吉字節）。如此海量的數據是寶貴的財富，也是棘手的挑戰：該如何存儲海量數據，并保證其可靠性呢？

分布式存儲系統是較為公認的、能有效解決海量數據存儲問題的方案。這種系統將數據分散存儲在多個獨立的設備上，利用多個存儲服務器分擔數據負荷。但分布式系統往往由成百上千個存儲節點組成，節點故障往往會導致災難性后果，容錯性面臨巨大挑戰。為了保證數據的可靠性，分布式存儲系統需要引入冗余機制，使節點間有多個物理網絡可以互為備份。糾刪碼可以極大地提高數據存儲空間利用率，所以相比于簡單易行的多副本策略，越來越多的存儲系統選擇使用糾刪碼策略。但是，糾刪碼過高時，計算復雜度會延遲存儲系統的反應時間，降低存儲系統可靠性以及增大CPU能量消耗。

以RS碼為例，RS編碼是一種在分布式存儲環境下可容錯的編碼方式，它將需要存儲的數據分成K個數據塊，每塊大小為L，通過編碼矩陣將這K個數據塊生成N個編碼塊，校驗數據塊為M，其中N =K+M，每個編碼塊存儲在一個存儲節點中，則當編碼塊損失數量不大于M時，系統可以從任意K個編碼塊中修復所有數據塊。RS碼需要復雜的有限域運算，特別是有限域的乘法運算，會極大地增加糾刪碼的計算復雜度，引起性能的下降。

不過，北京大學的一個研究團隊已經掌握了可以降低存儲編碼計算復雜度的編碼方法——一種改良的RS碼—— BRS（Binary Reed-Solomon）碼。BRS碼是一種高效、快速、滿足最大距離可分離（MDS）特性的糾刪碼，它把原始的K個數據塊編碼生成N個編碼塊，在分布式存儲環境下可修復節點數據損失。我們定義MDS特性為N個編碼塊中任意的K編碼塊均可解碼出原始的K個數據塊。BRS是具有MDS特性的糾刪碼，是一類特殊的MDS碼，它在編碼過程中只用到了異或運算，并且編碼的計算量達到了最少，因此能夠以簡單的編解碼方式獲得最快速的編解碼速度。在滿足單位數據冗余最優數據可靠性的糾刪碼（如傳統RS編碼和最優CRS編碼）中，BRS碼的編碼計算復雜度是最低的。

但是該種碼有一個致命的缺點，就是它的ZigZag解法要求系統塊的長度必須大于數據塊的長度，并且這個長度與K和M的乘積成正比。這個冗余長度會給實際應用帶來影響。為此，研究團隊在此基礎上進行改進，得到了一個改良的BRS碼，可以將冗余長度縮短至原來的一半以下。

傳統的RS碼構造都是基于有限域GF(q)，而BRS碼的優越性在于它編碼生成編碼塊的時候，只用到了異或運算。RS碼使用范特蒙德矩陣作為數據的編碼生成矩陣，將該生成矩陣的逆矩陣作為解碼矩陣。為了保證RS碼的MDS特性，傳統RS的編解碼運算都是在一個大的有限域上進行的。而BRS碼算法使用的編碼運算只包括了數據塊的移位和異或操作，將編解碼運算實現在一個大小為2的有限域GF（2）上，解碼運算使用ZigZag方式解碼，改善了傳統RS編碼的性能，提高了編解碼的運算速度。

在編碼過程中，BRS碼將原始數據塊（Blocksize）S平均分成K個塊，假設每一塊數據塊有l比特的數據；構建編碼塊M，M共有N-K個塊（即K=N+M，這里的加法均為異或操作）；在每個節點存儲數據，節點1的數據為S0,結點2的數據為S1，以此類推。

當有節點失效而出現數據丟失時，BRS碼將使用一種非常快速的解碼算法去修復丟失的數據，這成為BRS碼的另一個優越性。在BRS碼的解碼過程中，有一個必要條件：完好的檢驗數據塊的數目要大于等于損失的原始數據塊的數目，否則無法修復。

BRS碼使用ZigZag算法進行解碼。首先從現在的校驗塊中得到第1個損壞的字節，然后用這個字節去解出第2個字節，再用第二個字節去解出第3個字節，直到解出最后一個字節。整個過程如同抽絲剝繭一般，根據線索將迷題一層層解開，當將繭剝完時，也就得到了所需要的數據。因為整個ZigZag解法的方法固定又簡單，可以非常高效地進行解碼。根據迭代公式，每循環1次，就能算出2個比特的值。如果每個原始數據塊長度為10比特，則重復10次后，就能解出原始數據塊中的所有未知的比特。以此類推，就完成了數據的解碼。

為了更加直觀地了解BRS碼的性能及其與CRS碼和RS碼的對比，我們假設每個數據塊的大小為32768字節，共8或10個原始數據塊，生成4個校驗數據塊。

因為編碼原因，BRS碼的校驗數據塊大小為32768字節，原始數據塊大小為32768-7×3×8=32600字節。在同樣的假設下，CRS碼的數據塊大小為32768字節，剛好為4的整數倍，不需要改變，每個條帶（Strip）長度為8096字節。

對上述8個原始數據塊生成4個校驗數據塊，實驗連續重復10萬次。編碼速度為編碼生成的總數據量與編碼總時間的比值，其中，編碼生成的總數據量為32千字節×4校驗塊×10萬次=12500兆字節。

實驗表明，在編碼速率上，單核處理器下BRS碼的編碼速率約為RS編碼的6倍，約為CRS編碼的1.5倍，滿足“相比RS編碼，編碼速度提升不低于200%”的目標。在同樣條件下，對于不同缺失個數，BRS碼的解碼速率約為RS編碼的400%，約為CRS編碼的130%，滿足“相比RS碼，解碼速度提升100%”的目標。

在分布式系統應用日益普及的今天，在分布式存儲系統底層使用糾刪碼存儲數據可以增加系統的容錯性，在相同的冗余度下，與傳統的副本策略相比，BRS碼可以成倍地提高系統的可靠性。

BRS碼可應用在分布式存儲系統中，例如在HDFS平臺中，可以使用BRS編碼作為底層數據編碼。同時，BRS碼在性能上的優勢和其與CRS編碼在編碼方式上的相似性，使得BRS碼可以替代CRS編碼在分布式系統中使用。如今，Github上已有開源BRS碼的C語言實現，在分布式存儲系統的設計與實現中，可以使用BRS編碼方式存儲數據，實現系統自身的可容錯性。

糾刪碼引入冗余機制導致的系統復雜性被BRS碼以簡單的編解碼方式一一化解，并得到了極為快速的編解碼速度，這種BRS碼真正做到了繁簡兩相宜。

（編輯：小智）