網絡存儲系統容錯編碼技術進展

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

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

3.6 B碼

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

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

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

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

3.7 T碼

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

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

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

3.8 Weaver碼

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

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

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

4 結束語

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

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

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

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

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