網(wǎng)絡(luò )存儲系統容錯編碼技術(shù)進(jìn)展

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

1 存儲容錯編碼評價(jià)指標

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

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

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

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

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

分析表明[1]，對于k容錯的系統來(lái)說(shuō)，可以近似估計為：

因而，在大規模系統中，容錯數可以說(shuō)是另一種對系統可靠性的描述方式。市場(chǎng)中一般磁盤(pán)的MTTFdisk為105左右，系統修復時(shí)間MTTR一般為10左右。根據(1)式可以看出，當系統磁盤(pán)數為103～104時(shí)，一般2容錯或是3容錯編碼就基本上可以滿(mǎn)足存儲系統的容錯要求。

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

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

綜合上面討論，存儲系統容錯編碼問(wèn)題可以歸結為尋求對如下指標進(jìn)行優(yōu)化的編碼方法

系統滿(mǎn)足需要的容錯性能，容錯數為k的系統。

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

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

2 線(xiàn)性編碼

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

2.1 多維陣列碼

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

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

2.2 Full碼

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

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

2.3 RS碼

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

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