英文摘要: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)目：國家高技術(shù)研究發(fā)展(“863”)計(jì)劃(2008AA01Z401)；國家自然科學(xué)基金(60903028)
1 存儲容錯編碼評價指標(biāo)
近20年來，隨著計(jì)算機(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ì)算機(jī)系統(tǒng)由“以計(jì)算為中心”向著“以信息處理為中心”的轉(zhuǎn)變，以及信息量的爆炸式增長，人們對海量存儲系統(tǒng)的需求日益提高。海量存儲系統(tǒng)本質(zhì)上是將很多的單個存儲器件(下面均以磁盤為例)，通過系統(tǒng)的接口，連接整合為一個虛擬的容量巨大的單一存儲器，即磁盤陣列。
隨著陣列中磁盤數(shù)目的增多，系統(tǒng)的可靠性也隨之下降。工業(yè)界一般使用平均數(shù)據(jù)丟失時間(MTTDL)來衡量陣列的可靠性。
設(shè)單個磁盤的平均失效時間為MTTFdisk，則對于包含n塊磁盤的無冗余陣列來說，其MTTDL可簡單估計(jì)為：MTTDL=MTTFdisk/n?？梢姡?dāng)n較大時，整個系統(tǒng)的可靠性將成比例下降。這對于較大規(guī)模的系統(tǒng)來說是不可接受的。利用冗余數(shù)據(jù)編碼來提高系統(tǒng)可靠性是公認(rèn)的解決這一問題的較好方法。通過巧妙地將m塊標(biāo)準(zhǔn)大小的磁盤上的數(shù)據(jù)，增加部分冗余校驗(yàn)信息，編碼后存放于n塊磁盤上，使得系統(tǒng)滿足：對于任意k塊磁盤失效，都可以通過其他n-k塊未失效盤中的數(shù)據(jù)解碼恢復(fù)，則稱整個系統(tǒng)是k容錯的，或者稱k為系統(tǒng)的容錯數(shù)。
分析表明[1]，對于k容錯的系統(tǒng)來說，可以近似估計(jì)為：
因而，在大規(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ì)算機(jī)系統(tǒng)的速度與效率永遠(yuǎn)是需要考量的重要指標(biāo)。這里我們不討論如何有效地并行處理多磁盤中的數(shù)據(jù)讀取(那是另外一個較大的課題)，而著重研究由于冗余編碼帶來的額外計(jì)算開銷。對于即便是相同的編碼方法，由于編/解碼算法的不同，可能計(jì)算效率的差異較大。由于在計(jì)算機(jī)系統(tǒng)中，最終的編碼運(yùn)算都會反映為一些二進(jìn)制運(yùn)算，因而研究者通常使用編碼需要的總的二進(jìn)制異或運(yùn)算次數(shù)來衡量由于額外冗余編碼帶來的系統(tǒng)計(jì)算開銷。對于一個隨機(jī)存取的存儲系統(tǒng)來說，隨機(jī)小塊信息寫操作的性能尤為重要。編碼運(yùn)算中每個單元所參與的平均異或次數(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)來說，簡單的奇偶校驗(yàn)即可使得上面的3個指標(biāo)達(dá)到最優(yōu)。經(jīng)典的系統(tǒng)都是使用的這種方法。然而對于k大于1的情況，問題的解決就不是那么簡單了。從通信編碼理論的豐富成果中，兩種比較有代表性的編碼方法被人們挑選出來，并用于解決存儲容錯問題，他們是二進(jìn)制線性碼和RS碼。
2.1 多維陣列碼
圖1所示是二維陣列編碼及校驗(yàn)矩陣。二維陣列碼是奇偶校驗(yàn)的自然推廣，由圖1很容易看出它是雙容錯的。二維陣列碼保持了單容錯時奇偶校驗(yàn)碼的最優(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碼的校驗(yàn)矩陣。RS碼從最佳的冗余特性出發(fā)。達(dá)到Singleton界的RS碼被人們提出并廣泛應(yīng)用。
校驗(yàn)矩陣通過線性變換可以化為系統(tǒng)矩陣，用存儲系統(tǒng)的語言亦可顯式地區(qū)分出系統(tǒng)中哪些單元用于存儲校驗(yàn)單元?？梢钥闯觯仃囍械脑夭辉偈?ldquo;0”、“1”，而為有限域元素的冪，故編碼需要使用有限域運(yùn)算。在計(jì)算機(jī)系統(tǒng)中，有限域元素最后還是會被映射為“0”、“1”單元。這時每個有限域元素一般會被映射為多個“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)，那么是否存在對于多指標(biāo)同時最優(yōu)的k容錯編碼方法呢？自文獻(xiàn)[5]提出EVENODD碼起，一大類只使用異或運(yùn)算的陣列編碼被提出并被人們廣泛研究。
多維陣列或FULL碼等二進(jìn)制線性碼每塊磁盤只取一個邏輯單元進(jìn)行校驗(yàn)運(yùn)算。而陣列碼則在每塊磁盤上取多個邏輯單元，一起交叉進(jìn)行校驗(yàn)運(yùn)算。校驗(yàn)計(jì)算同2進(jìn)制線性碼一樣，只使用二進(jìn)制異或運(yùn)算，但冗余度卻可以與RS碼相同。
3.1 EVENODD碼
EVENODD碼的想法很簡單，每塊磁盤中取若干單元，排成方陣，然后將這些單元分成不同的校驗(yàn)組，另外添加兩塊磁盤用于存儲校驗(yàn)單元。所有校驗(yàn)組均使用簡單的二進(jìn)制奇偶校驗(yàn)。
水平校驗(yàn)與對角校驗(yàn)如表1所示。表1中D代表用戶數(shù)據(jù)單元，P代表冗余校驗(yàn)單元?？梢钥闯?，Disk1—Disk5存儲用戶數(shù)據(jù)單元；Disk6、7存儲冗余校驗(yàn)單元。Disk6的各單元為用戶數(shù)據(jù)各行的水平校驗(yàn)和，而Disk7的各單元為用戶數(shù)據(jù)的輔對角線校驗(yàn)和。
設(shè)存儲用戶數(shù)據(jù)盤的數(shù)目為p(如上例中p=5)，則系統(tǒng)包含p+2塊磁盤，前p+1塊磁盤中的最后一個單元為虛擬0元，故每盤實(shí)際包含p-1個單元，最后一塊磁盤包含p個單元?？梢宰C明，當(dāng)p為素?cái)?shù)時系統(tǒng)是雙容錯的。
簡單計(jì)算可知此時的系統(tǒng)的冗余度為(2p-1)/((p+2)(p-1)+1)。由于最后的校驗(yàn)盤多出一個單元，所以冗余度稍稍大于最優(yōu)的2/(p+2)。為了達(dá)到最優(yōu)值，文獻(xiàn)[5]中使用如下技巧：將多出的單元(即輔對角交驗(yàn)和)疊加到該盤其他單元上，構(gòu)造MDS的EVENODD碼如表2所示。
表2也可表示為如表3所示。
也就是說當(dāng)?shù)谝惠o對角校驗(yàn)和為1時，其他各對角校驗(yàn)為奇校驗(yàn)；當(dāng)?shù)谝惠o對角校驗(yàn)和為0時，其他各對角校驗(yàn)為偶校驗(yàn)。這就是它被命名為EVENODD碼的原因。
3.2 RDP碼
從表2可以看出，為了得到冗余最優(yōu)，EVENODD碼的輔對角線上的單元的更新復(fù)雜度很高。每次更新這些單元的數(shù)據(jù)時都要同時更新其他p個校驗(yàn)單元。對于雙容錯編碼來說，最優(yōu)值為2。文獻(xiàn)[6]中構(gòu)造的RDP編碼將這些單元的更新復(fù)雜度均衡到每個單元，從而有效地消除了寫操作中更新性能的不均衡。一個包含水平校驗(yàn)的對角線校驗(yàn)如表4所示。
與EVENODD不同處在于，做對角校驗(yàn)時也包含了水平校驗(yàn)單元的一列(因此，數(shù)據(jù)單元也比EVENODD少了一列)。
同樣的，RDP的最后一個校驗(yàn)盤多出一個單元，使得整個系統(tǒng)不為MDS碼。但RDP碼的優(yōu)勢在于，簡單地將多出的單元刪去，系統(tǒng)仍然為雙容錯的。即得到如表5所示陣列。
從表5可以看出，所有數(shù)據(jù)單元的更新負(fù)載為2或3，分布比EVENODD碼要均勻，不會產(chǎn)生由編碼方式帶來的額外“瓶頸”，但系統(tǒng)的平均更新復(fù)雜度是相同的。
3.3 Liberation碼
從前面幾種編碼可以看出，所使用的方法都是水平校驗(yàn)加其他一種校驗(yàn)共同構(gòu)成雙容錯。不同之處就在于“另一種校驗(yàn)”的不同選擇。如將另一校驗(yàn)盤上的校驗(yàn)元看作一個“0”、“1”向量，每塊數(shù)據(jù)盤上的單元對這些校驗(yàn)元的影響可用一個“0”、“1”矩陣來表示。如表5中的第1列的4個數(shù)據(jù)單元對Disk7中的各校驗(yàn)元的影響可表示為如圖4所示矩陣。
在這種表示下，前面所說的更新復(fù)雜度就對應(yīng)著矩陣中1的個數(shù)。于是構(gòu)造一個雙容錯陣列碼的問題就轉(zhuǎn)變?yōu)椋簩ふ胰舾蓚€這樣的矩陣，使得其中1的個數(shù)盡量少，并且任意2個之和為滿秩。
在p為素?cái)?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碼的充要條件均為：碼長與素?cái)?shù)相關(guān)(RDP為p+1，其他為p+2)。它們的雙容錯解碼方法均為根據(jù)一個已知單元，然后通過校驗(yàn)關(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)一個素?cái)?shù)。
所謂拉丁方是指n×n的方陣中填入n個不同符號，使得每行每列的符號都不重復(fù)。顯然拉丁方的每兩列構(gòu)成一個n元置換。所謂漢密爾頓拉丁方是指拉丁方的任何兩列構(gòu)成的置換為單環(huán)的。圖5為一個9階漢密爾頓拉丁方。
從一個給定的漢密爾頓拉丁方，我們可以用與EVENODD碼類似的方法構(gòu)造編碼，只不過各單元對于第二校驗(yàn)盤的校驗(yàn)關(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碼的想法也很簡單，仍然是在陣列中采用主對角線和輔對角線兩種校驗(yàn)，但是通過巧妙地將校驗(yàn)單元分布到各個磁盤中(而不是像其他方法中，校驗(yàn)單元被分離出來，獨(dú)立存放于校驗(yàn)盤)，使得系統(tǒng)同時達(dá)到了兩方面指標(biāo)同時最優(yōu)。
為了滿足雙容錯的要求，X碼也要求陣列中包含的列數(shù)(或說碼長)為素?cái)?shù)。碼長為素?cái)?shù)p的X碼中，每一列包含p-2個用戶數(shù)據(jù)單元，2個冗余校驗(yàn)單元。
3.6 B碼
是否還存在與X碼相同特性的其他編碼方案呢？顯然將兩個X碼陣列重疊，系統(tǒng)仍然保持最優(yōu)冗余與最優(yōu)更新復(fù)雜度。
這樣得到的新編碼，在磁盤數(shù)目不變的情況下，每塊盤需要關(guān)聯(lián)的單元數(shù)目加倍。而在實(shí)際中，為了簡化實(shí)現(xiàn)，我們實(shí)際上需要每塊盤關(guān)聯(lián)的單元數(shù)目盡量少。對于n塊磁盤，在保持最優(yōu)冗余與最優(yōu)更新復(fù)雜度的條件下，每塊盤最少需要多少個單元來關(guān)聯(lián)校驗(yàn)?zāi)?？文獻(xiàn)[10]提出的B碼在雙容錯的情況下很好地解決了這一問題。
通過將編碼構(gòu)造等同于圖論中的完全圖完美-因子分解問題。并根據(jù)圖論已有的結(jié)論，給出一種各方面性能均達(dá)到最優(yōu)的編碼。依據(jù)一個完全圖的一種完美1因子分解方案，我們可以構(gòu)造如表8所示的雙容錯編碼——B碼。
這種編碼，每塊磁盤包含至多1個校驗(yàn)單元，并且只有一塊磁盤不包含校驗(yàn)單元。它將n個符號的所有2元組分劃為多列，并且滿足雙容錯要求，因而在保持了最優(yōu)冗余度與更新復(fù)雜度的前提下，碼長達(dá)到最長。因而這種編碼也被稱做最長最低密度陣列碼。
3.7 T碼
對于3容錯的最長最低密度陣列碼的構(gòu)造較之雙容錯要復(fù)雜很多。文獻(xiàn)[11]最先給出了一種這樣的構(gòu)造，并利用計(jì)算機(jī)輔助證明了某些參數(shù)下，3、4容錯最長最低密度陣列碼的MDS性。在文獻(xiàn)[12]中獨(dú)立構(gòu)造了同樣的編碼并利用組合結(jié)構(gòu)近乎可分的不完全區(qū)組設(shè)計(jì)(NRB)給出了這種編碼的組合解釋，同時也給出了簡明的代數(shù)證明。
T碼從形式上與B碼相同，每塊磁盤包含至多1個校驗(yàn)單元，并且只有一塊磁盤不包含校驗(yàn)單元。文獻(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)的前提下，校驗(yàn)單元分布在各磁盤中的編碼比較容易構(gòu)造。為了簡化問題，文獻(xiàn)[13]選擇具有循環(huán)對稱性的陣列進(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)組，則必有對于任何0≤x
為了更容易地得到k容錯編碼，文獻(xiàn)[13]放寬了冗余的要求，只研究每塊磁盤中，冗余校驗(yàn)單元不少于用戶數(shù)據(jù)單元的情況。這樣，Weaver碼的最好冗余率只有50%。
4 結(jié)束語
陣列碼盡管有著很多性能優(yōu)勢，但在目前的存儲系統(tǒng)中，還是RS碼及層疊RAID(如RAID1+0等)使用得比較多。筆者認(rèn)為其原因主要為以下幾個方面：
首先是實(shí)現(xiàn)上的簡單性因素：RS碼已經(jīng)是工業(yè)界流行的技術(shù)，無論軟硬件都有成熟的實(shí)現(xiàn)方案，而層疊RAID原理十分簡單，所以這兩種編碼實(shí)施最簡單易行。與之相對，陣列碼多種多樣、原理復(fù)雜，實(shí)施需要一定的投入。目前海量存儲系統(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)營”階段。相對于易實(shí)施性、易維護(hù)性、易擴(kuò)展性，當(dāng)前階段冗余率還并不是主要決定因素。
但是，隨著單磁盤容量的日趨飽和，系統(tǒng)對性能、容錯、節(jié)能等需求的不斷變化，海量存儲系統(tǒng)構(gòu)造相應(yīng)的也會不斷發(fā)展。明天的存儲系統(tǒng)將會需要具備什么特性的編碼形式，還需我們不斷探索。
5 參考文獻(xiàn)
林勝，南開大學(xué)計(jì)算機(jī)專業(yè)博士畢業(yè)，天津理工大學(xué)副教授，研究方向?yàn)榇鎯幋a、組合算法。
劉曉光，南開大學(xué)計(jì)算機(jī)專業(yè)博士畢業(yè)，南開大學(xué)信息技術(shù)科學(xué)學(xué)院副教授，研究方向?yàn)楦咝阅苡?jì)算、海量信息存儲技術(shù)。
王剛，南開大學(xué)計(jì)算機(jī)專業(yè)博士畢業(yè)，南開大學(xué)信息技術(shù)科學(xué)學(xué)院教授，研究方向?yàn)楹Ａ啃畔⒋鎯夹g(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] 王新梅, 肖國鎮(zhèn). 糾錯碼——原理與方法 [Ｍ]. 西安：西安電子科技大學(xué)出版社, 2001.
[3] 林勝. 存儲系統(tǒng)容錯及陣列編碼 [D]. 天津：南開大學(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.