唐 聃 蔡紅亮 耿 微

1(成都信息工程大學軟件工程學院 成都 610225)

2(四川省信息化應用支撐軟件工程技術研究中心 成都 610225)

數據的可靠性是存儲系統(tǒng)需要考慮的首要問題，而隨著信息技術的發(fā)展以及向各個行業(yè)領域的滲透，需要存儲的數據量正持續(xù)地爆炸式增長.為了應對海量數據存儲的可靠性問題，同時也為了提高數據訪問的并發(fā)效率，通常有效的做法是使用多個存儲節(jié)點共同構建1個存儲系統(tǒng)，比如集中式的磁盤陣列(redundant arrays of independent disks, RAID)系統(tǒng)或基于網絡的分布式存儲系統(tǒng)等，而每個存儲節(jié)點可以是1個磁盤、1臺PC、1臺服務器或1個移動終端等可用作數據存儲的設備.與過去相比，當前單個存儲設備的穩(wěn)定性已經較高，但是對于由眾多節(jié)點構成的大規(guī)模存儲系統(tǒng)而言，節(jié)點故障事件仍然會頻繁發(fā)生[1-2].關于如何在部分節(jié)點故障后能保證數據不丟失，并且在故障節(jié)點被替換后能迅速恢復失效數據是近年來存儲領域研究的熱點.早期的多節(jié)點存儲系統(tǒng)多采用副本技術來為數據的可靠性提供保障，該技術把多個相同的數據副本存儲到不同的節(jié)點上，相同數據的不同副本之間可互為備份，當有存儲節(jié)點失效時，替換的節(jié)點可從任意1個或多個擁有相同數據副本的節(jié)點傳入數據進行數據重構.但副本技術會導致系統(tǒng)存儲效率過低的問題，如果需要在k(≥1)個節(jié)點同時失效后能有效重構數據，則需要把原始數據復制k份并分別存放在不同的節(jié)點上，整個系統(tǒng)的存儲效率僅有1/(k+1).因此，目前更多的研究集中在如何利用糾刪碼技術來保證存儲系統(tǒng)中的數據可靠性.與副本技術相比，使用糾刪碼來構建存儲系統(tǒng)的容錯機制可在相同容錯能力的條件下，極大地提高了存儲效率.

從編譯碼運算方式的角度看，大體可以把存儲系統(tǒng)中使用的糾刪碼分為2類：1)XOR類糾刪碼，這類編碼的編譯碼運算過程可以僅使用二進制的異或運算，因此編譯碼的速度很高，包括了陣列碼[2-8]和低密度奇偶校驗碼[9-11](low density parity check code, LDPC)等.陣列碼具有2維編碼結構，且通常有幾何形式的構造方法，工程實現時簡潔直觀，但具備極大距離可分(maximum distance deparable, MDS)性質的陣列碼通常容錯能力不超過3個[5-7]，導致其對當前實用的大規(guī)模存儲系統(tǒng)適應性不足.近年來，也有更高容錯能力的陣列碼被提出[2,8]，但是一般都會付出巨大的存儲效率代價.LDPC碼可以使得存儲效率逼近最優(yōu)，但該碼更適合構造長碼，且其成功譯碼具有概率性，因此目前在存儲系統(tǒng)中的使用較少.2)RS(Reed-Solomon codes)類糾刪碼[12-14]，此類編碼能達到理論最優(yōu)的存儲效率，即具有MDS性質，且能根據具體環(huán)境構造出任意容錯能力的碼字，具有很強的應用靈活性.由于它獨特的優(yōu)勢，目前的存儲系統(tǒng)也更多是偏向以RS類糾刪碼為基礎構建其容錯機制.但是，RS類糾刪碼的運算需要在多元有限域上進行，這導致RS類糾刪碼的計算效率大大低于XOR(exclusive-OR, XOR)類糾刪碼.對于RS類糾刪碼而言，其譯碼運算復雜度又遠高于其編碼運算.

針對這一問題，多年來不斷有學者積極尋求著解決方案.但是，相比于XOR類編碼，RS類糾刪碼很難在數據元素和校驗元素之間尋找到有幾何規(guī)律的碼鏈關系，從而在方法論的層面提升RS類糾刪碼計算的時間效率相對困難.現在對于RS類糾刪碼的譯碼方法研究更多集中在如何提高單節(jié)點失效后的重構效率[13]或者減少修復帶寬[14]，對能整體降低RS類糾刪碼刪除錯誤重構計算時間開銷的方法研究較少[15-16].目前RS類糾刪碼最為工程領域接受的計算效率提升途徑為，使用一些專門針對有限域運算進行優(yōu)化的指令集或底層方法來達到降低RS類糾刪碼計算時間成本的目的，其中比較常見的包括GF-Complete[17]，Jerasure[18]以及Intel公司推出的ISA-L library[19]，但是此類技術路線與本文研究內容關聯度不大，故不再詳述.

本文工作的主要貢獻包括3個方面：

1) 提出了一種針對RS類糾刪碼碼刪除錯誤的譯碼方法，適用于存儲系統(tǒng)中的失效數據重構，由于不再使用計算復雜度很高的矩陣求逆運算，能很大程度節(jié)省RS類糾刪碼的譯碼時間開銷；

2) 新的譯碼方法也可以推廣到所有的二進制XOR類糾刪碼；

3) 對該譯碼方法的研究表明：該方法還能在數據重構時規(guī)避某些節(jié)點的參與，可用于大規(guī)模存儲系統(tǒng)的數據重構時對重構參與節(jié)點的使用進行整體規(guī)劃.

1 相關工作及研究動機

