英文摘要: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.
英文關鍵字:storage systems; fault-tolerant coding; array code
基金項目：國家高技術研究發展(“863”)計劃(2008AA01Z401)；國家自然科學基金(60903028)
1 存儲容錯編碼評價指標
近20年來，隨著計算機技術的迅猛發展，大規模存儲系統的發展也十分迅速。當前，普通PC機的存儲器的容量已經達到了太比特級別，這較之20年前的20 MB存儲容量提高了10 000倍。
除了傳統的磁盤驅動器之外，新型的固態存儲(SSD)存儲器也已經走向市場。盡管單個存儲器的容量發展迅速，但是卻仍然趕不上人們對存儲容量需求的增長速度。
隨著大型計算機系統由“以計算為中心”向著“以信息處理為中心”的轉變，以及信息量的爆炸式增長，人們對海量存儲系統的需求日益提高。海量存儲系統本質上是將很多的單個存儲器件(下面均以磁盤為例)，通過系統的接口，連接整合為一個虛擬的容量巨大的單一存儲器，即磁盤陣列。
隨著陣列中磁盤數目的增多，系統的可靠性也隨之下降。工業界一般使用平均數據丟失時間(MTTDL)來衡量陣列的可靠性。
設單個磁盤的平均失效時間為MTTFdisk，則對于包含n塊磁盤的無冗余陣列來說，其MTTDL可簡單估計為：MTTDL=MTTFdisk/n。可見，當n較大時，整個系統的可靠性將成比例下降。這對于較大規模的系統來說是不可接受的。利用冗余數據編碼來提高系統可靠性是公認的解決這一問題的較好方法。通過巧妙地將m塊標準大小的磁盤上的數據，增加部分冗余校驗信息，編碼后存放于n塊磁盤上，使得系統滿足：對于任意k塊磁盤失效，都可以通過其他n-k塊未失效盤中的數據解碼恢復，則稱整個系統是k容錯的，或者稱k為系統的容錯數。
分析表明[1]，對于k容錯的系統來說，可以近似估計為：
因而，在大規模系統中，容錯數可以說是另一種對系統可靠性的描述方式。市場中一般磁盤的MTTFdisk為105左右，系統修復時間MTTR一般為10左右。根據(1)式可以看出，當系統磁盤數為103～104時，一般2容錯或是3容錯編碼就基本上可以滿足存儲系統的容錯要求。
系統用于增加容錯能力而添加的冗余越多，系統的額外造價也將越高。因而在具有相同容錯數的前提下，人們往往追求更小的冗余度，即(n-m)/n的值，其中n為系統磁盤數、m為存儲用戶數據的磁盤數。根據編碼理論的Singleton界，k容錯系統的最小冗余度為：k/n。達到這一最小值的編碼方法稱做MDS碼。目前多數存儲編碼研究都集中于構造不同參數下的MDS碼。
除了上述指標，任何計算機系統的速度與效率永遠是需要考量的重要指標。這里我們不討論如何有效地并行處理多磁盤中的數據讀取(那是另外一個較大的課題)，而著重研究由于冗余編碼帶來的額外計算開銷。對于即便是相同的編碼方法，由于編/解碼算法的不同，可能計算效率的差異較大。由于在計算機系統中，最終的編碼運算都會反映為一些二進制運算，因而研究者通常使用編碼需要的總的二進制異或運算次數來衡量由于額外冗余編碼帶來的系統計算開銷。對于一個隨機存取的存儲系統來說，隨機小塊信息寫操作的性能尤為重要。編碼運算中每個單元所參與的平均異或次數可以用來衡量這一指標，我們稱其為編碼的更新復雜度。
綜合上面討論，存儲系統容錯編碼問題可以歸結為尋求對如下指標進行優化的編碼方法
系統滿足需要的容錯性能，容錯數為k的系統。
系統有較小(或最優)的冗余度
系統有較小(或最優)的編碼/更新復雜度。
2 線性編碼
對于單容錯系統來說，簡單的奇偶校驗即可使得上面的3個指標達到最優。經典的系統都是使用的這種方法。然而對于k大于1的情況，問題的解決就不是那么簡單了。從通信編碼理論的豐富成果中，兩種比較有代表性的編碼方法被人們挑選出來，并用于解決存儲容錯問題，他們是二進制線性碼和RS碼。
2.1 多維陣列碼
圖1所示是二維陣列編碼及校驗矩陣。二維陣列碼是奇偶校驗的自然推廣，由圖1很容易看出它是雙容錯的。二維陣列碼保持了單容錯時奇偶校驗碼的最優編碼復雜度的特性，但是二維陣列碼的冗余度不再是最優的了。
二維陣列碼也很容易推廣為k維陣列。并且容易得到這樣編碼的k容錯特性。但是隨著k的增大，冗余會越來越大[2-3]。
2.2 Full碼
圖2所示是FULL-2碼。FULL-2碼可看做是二維陣列碼的推廣。
FULL碼依然保持了最優的編碼復雜度，并且冗余度要比陣列碼好很多。然而不幸的是，當k大于3時，FULL-k碼不再是k容錯的[4]。
2.3 RS碼
圖3所示是RS碼的校驗矩陣。RS碼從最佳的冗余特性出發。達到Singleton界的RS碼被人們提出并廣泛應用。
校驗矩陣通過線性變換可以化為系統矩陣，用存儲系統的語言亦可顯式地區分出系統中哪些單元用于存儲校驗單元。可以看出，矩陣中的元素不再是“0”、“1”，而為有限域元素的冪，故編碼需要使用有限域運算。在計算機系統中，有限域元素最后還是會被映射為“0”、“1”單元。這時每個有限域元素一般會被映射為多個“0”、“1”單元，而有限域運算也可以被分解為這些“0”、“1”單元的復雜運算。我們仍然以編碼所需的異或運算為基本單位，則編碼所需的異或運算次數和編碼算法的巧妙程度有關。目前較好的域運算算法所需的異或次數大約為O(n3)[5]，計算復雜度相當高。RS碼是MDS碼，故冗余度是最優的。
3 陣列編碼
上述幾種編碼各有優缺點，那么是否存在對于多指標同時最優的k容錯編碼方法呢？自文獻[5]提出EVENODD碼起，一大類只使用異或運算的陣列編碼被提出并被人們廣泛研究。
多維陣列或FULL碼等二進制線性碼每塊磁盤只取一個邏輯單元進行校驗運算。而陣列碼則在每塊磁盤上取多個邏輯單元，一起交叉進行校驗運算。校驗計算同2進制線性碼一樣，只使用二進制異或運算，但冗余度卻可以與RS碼相同。
3.1 EVENODD碼
EVENODD碼的想法很簡單，每塊磁盤中取若干單元，排成方陣，然后將這些單元分成不同的校驗組，另外添加兩塊磁盤用于存儲校驗單元。所有校驗組均使用簡單的二進制奇偶校驗。
水平校驗與對角校驗如表1所示。表1中D代表用戶數據單元，P代表冗余校驗單元?？梢钥闯?，Disk1—Disk5存儲用戶數據單元；Disk6、7存儲冗余校驗單元。Disk6的各單元為用戶數據各行的水平校驗和，而Disk7的各單元為用戶數據的輔對角線校驗和。
設存儲用戶數據盤的數目為p(如上例中p=5)，則系統包含p+2塊磁盤，前p+1塊磁盤中的最后一個單元為虛擬0元，故每盤實際包含p-1個單元，最后一塊磁盤包含p個單元?？梢宰C明，當p為素數時系統是雙容錯的。
簡單計算可知此時的系統的冗余度為(2p-1)/((p+2)(p-1)+1)。由于最后的校驗盤多出一個單元，所以冗余度稍稍大于最優的2/(p+2)。為了達到最優值，文獻[5]中使用如下技巧：將多出的單元(即輔對角交驗和)疊加到該盤其他單元上，構造MDS的EVENODD碼如表2所示。
表2也可表示為如表3所示。
也就是說當第一輔對角校驗和為1時，其他各對角校驗為奇校驗；當第一輔對角校驗和為0時，其他各對角校驗為偶校驗。這就是它被命名為EVENODD碼的原因。
3.2 RDP碼
從表2可以看出，為了得到冗余最優，EVENODD碼的輔對角線上的單元的更新復雜度很高。每次更新這些單元的數據時都要同時更新其他p個校驗單元。對于雙容錯編碼來說，最優值為2。文獻[6]中構造的RDP編碼將這些單元的更新復雜度均衡到每個單元，從而有效地消除了寫操作中更新性能的不均衡。一個包含水平校驗的對角線校驗如表4所示。
與EVENODD不同處在于，做對角校驗時也包含了水平校驗單元的一列(因此，數據單元也比EVENODD少了一列)。
同樣的，RDP的最后一個校驗盤多出一個單元，使得整個系統不為MDS碼。但RDP碼的優勢在于，簡單地將多出的單元刪去，系統仍然為雙容錯的。即得到如表5所示陣列。
從表5可以看出，所有數據單元的更新負載為2或3，分布比EVENODD碼要均勻，不會產生由編碼方式帶來的額外“瓶頸”，但系統的平均更新復雜度是相同的。
3.3 Liberation碼
從前面幾種編碼可以看出，所使用的方法都是水平校驗加其他一種校驗共同構成雙容錯。不同之處就在于“另一種校驗”的不同選擇。如將另一校驗盤上的校驗元看作一個“0”、“1”向量，每塊數據盤上的單元對這些校驗元的影響可用一個“0”、“1”矩陣來表示。如表5中的第1列的4個數據單元對Disk7中的各校驗元的影響可表示為如圖4所示矩陣。
在這種表示下，前面所說的更新復雜度就對應著矩陣中1的個數。于是構造一個雙容錯陣列碼的問題就轉變為：尋找若干個這樣的矩陣，使得其中1的個數盡量少，并且任意2個之和為滿秩。
在p為素數時，文獻[7]中構造的Liberation碼使得p×p階矩陣1的數目不超過p+1，其構造的p個矩陣可簡單地描述為：各對角線加一個額外單元。第k個矩陣的額外的1單元的位置可描述為(k(p-1)/2 Mod p,1+k(p=1)/2 Mod p)。得到的編碼如表6所示。
3.4 PDHLatin碼
前面這些編碼為MDS碼的充要條件均為：碼長與素數相關(RDP為p+1，其他為p+2)。它們的雙容錯解碼方法均為根據一個已知單元，然后通過校驗關系與失效單元形成的鏈式關系依次恢復所有單元。這使人們理解到其容錯能力的本質是任意兩列都可以形成這樣的關聯結構。文獻[8]中利用拉丁方構造了PDHLatin碼，使得碼長不再必須關聯一個素數。
所謂拉丁方是指n×n的方陣中填入n個不同符號，使得每行每列的符號都不重復。顯然拉丁方的每兩列構成一個n元置換。所謂漢密爾頓拉丁方是指拉丁方的任何兩列構成的置換為單環的。圖5為一個9階漢密爾頓拉丁方。
從一個給定的漢密爾頓拉丁方，我們可以用與EVENODD碼類似的方法構造編碼，只不過各單元對于第二校驗盤的校驗關系不再依單元所在對角線位置決定，而是根據拉丁方相應位置的符號決定。根據圖5，得到表7所示的PDHLatin碼。
3.5 X碼
上面介紹的幾種編碼方法雖然都達到了冗余的最優，但在更新復雜度方面均稍高于最優值，那么是否可以達到兩者同時最優呢？文獻[9]提出的X碼是一種這樣的雙容錯編碼。
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塊盤容量的數據并行的處理，因而將系統分為多個較小系統是有益的。
第三，硬盤的造價較低且發展迅速：這使得人們可以比較“奢侈”地使用存儲空間，因而大型存儲系統的建造目前還處于“粗曠經營”階段。相對于易實施性、易維護性、易擴展性，當前階段冗余率還并不是主要決定因素。
但是，隨著單磁盤容量的日趨飽和，系統對性能、容錯、節能等需求的不斷變化，海量存儲系統構造相應的也會不斷發展。明天的存儲系統將會需要具備什么特性的編碼形式，還需我們不斷探索。
5 參考文獻
林勝，南開大學計算機專業博士畢業，天津理工大學副教授，研究方向為存儲編碼、組合算法。
劉曉光，南開大學計算機專業博士畢業，南開大學信息技術科學學院副教授，研究方向為高性能計算、海量信息存儲技術。
王剛，南開大學計算機專業博士畢業，南開大學信息技術科學學院教授，研究方向為海量信息存儲技術、并行計算。
[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] 王新梅, 肖國鎮. 糾錯碼——原理與方法 [Ｍ]. 西安：西安電子科技大學出版社, 2001.
[3] 林勝. 存儲系統容錯及陣列編碼 [D]. 天津：南開大學, 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.