網(wǎng)絡存儲系統(tǒng)容錯編碼技術(shù)進展

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

為了滿足雙容錯的要求，X碼也要求陣列中包含的列數(shù)(或說碼長)為素數(shù)。碼長為素數(shù)p的X碼中，每一列包含p-2個用戶數(shù)據(jù)單元，2個冗余校驗單元。

3.6 B碼

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

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

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

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

3.7 T碼

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

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

對于普遍參數(shù)的T碼，或任意容錯的最長最低密度陣列碼的構(gòu)造，仍是困難問題。

3.8 Weaver碼

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

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

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

4 結(jié)束語

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

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

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

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

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