為了便于敘述，在此做約定：存儲系統(tǒng)有n個存儲節(jié)點，使用某一類(n,k)糾刪碼作為容錯的核心方法，其要點是：數據存儲前將原始數據分為k個大小相同的數據塊，k個數據塊對應著編碼的k個數據元素(長度為k的數據列向量D=(d0,d1,…,dk-1)T)，編碼后形成n個數據塊，分別存儲于存儲系統(tǒng)的n個不同節(jié)點上，而編碼得到的1個碼字C則分別對應著碼字的n個碼元(長度為n的碼字列向量C=(d0,d1,…,dk-1,c0,c1,…,cn-k-1)T=(c0,c1,…,ck-1,…,cn-1)T，ci為碼字的碼元)，其中k和n均為正整數，k為原始數據分組的長度，n為碼字的長度，且n>k，0≤i≤n-1.文中若提到碼元失效亦指該碼元對應的存儲節(jié)點失效，而存儲節(jié)點失效可以理解為該存儲節(jié)點上的全部數據丟失(亦即最壞的情況)，反之亦然.而本文的所有方法敘述中，若無特別說明，編碼的容錯能力即指對刪除錯誤的最大恢復能力，對于全部矩陣及存儲陣列的行列的計數從0開始，且不妨假設所有運算有限域的特征為2.下面，本節(jié)將首先以示例的形式簡要描述當前糾刪碼最常用的3類譯碼方法.

1.1 基于碼鏈的譯碼方法

Fig. 1 Data layout of RDP code圖1 RDP碼的布局結構

大多XOR類糾刪碼的構造可以由幾何形式表示，即碼字中所有存在校驗關系的數據位和校驗位的集合可以看作1條碼鏈[2]，1條碼鏈即對應1個校驗方程.特別是在陣列碼中，如果用線連接碼鏈上的所有碼元則通常具有一定的幾何規(guī)律.

以RDP碼[6]為例，使用素數5構造出RDP碼的碼字結構如圖1所示：

根據RDP碼的編碼規(guī)則，圖2中用箭頭連接起來的元素和所有圖形相同的碼元被稱為碼鏈，每條碼鏈上所有碼元的異或結果為0.而簡單來說，基于碼鏈關系的譯碼方法，即是按照一定規(guī)則搜索僅有1個失效碼元的碼鏈，利用碼鏈上其他有效碼元的異或求得失效碼元的值.

假設在本示例中RDP碼的第0列和第2列對應的存儲節(jié)點失效，則基于碼鏈的數據重構方法操作過程為：首先搜索到碼鏈[(0,1),(1,0),(1,5),(2,4),(3,3)]中僅有1個失效碼元(1,0)，則將該碼鏈上其他所有碼元異或，從而得到碼元(1,0)的值；碼元(1,0)數據恢復后，其所在的另一條碼鏈[(1,0),(1,1),(1,2),(1,3),(1,4)]上也就僅存在1個失效碼元(1,2)，異或該碼鏈上所有有效碼元則失效碼元(1,2)得到恢復；碼元(1,2)數據恢復后，其所在的另一條碼鏈[(0,3),(1,2),(2,1),(3,0),(3,5)]上也就僅存在1個失效碼元(3,0)，異或該碼鏈上所有有效碼元則失效碼元(3,0)得到恢復；以此類推，可以按照上述規(guī)律逐漸按序恢復出其他的失效碼元(3,0)，(3,2)，(0,0)，(0,2)，(2,0)，(2,2).

很多XOR類糾刪碼均可以用該譯碼方法進行數據重構，而基于碼鏈的譯碼方法邏輯簡單清晰，便于軟硬件實現，因此在實際工程中被廣泛使用.將運算的有限域GF(2w)上的所有數值替換為對應的w×w的2元域矩陣后，基于碼鏈的譯碼方法也能勉強用于RS類糾刪碼的譯碼，其中w為正整數.但是，RS類糾刪碼的構造方法與XOR類糾刪碼差異較大，一般沒有清晰的幾何編碼結構，因此用該譯碼方法將有較大概率不能完全重構本應該可以恢復的失效碼元.

1.2 基于生成矩陣的譯碼方法

RS類糾刪碼的編碼通常是采用生成矩陣乘以數據向量的做法，假設數據向量為D，生成矩陣為G，生成矩陣可以是由范德蒙矩陣或者柯西矩陣生成，但是本質上沒有太大差異.

圖3顯示了1個(7,4)RS糾刪碼的編碼過程，生成矩陣的上半部分為1個單位矩陣I，下半部分為1個3×4的柯西矩陣P，顯然這是1個容錯能力為3的系統(tǒng)柯西RS糾刪碼.

Fig. 3 Encoding process of RS code圖3 RS碼的編碼過程

其編碼過程可表達為G×D=C，其中的參數D=(d0,d1,…,dk-1)T，C=(d0,d1,…,dk-1,c0,c1,…,cn-k-1)T.

使用生成矩陣乘以由數據元素組成的列向量，從而得到由各碼字元素構成的碼字列向量.由矩陣的乘法定義可知，生成矩陣的第i行構成的行向量乘以數據元素構成的列向量得到碼字向量的第i個碼元，因此生成矩陣的第i行與碼字向量的第i個碼元存在對應關系.換句話說，抽取生成矩陣的任意行而組成的子矩陣，乘以數據元素構成的列向量，如果也選取碼字向量中與生成矩陣抽取行相同位置的碼元構成新的列向量，則圖3中的等式仍然成立.

假設碼字C中的元素d0和d2這2個碼元失效，我們可以去除碼字這2個碼元以及生成矩陣中對應的2行，等式仍然成立，如圖4所示.

Fig. 4 Decoding process based on the generating matrix圖4 基于生成矩陣的譯碼過程

此時，從仍然有效的碼元中任意選取4個(比如最后4個碼元)，構成列向量C′=(d3,c1,c2,c3)，并使用生成矩陣中與列向量C′中碼元相同位置的第4～7行，構成1個矩陣G′，若將數據元素列向量記作D，則顯然G′×D=C′成立，此時在該等式兩邊同時乘以矩陣B的逆，則能恢復出數據元素D=G′-1×C′.而矩陣B的可逆性則由柯西矩陣或者范德蒙矩陣的性質來保證，此處不再贅述.這就是基于生成矩陣譯碼的基本原理，也可用于任意糾刪碼的譯碼.

