唐 聃 蔡紅亮 耿 微

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

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

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

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

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

本文工作的主要貢獻(xiàn)包括3個(gè)方面：

1) 提出了一種針對(duì)RS類(lèi)糾刪碼碼刪除錯(cuò)誤的譯碼方法，適用于存儲(chǔ)系統(tǒng)中的失效數(shù)據(jù)重構(gòu)，由于不再使用計(jì)算復(fù)雜度很高的矩陣求逆運(yùn)算，能很大程度節(jié)省RS類(lèi)糾刪碼的譯碼時(shí)間開(kāi)銷(xiāo)；

2) 新的譯碼方法也可以推廣到所有的二進(jìn)制XOR類(lèi)糾刪碼；

3) 對(duì)該譯碼方法的研究表明：該方法還能在數(shù)據(jù)重構(gòu)時(shí)規(guī)避某些節(jié)點(diǎn)的參與，可用于大規(guī)模存儲(chǔ)系統(tǒng)的數(shù)據(jù)重構(gòu)時(shí)對(duì)重構(gòu)參與節(jié)點(diǎn)的使用進(jìn)行整體規(guī)劃.

1 相關(guān)工作及研究動(dòng)機(jī)

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

1.1 基于碼鏈的譯碼方法

Fig. 1 Data layout of RDP code圖1 RDP碼的布局結(jié)構(gòu)

大多XOR類(lèi)糾刪碼的構(gòu)造可以由幾何形式表示，即碼字中所有存在校驗(yàn)關(guān)系的數(shù)據(jù)位和校驗(yàn)位的集合可以看作1條碼鏈[2]，1條碼鏈即對(duì)應(yīng)1個(gè)校驗(yàn)方程.特別是在陣列碼中，如果用線連接碼鏈上的所有碼元?jiǎng)t通常具有一定的幾何規(guī)律.

以RDP碼[6]為例，使用素?cái)?shù)5構(gòu)造出RDP碼的碼字結(jié)構(gòu)如圖1所示：

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

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

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

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

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

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

Fig. 3 Encoding process of RS code圖3 RS碼的編碼過(guò)程

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

使用生成矩陣乘以由數(shù)據(jù)元素組成的列向量，從而得到由各碼字元素構(gòu)成的碼字列向量.由矩陣的乘法定義可知，生成矩陣的第i行構(gòu)成的行向量乘以數(shù)據(jù)元素構(gòu)成的列向量得到碼字向量的第i個(gè)碼元，因此生成矩陣的第i行與碼字向量的第i個(gè)碼元存在對(duì)應(yīng)關(guān)系.換句話(huà)說(shuō)，抽取生成矩陣的任意行而組成的子矩陣，乘以數(shù)據(jù)元素構(gòu)成的列向量，如果也選取碼字向量中與生成矩陣抽取行相同位置的碼元構(gòu)成新的列向量，則圖3中的等式仍然成立.

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

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

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

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

1.3 基于校驗(yàn)矩陣的譯碼方法

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

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

Fig. 5 The check matrix and correspondence between its column vectors and code elements圖5 校驗(yàn)矩陣及列向量與碼字元素的對(duì)應(yīng)關(guān)系

由校驗(yàn)矩陣的定義可知，校驗(yàn)矩陣的每一列與碼字中的各個(gè)碼元一一對(duì)應(yīng)：

(1)

將校驗(yàn)矩陣記作H，碼字向量記作C，則在所有碼元沒(méi)有錯(cuò)誤發(fā)生時(shí)恒有等式H×C=0成立.

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

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

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

1.4 本文的研究動(dòng)機(jī)

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

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

2 一類(lèi)新的RS類(lèi)糾刪碼的譯碼方法

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

2.1 碼元關(guān)系矩陣

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

(2)

本文將該非齊次線性方程組的系數(shù)矩陣定義為碼元關(guān)系矩陣W.

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

(3)

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

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

性質(zhì)1.對(duì)碼元關(guān)系矩陣進(jìn)行任何初等行變換后的結(jié)果不再是碼元關(guān)系矩陣.

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

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

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

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

下面就這3類(lèi)初等行變換進(jìn)行分別說(shuō)明：

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

2) 不妨假設(shè)將第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為整數(shù)且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)已經(jīng)不再是第i個(gè)元素ci的線性表達(dá)，因此，在線性關(guān)系矩陣中，把矩陣的某一行的t倍加到另一行之后的結(jié)果不再是線性關(guān)系矩陣.

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

證畢.

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

