1 存儲容錯編碼評價指標(biāo)

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

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

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

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

　　設(shè)單個磁盤的平均失效時間為MTTFdisk，則對于包含n塊磁盤的無冗余陣列來說，其MTTDL可簡單估計為：MTTDL=MTTFdisk/n。可見，當(dāng)n較大時，整個系統(tǒng)的可靠性將成比例下降。這對于較大規(guī)模的系統(tǒng)來說是不可接受的。利用冗余數(shù)據(jù)編碼來提高系統(tǒng)可靠性是公認(rèn)的解決這一問題的較好方法。通過巧妙地將m塊標(biāo)準(zhǔn)大小的磁盤上的數(shù)據(jù)，增加部分冗余校驗信息，編碼后存放于n塊磁盤上，使得系統(tǒng)滿足：對于任意k塊磁盤失效，都可以通過其他n-k塊未失效盤中的數(shù)據(jù)解碼恢復(fù)，則稱整個系統(tǒng)是k容錯的，或者稱k為系統(tǒng)的容錯數(shù)。

　　分析表明[1]，對于k容錯的系統(tǒng)來說，可以近似估計為：

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

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

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

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

　　系統(tǒng)滿足需要的容錯性能，容錯數(shù)為k的系統(tǒng)。

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

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

　　2 線性編碼

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

　　2.1 多維陣列碼

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

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

　　2.2 Full碼

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

　　FULL碼依然保持了最優(yōu)的編碼復(fù)雜度，并且冗余度要比陣列碼好很多。然而不幸的是，當(dāng)k大于3時，F(xiàn)ULL-k碼不再是k容錯的[4]。2.3 RS碼

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

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

　　3 陣列編碼

　　上述幾種編碼各有優(yōu)缺點，那么是否存在對于多指標(biāo)同時最優(yōu)的k容錯編碼方法呢?自文獻(xiàn)[5]提出EVENODD碼起，一大類只使用異或運算的陣列編碼被提出并被人們廣泛研究。

　　多維陣列或FULL碼等二進(jìn)制線性碼每塊磁盤只取一個邏輯單元進(jìn)行校驗運算。而陣列碼則在每塊磁盤上取多個邏輯單元，一起交叉進(jìn)行校驗運算。校驗計算同2進(jìn)制線性碼一樣，只使用二進(jìn)制異或運算，但冗余度卻可以與RS碼相同。

　　3.1 EVENODD碼

　　EVENODD碼的想法很簡單，每塊磁盤中取若干單元，排成方陣，然后將這些單元分成不同的校驗組，另外添加兩塊磁盤用于存儲校驗單元。所有校驗組均使用簡單的二進(jìn)制奇偶校驗。

　　水平校驗與對角校驗如表1所示。表1中D代表用戶數(shù)據(jù)單元，P代表冗余校驗單元?？梢钥闯觯珼isk1—Disk5存儲用戶數(shù)據(jù)單元;Disk6、7存儲冗余校驗單元。Disk6的各單元為用戶數(shù)據(jù)各行的水平校驗和，而Disk7的各單元為用戶數(shù)據(jù)的輔對角線校驗和。

　　設(shè)存儲用戶數(shù)據(jù)盤的數(shù)目為p(如上例中p=5)，則系統(tǒng)包含p+2塊磁盤，前p+1塊磁盤中的最后一個單元為虛擬0元，故每盤實際包含p-1個單元，最后一塊磁盤包含p個單元?？梢宰C明，當(dāng)p為素數(shù)時系統(tǒng)是雙容錯的。

　　簡單計算可知此時的系統(tǒng)的冗余度為(2p-1)/((p+2)(p-1)+1)。由于最后的校驗盤多出一個單元，所以冗余度稍稍大于最優(yōu)的2/(p+2)。為了達(dá)到最優(yōu)值，文獻(xiàn)[5]中使用如下技巧：將多出的單元(即輔對角交驗和)疊加到該盤其他單元上，構(gòu)造MDS的EVENODD碼如表2所示。

　　表2也可表示為如表3所示。

　　也就是說當(dāng)?shù)谝惠o對角校驗和為1時，其他各對角校驗為奇校驗;當(dāng)?shù)谝惠o對角校驗和為0時，其他各對角校驗為偶校驗。這就是它被命名為EVENODD碼的原因。

　　3.2 RDP碼