基于生成矩陣的譯碼方法，也有不少學者提出過改進方案.其中最典型的是Blomer等人[20]提出的降低有限域維度方案，該方案將運算在有限域GF(2w)上生成矩陣中的每個元素用1個w階的0-1方陣表示，源文件分為k個數據塊，每個數據塊由相同數量的運算單位構成，每個運算單位是1個w位的0-1比特串(看作是1個w維列向量)，這樣，編譯碼運算時均只需進行2元域的運算，從而提高計算速度.而此后Plank等人[21]又在此基礎之上提出如何減少生成矩陣中數值1的方法，從而進一步減少運算時間.不過，文獻[20-21]改進方案本質上是通過降低運算有限域的維度達到的，方法本身和本節(jié)敘述的原理沒有實質的差異.此外，隨著對容錯能力要求的提高，此類改進方案可能會導致生成矩陣的尺寸膨脹過快，從而譯碼運算時將面臨高復雜度的大矩陣求逆運算的問題.

1.3 基于校驗矩陣的譯碼方法

基于生成矩陣譯碼方法的問題為，對1個容錯能力為k(k>1)的RS糾刪碼，1個碼元失效和k個碼元失效，在譯碼過程中使用到的矩陣求逆運算的次數和所需求逆矩陣的尺寸是相同的.如果碼字的數據元素和校驗元素同時出現了失效，則使用該方法譯碼則需要先恢復數據元素，再重新進行編碼以恢復校驗元素，比較繁瑣，也增加了本來不必要的計算工作量.而基于校驗矩陣的譯碼方法可以在很大程度解決上述問題.基于校驗矩陣的譯碼方法幾經改進[15-16,22]，但譯碼原理總體一致，本節(jié)根據文獻[16]的方法，并以1.2節(jié)的(7,4)柯西RS糾刪碼為例進行簡要敘述.

1個(7,4)柯西RS糾刪碼的校驗矩陣的尺寸為3×7，其中校驗矩陣的前半部分為1個3×4的柯西矩陣P(和1.2節(jié)示例中的矩陣P相同)，后半部分為1個單位矩陣I，如圖5所示:

Fig. 5 The check matrix and correspondence between its column vectors and code elements圖5 校驗矩陣及列向量與碼字元素的對應關系

由校驗矩陣的定義可知，校驗矩陣的每一列與碼字中的各個碼元一一對應：

(1)

將校驗矩陣記作H，碼字向量記作C，則在所有碼元沒有錯誤發(fā)生時恒有等式H×C=0成立.

Fig. 6 Adjustment of position of column vectors and code elements in the check matrix圖6 調整校驗矩陣中列向量與碼字元素的位置

此時仍然假設碼字中的第0個和第2個碼元，即d0和d2失效，則做操作：如圖6所示，移動碼字向量C中的失效碼元到最右邊，并將其作為1個子向量記作y，剩余的有效碼元也記作1個新的子向量d，d和y組成的向量記作向量C=(d|y)；然后按照當前向量C中各碼元和校驗矩陣中各列向量的對應關系，重新排列校驗矩陣中的各列，將向量d中碼元對應校驗矩陣中的各列組成的子矩陣記作A，向量d中碼元對應校驗矩陣中的各列組成的子矩陣記作B，因此校驗矩陣可以表示為H=(A|B)，顯然等式H×C=A×d+B×y=0成立，因為運算有限域的特征為2，則等式A×d=B×y成立.

與基于生成矩陣的譯碼方法相比，本節(jié)方法在譯碼時能減小需要進行求逆運算的矩陣尺寸，對于1個r容錯的RS類糾刪碼而言，如果失效碼元數量為f(f≤r)，則需要進行求逆運算的矩陣尺寸為f×f，當僅有1個失效碼元需要重構時，則求1個特定數值在運算有限域上的乘法逆元即可.因此，此類譯碼方法的計算效率與基于生成矩陣的譯碼方法相比有了較為明顯的提高.

1.4 本文的研究動機

由于RS類糾刪碼使用了有限域上的計算操作，從而導致了很高的計算時間成本.不過，我們的實驗表明，與有限域上的加法及乘法相比，RS類糾刪碼譯碼操作中需要頻繁使用到的矩陣求逆運算才是導致RS碼計算效率低的最重要因素.表1顯示了在同一臺電腦上進行5 000次有限域GF(28)上的加法、乘法，以及不同階次方陣求逆運算的時間消耗對比.不難看出，有限域上加法和乘法操作的時間開銷基本相當，而矩陣求逆運算的時間開銷則是要高出加法和乘法運算好幾個數量級的，且隨著求逆矩陣尺寸的增加而成倍增長，從復雜度上來講，對于規(guī)模為n×n的矩陣來講，矩陣求逆的運算復雜度為O(n3)，這也是為什么基于校驗矩陣的譯碼方法時間效率優(yōu)于基于生成矩陣譯碼方法的原因.但是，基于校驗矩陣的譯碼方法并沒有消除矩陣求逆運算，只是減小了需要進行求逆運算的矩陣尺寸.如果能在譯碼過程中完全消除矩陣的求逆運算，則能更大程度減小RS類糾刪碼的譯碼時間開銷.這也是本文研究的出發(fā)點和動機.

Table 1 Time Cost Comparison of 5 000 Operations over the Finite Field GF(28)

2 一類新的RS類糾刪碼的譯碼方法

本節(jié)將提出一類新的RS類糾刪碼譯碼方法，該方法能完全消除譯碼過程中的矩陣求逆運算操作，從而降低譯碼操作的譯碼時間復雜度.在介紹新的方法之前，首先引入碼元關系矩陣的概念，并對重要性質進行說明.

2.1 碼元關系矩陣

有限域GF(q)上的所有(n,k)線性分組碼，碼字C=(c0,c1,c2…,cn-1)T中任意1個碼元ci，i為整數且0≤i≤n-1，均可由所有碼元的線性組合進行表示，則所有碼元可表示為

(2)

本文將該非齊次線性方程組的系數矩陣定義為碼元關系矩陣W.

顯然，對于任意1個(n,k)線性分組碼，其碼元關系矩陣一定是1個n×n的方陣：

