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

X碼的想法也很簡(jiǎn)單，仍然是在陣列中采用主對角線(xiàn)和輔對角線(xiàn)兩種校驗，但是通過(guò)巧妙地將校驗單元分布到各個(gè)磁盤(pán)中(而不是像其他方法中，校驗單元被分離出來(lái)，獨立存放于校驗盤(pán))，使得系統同時(shí)達到了兩方面指標同時(shí)最優(yōu)。

為了滿(mǎn)足雙容錯的要求，X碼也要求陣列中包含的列數(或說(shuō)碼長(cháng))為素數。碼長(cháng)為素數p的X碼中，每一列包含p-2個(gè)用戶(hù)數據單元，2個(gè)冗余校驗單元。

3.6 B碼

是否還存在與X碼相同特性的其他編碼方案呢?顯然將兩個(gè)X碼陣列重疊，系統仍然保持最優(yōu)冗余與最優(yōu)更新復雜度。

這樣得到的新編碼，在磁盤(pán)數目不變的情況下，每塊盤(pán)需要關(guān)聯(lián)的單元數目加倍。而在實(shí)際中，為了簡(jiǎn)化實(shí)現，我們實(shí)際上需要每塊盤(pán)關(guān)聯(lián)的單元數目盡量少。對于n塊磁盤(pán)，在保持最優(yōu)冗余與最優(yōu)更新復雜度的條件下，每塊盤(pán)最少需要多少個(gè)單元來(lái)關(guān)聯(lián)校驗呢?文獻[10]提出的B碼在雙容錯的情況下很好地解決了這一問(wèn)題。

通過(guò)將編碼構造等同于圖論中的完全圖完美-因子分解問(wèn)題。并根據圖論已有的結論，給出一種各方面性能均達到最優(yōu)的編碼。依據一個(gè)完全圖的一種完美1因子分解方案，我們可以構造如表8所示的雙容錯編碼——B碼。

這種編碼，每塊磁盤(pán)包含至多1個(gè)校驗單元，并且只有一塊磁盤(pán)不包含校驗單元。它將n個(gè)符號的所有2元組分劃為多列，并且滿(mǎn)足雙容錯要求，因而在保持了最優(yōu)冗余度與更新復雜度的前提下，碼長(cháng)達到最長(cháng)。因而這種編碼也被稱(chēng)做最長(cháng)最低密度陣列碼。

3.7 T碼

對于3容錯的最長(cháng)最低密度陣列碼的構造較之雙容錯要復雜很多。文獻[11]最先給出了一種這樣的構造，并利用計算機輔助證明了某些參數下，3、4容錯最長(cháng)最低密度陣列碼的MDS性。在文獻[12]中獨立構造了同樣的編碼并利用組合結構近乎可分的不完全區組設計(NRB)給出了這種編碼的組合解釋?zhuān)瑫r(shí)也給出了簡(jiǎn)明的代數證明。

T碼從形式上與B碼相同，每塊磁盤(pán)包含至多1個(gè)校驗單元，并且只有一塊磁盤(pán)不包含校驗單元。文獻[12]證明了對于任意容錯的最長(cháng)最低密度陣列碼均滿(mǎn)足這種性質(zhì)。

對于普遍參數的T碼，或任意容錯的最長(cháng)最低密度陣列碼的構造，仍是困難問(wèn)題。

3.8 Weaver碼

前面的編碼都將優(yōu)化冗余率最優(yōu)設為第一目標，同時(shí)兼顧編碼/更新復雜度。但在一些系統中，如果冗余率的適當損失可換來(lái)更好的性能或更易于部署，則也是可選擇的。文獻[13]從優(yōu)先考慮系統編碼/更新復雜度的角度，提出了易于構造的Weaver碼。

由B碼、T碼的構造也可以看出，在保持更新復雜度最優(yōu)的前提下，校驗單元分布在各磁盤(pán)中的編碼比較容易構造。為了簡(jiǎn)化問(wèn)題，文獻[13]選擇具有循環(huán)對稱(chēng)性的陣列進(jìn)行研究。也就是說(shuō)要求編碼滿(mǎn)足：(1)所有數據單元參與的校驗組數為常數;(2)所有校驗組包含的單元數目為常數;(3)如果磁盤(pán)i上的數據單元j參與磁盤(pán)k上的校驗單元p所代表的校驗組，則必有對于任何0≤x

為了更容易地得到k容錯編碼，文獻[13]放寬了冗余的要求，只研究每塊磁盤(pán)中，冗余校驗單元不少于用戶(hù)數據單元的情況。這樣，Weaver碼的最好冗余率只有50%。

4 結束語(yǔ)

陣列碼盡管有著(zhù)很多性能優(yōu)勢，但在目前的存儲系統中，還是RS碼及層疊RAID(如RAID1+0等)使用得比較多。筆者認為其原因主要為以下幾個(gè)方面：

首先是實(shí)現上的簡(jiǎn)單性因素：RS碼已經(jīng)是工業(yè)界流行的技術(shù)，無(wú)論軟硬件都有成熟的實(shí)現方案，而層疊RAID原理十分簡(jiǎn)單，所以這兩種編碼實(shí)施最簡(jiǎn)單易行。與之相對，陣列碼多種多樣、原理復雜，實(shí)施需要一定的投入。目前海量存儲系統正處于發(fā)展階段，什么是“最好的”編碼尚不能形成定論，因而就目前階段來(lái)講，最簡(jiǎn)單的就是最好的。

其次，受到目前大部分應用的存儲需求影響：盡管將多個(gè)單個(gè)部件合成一個(gè)統一的虛擬部件會(huì )有好處，但也會(huì )有相應的問(wèn)題。如對10 000塊磁盤(pán)是合成1個(gè)系統好呢?還是組成10每個(gè)包含1 000塊磁盤(pán)的小系統好呢?這要根據需求來(lái)判斷。一般來(lái)說(shuō)小一些的系統會(huì )更容易管理和維護。目前只有極少的應用需要對超過(guò)1 000塊盤(pán)容量的數據并行的處理，因而將系統分為多個(gè)較小系統是有益的。

第三，硬盤(pán)的造價(jià)較低且發(fā)展迅速：這使得人們可以比較“奢侈”地使用存儲空間，因而大型存儲系統的建造目前還處于“粗曠經(jīng)營(yíng)”階段。相對于易實(shí)施性、易維護性、易擴展性，當前階段冗余率還并不是主要決定因素。

但是，隨著(zhù)單磁盤(pán)容量的日趨飽和，系統對性能、容錯、節能等需求的不斷變化，海量存儲系統構造相應的也會(huì )不斷發(fā)展。明天的存儲系統將會(huì )需要具備什么特性的編碼形式，還需我們不斷探索。