英文摘要:Large professional hard disk storage systems are generally arranged as array systems consisting of many hard disks. However, as the number of hard disks increases, the probability of disk fault and data loss also increases. A redundant fault-tolerant coding technique can be employed that allows for faults among hard disks. Currently, only double fault-tolerant array codes are in widespread use; but with expansion of system size, different fault-tolerant coding streams will need to be investigated. Experts generally agree that triple- fault-tolerant coding will become the dominant technique with the next five to ten years.
英文關(guān)鍵字:storage systems; fault-tolerant coding; array code
基金項(xiàng)目：國(guó)家高技術(shù)研究發(fā)展(“863”)計(jì)劃(2008AA01Z401)；國(guó)家自然科學(xué)基金(60903028)
1 存儲(chǔ)容錯(cuò)編碼評(píng)價(jià)指標(biāo)
近20年來(lái)，隨著計(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)的磁盤(pán)驅(qū)動(dòng)器之外，新型的固態(tài)存儲(chǔ)(SSD)存儲(chǔ)器也已經(jīng)走向市場(chǎng)。盡管單個(gè)存儲(chǔ)器的容量發(fā)展迅速，但是卻仍然趕不上人們對(duì)存儲(chǔ)容量需求的增長(zhǎng)速度。
隨著大型計(jì)算機(jī)系統(tǒng)由“以計(jì)算為中心”向著“以信息處理為中心”的轉(zhuǎn)變，以及信息量的爆炸式增長(zhǎng)，人們對(duì)海量存儲(chǔ)系統(tǒng)的需求日益提高。海量存儲(chǔ)系統(tǒng)本質(zhì)上是將很多的單個(gè)存儲(chǔ)器件(下面均以磁盤(pán)為例)，通過(guò)系統(tǒng)的接口，連接整合為一個(gè)虛擬的容量巨大的單一存儲(chǔ)器，即磁盤(pán)陣列。
隨著陣列中磁盤(pán)數(shù)目的增多，系統(tǒng)的可靠性也隨之下降。工業(yè)界一般使用平均數(shù)據(jù)丟失時(shí)間(MTTDL)來(lái)衡量陣列的可靠性。
設(shè)單個(gè)磁盤(pán)的平均失效時(shí)間為MTTFdisk，則對(duì)于包含n塊磁盤(pán)的無(wú)冗余陣列來(lái)說(shuō)，其MTTDL可簡(jiǎn)單估計(jì)為：MTTDL=MTTFdisk/n?？梢?jiàn)，當(dāng)n較大時(shí)，整個(gè)系統(tǒng)的可靠性將成比例下降。這對(duì)于較大規(guī)模的系統(tǒng)來(lái)說(shuō)是不可接受的。利用冗余數(shù)據(jù)編碼來(lái)提高系統(tǒng)可靠性是公認(rèn)的解決這一問(wèn)題的較好方法。通過(guò)巧妙地將m塊標(biāo)準(zhǔn)大小的磁盤(pán)上的數(shù)據(jù)，增加部分冗余校驗(yàn)信息，編碼后存放于n塊磁盤(pán)上，使得系統(tǒng)滿足：對(duì)于任意k塊磁盤(pán)失效，都可以通過(guò)其他n-k塊未失效盤(pán)中的數(shù)據(jù)解碼恢復(fù)，則稱整個(gè)系統(tǒng)是k容錯(cuò)的，或者稱k為系統(tǒng)的容錯(cuò)數(shù)。
分析表明[1]，對(duì)于k容錯(cuò)的系統(tǒng)來(lái)說(shuō)，可以近似估計(jì)為：
因而，在大規(guī)模系統(tǒng)中，容錯(cuò)數(shù)可以說(shuō)是另一種對(duì)系統(tǒng)可靠性的描述方式。市場(chǎng)中一般磁盤(pán)的MTTFdisk為105左右，系統(tǒng)修復(fù)時(shí)間MTTR一般為10左右。根據(jù)(1)式可以看出，當(dāng)系統(tǒng)磁盤(pán)數(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)磁盤(pán)數(shù)、m為存儲(chǔ)用戶數(shù)據(jù)的磁盤(pán)數(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)。這里我們不討論如何有效地并行處理多磁盤(pán)中的數(shù)據(jù)讀取(那是另外一個(gè)較大的課題)，而著重研究由于冗余編碼帶來(lái)的額外計(jì)算開(kāi)銷。對(duì)于即便是相同的編碼方法，由于編/解碼算法的不同，可能計(jì)算效率的差異較大。由于在計(jì)算機(jī)系統(tǒng)中，最終的編碼運(yùn)算都會(huì)反映為一些二進(jìn)制運(yùn)算，因而研究者通常使用編碼需要的總的二進(jìn)制異或運(yùn)算次數(shù)來(lái)衡量由于額外冗余編碼帶來(lái)的系統(tǒng)計(jì)算開(kāi)銷。對(duì)于一個(gè)隨機(jī)存取的存儲(chǔ)系統(tǒng)來(lái)說(shuō)，隨機(jī)小塊信息寫(xiě)操作的性能尤為重要。編碼運(yùn)算中每個(gè)單元所參與的平均異或次數(shù)可以用來(lái)衡量這一指標(biāo)，我們稱其為編碼的更新復(fù)雜度。
綜合上面討論，存儲(chǔ)系統(tǒng)容錯(cuò)編碼問(wèn)題可以歸結(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)來(lái)說(shuō)，簡(jiǎn)單的奇偶校驗(yàn)即可使得上面的3個(gè)指標(biāo)達(dá)到最優(yōu)。經(jīng)典的系統(tǒng)都是使用的這種方法。然而對(duì)于k大于1的情況，問(wèn)題的解決就不是那么簡(jiǎn)單了。從通信編碼理論的豐富成果中，兩種比較有代表性的編碼方法被人們挑選出來(lái)，并用于解決存儲(chǔ)容錯(cuò)問(wèn)題，他們是二進(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ì)越來(lái)越大[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)矩陣通過(guò)線性變換可以化為系統(tǒng)矩陣，用存儲(chǔ)系統(tǒng)的語(yǔ)言亦可顯式地區(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)制線性碼每塊磁盤(pán)只取一個(gè)邏輯單元進(jìn)行校驗(yàn)運(yùn)算。而陣列碼則在每塊磁盤(pán)上取多個(gè)邏輯單元，一起交叉進(jìn)行校驗(yàn)運(yùn)算。校驗(yàn)計(jì)算同2進(jìn)制線性碼一樣，只使用二進(jìn)制異或運(yùn)算，但冗余度卻可以與RS碼相同。
3.1 EVENODD碼
EVENODD碼的想法很簡(jiǎn)單，每塊磁盤(pán)中取若干單元，排成方陣，然后將這些單元分成不同的校驗(yàn)組，另外添加兩塊磁盤(pán)用于存儲(chǔ)校驗(yàn)單元。所有校驗(yàn)組均使用簡(jiǎ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ù)盤(pán)的數(shù)目為p(如上例中p=5)，則系統(tǒng)包含p+2塊磁盤(pán)，前p+1塊磁盤(pán)中的最后一個(gè)單元為虛擬0元，故每盤(pán)實(shí)際包含p-1個(gè)單元，最后一塊磁盤(pán)包含p個(gè)單元。可以證明，當(dāng)p為素?cái)?shù)時(shí)系統(tǒng)是雙容錯(cuò)的。
簡(jiǎn)單計(jì)算可知此時(shí)的系統(tǒng)的冗余度為(2p-1)/((p+2)(p-1)+1)。由于最后的校驗(yàn)盤(pán)多出一個(gè)單元，所以冗余度稍稍大于最優(yōu)的2/(p+2)。為了達(dá)到最優(yōu)值，文獻(xiàn)[5]中使用如下技巧：將多出的單元(即輔對(duì)角交驗(yàn)和)疊加到該盤(pán)其他單元上，構(gòu)造MDS的EVENODD碼如表2所示。
表2也可表示為如表3所示。
也就是說(shuō)當(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ò)編碼來(lái)說(shuō)，最優(yōu)值為2。文獻(xiàn)[6]中構(gòu)造的RDP編碼將這些單元的更新復(fù)雜度均衡到每個(gè)單元，從而有效地消除了寫(xiě)操作中更新性能的不均衡。一個(gè)包含水平校驗(yàn)的對(duì)角線校驗(yàn)如表4所示。
與EVENODD不同處在于，做對(duì)角校驗(yàn)時(shí)也包含了水平校驗(yàn)單元的一列(因此，數(shù)據(jù)單元也比EVENODD少了一列)。
同樣的，RDP的最后一個(gè)校驗(yàn)盤(pán)多出一個(gè)單元，使得整個(gè)系統(tǒng)不為MDS碼。但RDP碼的優(yōu)勢(shì)在于，簡(jiǎn)單地將多出的單元?jiǎng)h去，系統(tǒng)仍然為雙容錯(cuò)的。即得到如表5所示陣列。
從表5可以看出，所有數(shù)據(jù)單元的更新負(fù)載為2或3，分布比EVENODD碼要均勻，不會(huì)產(chǎn)生由編碼方式帶來(lái)的額外“瓶頸”，但系統(tǒng)的平均更新復(fù)雜度是相同的。
3.3 Liberation碼
從前面幾種編碼可以看出，所使用的方法都是水平校驗(yàn)加其他一種校驗(yàn)共同構(gòu)成雙容錯(cuò)。不同之處就在于“另一種校驗(yàn)”的不同選擇。如將另一校驗(yàn)盤(pán)上的校驗(yàn)元看作一個(gè)“0”、“1”向量，每塊數(shù)據(jù)盤(pán)上的單元對(duì)這些校驗(yàn)元的影響可用一個(gè)“0”、“1”矩陣來(lái)表示。如表5中的第1列的4個(gè)數(shù)據(jù)單元對(duì)Disk7中的各校驗(yàn)元的影響可表示為如圖4所示矩陣。
在這種表示下，前面所說(shuō)的更新復(fù)雜度就對(duì)應(yīng)著矩陣中1的個(gè)數(shù)。于是構(gòu)造一個(gè)雙容錯(cuò)陣列碼的問(wèn)題就轉(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ù)目不超過(guò)p+1，其構(gòu)造的p個(gè)矩陣可簡(jiǎn)單地描述為：各對(duì)角線加一個(gè)額外單元。第k個(gè)矩陣的額外的1單元的位置可描述為(k(p-1)/2 Mod p,1+k(p=1)/2 Mod p)。得到的編碼如表6所示。
3.4 PDHLatin碼
前面這些編碼為MDS碼的充要條件均為：碼長(zhǎng)與素?cái)?shù)相關(guān)(RDP為p+1，其他為p+2)。它們的雙容錯(cuò)解碼方法均為根據(jù)一個(gè)已知單元，然后通過(guò)校驗(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碼，使得碼長(zhǎng)不再必須關(guān)聯(lián)一個(gè)素?cái)?shù)。
所謂拉丁方是指n×n的方陣中填入n個(gè)不同符號(hào)，使得每行每列的符號(hào)都不重復(fù)。顯然拉丁方的每?jī)闪袠?gòu)成一個(gè)n元置換。所謂漢密爾頓拉丁方是指拉丁方的任何兩列構(gòu)成的置換為單環(huán)的。圖5為一個(gè)9階漢密爾頓拉丁方。
從一個(gè)給定的漢密爾頓拉丁方，我們可以用與EVENODD碼類似的方法構(gòu)造編碼，只不過(guò)各單元對(duì)于第二校驗(yàn)盤(pá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碼的想法也很簡(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ì)需要具備什么特性的編碼形式，還需我們不斷探索。
5 參考文獻(xiàn)
林勝，南開(kāi)大學(xué)計(jì)算機(jī)專業(yè)博士畢業(yè)，天津理工大學(xué)副教授，研究方向?yàn)榇鎯?chǔ)編碼、組合算法。
劉曉光，南開(kāi)大學(xué)計(jì)算機(jī)專業(yè)博士畢業(yè)，南開(kāi)大學(xué)信息技術(shù)科學(xué)學(xué)院副教授，研究方向?yàn)楦咝阅苡?jì)算、海量信息存儲(chǔ)技術(shù)。
王剛，南開(kāi)大學(xué)計(jì)算機(jī)專業(yè)博士畢業(yè)，南開(kāi)大學(xué)信息技術(shù)科學(xué)學(xué)院教授，研究方向?yàn)楹Ａ啃畔⒋鎯?chǔ)技術(shù)、并行計(jì)算。
[1] HARTLINE J R, RAO K K. Notes on Reliability Models for Non-MDS Erasure Codes [R]. Research Report. RJ10391(A0610-035). San Jose, CA,USA: IBM. 2006.
[2] 王新梅, 肖國(guó)鎮(zhèn). 糾錯(cuò)碼——原理與方法 [Ｍ]. 西安：西安電子科技大學(xué)出版社, 2001.
[3] 林勝. 存儲(chǔ)系統(tǒng)容錯(cuò)及陣列編碼 [D]. 天津：南開(kāi)大學(xué), 2010.
[4] HELLERSTEIN L, GIBSON G A, KARP R M, et al. Coding Techniques for Handling Failures in Large Disk Arrays [J]. Algorithmic, 1994,12(3/4):182-208.
[5] BLAUM M, BRADY J, BRUCK J, et al. EVENODD: An Optimal Scheme for Tolerating Double Disk Failures in RAID Architectures [J]. ACM SIGARCH Computer Architecture News, 1994,22(1):245-254.
[6] CORBETT P, ENGLISH B, GOEL A. Row-diagonal Parity for Double Disk Failure Correction [C]//Proceedings of the 3rd USENIX Conference on File and Storage Technologies(FAST’04), Mar 31-Apr 2, 2004, San Francisco, CA,USA. Berkeley, CA, USA: USENIX Association, 2004: 14p.
[7] PLANK J S. The RAID-6 Liberation Codes [C]//Proceedings of the 6th USENIX Conference on File and Storage Technologies(FAST’08), Feb 26-29, 2008, San Jose, CA, USA. Berkeley, CA, USA: USENIX Association, 2008:97-110.
[8] WANG Gang, LIN Sheng, LIU Xiaoguang, et al. Combinatorial Constructions of Multi-erasure-correcting Codes with Independent Parity Symbols for Storage Systems [C]//Proceedings of the 13th IEEE Pacific Rim International Symposium on Dependable Computing(PRDC’07), Dec 17-19, 2007, Melbourne, Australia. Piscataway, NJ, USA: IEEE, 2007:61-68.
[9] XU Lihao, BRUCK J. X-code: MDS Array Codes with Optimal Encoding [J]. IEEE Transactions on Information Theory, 1999,45(1):272-276.
[10] XU Lihao, BOHOSSIAN V, BRUCK J, et al. Low Density MDS Codes and Factors of Complete Graphs [J]. IEEE Transactions on Information Theory, 1999,45(6): 1817-1826.
[11] LOUIDOR E, ROTH R M. Lowest-density MDS Codes over Extension Alphabets [C]//Proceedings of the IEEE International Symposium on Information Theory (ISIT’03), Jun 29-Jul 4,2003, Yokohama, Japan. Piscataway, NJ, USA: IEEE, 2003:58.
[12] LIN Sheng, WANG Gang, STONES D S, et al. T-code: 3-erasure Longest Lowest-density MDS Codes [J]. IEEE Journal on Selected Areas in Communications, 2010, 28(2):289-296.
[13] HAFNER J L. WEAVER Codes: Highly Fault Tolerant Erasure Codes for Storage Systems [C]//Proceedings of the 4th USENIX Conference on File and Storage Technologies(FAST’05), Dec 13-16,2005, San Francisco, CA,USA. Berkeley, CA, USA: USENIX Association, 2005.