(3)

由碼元關系矩陣的定義可知，W的第i行Wi=(ai,0,ai,1,…,ai,n-1)代表了碼字第i個碼元ci的一類線性表示方法，即ci=ai,0c0+ai,1c1+…+ai,n-1cn-1，i為整數且0≤i≤n-1，矩陣W的第j列對應著參與計算的碼字中的第j個碼元，j為整數且0≤j≤n-1.

對于任意線性分組碼，其碼元關系矩陣W通常不會是唯一的，但是單位矩陣顯然是碼元關系矩陣，它表示每一個碼元和自身相等.下面給出碼元關系矩陣的2個性質：

性質1.對碼元關系矩陣進行任何初等行變換后的結果不再是碼元關系矩陣.

證明.在有限域GF(q)中，矩陣的初等行變換包含3類變換[23]：

1) 以1個非0的數t乘以矩陣的某一行，其中t∈GF(q)；

2) 把矩陣的某一行的t倍加到另一行，其中t為GF(q)中非0元素；

3) 互換矩陣中任意2行的位置.

下面就這3類初等行變換進行分別說明：

1) 根據定義，線性關系矩陣中的第i行代表了碼字C=(c0,c1,…,cn-1)中第i個碼元由所有碼元的1種線性表示方式：ci=ai,0c0+ai,1c1+…+ai,n-1cn-1，其中i為整數且0≤i≤n-1.對其中1行乘以1個非0數t則等價于把該碼元也乘以t：t×ci=t×(ai,0c0+ai,1c1+…+ai,n-1cn-1).顯然，由于t為非0數，則ci≠t×(ai,0c0+ai,1c1+…+ai,n-1cn-1).因此，在線性關系矩陣中，第i行乘以t后得到的新的第i行(t×ai,0,t×ai,1,…+t×ai,n-1)不再是第i個元素ci的線性表達，所以1個非0數t乘以原始碼元關系矩陣的某一行后的結果不再是線性關系矩陣.

2) 不妨假設將第j行的t倍加到i行上，可以表示為：t×cj+ci=(t×aj,0+ai,0)c0+(t×aj,1+ai,1)c1+…+(t×aj,n-1+ai,n-1)cn-1，其中i和j為整數且0≤i≤n-1.除非t=0，否則t×cj+ci≠ci.因此，第j行的t倍加到第i行的新的第i行(t×aj,0+ai,0,t×aj,1+ai,1,…,t×aj,n-1+ai,n-1)已經不再是第i個元素ci的線性表達，因此，在線性關系矩陣中，把矩陣的某一行的t倍加到另一行之后的結果不再是線性關系矩陣.

3) 根據碼元關系矩陣的定義可知，線性關系矩陣的每一行代表了不同的元素，顯然任意2行相互交換后的結果不再是線性關系矩陣.

證畢.

性質2.對于任意長度為n的行向量v=(v0,v1,…,vn-1)，將v的t倍加到碼字C=(c0,c1,…,cn-1)對應的碼元關系矩陣的任意行，其結果仍然為碼元關系矩陣，其中v0c0+v1c1+…+vn-1cn-1=0，且ci,vi,t∈GF(q).

證明.根據碼元關系矩陣的定義可知，碼元關系矩陣的第i行Wi=(ai,0,ai,1,…,ai,n-1)為碼字C中第i個碼元ci由所有碼元的其中1種線性表示：ci=ai,0c0+ai,1c1+…+ai,n-1cn-1.則等式ci=ai,0c0+ai,1c1+…+ai,n-1cn-1+0顯然成立.而根據前提條件，對于向量v，有等式v0c0+v1c1+…+vn-1cn-1=0成立.則等式tv0c0+tv1c1+…+tvn-1cn-1=t×0=0也成立.那么，等式ci=(ai,0c0+ai,1c1+…+ai,n-1cn-1)+(tv0c0+tv1c1+…+tvn-1cn-1)也成立，對該等式歸并同類項后得到等式：ci=(ai,0+tv0)c0+(ai,1+tv1)c1+…+(ai,n-1+tvn-1)cn-1.

顯然，這也是對第i個碼元ci的一類線性表示.因此，將向量v的t倍加到線性關系矩陣任意行后的結果仍然是同一碼字的碼元關系矩陣.

證畢.

2.2 失效數據恢復步驟

不妨假設在有限域GF(q)上構建1個(n,k)RS糾刪碼，其中q=pw，p為素數，w,n,k均為正整數，且k

假設其中有f個碼元失效，f≤n-k，將失效碼元組成的集合標記為F，F={F1,F2,…,Ff}，即{F1,F2,…,Ff}={cs1,cs2,…,csf}，其中下標{s1,s2,…,sf}∈{0,1,2,…,n-1}，也就是下標為失效碼元位置.

步驟1.初始化碼元關系矩陣.生成1個尺寸為n×n的單位矩陣In×n，根據碼元關系矩陣的定義，因為ci=ci，i為整數且0≤i≤n-1，因此In×n可以作為初始的碼元關系矩陣Wn×n，記作：

(4)

步驟2.定義譯碼變換矩陣并初始化.將碼元關系矩陣Wn×n和校驗矩陣H(n-k)×n拼接成1個矩陣，稱為初始譯碼變換矩陣，記作S0：

在這種嚴峻的形勢下，學校體育教學只有不斷喚醒學生的運動體驗才能徹底轉變這種劣勢，才能使學生在運動體驗中獲得強烈的快感，才能轉變學生們對于體育課程的看法，才能增強學生的健康意識，使其全身心的投入到體育實踐活動中來。從當前學生對于學校體育教學的認識來看，他們普遍認為學習體育對其沒有任何意義，只能作為緊張忙碌的文化學習后緩解疲憊身心的一種方式。因此，學校體育教學應當使學生們對于體育教學有一個重新的認識，要讓他們了解到體育可以在調節(jié)情緒的同時成為他們學習下一門學科的一大助力。學校體育教學只有通過不斷縮短運動和生活的距離，才能使學生們全面了解到體育的內涵。

