?

　　1 存儲(chǔ)容錯(cuò)編碼評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

?

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

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

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

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

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

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

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

　　2 線性編碼

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

　　2.1 多維陣列碼

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

?

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

　　2.2 Full碼

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

?

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

　　2.3 RS碼

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

?

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

　　3 陣列編碼

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

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

　　3.1 EVENODD碼

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

　　水平校驗(yàn)與對(duì)角校驗(yàn)如表1所示。表1中D代表用戶數(shù)據(jù)單元，P代表冗余校驗(yàn)單元。可以看出，Disk1—Disk5存儲(chǔ)用戶數(shù)據(jù)單元;Disk6、7存儲(chǔ)冗余校驗(yàn)單元。Disk6的各單元為用戶數(shù)據(jù)各行的水平校驗(yàn)和，而Disk7的各單元為用戶數(shù)據(jù)的輔對(duì)角線校驗(yàn)和。

?

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

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

?

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

?

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

　　3.2 RDP碼

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

?

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

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

?

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

　　3.3 Liberation碼

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

?

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

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

?

　　3.4 PDHLatin碼

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

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

?

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

?

　　3.5 X碼

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

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

　　為了滿足雙容錯(cuò)的要求，X碼也要求陣列中包含的列數(shù)(或說碼長)為素?cái)?shù)。碼長為素?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ù)雜度。

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

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

?

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

　　3.7 T碼

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

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

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

　　3.8 Weaver碼

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

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

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

　　4 結(jié)束語

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

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

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

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

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