　　從表2可以看出，為了得到冗余最優(yōu)，EVENODD碼的輔對角線上的單元的更新復(fù)雜度很高。每次更新這些單元的數(shù)據(jù)時都要同時更新其他p個校驗單元。對于雙容錯編碼來說，最優(yōu)值為2。文獻(xiàn)[6]中構(gòu)造的RDP編碼將這些單元的更新復(fù)雜度均衡到每個單元，從而有效地消除了寫操作中更新性能的不均衡。一個包含水平校驗的對角線校驗如表4所示。

　　與EVENODD不同處在于，做對角校驗時也包含了水平校驗單元的一列(因此，數(shù)據(jù)單元也比EVENODD少了一列)。

　　同樣的，RDP的最后一個校驗盤多出一個單元，使得整個系統(tǒng)不為MDS碼。但RDP碼的優(yōu)勢在于，簡單地將多出的單元刪去，系統(tǒng)仍然為雙容錯的。即得到如表5所示陣列。

　　從表5可以看出，所有數(shù)據(jù)單元的更新負(fù)載為2或3，分布比EVENODD碼要均勻，不會產(chǎn)生由編碼方式帶來的額外“瓶頸”，但系統(tǒng)的平均更新復(fù)雜度是相同的。3.3 Liberation碼

　　從前面幾種編碼可以看出，所使用的方法都是水平校驗加其他一種校驗共同構(gòu)成雙容錯。不同之處就在于“另一種校驗”的不同選擇。如將另一校驗盤上的校驗元看作一個“0”、“1”向量，每塊數(shù)據(jù)盤上的單元對這些校驗元的影響可用一個“0”、“1”矩陣來表示。如表5中的第1列的4個數(shù)據(jù)單元對Disk7中的各校驗元的影響可表示為如圖4所示矩陣。

　　在這種表示下，前面所說的更新復(fù)雜度就對應(yīng)著矩陣中1的個數(shù)。于是構(gòu)造一個雙容錯陣列碼的問題就轉(zhuǎn)變?yōu)椋簩ふ胰舾蓚€這樣的矩陣，使得其中1的個數(shù)盡量少，并且任意2個之和為滿秩。

　　在p為素數(shù)時，文獻(xiàn)[7]中構(gòu)造的Liberation碼使得p×p階矩陣1的數(shù)目不超過p+1，其構(gòu)造的p個矩陣可簡單地描述為：各對角線加一個額外單元。第k個矩陣的額外的1單元的位置可描述為(k(p-1)/2 Mod p,1+k(p=1)/2 Mod p)。得到的編碼如表6所示。

　　3.4 PDHLatin碼

　　前面這些編碼為MDS碼的充要條件均為：碼長與素數(shù)相關(guān)(RDP為p+1，其他為p+2)。它們的雙容錯解碼方法均為根據(jù)一個已知單元，然后通過校驗關(guān)系與失效單元形成的鏈?zhǔn)疥P(guān)系依次恢復(fù)所有單元。這使人們理解到其容錯能力的本質(zhì)是任意兩列都可以形成這樣的關(guān)聯(lián)結(jié)構(gòu)。文獻(xiàn)[8]中利用拉丁方構(gòu)造了PDHLatin碼，使得碼長不再必須關(guān)聯(lián)一個素數(shù)。

　　所謂拉丁方是指n×n的方陣中填入n個不同符號，使得每行每列的符號都不重復(fù)。顯然拉丁方的每兩列構(gòu)成一個n元置換。所謂漢密爾頓拉丁方是指拉丁方的任何兩列構(gòu)成的置換為單環(huán)的。圖5為一個9階漢密爾頓拉丁方。

　　從一個給定的漢密爾頓拉丁方，我們可以用與EVENODD碼類似的方法構(gòu)造編碼，只不過各單元對于第二校驗盤的校驗關(guān)系不再依單元所在對角線位置決定，而是根據(jù)拉丁方相應(yīng)位置的符號決定。根據(jù)圖5，得到表7所示的PDHLatin碼。

　　3.5 X碼

　　上面介紹的幾種編碼方法雖然都達(dá)到了冗余的最優(yōu)，但在更新復(fù)雜度方面均稍高于最優(yōu)值，那么是否可以達(dá)到兩者同時最優(yōu)呢?文獻(xiàn)[9]提出的X碼是一種這樣的雙容錯編碼。

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

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

　　3.6 B碼

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

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

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

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

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

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

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

　　3.8 Weaver碼

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

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

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

　　4 結(jié)束語

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

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

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

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

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