(5)

顯然，矩陣S0的尺寸為(2n-k)×n，這里的矩陣的下標從0開始，將S0中前n行構成的子矩陣記作S_up0，而將其最后n-k行構成的子矩陣記作S_down0.

在該譯碼過程中，對于f個丟失碼元，需要對初始譯碼變換矩陣S0進行f次變換操作.將經過第i次矩陣變換之后更新的譯碼變換矩陣Si中前n行構成的子矩陣記作S_upi，而將其最后n-k行構成的子矩陣記作作S_downi，i為整數且1≤i≤f.

在每次進行譯碼變換矩陣的變換過程中，由于只進行了行變換，那么對于S_upi和S_downi，第i列均對應著碼字中的第i個碼元，因此譯碼變換矩陣Si的每一列與碼元也有相同的對應關系.

步驟6.反復執(zhí)行第5步，直到集合Rsi為空.將矩陣Si的第id_row行上所有元素置為0，然后將集合F中的元素csi刪除.

步驟7.判斷矩陣Si的子矩陣S_downi是否所有元素均為0，若是則表明不能再恢復任何失效碼元，若此時集合F中還存在元素則表明這些失效碼元不可恢復，終止.

步驟8.重復步驟3～7，直到失效碼元集合F為空，即所有失效碼元可成功恢復，轉到步驟9.當存在失效碼元不可恢復時，終止.

步驟9.此時Si的上半部分子矩陣S_upi仍然為碼元關系矩陣，其中包含著有效碼元對失效碼元的線性關系，也可簡稱為譯碼矩陣，記R，R=S_upi，顯然，矩陣R的尺寸為n×n，而矩陣R的第si行(列)對應碼字的第si個碼元.那么失效碼元csi可以進行恢復：

(6)

其中，1≤i≤f，0≤u≤n-1.

使用步驟1～9，可以對有限域GF(q)上的RS類糾刪碼的失效碼元進行恢復，或者是所有失效碼元能被恢復成功，若不能將所有碼元成功恢復也能清楚地知道哪些碼元可恢復而哪些不能恢復.

2.3 方法的正確性及分析

本節(jié)首先對和新譯碼方法相關的一些重要定理進行闡述，并在此基礎上說明本文方法的正確性.

定理1.對于有限域GF(q)，S為(n,k)線性分組碼的譯碼變換矩陣，則將矩陣S第i行乘以t后，矩陣S的子矩陣S_down仍然為校驗矩陣.其中q=pm，p為素數，t≠0,t∈GF(q)，i為整數且n≤i≤n+k-1.

證明.由譯碼變換矩陣S的構造方法可知，該矩陣最上面n行為碼元關系矩陣，而下面的n-k行為該編碼的校驗矩陣.因此，在譯碼變換矩陣S中最下面的n-k行均代表碼字的校驗方程：ai,0c0+ai,1c1+…+ai,k-1ck，其中i為整數且n≤i≤n+k-1.對譯碼變換矩陣S第i行乘以t，則等價于t×ai,0×c0+t×ai,1×c1+…+t×ai,k-1×ck-1=t×(ai,0c0+ai,1c1+…+ai,k-1ck-1)=0.因此，對于譯碼變換矩陣S而言，在其最下面的n-k行的任意1行上乘以1個非0數t后，組成的子矩陣S_down仍然為校驗矩陣.

證畢.

定理2.對于任意有限域GF(q)，S為n-k線性分組碼的譯碼變換矩陣，則將矩陣S第j行乘以t并加到第i行后，矩陣S的子矩陣S_up仍然為碼元關系矩陣.其中q=pm，p為素數，t≠0,t∈GF(q)，i和j均為整數且n≤j≤n+k-1,0≤i≤n+k-1.

證明.分2種情況討論：

1) 當n≤i≤2n-k-1時.此時對譯碼變換矩陣S的變換集中在該矩陣的最下面n-k行，該部分由編碼的校驗矩陣初始化.此時第i行對應的校驗方程為ai,0c0+ai,1c1+…+ai,k-1ck-1=0，第j行對應的校驗方程為aj,0c0+aj,1c1+…+aj,k-1ck-1=0，則將矩陣S第j行乘以t后加到第i行則等價于(taj,0+ai,0)c0+(taj,1+ai,1)c1+…+(taj,k-1+ai,k-1)ck-1=0，顯然成立.

2) 當0≤i≤n-1時.此時，譯碼變換矩陣S的第i行對應的是碼元線性關系方程ci=ai,0c0+ai,1c1+…+ai,n-1cn-1，而譯碼變換矩陣S的第j行對應的為該編碼的校驗方程aj,0c0+aj,1c1+…+aj,k-1ck-1=0.將矩陣S第j行乘以t加到第i行則等價于：ci=ai,0c0+ai,1c1+…+ai,n-1cn-1+0，顯然也成立.這與線性關系矩陣的性質2也剛好吻合.因此，定理2成立.

證畢.

根據2.2節(jié)的描述，新的譯碼方法總是在譯碼變換矩陣S的最下面n-k行中選取符合條件的行，標記為第i行，然后將第i行乘以1個數后加到矩陣S的另外1行或多行上.換句話說，即對譯碼變換矩陣S進行有一定限制條件的初等變換.由于方法每次選取的第i行均滿足條件n≤i≤n+k-1.根據定理1和定理2，雖然譯碼變換矩陣S在不斷地進行變換和運算，其子矩陣S_up一直是碼元關系矩陣，并能最終作為失效碼元恢復的譯碼矩陣.綜上所述，新方法可以對RS碼字中的刪除錯誤進行恢復.

該方法與文獻[24]中的基于生成矩陣譯碼方法的譯碼方法，及文獻[16]的基于校驗矩陣的譯碼方法對比，主要存在2個方面的創(chuàng)新及優(yōu)勢：

1) 算法復雜度較低

對于1個(n,k)RS編碼而言，k