證明.根據(jù)碼元關(guān)系矩陣的定義可知，碼元關(guān)系矩陣的第i行Wi=(ai,0,ai,1,…,ai,n-1)為碼字C中第i個(gè)碼元ci由所有碼元的其中1種線性表示：ci=ai,0c0+ai,1c1+…+ai,n-1cn-1.則等式ci=ai,0c0+ai,1c1+…+ai,n-1cn-1+0顯然成立.而根據(jù)前提條件，對(duì)于向量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)也成立，對(duì)該等式歸并同類(lèi)項(xiàng)后得到等式：ci=(ai,0+tv0)c0+(ai,1+tv1)c1+…+(ai,n-1+tvn-1)cn-1.

顯然，這也是對(duì)第i個(gè)碼元ci的一類(lèi)線性表示.因此，將向量v的t倍加到線性關(guān)系矩陣任意行后的結(jié)果仍然是同一碼字的碼元關(guān)系矩陣.

證畢.

2.2 失效數(shù)據(jù)恢復(fù)步驟

不妨假設(shè)在有限域GF(q)上構(gòu)建1個(gè)(n,k)RS糾刪碼，其中q=pw，p為素?cái)?shù)，w,n,k均為正整數(shù)，且k

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

步驟1.初始化碼元關(guān)系矩陣.生成1個(gè)尺寸為n×n的單位矩陣In×n，根據(jù)碼元關(guān)系矩陣的定義，因?yàn)閏i=ci，i為整數(shù)且0≤i≤n-1，因此In×n可以作為初始的碼元關(guān)系矩陣Wn×n，記作：

(4)

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

在這種嚴(yán)峻的形勢(shì)下，學(xué)校體育教學(xué)只有不斷喚醒學(xué)生的運(yùn)動(dòng)體驗(yàn)才能徹底轉(zhuǎn)變這種劣勢(shì)，才能使學(xué)生在運(yùn)動(dòng)體驗(yàn)中獲得強(qiáng)烈的快感，才能轉(zhuǎn)變學(xué)生們對(duì)于體育課程的看法，才能增強(qiáng)學(xué)生的健康意識(shí)，使其全身心的投入到體育實(shí)踐活動(dòng)中來(lái)。從當(dāng)前學(xué)生對(duì)于學(xué)校體育教學(xué)的認(rèn)識(shí)來(lái)看，他們普遍認(rèn)為學(xué)習(xí)體育對(duì)其沒(méi)有任何意義，只能作為緊張忙碌的文化學(xué)習(xí)后緩解疲憊身心的一種方式。因此，學(xué)校體育教學(xué)應(yīng)當(dāng)使學(xué)生們對(duì)于體育教學(xué)有一個(gè)重新的認(rèn)識(shí)，要讓他們了解到體育可以在調(diào)節(jié)情緒的同時(shí)成為他們學(xué)習(xí)下一門(mén)學(xué)科的一大助力。學(xué)校體育教學(xué)只有通過(guò)不斷縮短運(yùn)動(dòng)和生活的距離，才能使學(xué)生們?nèi)媪私獾襟w育的內(nèi)涵。

(5)

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

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

在每次進(jìn)行譯碼變換矩陣的變換過(guò)程中，由于只進(jìn)行了行變換，那么對(duì)于S_upi和S_downi，第i列均對(duì)應(yīng)著碼字中的第i個(gè)碼元，因此譯碼變換矩陣Si的每一列與碼元也有相同的對(duì)應(yīng)關(guān)系.

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

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

步驟8.重復(fù)步驟3～7，直到失效碼元集合F為空，即所有失效碼元可成功恢復(fù)，轉(zhuǎn)到步驟9.當(dāng)存在失效碼元不可恢復(fù)時(shí)，終止.

步驟9.此時(shí)Si的上半部分子矩陣S_upi仍然為碼元關(guān)系矩陣，其中包含著有效碼元對(duì)失效碼元的線性關(guān)系，也可簡(jiǎn)稱(chēng)為譯碼矩陣，記R，R=S_upi，顯然，矩陣R的尺寸為n×n，而矩陣R的第si行(列)對(duì)應(yīng)碼字的第si個(gè)碼元.那么失效碼元csi可以進(jìn)行恢復(fù)：

(6)

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

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

2.3 方法的正確性及分析

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

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

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

證畢.

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

證明.分2種情況討論：

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

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

證畢.

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

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

1) 算法復(fù)雜度較低

對(duì)于1個(gè)(n,k)RS編碼而言，k

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

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

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

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

