存储系统中的纠删码研究综述

现有国内外存储编码技术综述 计算机研究与发展期刊论文罗象宏等:存储系统中的纠删码研究综述编码、RD尸P编码⑩等都是横式编码.在横式编码蒙RS编码使用的生成矩阵是范德蒙矩阵,而柯西中,通常将存储数据的磁盘数目记为n,存储冗余的RS编码所用的生成矩阵则为柯西矩阵磁盘数目记为m2.1.1范德蒙RS编码7)纵式编码( vertical codes)冗余存储在图2所示为RS编码的编码和重构原理.RS数据磁盘中的编码方式,即在纵式编码中,某些条块编码实际上就是利用生成矩阵与数据列向量的乘积中既存储了数据元素,又存储了冗余元素,例如Ⅹ来计算得到信息列向量的.其重构算法实际上也是code编码等利用未出错信息所对应的残余生成矩阵的逆矩阵与8)容错率( fault tolerance)—可以容忍的最未出错的信息列向量相乘来恢复原始数据的,具体多任意条块出错数目,记为t.即当任意不多于t块算法可参见文献[13].但是在RS编码重构原理的条块出错时,均一定可以通过相应的重构方法恢复推导过程中,有一个条件至关重要,那就是未出错信出所有出错的条块.而存在某t+1块条块,如果这息所对应的残余生成矩阵在GF(2)域上必须要满t十1块条块出错,将没有办法通过重构方法恢复出足可逆的条件.更进一步来说,为了满足RS编码在所有出错的条块任何情况下均是可重构的,对于任意的m个元素出9)存储利用率( storage efficiency)-—存储错时,均要能够通过重构算法恢复出数据,这就要求系统的存储效率即是指存储的数据量与所有的信息对于任意的n个元素(n的含义是指去掉m个出错量(所有的信息量是指数据量与冗余量之和)之比,元素以后剩下的n个未出错的元素),其对应的残余记为E生成矩阵均要在GF(2ˉ)域上满足可逆,这就对RSMDS编码( maximum distance separable编码的生成矩阵提出了很高的要求.在生成矩阵中,codes)满足了 Singleton边界条件12的编码方要求任意n个行向量均必须在GF(2)域上满足线式,即达到了理论上最优的存储利用率的编码性无关(行向量线性无关是矩阵可逆的充要条件)11)编码( encoding)-在纠删码算法下由数据计算出冗余的过程.12)更新( updating)当数据元素需要进行修改时,在纠删码算法下,重新计算与该数据相关联00n+m[000的冗余的过程.在存储系统中,数据更新非常频繁,因此更新效率是评价纠删码算法的最重要标志BuB2B13B1Bi2B2B2242C13)重构( decoding)——当部分磁盘或者磁盘B31 B32 B33 B35中的某些数据块出错时,利用纠删码对应的重构算B法,从剩余的未出错信息中恢复出所有数据的过程.100002存储系统中典型的纠删码01000D本节主要介绍当前典型和常见的各类纠删码并对这些纠删码进行分析和比较.001|02.1RS(Reed- Solomon)编码SurvivorsRS编码是唯一可以满足任意的数据磁盘数目Fig. 2 Encoding and decoding principle for Reed-(n)和冗余磁盘数目(m)的MDS( maximum distanceSolomon codel15jseparable)的编码方法.RS编码起源于1960年13,图2RS编码的编码和重构原理15经过长期的发展,已经具有较为完善的理论基础在数学上应用极广的范德蒙矩阵( VandermondeRS编码是在 Galois域GF(2)上进行所对应的域 matriⅸx)正好就可以满足RS码的重构原理对于生元素的多项式运算(包括加法运算和乘法运算)的编成矩阵提出的要求13.在GF(2)域上,将范德蒙矩码方式,它属于横式编码.RS编码通常分为2类阵进行初等变换,将其前n行变成一个单位矩阵,就类是范德蒙RS编码( Vandermonde rs codes13);可以得到满足RS编码要求的生成矩阵.基于这个另一类是柯西RS编码( Cauchy RS codes14).范德生成矩阵的RS编码就是范德蒙RS编码计算机研究与发展2012,49(1)在GF(2∞)域上,加法的定义实际上就是异或用也最广.下面我们首先介绍横式阵列码,然后在(XOR)运算,而乘法则要复杂得多,通常需要借助2.3节中介绍纵式阵列码离散对数运算和査表才能进行.因此,标准RS编码横式阵列码( horizontal parity array codes)是的计算开销太大,无法适应存储系统对于计算效率指冗余独立于数据条块,单独存储在冗余条块中的的要求阵列编码方式.它的结构特点是让冗余单独存放在2.1.2柯西RS编码独立的磁盘中(这些磁盘被称为冗余磁盘),而让剩在GF(2)域上,复杂的乘法运算和矩阵求逆下的磁盘专门用于存储数据,这样的排布方式使得运算成为制约标准RS编码进一步发展的障碍.除整个磁盘阵列具有非常好的可扩展性横式阵列码了范德蒙矩阵以外,是否还存在别的矩阵同样可以的容错率一般都不是很大,例如,容错率为2的编码满足RS编码的重构算法对于生成矩阵提出的要包括 EVENODD”,RDP1,EEO10, Liberation求?是否存在一种生成矩阵可以将GF(2)域上的Code等.容错率大于2的编码目前还研究得较乘法化繁为简?柯西RS编码的出现给予了这些问少,但是也涌现了一些成果,例如STAR2编码等题肯定的回答图4给出了2类典型的横式编码的示意图柯西RS编码使用柯西矩阵来代替范德蒙行EVENODD编码被公认是阵列码的始祖,RDP10列式,使得生成矩阵变得更为简单.同时,文献[14]也是一类应用很广的横式编码.在这些编码体系中中提出的位运算转换方法可以对于柯西RS编码中都对磁盘数目提出了严格的要求(要求磁盘数目必的乘法运算进行改进经过简单的改造,柯西RS编须是素数或素数-1),同时还要求在单个条块中的码可以将GF(2∞)域上的乘法运算转化成二进制的数据元素的个数必须与磁盘数目相匹配(具体要求乘法运算.因此,整个RS编码的运算就可以转化成可参看文献[9-10],此不赘述).从空间利用率上看,这2类编码在理论上满足了最优的存储效率,都是只包含异或(XOR)的简单运算.如图3所示就是经MDS( maximum distance separable)的编码过改造过后的RS码的编码过程示意图161(田申排田 One strip= packets田腓田田噩W目ParityD1,1 D1,2 D1,3DParityParityParityCodewordStrips/PacketsStrips/ packetsFig. 3 Modified encoding principle for Cauchy Reedolomon code16图3改造后的柯西RS码的编码原理16(a) evenodd codel15j仔细观察改造后的RS码的编码过程,很容易DataDataData发现,编码的效率直接决定于生成矩阵中“1”的数Disk 0 Disk 1 Disk 2 Disk 3 ParityParity目,同时,这个“1”的数目还影响着RS码的更新效40率.那么,如何尽量减少生成矩阵中“1”的数目,从而3得到最优的编码和更新效率呢?文献[17]对此专门(b) rdP codel1oj作了深入的研究,由于篇幅有限,此不赘述.2.2横式阵列码Fig. 4 Two kinds of typical horizontal codes与RS编码相比,阵列码( array codel8)完全基图4两类典型的横式编码于异或(XOR)运算,这是纠删码研究的重点.阵列由文献[6]可知,任意的编码结构在数学上实际码的含义就是将原始的数据和冗余都存储在一个2都可以使用一个生成矩阵来进行描述那么,从这样维(或者多维)的阵列中.与传统的RS编码相比,在的角度来看,决定一种纠删码的编码效率和更新效率阵列码中,仅使用异或(ⅩOR)操作,实现容易,编实际上就是生成矩阵中“1”的数目,如何能够减少生码、更新、以及重构的过程都相对比较简单,因此应成矩阵中“1”的数目,从而提高纠删码的效率,成为罗象宏等:存储系统中的纠删码研究综述个新兴的研究问题.文献[20,22-23]对于RAID-6对于磁盘数目n的要求非常严格,要求n必须是中的这个问题进行了深入的研究,并形成了一个个素数,才能保证在任意2块磁盘出错的情况下均最低密度RAID-6编码的体系( minimal density能恢复出所有的数据.由于n必须是素数的限制,以RAID-6 codes)及各个冗余元素与几乎每块盘的数据元素均有关从传统的 EVENODD和RDP编码出发,为了系,因此Ⅹ-code的可扩展性很差.在 X-code中,冗提高编码的容错能力,又派生出一系列新的可以容余元素与数据元素联系紧密,这导致了很难从X更高错误的编码,例如STAR2, Generalized code推广出容错率更高的编码.另外,在重构的过EVENODD cOde2,Feng' Codel2526等.它们都属程中,必须按一定的顺序进行迭代的重构,不能利用于横式阵列码的范畴,都具有较好的编码效率和存并行操作提高其重构效率,这些均是Ⅹ-code的不足储利用率,限于篇幅,此不赘述之处.但是总体来讲, X-code仍然是一类非常好的2.3纵式阵列码纠删码技术.目前大部分垂直码均是MDS的编码,纵式阵列码( vertical parity array codes)是指其容错能力一般也不高.但是 WEAVER编码是冗余存储在数据条块中的阵列编码方式,即在纵式个例外,它可以提供高达12的容错能力,但是其编码中某些条块中既存储了数据元素,又存储了冗空间利用率始终不能超过50%余元素.纵式阵列码一般都具有较简单的几何构造2.4LDPC编码结构,其计算复杂度的开销均匀地分摊到各块磁盘LDPC( low-density parity-check code2)码是上.在横式编码中,连续不断的写操作会带来磁盘热又一类所有运算过程均完全基于异或(XOR)运算点非常集中的瓶颈问题(即冗余数据盘在连续的写的编码.LDPC编码不是MDS的编码,但是它非常操作中会连续用到).而在纵式编码中,由于其结构接近MDS的存储效率,因此可以认为是渐进MDS上的均衡性,这一瓶颈得到了天然的解决.但是纵式( asymptotically mds)的并且从计算效率上来编码的均匀性也导致了磁盘相互之间的依赖性很强,看,IDPC编码比其他的MDS编码要快得多,运算这也就导致了其可扩展性很差.随着研究的深入,各复杂度可以达到O(m)(m表示LDPC编码所在的种各样的纵式编码被陆续提出,例如ⅹcode1,P图上的边数)code2, WEAVER23等.IDPC编码的编码方式实际上是构建在一个二codell是一类MDS的纵式编码,与横式编部图之上·比较典型的IDPC编码是构建在 Tanner码相比,它在编码、更新、重构阶段均具有理论上的图上的编码方式31,在这种编码方式中,二部图的最优效率,但是由于其磁盘之间的关系紧密,因此可左端包括了所有的数据元素和冗余元素,右端的每抄展性较差.如图5所示,在 X-code的编码体系个点则代表了一个等式关系,表示与其相连的左端中,包括n块磁盘,在每块磁盘中包含n个元素,在的各数据元素的异或之和为0.如图6所示,在这其中数据元素有n-2个,冗余元素有2个,特别Tanner图形式下的LDPC编码相当灵活,在重构运需要注意的是,n必须恰好是一个大于2的素数算中,可以忽略数据元素与冗余元素之间的区别,将它们视为同一类数据元素,直接采用以二部图理论为基础的重构算法.LDPC编码最大的特点就是重构过程简单、速度很快.D1+D3+D4+C1=0D1+D2+D3+C2=0Fig. 5 X-code 15JD2+ D3+ De图5 X-codel1lⅩ-code在运算的各阶段均能够达到理论上最优的效率,这是横式编码所不具有的优点.而且在存Fig. 6 LDPC code under Tanner graph 151储利用率上,Ⅹ-code也是MDS的编码.但是Ⅹ-code图6 Tanner图下的LDPC编码1计算机研究与发展2012,49(1)对于LDPC编码的研究还包括基于矩阵表示对于这个问题进行了深入的研究,严格地证明了它方法的重构算法,以及纵式IDC编码等等,这里限们之间的相互转化关系,为阵列码的构造提供了于篇幅,不再详细讨论.但是总体来说,对于LDPC大类新的方法.其中文献[33]的编码通常称为B码的研究更多的还是处于理论研究阶段,在实践中code,另外,P-code也正是利用这种方法构造出使用得很少,这个主要与LDPC编码的构造相对较来的.难以及大部分LDPC码都是不规则编码有关,因此对于存储系统纠删码的易实现性也成为研究中在LDPC编码领域还需要更为深入的研究个值得关注的问题,为此研究人员又提出一类新2.5若干新式编码的称为 Cyclic Code3536的编码.对于这类编码的以上介绍的几类纠删码都是比较传统而又经典研究还处于起步阶段,也许会成为一个未来研究的的.近年来,随着研究的深入,一些新式的纠删码不热点断涌现出来,丰富了纠删码的算法类型.如对于前面所提到的横式阵列码和纵式阵列码,它们各有优缺点如何构造出横纵相结合的新式编码,以充分发探3评价纠删码的重要指标及未来改进趋势出阵列码的优势,成为一个研究的新兴热点.目前对于这类编码的研究尚处于初级阶段,只出现少部分纠删码的容错能力、存储利用率以及计算效率的编码,例如 HoVer编码3等是在存储系统中评价纠删码的重要指标,其中,计算在传统的纠删码结构中,都是采用元素作为计效率又分为编码、更新和重构三大计算效率在本节算的基本单位,在这样的计算方法中,纠删码在容错中,我们将从这几个方面对常见的纠删码作出比能力、计算效率、存储利用率方面都不同程度地存在较和分析,并指出纠删码在各个指标上未来的改进较大的缺陷,难以同时使得3个目标都达到理想的趋势状态.以条块为计算的基本单位的GRID编码解3.1容错能力和磁盘要求决了这个问题,它在本质上仍是横纵相结合的阵列容错能力是纠删码算法的基石,同时,很多纠删码,但是它最高可以达到15的容错能力,并且实现码对于磁盘数目和单一条块中的元素数目也有着很起来也比较简单,在存储利用率方面最高可达80%多要求,我们在本节中将首先对这两方面展开分析以上如表1所示,我们列出了当前较为常见的纠删码的在数学中,对于完全图的完美1-因子分解的研容错能力以及编码对于数据磁盘数目和单一条块中究也为阵列码的构造提供了新的方法,文献[33-34]元素数目的要求Table 1 Fault Tolerance ability and requirements for the Number of Data Disks and the Number ofElements in Single Strip in Erasure Codes表1纠删码的容错能力以及编码对于数据磁盘数目和条块中元素数目的要求Fault toleranceRequirement for theRequirement for the numberErasure codeabilitNumber of data disksof Elements in Single StripReed-Solomon codeArbitraryDepend on the length of codewordDepend on the length of codewordEVENODDPrimeNumber of disRDPPrime-1Number of disksLiberation codePrime that not less than the number of disksSTARPrimeNumber of disks--1X-coderimeNumber of disksWEAVERSolution for corresponding mathematics 2 X Number of disks or 2 X Number ofB-code2problemdisks+1P-codePrime or prime-1Number of disks divides 2罗象宏等:存储系统中的纠删码研究综述在表1中,大部分编码对于数据磁盘数目和单目限制、容错率、计算效率等方面有着其独到的优一条块中元素数目的要求都非常严格,一般都要求势.下面,我们将讨论这些编码的特点,并分析空间数据磁盘的数目为素数,这就对磁盘阵列提出了很利用率和这些优势之间的关系高的要求,同时也导致了这些编码的可扩展性较差WEAVER编码28与前面介绍到的众多编码不在容错能力为2的编码中只有 B-code编码和同的是,它不再一定是MDS的编码,其空间利用率Liberation编码没有对于数据磁盘数目的素性提出不到50%,但是容错率却可以高达12.另外, WEAVER要求,但是它们也有各自的问题: B-code的构造方编码突破了素数的限制,对于任意不超过12的磁盘法对应着数学中的一个公开难题,因此对于小规模数目均存在对应的 WEAVER编码的构造方法.这的B-code只可以使用搜索技术找寻其构造方法,而些优点都是从它的空间损失上换取到的,可以说,它对于大规模的 B-code的构造则只能寄希望于该数在数据磁盘数目限制、容错率、空间效率和计算效率学问题的圆满解决. Liberation编码同样对于磁盘等方面达到了一个比较好的平衡数目没有非常苛刻的要求,但是该编码要求在单LDPC编码是另一类非MDS的编码,但是它非条块中包含的元素数目必须恰好是一个素数,并且常接近MDS的存储效率,因此可以认为是渐进要求数据磁盘的数目不能超过单一条块中的元素数MDS的.LDPC编码在空间上的损失同样换来了目,这样的条件同样很难得到满足计算效率上的优势,从计算效率来看,LDPC编码在横式编码中,对于数据磁盘数目的要求是可比其他的MDS编码都要快,其运算复杂度可以达以灵活变通的.因为在横式编码中,大部分磁盘是专到O(m)(m在这里表示LDPC编码所在的图上的用于存储数据的,于是可以在逻辑上,令这些磁盘上边数)的所有数据均恰好为“0”,而在实际应用中去除掉这3.3编码效率些数据磁盘,这样就可以使得横式编码在实际应用个纠删码的实用性往往取决于其在编码阶段中摆脱对于数据磁盘数目的限制.这样的磁盘扩展的开销情况,因此,编码效率成为评价纠删码的又方法是由于这些磁盘上没有存储冗余,所以这样的重要指标方法对于纵式编码来说并不适用RS编码是定义在 Galois域GF(2)上的纠删从表1中还可以发现,大部分纠删码的容错能码,在它的运算中,加法是较为简单的,但是乘法的力都不太高,但是也有两类编码的容错能力是不错运算却非常复杂,甚至需要借助离散对数运算和査的,并且它们对于数据磁盘数目和单一条块中的元表才能实现,这样的纠删码的编码效率是远低于只素数目都没有特殊要求,但是这两类编码也有各自采用异或运算的编码的.尽管柯西RS编码克服了的问题.RS编码虽然可以适应任意的容错能力的需标准RS编码中的乘法问题,但是其生成矩阵中“1”求,但是RS编码是基于 Galois域GF(2)上进行运的数目较多仍然导致了其编码效率不高,尽管文献算的,其运算效率很差,并且RS编码对于生成矩阵17对此作了深入的研究,最优化了柯西RS纠删的要求极为苛刻,导致RS编码的构造很难,目前已码的编码效率,但是这个编码效率与其他的阵列码知构造出来的运算都比较复杂.同样, WEAVER编相比还是有较大的差距.码虽然也拥有较好的容错能力,但是它没有系统的对于非MDS的编码,它们的构造一般比较复构造方法,大多都需要依靠搜索技术才能确定它的杂,不具有规律性,因此难以系统地讨论它们的编码编码构造,这样的方法难以推广效率.下面,我们将采用在编码过程中生成单个冗余3.2空间利用率元素需要作的平均异或(XOR)次数来度量各类纠删码的使用产生了冗余的数据,这就带来了MDS纠删码的编码效率.很显然,在MDS的横式额外的空间开销.如何充分地利用存储资源,提高空纠删码中,对于数据磁盘数目为η的编码,生成单个间利用率,成为纠删码研究中的一个重要问题冗余元素的理论最少异或次数为n-1,因此,我们在目前常见的纠删码中,MDS的编码以其理论将生成单个冗余元素的平均异或次数除以n-1,来上最优的存储利用率而被广泛推崇.前面介绍的大正规化地表示各类横式纠删码的编码开销.如图7部分编码都是满足MDS的编码,例如RS, EVENODD,所示,图中纵轴表示的是各类纠删码中生成单个冗余RDP, Liberation code,STAR,X-code等.但也有一元素的平均异或次数与理论最少异或次数之比(很显些编码是非MDS的,这些编码往往在数据磁盘数然,纵轴上的1代表的是理论最优的编码效率)计算机研究与发展2012,49(1)18仍是一个开放问题,还需要更深入的研究Liberation(w=17)Liberation w=31)51.14Liberation(w=101)Reduces Xors fromEVENODD41to28(31.7%)RDPOptimal= 24STAR1.10X-codeA=∑口C1,1=A+E+■B=∑■C=∑口+B□+口+口C2,=C+E+口+口1.02C2,2=B+D+口+口甚志上E=∑口C2,3=A+口+口+口1015Fig.8 Parity Scheduling technique 151Number of data disks图8 Parity Scheduling技术15Fig. 7 Encoding efficiency comparison for erasure codes.3.4更新效率图7各类纠删码的编码效率对比纠删码应用在通信传输中时数据不存在更新的在图7中,我们使用 X-code来代表MDS的纵问题,因此在过去的研究中,编码算法和重构算法得式编码,它们在编码效率上可以达到理论上的最优到了更多的关注然而在存储系统中,连续不断的效率,但是由于他们对于磁盘数目的限制非常严格,IO是其重要的特点,由于系统中有了冗余,当数据只能当磁盘数目为素数时才能满足编码构造,因此,被更新时,同时也就需要去更新与它相关联的所有在图7中, X-code的图像是一些离散在磁盘数目为冗余,这就增加了存储系统的更新开销.由于数据是素数上的点.不断被更新的,因此,对于存储系统中的纠删码,其如同4.1节中提到的,横式编码可以在实际应更新效率更受关注,更新效率成为了评价一类纠删用中“减少”其磁盘数目,在图7中给出了各类横式码最重要的标志纠删码的编码效率对比.RDP的编码效率相对较在本节中,我们使用更新单个数据元素时平均好,但是当“缩短”其磁盘数目时,效率也受到了较大需要同步更新的冗余元素数目来表示一类纠删码的的影响.对于磁盘数目的“缩短”方案,由于编码的不更新效率.如图9所示,我们对比了各类容错率为2对称性,在RDP编码中“去掉”靠前的磁盘是最好的的纠删码的更新效率选择,而相反的是, EVENODI和STAR编码中“去掉”靠后的磁盘则比较好.从图7中还可以看出,2.9Liberation编码较以往传统的横式编码而言,在编2.7码效率上得到了大大的提高,特别是随着编码中τReed-Solomon这一参数的增大,其编码效率越来越接近理论上的2.5EVENODDRDP最优编码效率20Liberation(w=31)2.3对于编码效率的提高,除了研究在生成矩阵中“1”的数量更少的纠删码以外,另一类可以提高编码效率的技术就是 Parity Scheduling技术20.如图81.9所示1, Parity Scheduling技术通过改变各冗余的15计算顺序以及生成矩阵中某些重叠部分的预计算,Number of Data disks使得后续计算充分利用到前缀计算的结果,以此来Fig.9 Updating efficiency comparison for erasure codes减少编码运算中的异或次数. Parity scheduling的图9各类纠删码的更新效率对比方法不仅可以应用于编码运算中,在重构运算中同尽管在RS编码中,更新单个数据元素时只需样可以发挥巨大的作用. Parity Scheduling技术目要同步更新2个冗余元素,是理论上最优数目,但是前还只能适用于少数生成矩阵,还没有一种有效的由于RS编码的运算是定义在 Galois域GF(2)上可以使得任意生成矩阵都能得到最优 Parity的,它的运算效率远低于只采用异或运算的编码,因Schedule的一般算法.对于这类算法的研究目前还此实际上RS编码的更新效率很低.而对于柯西RS罗象宏等:存储系统中的纠删码研究综述编码,与编码效率的分析一样,其生成矩阵中“1”的出错的磁盘组合情况,用以严谨地分析编码的重构数目较多导致了其更新效率不高,尽管文献[17]对效率.与4.3节中分析编码效率时类似,我们采用重此作了深入的研究,最优化了柯西RS纠删码的生构运算中恢复单个错误元素需要的平均异或次数作成矩阵,但是它的更新效率与其他的阵列码相比还为评价一类纠删码的重构效率的标准.在MDS的是有较大的差距.横式编码中,对于磁盘数目为n的存储系统,恢复单与3.3节一样,我们釆用 X-cOde来代表所有纵个错误元素理论上需要的最少异或次数是n-1,因式编码的更新效率,对于磁盘数目的严格限制导致此在图10中,与4.3节中分析编码效率时一样,我纵式编码在图9中仍然表现为一些离散的点,但是们将恢复单个错误元素需要的平均异或次数除以n它的更新效率仍然可以达到理论上最优效率.1,用以正规化地表示各类横式纠删码的重构开EVENODD和RDP的更新效率随着磁盘数目销如图10所示,图中纵轴表示的是各类纠删码中的增长而逐步降低,如图9所示,同时在理论上可以恢复单个出错元素需要的平均异或次数与理论最少证明的是,在 EVENODD和RDP编码中,更新单个异或次数之比(很显然,纵轴上的1代表的是理论上数据元素时,平均需要同步更新的冗余元素的数目最优的重构效率)上界是3个.由于STAR的容错率为3,与容错率为1.202的编码在更新效率上不具有可比性,因此未在图9EVENODD中标示出来,但是由于STAR是 EVENODD的高61.16RDP△Ⅹ-code种扩展,因此通过理论分析和证明可知,STAR的更新效率也是随着磁盘数目的增长而逐步降低的,并且更新单个数据元素时,其平均需要同步更新的冗1.08余元素的数目上界是5个文献[20,22-23]证明了MDS横式编码的更新e1.04+++效率不可能达到数学上的理论最优效率. Liberation1.00△公编码的生成矩阵中“1”的数目就是横式编码在理论上的下界.因此在图9中, Liberation编码的更新效Number of data disks率远好于其他横式阵列码.由此可知,最优更新效率Fg.10 Decoding efficiency comparison for erasure codes与MDS的特性不可兼得.图10各类纠删码的重构效率对比3.5重构效率与3.3节、3.4节一样,我们使用Ⅹcode来代在纠删码研究中,重构过程的效率决定了纠删表纵式编码,特殊的排布结构决定了它的重构效率码算法对于整个存储系统的影响,那么,各类纠删依然可以达到理论上的最优效率,但是大部分纵式码的重构效率到底怎样呢?我们将在本节中进行编码对于磁盘数目严格的限制导致Ⅹ-code仍然表讨论.现为一些离散的点RS编码的重构过程通常分为2步,首先需要作Liberation编码和柯西RS编码并未在图10矩阵求逆,然后才能进行矩阵乘法运算恢复出错的中标明,这是因为它们的重构矩阵都比较复杂,导致元素而且RS编码是定义在 Galois域城GF(2)上的其重构效率不高.然而,4.3节中提到的 Parity纠删码,其乘法运算非常复杂,矩阵的求逆运算就更 Scheduling技术2也同样适用于重构运算,这样可加复杂,因此RS编码的重构效率非常低下,对存储以显著地提高重构效率,提高后的重构效率甚至可系统效率的影响很大以接近理论上的最优效率,具体的应用方法可参考在容错率为2的编码中,当存储系统岀现单个文献[17,20J,此不赘述磁盘的错误时,如果出错的磁盘是冗余磁盘,那么就3.6不同存储系统对于纠删码各类性能的需求可以完全按照编码的方法来重构出错的磁盘,否则,不同的存储系统有着其独到的对于纠删码的需也可以很轻易地按照类似于RAID5的方法来重构求,在本节中,我们将从应用的角度对这个问题进行出错的元素.因此下面我们将只讨论恰好2块磁盘分析.出错情况下的重构效率1)磁盘阵列系统:这类系统的特点是数据磁盘在图10中,我们枚举了在各类编码中所有可能的数量很大,但是冗余磁盘的数目相对较少.在这类计算机研究与发展2012,49(1)系统中,计算效率通常是最受关注的一个因素,纠删制,而横式编码虽然可以“减少”其磁盘数目,却难以码通常是安装在磁盘控制器上的,因此阵列码对于在计算效率上达到最优.如何利用这些编码结构的这类系统比较合适,RAI33是这类编码系统最优点构造出新型的纠删码,也是一个未来很有趣的常见的模型问题.2)P2P系统:这类系统的特点是用于存储数据目前纠删码在容错能力、计算效率、存储利用率和冗余的介质都非常多,这类系统具有廉价性.另方面都不同程度地存在着较大的缺陷,难以同时使方面,由于P2P系特有的流动性,存储介质出错或得3个目标都达到理想的状态.如何构造出各方面者离开网络的概率也非常高,因此需要高容错的纠具优的纠删码仍是未来研究中任重道远的问题删码支持.基于以上特点,利用多副本技术实现容错是P2P系统的最佳选择参考文献3)分布式存储系统:在这类系统中,存储介质的数目同样是相当多的,且它对可用性的要求很高L1 Layman P, Varian H R. How much information 2003?因此,纠删码的重构效率成为影响这类系统性能的Leb/Olj.[2010-10-18.http://www2.simsberkeleyedu/research/ projects/how-much-info-2003关键,而存储利用率并不是关注的焦点[2 Pinheiro E, Weber W D, Barroso L A. Failure trends in a4)归档存储:数据的高可靠性是这类系统唯large disk drive population [c]/ Proc of the 5th USENIX的要求,需要高容错率的纠删码才能适用于这类Conf on File and Storage Technologies. Berkeley, CA:系统USENIX ASSOCiation. 2007: 17-28[3 Schroeder B, Gibson G A. Disk failures in the real worldWhat does an MTTF of 1,000, 000 hours mean to you?4总结和展望LC]//Proc of the 5th USENIX Conf on File and StorageTechnologies. Berkeley, CA: USENIX Association, 2007随着计算机科技的进步和存储系统海量化的发展,为了保证存储系统的高可靠性和可用性,纠删码4 Bairavasundaram L N, Goodson GR, Pasupathy S, et al越来越受到存储系统研究者们的重视.本文介绍了An analysis of latent sector errors in disk drives C//Proc of2007 ACM SIGMETRICS Int Conf on Measurement and当前典型和常见的各类纠删码,并从评价纠删码性Modeling of Computer Systems. New York ACM, 2007能的各项重要指标的角度对比和分析了现有的纠删码技术,为未来纠删码可能的研究方向提供了理论[5 Zheng Qingji. Research on erasure code for secure storage依据system [D]. Shanghai: Shanghai Jiaotong University, 2009经过多年的发展,RS编码作为最早的纠删码(in Chinese)(郑清吉.安全存储系统中纠删码技术硏究[D].上海:上海类型,已被研究得较为透彻.它无论是在编码效率交通大学,2009)更新效率,还是重构效率上,都难已再有提高的空[6] Hafner J M, Deenadhayalan v,RaoK,etal. Matri间.而反观阵列码,因它是建立在异或运算之上的methods for lost data reconstruction in erasure codes [c] /类纠删码,由于其运算简单,容易实现,因而在近年Proc of the 4th USENIX Conf on File and Storage来得到了广泛的关注,还有很多工作值得继续研究.Technologies. Berkeley, CA: USENIX Association, 2005在阵列码中,由于目前提出的各类RAID-6编[7 Hafner J M, Deenadhayalan V, Kanungo T, et al码总是或多或少地存在着各自的缺陷,还没有一类Performance metrics for erasure codes in storage systems, RJ被公认为RAID-6最佳解决方案的纠删码出现,因10321LR]. San Jose, CA: IBM Research, 2004此在未来的一段时间以内,对于RAI6编码的研[8 Li M, Shu J, Zheng W. GRID Codes: Strip-based erasure究仍会是一个热点.同时,随着大规模存储系统的应codes with high fault tolerance for storage systems J. ACMTrans on Storage, 2009, 4(4): 1-22用与发展,低容错率的纠删码已难以适应存储系统9 Blaum M, Brady J, Bruck J, et al. EVENODD: An efficient对于高可靠性的需求,因此,更高容错率的纠删码也scheme for tolerating double disk failures in RAID必然成为未来发展的一个方向.architectures LJ. IEEE Trans on Computer, 1995, 44(2)在对于影响纠删码性能的各项参数的分析和对192-202比中,我们发现,各类纠删码都有各自的优势和缺L10 Corbett P, English B, Goel Aredundant for double disk failure correction [C] //Proc of the点,例如纵式编码在各项计算效率上都可以达到理3rd USENIX Conf on File and Storage Technologies论上的最优效率,但是却受到了磁盘数目严格的限Berkeley, CA: USENIX Association, 2004: 2-15