證明.本文所提的譯碼恢復方法的主要運算除了最后步驟9中如式(6)恢復計算f個失效碼元固定次數E0=f×n的譯碼恢復運算，其余主要的運算集中在當i=1:f循環(huán)執(zhí)行的步驟3～7對f個丟失碼元的譯碼變換矩陣Si的更新操作，1≤i≤f.

在i=1:f的每次循環(huán)中，其主要的有限域計算主要是步驟5中的對于j=1:p且j≠v循環(huán)執(zhí)行的公式所述的運算，這里需要循環(huán)的次數為p-1，p為對應列非0元素的個數.

在j=1:p且j≠v的每次循環(huán)中，根據步驟5中的執(zhí)行公式，可以得出需要執(zhí)行n次乘法運算，故譯碼變換運算需執(zhí)行的運算次數E1≤f×p×n，因此可得總體的運算次數E=E0+E1≤(p+1)×f×n，可以得出該方法的時間復雜度為O(f×n).

而文獻[24]所采用的生成矩陣求逆方法運算復雜度約為O(n3)，1個(n,k)線性分組碼作為糾刪碼時，當丟失的碼元數量小于其分組碼的最小碼距的時候，這個糾刪碼的譯碼是可解的.文獻[16]中采用基于校驗矩陣的譯碼方法，根據1.3節(jié)中的方法描述，當其中有f個碼元丟失時，其所需要進行的是對校驗矩陣提取的對應的f×f滿秩的子矩陣進行矩陣求逆，以進行后續(xù)的f個丟失碼元的恢復，故其復雜度為O(f3).而文獻[25]中的方法根據文中的描述，其復雜度為O(f×n2).

證畢.

2) 可同時恢復原始數據碼元和校驗碼元

本文所述方法中丟失的校驗碼元可在譯碼過程中直接求得，無需額外計算.該方法可通過變換1次性的同時求得原始數據碼元以及校驗碼元，這也有益于減少譯碼運算，降低所有失效元素恢復的時間.

而文獻[24]和文獻[25]所述方法中需要先求得原始數據，再通過式(2)所示方程組進行運算得到丟失的校驗碼元，增加了運算次數.

2.4 新方法示例

我們以在第1節(jié)中提到的RS糾刪碼為例來說明新方法的執(zhí)行過程，如1.2節(jié)所述，這是1個(7,4)系統(tǒng)碼，首先在有限域GF(28)上構造出該碼的生成矩陣G(其中的子矩陣P為柯西矩陣):

(7)

不妨假設數據元素向量為D=(1,2,3,4)T，則碼字向量C=(c0,c1,…,c6)T能計算得出：C=G×D=(1,2,3,4,0,241,160)T.其中有限域的構建方法可參考文獻[26]，由于篇幅原因本文不再敘述.

仍然假設碼字中的第0和第2個元素失效，則失效碼元集合為F={c0,c2}.首先初始化譯碼變換矩陣S0(子矩陣W為單位矩陣、而子矩陣H為該編碼的校驗矩陣)：

(8)

(9)

反復從集合Rs2中取出元素并執(zhí)行2.2節(jié)中詳細步驟操作，直到集合Rs2為空.并刪除元素c2后，集合F為空，循環(huán)退出.所有變換完成后，矩陣S2：

(10)

其中的前7行構成的子矩陣S_up2即為可用作失效元素恢復的碼元關系矩陣，即譯碼矩陣R.

根據碼元關系矩陣的定義可以，2個失效碼元可以計算得出:

(11)

3 新方法的性能分析及應用擴展

首先說明實驗運行的平臺信息(以下簡稱為實驗平臺)，實驗平臺使用了Ceph v13.2.3進行分布式存儲系統(tǒng)的搭建，所有糾刪碼代碼由Python2.7實現，但是為了編譯碼方法代碼構建與分析的方便，沒有直接使用ceph的邏輯存儲關系，系統(tǒng)中使用完全相同的計算機作為存儲節(jié)點.其主要配置信息為：CPU為Intel i5-4570U，6 MB緩存，內存容量為8 GB，而每臺計算機上僅搭建1個OSD(object storage daemon).在實驗時，每個存儲節(jié)點對應碼字中相同位置的1個碼元，碼元失效即對應的節(jié)點失效.

3.1 RS類糾刪碼譯碼的時間開銷

本節(jié)實驗除了使用到本文的譯碼方法，一方面我們還選用了文獻[24]中的譯碼方法作為基于生成矩陣譯碼方法的代表，選用了文獻[16]的譯碼方法作為基于校驗矩陣的譯碼方法，以及文獻[25]中的譯碼方法，在同樣的環(huán)境下進行運行測試.另一方面，選用了硬件加速方法[18]及降低有限域規(guī)模的方法[20]進行對比.在這些實驗中，若無特別說明，用于編譯碼測試的原始數據均為10 MB.

實驗1.在實驗平臺上分別構建(4,2)，(5,3)，(7,4)，(7,3)柯西RS糾刪碼作為容錯方法，計算有限域為GF(28).將10 MB原始數據編碼后按序存儲到各個存儲節(jié)點中，分別使其中的1個和2個存儲節(jié)點失效，在用新的節(jié)點替換后，分別采用基于生成矩陣的譯碼方法[24]、基于校驗矩陣的譯碼方法[16]、文獻[25]中的譯碼方法及本文方法重構數據，其數據重構的時間開銷分別如圖7和圖8所示.

Fig. 7 Comparison of the time cost of four different methods to reconstruct a single failed node圖7 4種不同方法重構單個失效節(jié)點的時間開銷對比

Fig. 8 Comparison of the time cost of four different methods to reconstruct two failed nodes圖8 4種不同方法重構2個失效節(jié)點的時間開銷對比

總體來看，單個失效節(jié)點失效時采用基于校驗矩陣的譯碼方法進行數據重構的時間開銷最低，新方法略高于此，但是從2個失效節(jié)點開始，采用新譯碼方法進行數據重構的時間開銷就低于另外3種方法.