證畢.

2) 可同時(shí)恢復(fù)原始數(shù)據(jù)碼元和校驗(yàn)碼元

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

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

2.4 新方法示例

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

(7)

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

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

(8)

(9)

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

(10)

其中的前7行構(gòu)成的子矩陣S_up2即為可用作失效元素恢復(fù)的碼元關(guān)系矩陣，即譯碼矩陣R.

根據(jù)碼元關(guān)系矩陣的定義可以，2個(gè)失效碼元可以計(jì)算得出:

(11)

3 新方法的性能分析及應(yīng)用擴(kuò)展

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

3.1 RS類(lèi)糾刪碼譯碼的時(shí)間開(kāi)銷(xiāo)

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

實(shí)驗(yàn)1.在實(shí)驗(yàn)平臺(tái)上分別構(gòu)建(4,2)，(5,3)，(7,4)，(7,3)柯西RS糾刪碼作為容錯(cuò)方法，計(jì)算有限域?yàn)镚F(28).將10 MB原始數(shù)據(jù)編碼后按序存儲(chǔ)到各個(gè)存儲(chǔ)節(jié)點(diǎn)中，分別使其中的1個(gè)和2個(gè)存儲(chǔ)節(jié)點(diǎn)失效，在用新的節(jié)點(diǎn)替換后，分別采用基于生成矩陣的譯碼方法[24]、基于校驗(yàn)矩陣的譯碼方法[16]、文獻(xiàn)[25]中的譯碼方法及本文方法重構(gòu)數(shù)據(jù)，其數(shù)據(jù)重構(gòu)的時(shí)間開(kāi)銷(xiāo)分別如圖7和圖8所示.

Fig. 7 Comparison of the time cost of four different methods to reconstruct a single failed node圖7 4種不同方法重構(gòu)單個(gè)失效節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo)對(duì)比

Fig. 8 Comparison of the time cost of four different methods to reconstruct two failed nodes圖8 4種不同方法重構(gòu)2個(gè)失效節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo)對(duì)比

總體來(lái)看，單個(gè)失效節(jié)點(diǎn)失效時(shí)采用基于校驗(yàn)矩陣的譯碼方法進(jìn)行數(shù)據(jù)重構(gòu)的時(shí)間開(kāi)銷(xiāo)最低，新方法略高于此，但是從2個(gè)失效節(jié)點(diǎn)開(kāi)始，采用新譯碼方法進(jìn)行數(shù)據(jù)重構(gòu)的時(shí)間開(kāi)銷(xiāo)就低于另外3種方法.

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

實(shí)驗(yàn)3.在實(shí)驗(yàn)平臺(tái)上構(gòu)建(9,4)柯西RS糾刪碼作為容錯(cuò)方法，將原始數(shù)據(jù)編碼后按序存儲(chǔ)到各個(gè)存儲(chǔ)節(jié)點(diǎn)中，計(jì)算有限域?yàn)镚F(28).可知該存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)容錯(cuò)能力為5，即最多5個(gè)節(jié)點(diǎn)失效后，其數(shù)據(jù)可以得到有效恢復(fù).分別使其中的1～5個(gè)存儲(chǔ)節(jié)點(diǎn)失效，并用新的節(jié)點(diǎn)替換后，采用文中的方法與本文方法進(jìn)行數(shù)據(jù)重構(gòu)，數(shù)據(jù)重構(gòu)的時(shí)間開(kāi)銷(xiāo)變化如圖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種不同方法重構(gòu)不同數(shù)量失效節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo) 對(duì)比

不難看出，采用基于校驗(yàn)矩陣的譯碼方法進(jìn)行數(shù)據(jù)重構(gòu)的時(shí)間開(kāi)銷(xiāo)會(huì)隨著所需重構(gòu)節(jié)點(diǎn)數(shù)的增加而逼近基于生成矩陣的譯碼方法，文中的方法整體時(shí)間開(kāi)銷(xiāo)比本文要高一些，而采用新方法進(jìn)行數(shù)據(jù)重構(gòu)的時(shí)間開(kāi)銷(xiāo)則總體隨著所需重構(gòu)數(shù)據(jù)量的增加而線性增加.

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

