摘要:專業(yè)的大型磁盤存儲(chǔ)系統(tǒng)均發(fā)展為包含多塊磁盤的大型陣列系統(tǒng)。隨著系統(tǒng)中的磁盤數(shù)目的不斷增加，由磁盤失效引起的數(shù)據(jù)丟失的可能性越來越大。對(duì)于由存儲(chǔ)系統(tǒng)中部分磁盤失效所引起的數(shù)據(jù)丟失的問題，目前業(yè)界公認(rèn)的比較好的解決方案是使用冗余容錯(cuò)編碼技術(shù)來實(shí)現(xiàn)磁盤的容錯(cuò)。在工程實(shí)踐中，目前廣泛應(yīng)用的編碼方法大多局限于雙容錯(cuò)陣列碼。隨著系統(tǒng)規(guī)模的進(jìn)一步加大，3容錯(cuò)甚至更多容錯(cuò)的編碼方法已引起研究者的重視。今后的5至10年間，對(duì)于3容錯(cuò)或多容錯(cuò)的編碼方法的研究將會(huì)成為新的熱點(diǎn)。

1 存儲(chǔ)容錯(cuò)編碼評(píng)價(jià)指標(biāo)

近20年來，隨著計(jì)算機(jī)技術(shù)的迅猛發(fā)展，大規(guī)模存儲(chǔ)系統(tǒng)的發(fā)展也十分迅速。當(dāng)前，普通PC機(jī)的存儲(chǔ)器的容量已經(jīng)達(dá)到了太比特級(jí)別，這較之20年前的20 MB存儲(chǔ)容量提高了10 000倍。

除了傳統(tǒng)的磁盤驅(qū)動(dòng)器之外，新型的固態(tài)存儲(chǔ)(SSD)存儲(chǔ)器也已經(jīng)走向市場。盡管單個(gè)存儲(chǔ)器的容量發(fā)展迅速，但是卻仍然趕不上人們對(duì)存儲(chǔ)容量需求的增長速度。

隨著大型計(jì)算機(jī)系統(tǒng)由“以計(jì)算為中心”向著“以信息處理為中心”的轉(zhuǎn)變，以及信息量的爆炸式增長，人們對(duì)海量存儲(chǔ)系統(tǒng)的需求日益提高。海量存儲(chǔ)系統(tǒng)本質(zhì)上是將很多的單個(gè)存儲(chǔ)器件(下面均以磁盤為例)，通過系統(tǒng)的接口，連接整合為一個(gè)虛擬的容量巨大的單一存儲(chǔ)器，即磁盤陣列。

隨著陣列中磁盤數(shù)目的增多，系統(tǒng)的可靠性也隨之下降。工業(yè)界一般使用平均數(shù)據(jù)丟失時(shí)間(MTTDL)來衡量陣列的可靠性。

設(shè)單個(gè)磁盤的平均失效時(shí)間為MTTFdisk，則對(duì)于包含n塊磁盤的無冗余陣列來說，其MTTDL可簡單估計(jì)為：MTTDL=MTTFdisk/n?？梢姡?dāng)n較大時(shí)，整個(gè)系統(tǒng)的可靠性將成比例下降。這對(duì)于較大規(guī)模的系統(tǒng)來說是不可接受的。利用冗余數(shù)據(jù)編碼來提高系統(tǒng)可靠性是公認(rèn)的解決這一問題的較好方法。通過巧妙地將m塊標(biāo)準(zhǔn)大小的磁盤上的數(shù)據(jù)，增加部分冗余校驗(yàn)信息，編碼后存放于n塊磁盤上，使得系統(tǒng)滿足：對(duì)于任意k塊磁盤失效，都可以通過其他n-k塊未失效盤中的數(shù)據(jù)解碼恢復(fù)，則稱整個(gè)系統(tǒng)是k容錯(cuò)的，或者稱k為系統(tǒng)的容錯(cuò)數(shù)。

分析表明[1]，對(duì)于k容錯(cuò)的系統(tǒng)來說，可以近似估計(jì)為：

因而，在大規(guī)模系統(tǒng)中，容錯(cuò)數(shù)可以說是另一種對(duì)系統(tǒng)可靠性的描述方式。市場中一般磁盤的MTTFdisk為105左右，系統(tǒng)修復(fù)時(shí)間MTTR一般為10左右。根據(jù)(1)式可以看出，當(dāng)系統(tǒng)磁盤數(shù)為103～104時(shí)，一般2容錯(cuò)或是3容錯(cuò)編碼就基本上可以滿足存儲(chǔ)系統(tǒng)的容錯(cuò)要求。

系統(tǒng)用于增加容錯(cuò)能力而添加的冗余越多，系統(tǒng)的額外造價(jià)也將越高。因而在具有相同容錯(cuò)數(shù)的前提下，人們往往追求更小的冗余度，即(n-m)/n的值，其中n為系統(tǒng)磁盤數(shù)、m為存儲(chǔ)用戶數(shù)據(jù)的磁盤數(shù)。根據(jù)編碼理論的Singleton界，k容錯(cuò)系統(tǒng)的最小冗余度為：k/n。達(dá)到這一最小值的編碼方法稱做MDS碼。目前多數(shù)存儲(chǔ)編碼研究都集中于構(gòu)造不同參數(shù)下的MDS碼。