實驗2.在實驗平臺上同樣構建(4,2)，(5,3)，(7,4)，(7,3)柯西RS糾刪碼作為容錯方法，計算有限域為GF(28).將原始數據編碼后按序存儲到各個存儲節(jié)點中，采用的原始數據文件大小分別為10 MB，50 MB，100 MB，文件分塊大小分別為1 KB，4 KB，1 MB.分別使其中的1個和2個存儲節(jié)點失效，分別采用基于生成矩陣的譯碼方法[24]、基于校驗矩陣的譯碼方法[16]、文獻[25]中的譯碼方法及本文方法重構數據，其數據重構的時間開銷分別如表2和表3所示.從實驗結果來看，在不同的文件分塊大小情況下，本文所提的方法總體上較其他方法的譯碼時間開銷更低.

實驗3.在實驗平臺上構建(9,4)柯西RS糾刪碼作為容錯方法，將原始數據編碼后按序存儲到各個存儲節(jié)點中，計算有限域為GF(28).可知該存儲系統(tǒng)的節(jié)點容錯能力為5，即最多5個節(jié)點失效后，其數據可以得到有效恢復.分別使其中的1～5個存儲節(jié)點失效，并用新的節(jié)點替換后，采用文中的方法與本文方法進行數據重構，數據重構的時間開銷變化如圖9所示.

Table 2 Comparison of the Time Cost of Reconstructing a Single Failed Node

Table 3 Comparison of the Time Cost of Reconstructing Two Failed Nodes

Fig. 9 Comparison of the time cost of four different methods to reconstruct different number of failed nodes圖9 4種不同方法重構不同數量失效節(jié)點的時間開銷 對比

不難看出，采用基于校驗矩陣的譯碼方法進行數據重構的時間開銷會隨著所需重構節(jié)點數的增加而逼近基于生成矩陣的譯碼方法，文中的方法整體時間開銷比本文要高一些，而采用新方法進行數據重構的時間開銷則總體隨著所需重構數據量的增加而線性增加.

實驗4和實驗5主要是將本文所提方法與硬件加速方法Jerasure[18]、降低有限域規(guī)模的方法[20]進行比較.Jerasure[18]采用了硬件加速方法，屬于硬件類方法，其通過SSE指令集來加速編解碼的速度，并且支持不同的有限域上的編碼運算，對RS編碼和柯西RS編碼的支持較好.Jerasure已經發(fā)展到2.0版本，該方法在僅使用SSE的情況下，依然能夠有效地提升RS類糾刪碼的編譯碼表現.降低有限域規(guī)模的方法主要是將運算進行分解以便在較小的有限域上執(zhí)行以降低有限域運算的開銷.

實驗4.在分布式存儲實驗平臺上以柯西RS糾刪碼作為其存儲編碼方法，柯西RS編碼參數分別為(4,2)，(5,3)，(7,4)，(7,3)，計算有限域同樣為GF(28).對原始文件采用相應的編碼方法進行編碼后將編碼分片存儲到各個存儲節(jié)點中，當1個和2個存儲節(jié)點失效，分別采用硬件加速方法Jerasure[18]、降低有限域規(guī)模的方法[20]和本文方法進行重構，數據重構的時間開銷分別如圖10和圖11所示.

Fig. 10 Comparison of the time cost of three different methods to reconstruct a single failed node圖10 3種不同方法重構單個失效節(jié)點的時間開銷對比

Fig. 11 Comparison of the time cost of three different methods to reconstruct two failed nodes圖11 3種不同方法重構2個失效節(jié)點的時間開銷對比

可以看出，該方法與文獻[20]中基于降低有限域規(guī)模的方法相比其譯碼效率顯著提高，而稍差于硬件加速方法Jerasure[18].

實驗5.在實驗平臺上以柯西RS糾刪碼作為存儲容錯方法，編碼參數為(8,4)，計算有限域為GF(28).經過編碼后將數據分存在不同節(jié)點，節(jié)點失效數目從1開始逐漸增大到4，即最大容錯能力.分別采用硬件加速方法[18]、降低有限域規(guī)模的方法[20]與本文方法進行數據重構，其數據重構時間開銷如圖12所示.

Fig. 12 Comparison of the time cost of three different methods to reconstruct different number of failed nodes圖12 3種不同方法重構不同數量失效節(jié)點的時間開銷 對比

從圖12中可以看出，本文所述方法的譯碼時間較降低有限域規(guī)模方法大幅降低，較硬件加速方法偏高，并隨著失效節(jié)點數目的增加譯碼時間增長速度較緩.

從實驗4和實驗5的結果來看，本文所提的方法的譯碼表現比同屬于軟件類的非理論改進的降低有限域規(guī)模的方法[20]的表現要好，比基于硬件加速方法的Jerasure[18]表現要差一些.因本文的研究內容及改進方法都是屬于軟件方法領域，故從軟件方法的角度來講，本文所提的方法比其他軟件理論改進方法要優(yōu)，而本文所提的理論方法改進與硬件方法的改進并不是對立的，可以將理論方法改進與硬件加速結合來進一步提升編譯碼效率，這可以作為以后的一個研究方向.

3.2 適用于XOR類糾刪碼譯碼

一般而言，XOR類糾刪碼的構造均有一定幾何形式的規(guī)律，在編譯碼操作中通常會基于碼鏈關系進行，這種做法直觀形象且更加容易理解，因此最頻繁使用的是二進制的異或運算.和RS類糾刪碼一樣，XOR類糾刪碼也是線性碼的1個子類，它繼承了線性碼的所有性質，而對所有線性碼的譯碼方法也能適用.比如，在本文第1節(jié)中構造的RDP碼，它的生成矩陣即為1個24×16的矩陣G，而原始數據元素也可以表示為1個16×1的列向量D，RDP碼的碼字仍然可以計算得出：C=G×D，其中矩陣G、數據向量D和碼字向量C中的元素均為0或者1.所有操作涉及的乘法即為二進制與，而加法則為二進制異或，換句話說XOR類糾刪碼的運算在有限域GF(2)上進行.而在GF(2)中，1+1=0，顯然其特征為2，所以，本文中講到的基于生成矩陣譯碼的方法、基于校驗矩陣譯碼的方法和本文提出的新方法均能適用于XOR類糾刪碼.

