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

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

為了滿足雙容錯(cuò)的要求，X碼也要求陣列中包含的列數(shù)(或說(shuō)碼長(zhǎng))為素?cái)?shù)。碼長(zhǎng)為素?cái)?shù)p的X碼中，每一列包含p-2個(gè)用戶數(shù)據(jù)單元，2個(gè)冗余校驗(yàn)單元。

3.6 B碼

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

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

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

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

3.7 T碼

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

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

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

3.8 Weaver碼

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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