Extending and analysis of X-Code

J Shanghai Univ (Engl Ed), 2011, 15(3): 194-200Digital Object Identifier(DOI): 10.1007/511741-011-0720-2Extending and analysis of X-CodeJIN Chao(金超)， FENG Dan(冯丹)， LIU Jing-ning (刘景宁)Wuhan National Laboratory for Optoelectronics, School of Computer Science and Technology, Huazhong University ofScience and Technology, Wuhan 430074, P. R. China@Shanghai University and Springer-Verlag Berlin Heidelberg 2011Abstract X-Code is one of the most important redundant array of independent disk (RAID)-6 codes which are capable oftolerating double disk failures. However, the code length of X-Code is restricted to be a prime number, and such code lengthrestriction of X-Code limits its usage in the real storage systems. Moreover, 8as a vertical RAID-6 code, X-Code can not beextended easily to an arbitrary code length like horizontal RAID-6 codes. In this paper, a novel and fficient code shorteningalgorithm for X-Code is proposed to extend X-Code to an arbitrary length. It can be further proved that the code shorteningalgorithm maintains the maximum-distance -separable (MDS) property of X-Code, and namely, the shortened X-Code is stillMDS code with the optimal space eficiency. In the context of the shortening algorithm for x-Code, an in-depth performanceanalysis on X-Code at consecutive code lengths is conducted, and the impacts of the code shortening algorithm on the perfor-mance of X-Code in various performance metrics are revealed.Keywords redundant array of independent disk (RAID)-6, X-Code, vertical code, code shortening, performance analysisIntroduction6 code. It guarantees the fault-tolerant capability of theRAID-6 system, and also largely deternines the per-The redundant array of independent disk (RAID)4]formance of the system. To measure the performancearchitecture is playing an increasingly important roleof a RAID-6 code, three metrics are employed, thatin modern storage systems. The fault-tolerance featureis, computational complexity, update complexity, andof RAID, addressing the critical issue of data reliabil-space eficiency. These metrics have been widely usedity and availability, has been drawing more and moreby the storage research community in the studies ofattention from the academia and industry. There areRAID-6 codesl6-71. Computational complexity is pro-two major reasons behind this. First, recent findingsportional to the CPU computational overhead duringhave reported that partial or complete disk failure ratesconstruction and reconstruction of the RAID-6 array.are actually much higher than previously and commonlyUpdate complexity indicates the average number of par-estimated2. Second, while the number and capacity ofity blocks affected by an update (write) to a single datathe disks have been growing expontially, individualblock8. Space eficiency measures the percentage ofdisk failure rates remain largely unchangedl3l. Thus, instorage space lused by the parity blocks to protect thethe data centers, the event of disk failures becomes nodata blocks. The smaller the percentage is, the higherlonger rare, and the fault-tolerance ability of the storagethe space eficiency is. Generally, for any erasure code,systems becomes ever more importantl4-5. Among allits error-correcting ability and redundancy rate satisfythe RAID levels, RAID-6 outperforms the others in diskthe Singleton formulalel. Particularly, if it attains thefailure tolerance due to its ability to recover from arbi-Singleton bound, it will be called a maximum-distancetrary two concurrent disk failures in the array. Thus,separable (MDS) code. In other words, it attains themany storage companies, as well as academic researchoptimal space eficiency.groups, are conducting active research on RAID-6 sy8-RAID-6 codes can be broadly divided into two cate-tems.gories, horizontal codes and vertical codes. In the codeThe key component of a RAID-6 system is the RAID-Received Jun.8, 2010; Revised Dec.24, 2010Project supported by the National Basic Research Program of China (Grant Nos.201 1CB302300, 201 1CB302301), the NationalHigh-Technology Research and Development Program of China (Gran中国煤化二十1A402), the NationalNatural Science Foundation of China (Grant Nos.60873028, 60933002,Innovation Group ofEducation of China (Grant No.IRT0725)MHCNMHGCorresponding author JIN Chao, Ph D, E-mail: chjinbust@gmail.comJ Shanghai Univ (Engl Ed), 2011, 15(3): 194-200structure of a horizontal code, such as EVENODDI10]in dn, (5,9) in d2, (2,9) in ds, and the parity block (9)and RDPI7I, the parity blocks are stored in dedicatedin ds form the diagonal parity stripe P(9) along slopeparity columns, while the data columns contain only-1. The coding scheme shapes like the letter “X”indata blocks. On the other hand, in the code struc-geometry, hence the name.ture of a vertical code, such as X-Codel8), the parityd\drdblocks are spread across the data columns, and thereis no dedicated parity column. The original definitions,9 | 4,10 5,6,7,8of RAID-6 codes usually have code length restrictions.,8| 5,9| 1,10,63,7For instance, the length of a standard EVENODD codemust be prime+2; the length of a standard RDP code,8 2,93,10must be prime+1; and the length of a standard X-Codemust be prime. Horizontal codes are very easy to beextended to an arbitrary length through code shorten-10ing, however vertical codes are not easy to be shortened.While implementing a RAID-6 code in a practical diskFig.1 Standard X-Code with 5 columnsarray, the length of the code corresponds to the numberof disks in the array. Thus, such code-length restrictionsUpon double column erasures, X-Code can recoverof vertical codes severely limit their usage in real storagesystems.all the erased blocks in the two columns step by step u8-In this paper, a novel and efficient code shorteninging the parity stripes. Figure 2 ilulstrates the recoveryalgorithm for X-Code is proposed. The algorithm is ca-process for the two erased columns d2 and d3. First, thepable of extending the standard (i.e, originally defined)data block (4,10) can be recovered using parity stripeX-Code to an arbitrary length. Moreover, the extendedP(4), since all the other blocks in P(4) are available.X-Code maintains the MDS property of the standardGiven the data block (4,10) is recovered, we can subse-X-Code. In the context of the proposed shortening algo-quently recover the data block (1,10) using parity striperithm for X-Code, we give a detailed performance analy-P(10). Then, we can use parity stripe P(1) to recoversis on X-Code at all typical code lengths, and reveal theblock (1,8), and use parity stripe P(8) to recover blockimpacts of the code shortening algorithms on the per-(8). Simnilarly, all the rest blocks in these two columnsformance of X-Code in the aforementioned performancecan be recovered step by step. It has been proven for-metrics.mally in [8] that X-Code can recover from either pair oferased columns.1 Background and related workIt has been proven that X-Code has the optimal com-putational complexity, optimal update complexity, and1.1 X-code overviewoptimal space eficiency among all the RAID-6 codesl1l.In this section, the original definition of the standardHowever the code length of X-Code (i.e., the number ofX-Code is reviewed. We use a label-based approach tocolumns in its code structure) is restricted to be a primeillustrate the code structure of X-Code is reviewed. Asnumber. This problem will be discussed in this paper,is shown in Fig. 1, each data or parity block in the codeand a code shortening algorithm is proposed to extendstructure is assigned a label. Each integer in the labelsX-Code to an arbitrary length.represents the index of a parity stripe. A label for adata block is composed of a two integer-tuple that in-_dddsforms which two parity stripes this data block partici-.9 X01.7.8pants in. For instance, the data block labeled with (3,9)in the column d1 is in both parity stripe P(3) and P(9). .1,8X0) 2.6 .,7 |A label for a parity block is a single integer, since eachs, 1Bx829 3,101.6 |parity block belongs to exactly one parity stripe.X-Code has a structure of p rows and p columns,where p must be a prime number. The data blocks, heldin the first (p- -2) rows, are covered by p diagonal par-ity stripes along slope 1 and another p diagonal paritystripes along slope -1. The parity blocks of the parityFig.中国煤化工two column erasuresstripes are stored in the last two rows. For instance, thedata block (1,7) in the column ds, (1,10) in d3, (1,8)1.2TYTHCNMHGin d2, and the parity block (1) in di form the diagonalIn this section, we review the existing techniques thatparity stripe P(1) along slope 1; the data block (3,9)can extend the RAID-6 codes to an arbitrary length.196J Shanghai Univ (Engl Ed), 2011, 15(3): 194-200Horizontal codes are very easy to be extendedbut also parity blocks. Thus, if we remove one column,through code shortening. For a standard horizontalthe parity blocks in this column also removed, and thecode, some of the data columns can simply be removedcorresponding parity stripes may be rendered in an in-from its code structure, by assuming that the removedconsistent state. In this section, a novel code shorteningdata columns contain only imaginary zeros. Since thealgorithm for X-Code will be introduced. The algorithmzero blocks do not contribute to the XOR parity, theyis capable of extending X-Code to an arbitrary length,need not to be actually stored. It has been shown inwhile maintaining the MDS property of it.[7] that RDP can be extended to an arbitrary length in2.1 Code shortening algorithmthis way. Obviously, this shortening scheme is suitableFirst, we give a quick look of the code shorteningfor an arbitrary horizontal RAID-6 code.algorithm by an example. Suppose we want to shortenXu, et al.12] found the equivalence between the con-a 5-column X-Code (as shown in Fig.2) by one column.struction of a new kind of vertical RAID-6 code, calledThen the last column ds, the parity block of the 5th par-B-Code, and the perfect one factorization of completeity stripe P(5) and the parity block of the 10th paritygraphs. The structure of B-Code consists of n columns,stripe P(10) should be removed. Hence, we select the杂rows when n is evenor 2 rows when n is odd. Thedata block (5,7) in Column d1 to be the new parity blockexistence of perfect one-factorizations for every completeof P(5), and select the data block (4,10) in Column d2graph with an even number of nodes is 8 famous conjec-to be the new parity block of P(10). In this way, weture in graph theoryl3, Unfortunately, the conjecturehave constructed a shortened X-Code with 4 columns.has not been proven so far. Thus the possibility of con-The structure of the 4-column X-Code is shown in Fig.3.structing B-Code with an arbitrary code length can notFigure 4 presents the algorithm for constructing an n-be afirmed.column X-Code by shortening from a standard p columnWang, et al. proposed a novel way to construct hori-X-Code, where n is an arbitrary integer and p is a primezontal RAID-6 codes. They found the close relationshipnumber greater than n.between the horizontal RAID-6 codes and the column-hamiltonian latin squares (CHLS). Given a CHLS ofdd2order n, a parity dependent horizontal RAID-6 code(PDHLatin) with n+1 columns(14) and a parity inde-5,61.pendent horizontal RAID-6 code (PIHLatin) with n+2,8 5,9 1,102.6columns(15] can be constructed. In fact, PDHLatin canbe regarded as the extension of RDP, and PIHLatin can5,7。,8,93,10be regarded as the extension of EVENODD. The au-thors proved the bijection between CHLS and the per-2s. 4fect one-factorizations of the complete graphs. Thus,7like B-Code, the existence of PDHLatin code or PIH-Latin code with an arbitrary length remains a conjec-Fig.3 Shortened X-Code with 4 columnsture.Different from the above techniques, our code short-ening algorithm works on the structure of an existingvertical RAID-6 code (i.e, X-Code), and can extend its1. Select a prime number p that stisfes p>r.length to an arbitrary size. The proposed algorithm pro-2. Construct a standard X. Code with P columns.vides a general way to extend a vertical RAID-6 code.3. Remove the last p-n columns from theIt must be noted that the algorithm is also suitable forother vertical RAID-6 codes such as P-Codel11].4. Select a data block in parity stripe P(n+1) from2 Code shortening algorithm for X-Codecolumn dh or dh, and set it to be the new parityblock of P(r+1); keep its label unchanged.RAID-6 codes usually have code-length restrictions.5. Repeat Step 4 for P(r+1+p), P(+2), .P(+2+p),”P(2p).Such restrictions make these codes somewhat impracti-cal in a real environment, since the storage administra-tors might be expecting to configure a disk array withFig.4 Code shortening algorithm for constructing an n-an arbitrary number of disks. Thus, it is necessary to中国煤化工extend a RAID-6 code to an arbitrary code length.As a vertical code, X-Code can not be shortenedIn |MHC N M H Gning agrithm, thestraightforwardly like horizontal codes. In the structurenew parity blocks are selected from the data blocks inof X-Code, each column contains not only data blockscolumn d1 or d2. In fact, we can choose arbitrary twoJ Shanghai Univ (Engl Ed), 2011, 15(3): 194-200197columns for the selection of parity blocks, not neces-stripe P(1) to recover block (1,8), and use parity stripesarily d1 and d2. One column alone may not have theP(8) to recover block (8), etc. We can see this recoverysuficient proper data blocks for the selection, but twoprocess is exactly the same as that of the standard X-columns collectively can provide suficient data blocksCode in Section 1.for the selection even if we remove all the other columnsThe only difference between the standard and thein the code structure. The reason is the total number ofshortened X-Code is that, in the structure of the short-blocks in two columns is exactly the same as the totalened X-Code, the parity blocks are not fully indepen-number of parity stripes. Thus it is possible to assigndent like those of the standard X Code. For instance,a block to each parity stripe as the parity block. Forin Fig.3, the block (5,7) is not a data block but theinstance, the structure of a 4 column X-Code is shownparity block of parity stripe P(5), at the same timein Fig.3. If we remove column ds, we can assign blockit still participants in parity stripe P(7). Thus, if a(4,8) in column d1 to be the parity block of parity stripedata block in P(5) is updated, the parity block of P(5)P(4), and block (5,9) in colunn d2 to be the parity blockshould be subsequently updated, and then the parityof parity stripe P(9); if we further remove column ds,block of P(7) should also be updated. As a result,we can assign block (3,9) in column d1 to be the paritythe shortened X-Code may have increased update com-block of parity stripe P(3), and block (1,8) in column drplexity and computational complexity compared withto be the parity block of parity stripe P(8). It would bethe standard X-Code. However, the shortened X-Codemeaningless to remove all the columns except columnsmaintains the MDS property (ie, optimal space efi-dy and d2 because there will be no data blocks left inciency will be proved in Section 3), which is believed tothe code structure.be a more important metric for RAID-6 codes in modernThe fact that the only restriction for the selection ofstorage systems.he prime number p in the first step of the algorithmis that p must be greater than the column number n.3 Performance analysisThis indicates that we have various choices to constructAs is mentioned before, we have multiple choicesa shortened X-Code.For instance, we can constructwhen constructing a shortened X-Code using the codea 4-column X-Code by shortening 1 column from a 5-shortening algorithm. In other words, the selection ofcolumn X-Code, 3 columns ftom a 7-column X-Code, 7the prime number p is not restricted in the code short-columns from an 11-column X-Code, etc. The resultingening algorithm for X-Code. In this section, we providestructures are all MDS codes. But they have diferenta quantitative analysis on the performance (i.e, com-numbers of rows, and they may also have different com-putational complexity, update complexity and space ef-putational complexity and update complexity. We willficiency) of X-Code at consecutive code lengths betweenstudy the impact of the code shortening algorithm on4 and 30. This length range is enough for a practicalthe performance of X- Code in Section 3.RAID-6 array. A general set of formulas are worked2.2 Proof of correctnessout. Through these formulas we can easily discern theIn this section, the correctness of the code shorteningimpacts of the code shortening algorithm on the perfor-algorithm for X-Code will be proved, namely, the short-mance of X-Code.ened X-Code can recover from two column erasures.3.1 RAID-6 optimal propertiesIt has been shown in Section 1 that the standard X-In this section we review the optimal bounds for theCode can recover from any two column erasures. UponRAID-6 performance metrics.the occurrence of double columns erasures, X Code in-First, according to the Singleton formulal9l, the nec-volves in a recovery process that is able to recover allessary and sufficient condition for a RAID-6 code withthe lost blocks in the two erased columns step by stepn columns to be maximum-distance-separable (MDS) isusing the parity stripes.that it has a ratio of 2 parity blocks for every (n-2)As for the shortened X-Code, the recovery algorithmdata blocks. Being MDS means that the code has theis exactly the same as that of a standard X-Code. This isoptimal space efficiency. Thus, the optimal space effi-because all the labels of the blocks remain unchanged,ciency for all the RAID-6 codes is -2.enabling the recovery process to work correctly. TakeSecond, it has been proven that the optimal compu-the 4-column shortened X-Code shown in Fig.3 as antational complexity during construction (i.e., encoding)example, and assume again the columns dz and d3 arefor any MDS RAID-6 code, in terms of the average num-erased. First, the parity block (4,10) can be recoveredber (中国煤化工k, is2- 1Onusing parity stripe P(4), since all the other blocks inthe oErven that the optimalP(4) are available. Given the parity block (4,10) is recompiYHC N M H Goubledisk-lailure ecovered, we can subsequently recover the data blockconstruction (i. e,decoding), in terms of the average(1,10) parity stripe P(10). Then, we can use paritynumber of XOR operations per lost block regeneration,198J Shanghai Univ (Engl Ed), 2011, 15(3): 194 -200is (n-3), where n is the number of columnsl1I,omit it here due to space limitation.Third, in order to be able to recover from double diskfailures, each data block in a RAID-6 code must partici-1.44pant in at least two parity stripes on average. Thus, the1.40-o X-Codeoptimal (i.e, lowest) update complexity for any RAID-61.36-+- X-Code (=31)code is 2.1.321.283.2 Computational complexity8 1.24 tThe standard length of X-Code is a prime number.1.20Consider an n-column X-Code shortened from a stan-1.16dard X-Code of length p by (p - n) columns, where p is1.12 ta prime number. There are a total number of 2p parity1.08stripes in the structure of X-Code. When shortening1091.00one more column from X-Code, (2p-2) out of the 2pparity stripes will be reduced by one block each. Thus24 28 32the total number of XOR operations during encodingLength n .is reduced by (2p-2). For the n-column shortened X-Fig.5 Normalized encoding computational complexity forCode, the total number of XOR operations is reducedX-Codeby (p- -n)(2p- -2) compared with that of the p columnstandard X Code, and the total number of data blocksis reduced by (p- -n)p.3.3 Update complexityIt has been proven that the p column standard X-In the structure of the standard X-Code, each dataCode has the optimal computational complexity, andblock participants in the calculation of, and is protectedits encoding computational complexity is2- 2 XORby, exactly 2 parity blocks. At the same time, the par-operations per data block. Since the total number ofity blocks are independent from each other. Thus, andata blocks in the structure of the p-column standardupdate to a data block afects exactly 2 parity blocks,X-Code is p(p- -2), the total number of XOR operationsnamnely, the update complexity of the standard X-Codeneeded in the encoding procedure is 2p(p- -3). Therefore,is 2, which is optimal.the encoding computational complexity of the n-columnX-Code can be calculated a8Code is slightly more complicated. From the code short-2p(p- 3)- (中p- n)(2p-2)ening algorithm, when a column is removed from the(1)structure of X-Code, the parity blocks in this column(p-2)- (p- n)pis relocated to the data blocks in column di or d2. ForFigure 5 plots the encoding computational complex-example, in Fig.3, when column ds is removed from X-ity for X-Code at the lengths between 4 and 30. All theCode, the parity block of parity stripe P(5) is relocatedvalues are normalized to the optimal value of2-二玉.to the block (5,7) in column d1, and the parity block ofThere are two curves in the figure. The curve entitledparity stripe P(10) is relocated to the block (4,10) inwith X-Code refers that the selection of p for the currentcolumn d2. As a result of the parity block relocation,length n is the smallest prime number that greater thanthe parity blocks of the parity stripes are now no longern, and the curve entitled with X-Code (p= -31) refers thatindependent from each other, and the update complex-the selection of p is fixed to the prime number 31.ity of the X-Code increases. Take Fig.3 as an exampleFrom Fig.5, it can be seen that the encoding com-again, if the data block (5,6) is updated, the parity blockputational complexity of X-Code is very close to the(6) of P(6) and the parity block (5,7) of P(5) should beoptimal, and it reaches the optimal at its correspondingupdated first. Then the parity block (7) of P(7) shouldstandard lengths. On the other hand, when the selectionalso be updated, since the parity block (5,7) of P(5) alsoof p is fixed to be 31, the encoding computational com-participants in the calculation of the parity block (7) ofplexity of X-Code (p= -31) increases with the decrease ofP(7). Thus, the update complexity of data block (5,6) isthe code length. It indicates that the encoding compu-3. Similarly, all the data blocks in P(5) and P(10) havetational complexity of X-Code increases when it is short-the update complexity of 3, and the other data blocksened. To construct an n-column shortened X-Code, sestill have the update complexity of 2. The average up-lecting a smaller p means that the standard code needsdate中国煤化工-Code can thereforeto be shortened by fewer columns, and thus would resultbe Cain a lower encoding computational complexity.THCNMHGAs for the computational complexity of decoding,4x3+6x 2since it has a similar pattern to that of encoding, we10--=2.4.(2)J Shanghai Univ (Engl Ed), 2011, 15(3); 194 200.199Cenerally, the update complexity of the n-columnsfficiency of the shortened X-Code isX-Code is derived as in (3)np- 2p，(2+ 245-n)(n-1)-2.n>(4)p(n-2)It can be seen that the shortened X-Code attains2+ (p+3- 2n)(1 +(n-2)(p+4- 2n))(3)the optimal space eficiency of n-2, and thus is an MDScode.+ 2(n - 1)(nr - 3)/p(n- 2),therwise.4 ConclusionsFigure 6 plots the update complexity for X-Code atIn this paper, a code shortening algorithm for x-the lengths between4 and 30. Similar as Fig.5, theCode is presented. The algorithm is capable of extend-curve entitled with X-Code refers that the selection ofing X-Code to an arbitrary code length while maintain-p for the current length n is the smallest prime num-ing. its MDS property. In the context of the proposedber that greater than n, and the curve entitled withcode shortening algorithm for X-Code, we conduct anX-Code (P= -31) refers that the selection of p is fixedin-depth perfrmance analysis on X Code and reveal theto be the prime number 31. We can see that the up-impacts of the code shortening algorithms on the per-date complexity of X-Code reaches the optimal at itsformance of X-Code.standard lengths, and at a few other lengths it is a lit-As a diretion for the future work, we frst plan totle higher than the optimal. On the other hand, when .apply the erasure codes to the new storage media such asthe parameter p is fixed to be 31, the update com-SSD or PCM On the other hand, it would also be valu-plexity of X-Code (p=31) increases linearly when n isable to fullyl explore the potential computational abilitylarge (ie,n>呓), and more rapidly when n is smallof modern multi-core processors or GPGPUs to benifitthe erasure coded storage systems.(i.e,n ≤啦), with the decreasing of its length. ThisReferencesis because the smaller the length n is, the more columnsit should be shortened from the standard length (ie,[凹PATTERSON D, GIBSON G, KATz R. A case for redun-31 in this example), and the more dependencies amongdant arrays of inexpensive disks (RAID) [C]// Proceed-the parity blocks it incurs. Thus, it can be concludedings of the ACM Conference onManagement of Data,that, the update complexity of X-Code increases when itChicago, USA. 1988:109-116.is sbhortened, and when constructing an n- column short-[2] SCHROEDER B, GIBSON G. Disk failures in the realened X-Code, selecting a smaller p would be better, sinceworld: What does an MTTF of 1 000000 bhours meanit would result in a lower update complexity.to you? [C]// Proceedings of the 5th USENIX Confer-ence on File and Storage Technologies, San Jose, USA.2r2007: 1-16.20 t。X-Code[3} PINHEIRO E, WEBER w, BARROSO L A. Failure trends8-+- X-Code (p -31)in a large disk drive population [CI// Proceedings ofthe 5th USENIX Conference on File and Storage Techr14 tnologies, San Jose, USA. 2007: 17-29.4 Wu w, XIE C, HUANG J, ZHANG C. Highly scalablemetadata distribution algorithm in mass storage sy8-tem (J]. Journal of Shanghai University (English Edi-tion), 2008, 12(5): 419- 425.同] MAO B, FENG D, Wu 8. MP-RAID: Mirror and parityprotected disk array [J]. Journal of ShanghaiUniversity(English Edition), 2009, 13(6): 444 449.8121620242832Lengthn[6] PLANK J, LUO J, SCHUMAN C, Xu L, HEARNZ. A per-Fig.8 Update complexity of X-Codeformance evaluation and examination ofen- sourceerasure coding librarfor storage [C]// Proceedingsof the 7th USENIX Conference on File Storage Tech-3.4 Space efficiency中国煤化工)9: 253-265.In the structure of an n-column shortened X-Code,[7a fior double disk failurethere is a total number of np blocks. Therein, the num-HCNMHGhe 3rd USENIX Con- ,ber of parity blocks is still the samne as that of the stan-ference on File Storage Technologies, San Francisco,dard X-Code, namely, 2p parity blocks. Thus, the spaceUSA.2004: 1-14.200J Shanghai Univ (Engl Ed), 2011, 15(3): 194-200[8] Xu L, BRUCK J. X-Code:MDS array codes with opti-IEEE Transactions on Information Theory, 1999, 45(6):mal encoding [J]. IEEE Transactions on Information1817-1826.Theory, 1999, 45(1): 272 -276.[13] WAGNER D. On the perfect one-factorization conjec-9] BLAUM M, ROTH R. On lowest density MDS codes小]ture ([J. Discrete Mathematics, 1992, 104(2): 211 -215.IEEE Transactions on Information Theory, 1999, 45(1):[14] WANG G, LIN s, Liu X, XIE G, LrU J. Combinatorial46- -59.constructions of multi-erasure-correcting codes with in-[10] BLAUM M, BRADY J, BRUCK J, MENON J. EVENODD:dependent parity symbols for storage systems [C]//Proceedings of the IEEE Pacific Rim InternationalAn optimal scheme for tolerating double disk failure inSymposium on Dependable Computing, Melbourne,RAID architectures [J]. IEEE Transactions on Comput-Victoria, Australia. 2007: 61- 68.ers, 1995, 44(2): 192-202.[15] WANG G, Liu X, Liu S, XIE G, Liu J. Generalizing[11] JIN C, JIANG H, FENG D, TIAN L. P-Code: A new .RDP codes using the combinatorial method [C]// Pro-RAID-6 code with optimal properties [C]// Proceed-ceedings of the IEEE International Symposium on Net-ings of the 23rd International Conference on Supercom-work Computing and Applications, Cambridge, USA.puting, New York, USA. 2009: 360 369.2008: 93-100.[12] Xu L, BOHOSSIAN V, BRUCK J, WAGNER D. Low-density MDS codes and factors of complete graphs [J].(Editor HONG Ou)中国煤化工MYHCNMHG