實(shí)驗(yàn)4.在分布式存儲(chǔ)實(shí)驗(yàn)平臺(tái)上以柯西RS糾刪碼作為其存儲(chǔ)編碼方法，柯西RS編碼參數(shù)分別為(4,2)，(5,3)，(7,4)，(7,3)，計(jì)算有限域同樣為GF(28).對(duì)原始文件采用相應(yīng)的編碼方法進(jìn)行編碼后將編碼分片存儲(chǔ)到各個(gè)存儲(chǔ)節(jié)點(diǎn)中，當(dāng)1個(gè)和2個(gè)存儲(chǔ)節(jié)點(diǎn)失效，分別采用硬件加速方法Jerasure[18]、降低有限域規(guī)模的方法[20]和本文方法進(jìn)行重構(gòu)，數(shù)據(jù)重構(gòu)的時(shí)間開(kāi)銷(xiāo)分別如圖10和圖11所示.

Fig. 10 Comparison of the time cost of three different methods to reconstruct a single failed node圖10 3種不同方法重構(gòu)單個(gè)失效節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo)對(duì)比

Fig. 11 Comparison of the time cost of three different methods to reconstruct two failed nodes圖11 3種不同方法重構(gòu)2個(gè)失效節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo)對(duì)比

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

實(shí)驗(yàn)5.在實(shí)驗(yàn)平臺(tái)上以柯西RS糾刪碼作為存儲(chǔ)容錯(cuò)方法，編碼參數(shù)為(8,4)，計(jì)算有限域?yàn)镚F(28).經(jīng)過(guò)編碼后將數(shù)據(jù)分存在不同節(jié)點(diǎn)，節(jié)點(diǎn)失效數(shù)目從1開(kāi)始逐漸增大到4，即最大容錯(cuò)能力.分別采用硬件加速方法[18]、降低有限域規(guī)模的方法[20]與本文方法進(jìn)行數(shù)據(jù)重構(gòu)，其數(shù)據(jù)重構(gòu)時(shí)間開(kāi)銷(xiāo)如圖12所示.

Fig. 12 Comparison of the time cost of three different methods to reconstruct different number of failed nodes圖12 3種不同方法重構(gòu)不同數(shù)量失效節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo) 對(duì)比

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

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

3.2 適用于XOR類(lèi)糾刪碼譯碼

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

實(shí)驗(yàn)6.在實(shí)驗(yàn)平臺(tái)上，使用素?cái)?shù)5構(gòu)建1個(gè)RDP碼作為容錯(cuò)方法，其存儲(chǔ)陣列尺寸為4×6，計(jì)算有限域?yàn)镚F(2).將原始數(shù)據(jù)編碼后按序存儲(chǔ)到各個(gè)存儲(chǔ)節(jié)點(diǎn)中，分別使其中的第0個(gè)存儲(chǔ)節(jié)點(diǎn)失效，以及第0個(gè)和第2個(gè)存儲(chǔ)節(jié)點(diǎn)同時(shí)失效，并用新的節(jié)點(diǎn)替換后，數(shù)據(jù)重構(gòu)的時(shí)間開(kāi)銷(xiāo)如圖13所示.

Fig. 13 Time cost of reconstructing in the RDP codes storage system圖13 基于RDP碼存儲(chǔ)系統(tǒng)中的數(shù)據(jù)重構(gòu)時(shí)間開(kāi)銷(xiāo)

不難看出，對(duì)于基于二進(jìn)制運(yùn)算的糾刪碼譯碼，采用基于碼鏈關(guān)系的譯碼方法的計(jì)算時(shí)間開(kāi)銷(xiāo)最小，本文的新方法在計(jì)算時(shí)間開(kāi)銷(xiāo)上相比略高.

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

3.3 數(shù)據(jù)重構(gòu)的參與節(jié)點(diǎn)規(guī)劃

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

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

(12)

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

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

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

(13)

根據(jù)譯碼矩陣R，2個(gè)失效節(jié)點(diǎn)上的數(shù)據(jù)可計(jì)算得出：

(14)

顯然節(jié)點(diǎn)1此時(shí)不再參與失效數(shù)據(jù)的重構(gòu).

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

對(duì)于r容錯(cuò)能力的糾刪碼，當(dāng)有f個(gè)節(jié)點(diǎn)失效時(shí)，我們最多能避免r-f個(gè)有效節(jié)點(diǎn)參與重構(gòu)運(yùn)算，其中r,f為正整數(shù)，且f≤r.

4 總 結(jié)

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

作者貢獻(xiàn)聲明：唐聃提出了算法思路和實(shí)驗(yàn)方案；蔡紅亮提出指導(dǎo)意見(jiàn)并修改論文；耿微負(fù)責(zé)完成實(shí)驗(yàn)并撰寫(xiě)論文.