北京大學(xué)的一個研究團隊提出了可以降低存儲編碼計算復(fù)雜度的編碼方法，一種改良的RS 碼，即基于GF（2）域的RS碼——BRS碼，實現(xiàn)了以簡單的編解碼方式獲得最快速的編解碼速度。
互聯(lián)網(wǎng)、移動設(shè)備和點對點通信的發(fā)展導(dǎo)致數(shù)據(jù)不斷增長。2010年，全球線上和線下數(shù)據(jù)第一次超過1澤字節(jié)（1021字節(jié)），從此我們步入了澤字節(jié)的時代。而IDC的報告顯示，預(yù)計到2020年，全球數(shù)據(jù)總量將超過40澤字節(jié)（相當(dāng)于4萬億吉字節(jié)）。如此海量的數(shù)據(jù)是寶貴的財富，也是棘手的挑戰(zhàn)：該如何存儲海量數(shù)據(jù)，并保證其可靠性呢？
分布式存儲系統(tǒng)是較為公認(rèn)的、能有效解決海量數(shù)據(jù)存儲問題的方案。這種系統(tǒng)將數(shù)據(jù)分散存儲在多個獨立的設(shè)備上，利用多個存儲服務(wù)器分擔(dān)數(shù)據(jù)負(fù)荷。但分布式系統(tǒng)往往由成百上千個存儲節(jié)點組成，節(jié)點故障往往會導(dǎo)致災(zāi)難性后果，容錯性面臨巨大挑戰(zhàn)。為了保證數(shù)據(jù)的可靠性，分布式存儲系統(tǒng)需要引入冗余機制，使節(jié)點間有多個物理網(wǎng)絡(luò)可以互為備份。糾刪碼可以極大地提高數(shù)據(jù)存儲空間利用率，所以相比于簡單易行的多副本策略，越來越多的存儲系統(tǒng)選擇使用糾刪碼策略。但是，糾刪碼過高時，計算復(fù)雜度會延遲存儲系統(tǒng)的反應(yīng)時間，降低存儲系統(tǒng)可靠性以及增大CPU能量消耗。
以RS碼為例，RS編碼是一種在分布式存儲環(huán)境下可容錯的編碼方式，它將需要存儲的數(shù)據(jù)分成K個數(shù)據(jù)塊，每塊大小為L，通過編碼矩陣將這K個數(shù)據(jù)塊生成N個編碼塊，校驗數(shù)據(jù)塊為M，其中N =K+M，每個編碼塊存儲在一個存儲節(jié)點中，則當(dāng)編碼塊損失數(shù)量不大于M時，系統(tǒng)可以從任意K個編碼塊中修復(fù)所有數(shù)據(jù)塊。RS碼需要復(fù)雜的有限域運算，特別是有限域的乘法運算，會極大地增加糾刪碼的計算復(fù)雜度，引起性能的下降。
不過，北京大學(xué)的一個研究團隊已經(jīng)掌握了可以降低存儲編碼計算復(fù)雜度的編碼方法——一種改良的RS碼—— BRS（Binary Reed-Solomon）碼。BRS碼是一種高效、快速、滿足最大距離可分離（MDS）特性的糾刪碼，它把原始的K個數(shù)據(jù)塊編碼生成N個編碼塊，在分布式存儲環(huán)境下可修復(fù)節(jié)點數(shù)據(jù)損失。我們定義MDS特性為N個編碼塊中任意的K編碼塊均可解碼出原始的K個數(shù)據(jù)塊。BRS是具有MDS特性的糾刪碼，是一類特殊的MDS碼，它在編碼過程中只用到了異或運算，并且編碼的計算量達(dá)到了最少，因此能夠以簡單的編解碼方式獲得最快速的編解碼速度。在滿足單位數(shù)據(jù)冗余最優(yōu)數(shù)據(jù)可靠性的糾刪碼（如傳統(tǒng)RS編碼和最優(yōu)CRS編碼）中，BRS碼的編碼計算復(fù)雜度是最低的。
但是該種碼有一個致命的缺點，就是它的ZigZag解法要求系統(tǒng)塊的長度必須大于數(shù)據(jù)塊的長度，并且這個長度與K和M的乘積成正比。這個冗余長度會給實際應(yīng)用帶來影響。為此，研究團隊在此基礎(chǔ)上進行改進，得到了一個改良的BRS碼，可以將冗余長度縮短至原來的一半以下。
傳統(tǒng)的RS碼構(gòu)造都是基于有限域GF(q)，而BRS碼的優(yōu)越性在于它編碼生成編碼塊的時候，只用到了異或運算。RS碼使用范特蒙德矩陣作為數(shù)據(jù)的編碼生成矩陣，將該生成矩陣的逆矩陣作為解碼矩陣。為了保證RS碼的MDS特性，傳統(tǒng)RS的編解碼運算都是在一個大的有限域上進行的。而BRS碼算法使用的編碼運算只包括了數(shù)據(jù)塊的移位和異或操作，將編解碼運算實現(xiàn)在一個大小為2的有限域GF（2）上，解碼運算使用ZigZag方式解碼，改善了傳統(tǒng)RS編碼的性能，提高了編解碼的運算速度。
在編碼過程中，BRS碼將原始數(shù)據(jù)塊（Blocksize）S平均分成K個塊，假設(shè)每一塊數(shù)據(jù)塊有l(wèi)比特的數(shù)據(jù)；構(gòu)建編碼塊M，M共有N-K個塊（即K=N+M，這里的加法均為異或操作）；在每個節(jié)點存儲數(shù)據(jù)，節(jié)點1的數(shù)據(jù)為S0,結(jié)點2的數(shù)據(jù)為S1，以此類推。
當(dāng)有節(jié)點失效而出現(xiàn)數(shù)據(jù)丟失時，BRS碼將使用一種非常快速的解碼算法去修復(fù)丟失的數(shù)據(jù)，這成為BRS碼的另一個優(yōu)越性。在BRS碼的解碼過程中，有一個必要條件：完好的檢驗數(shù)據(jù)塊的數(shù)目要大于等于損失的原始數(shù)據(jù)塊的數(shù)目，否則無法修復(fù)。
BRS碼使用ZigZag算法進行解碼。首先從現(xiàn)在的校驗塊中得到第1個損壞的字節(jié)，然后用這個字節(jié)去解出第2個字節(jié)，再用第二個字節(jié)去解出第3個字節(jié)，直到解出最后一個字節(jié)。整個過程如同抽絲剝繭一般，根據(jù)線索將迷題一層層解開，當(dāng)將繭剝完時，也就得到了所需要的數(shù)據(jù)。因為整個ZigZag解法的方法固定又簡單，可以非常高效地進行解碼。根據(jù)迭代公式，每循環(huán)1次，就能算出2個比特的值。如果每個原始數(shù)據(jù)塊長度為10比特，則重復(fù)10次后，就能解出原始數(shù)據(jù)塊中的所有未知的比特。以此類推，就完成了數(shù)據(jù)的解碼。
為了更加直觀地了解BRS碼的性能及其與CRS碼和RS碼的對比，我們假設(shè)每個數(shù)據(jù)塊的大小為32768字節(jié)，共8或10個原始數(shù)據(jù)塊，生成4個校驗數(shù)據(jù)塊。
因為編碼原因，BRS碼的校驗數(shù)據(jù)塊大小為32768字節(jié)，原始數(shù)據(jù)塊大小為32768-7×3×8=32600字節(jié)。在同樣的假設(shè)下，CRS碼的數(shù)據(jù)塊大小為32768字節(jié)，剛好為4的整數(shù)倍，不需要改變，每個條帶（Strip）長度為8096字節(jié)。
對上述8個原始數(shù)據(jù)塊生成4個校驗數(shù)據(jù)塊，實驗連續(xù)重復(fù)10萬次。編碼速度為編碼生成的總數(shù)據(jù)量與編碼總時間的比值，其中，編碼生成的總數(shù)據(jù)量為32千字節(jié)×4校驗塊×10萬次=12500兆字節(jié)。
實驗表明，在編碼速率上，單核處理器下BRS碼的編碼速率約為RS編碼的6倍，約為CRS編碼的1.5倍，滿足“相比RS編碼，編碼速度提升不低于200%”的目標(biāo)。在同樣條件下，對于不同缺失個數(shù)，BRS碼的解碼速率約為RS編碼的400%，約為CRS編碼的130%，滿足“相比RS碼，解碼速度提升100%”的目標(biāo)。
在分布式系統(tǒng)應(yīng)用日益普及的今天，在分布式存儲系統(tǒng)底層使用糾刪碼存儲數(shù)據(jù)可以增加系統(tǒng)的容錯性，在相同的冗余度下，與傳統(tǒng)的副本策略相比，BRS碼可以成倍地提高系統(tǒng)的可靠性。
BRS碼可應(yīng)用在分布式存儲系統(tǒng)中，例如在HDFS平臺中，可以使用BRS編碼作為底層數(shù)據(jù)編碼。同時，BRS碼在性能上的優(yōu)勢和其與CRS編碼在編碼方式上的相似性，使得BRS碼可以替代CRS編碼在分布式系統(tǒng)中使用。如今，Github上已有開源BRS碼的C語言實現(xiàn)，在分布式存儲系統(tǒng)的設(shè)計與實現(xiàn)中，可以使用BRS編碼方式存儲數(shù)據(jù)，實現(xiàn)系統(tǒng)自身的可容錯性。
糾刪碼引入冗余機制導(dǎo)致的系統(tǒng)復(fù)雜性被BRS碼以簡單的編解碼方式一一化解，并得到了極為快速的編解碼速度，這種BRS碼真正做到了繁簡兩相宜。
（編輯：小智）