除了上述指標(biāo)，任何計(jì)算機(jī)系統(tǒng)的速度與效率永遠(yuǎn)是需要考量的重要指標(biāo)。這里我們不討論如何有效地并行處理多磁盤中的數(shù)據(jù)讀取(那是另外一個(gè)較大的課題)，而著重研究由于冗余編碼帶來的額外計(jì)算開銷。對(duì)于即便是相同的編碼方法，由于編/解碼算法的不同，可能計(jì)算效率的差異較大。由于在計(jì)算機(jī)系統(tǒng)中，最終的編碼運(yùn)算都會(huì)反映為一些二進(jìn)制運(yùn)算，因而研究者通常使用編碼需要的總的二進(jìn)制異或運(yùn)算次數(shù)來衡量由于額外冗余編碼帶來的系統(tǒng)計(jì)算開銷。對(duì)于一個(gè)隨機(jī)存取的存儲(chǔ)系統(tǒng)來說，隨機(jī)小塊信息寫操作的性能尤為重要。編碼運(yùn)算中每個(gè)單元所參與的平均異或次數(shù)可以用來衡量這一指標(biāo)，我們稱其為編碼的更新復(fù)雜度。

綜合上面討論，存儲(chǔ)系統(tǒng)容錯(cuò)編碼問題可以歸結(jié)為尋求對(duì)如下指標(biāo)進(jìn)行優(yōu)化的編碼方法

系統(tǒng)滿足需要的容錯(cuò)性能，容錯(cuò)數(shù)為k的系統(tǒng)。

系統(tǒng)有較小(或最優(yōu))的冗余度

系統(tǒng)有較小(或最優(yōu))的編碼/更新復(fù)雜度。

2 線性編碼

對(duì)于單容錯(cuò)系統(tǒng)來說，簡單的奇偶校驗(yàn)即可使得上面的3個(gè)指標(biāo)達(dá)到最優(yōu)。經(jīng)典的系統(tǒng)都是使用的這種方法。然而對(duì)于k大于1的情況，問題的解決就不是那么簡單了。從通信編碼理論的豐富成果中，兩種比較有代表性的編碼方法被人們挑選出來，并用于解決存儲(chǔ)容錯(cuò)問題，他們是二進(jìn)制線性碼和RS碼。

2.1 多維陣列碼

圖1所示是二維陣列編碼及校驗(yàn)矩陣。二維陣列碼是奇偶校驗(yàn)的自然推廣，由圖1很容易看出它是雙容錯(cuò)的。二維陣列碼保持了單容錯(cuò)時(shí)奇偶校驗(yàn)碼的最優(yōu)編碼復(fù)雜度的特性，但是二維陣列碼的冗余度不再是最優(yōu)的了。

二維陣列碼也很容易推廣為k維陣列。并且容易得到這樣編碼的k容錯(cuò)特性。但是隨著k的增大，冗余會(huì)越來越大[2-3]。

2.2 Full碼

圖2所示是FULL-2碼。FULL-2碼可看做是二維陣列碼的推廣。

FULL碼依然保持了最優(yōu)的編碼復(fù)雜度，并且冗余度要比陣列碼好很多。然而不幸的是，當(dāng)k大于3時(shí)，F(xiàn)ULL-k碼不再是k容錯(cuò)的[4]。

2.3 RS碼

圖3所示是RS碼的校驗(yàn)矩陣。RS碼從最佳的冗余特性出發(fā)。達(dá)到Singleton界的RS碼被人們提出并廣泛應(yīng)用。

校驗(yàn)矩陣通過線性變換可以化為系統(tǒng)矩陣，用存儲(chǔ)系統(tǒng)的語言亦可顯式地區(qū)分出系統(tǒng)中哪些單元用于存儲(chǔ)校驗(yàn)單元?？梢钥闯?，矩陣中的元素不再是“0”、“1”，而為有限域元素的冪，故編碼需要使用有限域運(yùn)算。在計(jì)算機(jī)系統(tǒng)中，有限域元素最后還是會(huì)被映射為“0”、“1”單元。這時(shí)每個(gè)有限域元素一般會(huì)被映射為多個(gè)“0”、“1”單元，而有限域運(yùn)算也可以被分解為這些“0”、“1”單元的復(fù)雜運(yùn)算。我們?nèi)匀灰跃幋a所需的異或運(yùn)算為基本單位，則編碼所需的異或運(yùn)算次數(shù)和編碼算法的巧妙程度有關(guān)。目前較好的域運(yùn)算算法所需的異或次數(shù)大約為O(n3)[5]，計(jì)算復(fù)雜度相當(dāng)高。RS碼是MDS碼，故冗余度是最優(yōu)的。