實驗6.在實驗平臺上，使用素數5構建1個RDP碼作為容錯方法，其存儲陣列尺寸為4×6，計算有限域為GF(2).將原始數據編碼后按序存儲到各個存儲節(jié)點中，分別使其中的第0個存儲節(jié)點失效，以及第0個和第2個存儲節(jié)點同時失效，并用新的節(jié)點替換后，數據重構的時間開銷如圖13所示.

Fig. 13 Time cost of reconstructing in the RDP codes storage system圖13 基于RDP碼存儲系統(tǒng)中的數據重構時間開銷

不難看出，對于基于二進制運算的糾刪碼譯碼，采用基于碼鏈關系的譯碼方法的計算時間開銷最小，本文的新方法在計算時間開銷上相比略高.

但是，如第1節(jié)所述，成功使用基于碼鏈的譯碼方法進行數據重構的關鍵為能找到僅有1個失效元素的碼鏈，而如果不存在這樣的碼鏈，則顯然無法使用該方法.容易驗證，使用素數5構造的EVENODD碼，假設其第0列和第2列發(fā)生錯誤失效(并沒有超過EVENODD碼的容錯能力)，則無法使用基于碼鏈的譯碼方法恢復失效數據.而使用本文提出的譯碼方法則能順利恢復所有失效數據.

3.3 數據重構的參與節(jié)點規(guī)劃

將糾刪碼作為容錯方法的存儲系統(tǒng)中，失效節(jié)點的數據重構過程，是從有效節(jié)點中傳入與失效數據有相關性的數據并通過計算達到恢復丟失數據的目的.通常而言，恢復丟失數據可以有不止1種重構方案，換句話說，碼元的線性表達式一般不止1個.如果在實際存儲系統(tǒng)的運行過程中，存在某些負載過重的節(jié)點，則從系統(tǒng)整體運行效率的角度而言是不希望這些節(jié)點再參與到重構過程中的.本節(jié)將通過1個典型示例說明如何使用本文的譯碼方法規(guī)劃參與數據重構的有效節(jié)點.

繼續(xù)沿用2.2節(jié)中的示例，在實驗平臺上構建(7,4)柯西RS糾刪碼作為容錯方法，將原始數據編碼后生成的各個碼元按序存儲到各對應存儲節(jié)點中，計算有限域為GF(28).該柯西RS糾刪碼的生成矩陣如式(7)所示，若數據元素向量為D=(1,2,3,4)T，則計算得到的碼元向量為C=(1,2,3,4,0,241,160)T.仍然假設碼元C0和C2失效，即存儲系統(tǒng)中第0個和第2個節(jié)點失效.將2.4節(jié)計算出的譯碼矩陣記作R：

(12)

因此根據譯碼矩陣R的第0行和第2行可知，這2個失效節(jié)點上的數據全部可由式(11)計算得出.恢復失效碼元用到的有效碼元為c1,c3,c4,c5，即存儲系統(tǒng)中對應的第1，3，4，5個節(jié)點上的數據參與了數據重構的過程.

若在存儲系統(tǒng)的運行過程中，某個有效節(jié)點的負載較重，不希望其參與數據重構的過程，則可以檢查此時的譯碼變換矩陣的子矩陣S_down，在矩陣S_down中，若該節(jié)點對應的列上存在非0元素則可以規(guī)劃該節(jié)點不參加重構運算，若該節(jié)點對應的列上元素全部為0，則該節(jié)點必需參加到失效節(jié)點的重構中.

具體操作時，首先檢查某有效節(jié)點對應矩陣S_down中的列是否為全0，若不是則可以在譯碼方法執(zhí)行時將該列對應的碼元看作失效.比如2.2節(jié)的示例中，假設我們不希望節(jié)點1參與重構運算，則首先檢查矩陣S_down的第1列，發(fā)現該列為(0,0,207)T，不是全0列，因此節(jié)點1可以不參與重構運算.在譯碼時將節(jié)點1也作為失效節(jié)點對待，即設置F={c0,c1,c2}，然后再執(zhí)行譯碼方法進行數據重構.這樣最終得到的譯碼矩陣R：

(13)

根據譯碼矩陣R，2個失效節(jié)點上的數據可計算得出：

(14)

顯然節(jié)點1此時不再參與失效數據的重構.

當然，計算完成后，譯碼變換矩陣的子矩陣S_down也變?yōu)榱肆憔仃?，換句話說，3個刪除錯誤已經達到了該編碼的最大容錯能力，任意的第4個節(jié)點如果失效將導致所有數據丟失不可恢復.將本來有效的節(jié)點作為失效節(jié)點，我們是使用這一策略來規(guī)避該有效節(jié)點參與重構運算.所以，使用本文方法來進行重構運算的節(jié)點規(guī)劃時有如下結論成立：

對于r容錯能力的糾刪碼，當有f個節(jié)點失效時，我們最多能避免r-f個有效節(jié)點參與重構運算，其中r,f為正整數，且f≤r.

4 總 結

本文提出了一類新的RS類糾刪碼的譯碼方法，該方法完全避免了在有限域上計算復雜度很高的矩陣求逆運算，僅通過簡單的矩陣初等變換，使用加法和乘法即可對失效數據進行重構.經實驗表明，該方法與目前RS類糾刪碼譯碼主要使用的基于生成矩陣和校驗矩陣的方法相比，整體譯碼的計算時間開銷有較大幅度的降低.雖然是為了降低RS類糾刪碼譯碼計算代價提出，但該方法同樣適用于XOR類糾刪碼等其他類型的糾刪碼.此外，新的方法經過少量改動，即可對參與重構運算的有效節(jié)點做出動態(tài)規(guī)劃，有利于平衡存儲系統(tǒng)的整體性能.

作者貢獻聲明：唐聃提出了算法思路和實驗方案；蔡紅亮提出指導意見并修改論文；耿微負責完成實驗并撰寫論文.