基于纠删码的云计算存储备份及恢复策略-芦欣.pdf

《基于纠删码的云计算存储备份及恢复策略-芦欣.pdf》由会员分享，可在线阅读，更多相关《基于纠删码的云计算存储备份及恢复策略-芦欣.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、56 2016，52(4) ComputerEngineeringandApplications计算机工程与应用基于纠删码的云计算存储备份及恢复策略芦 欣，刘 渊LU Xin，LIUYuan江南大学数字媒体学院，江苏无锡214122School of Digital Media，Jiangnan University,Wuxi，Jiangsu 214122，ChinaLU Xin，LIU YuanCloud storagebackup and recoVerystl?ategy based onerasure codesComputer Engineering andApplications，

2、2016，52(4)：56-60Abstract：It is a hot topic in the area of cloud computing how to guarantee data reliability in cloud storage systemsThecopy backup technology is an important approach to guaranteeing data reliabilityHowever,there are some disadvantagessuch as taking up too much disk space and having

3、low saving efficiencyErasure code can provide optimized data redundancy thereby preventing data lossApplying erasure code properly can help improve space utilization ratios and acquiresatisfactory data protection effectsIt has been widely used in communicationsThis paper introduces erasure code tocl

4、oud storage systems to replace the copy backup strategy and improve the performance of cloud storage systemsExperiments show that the scheme Call effectively improve data reliability and space utilizationKey words：cloud storage；erasure codes；tolerant；redundant backup摘要：如何保障云存储系统中数据的可靠性是云计算领域的热点问题。副本

5、备份技术是保障数据可靠性的重要手段，但是存在占用存储空间大、存储效率低等问题。纠删码能够提供优化的数据冗余度，以防止数据丢失，恰当地使用纠删码可以提高空间的利用效率并获得较好的数据保护效果，在通讯方面已经得到广泛应用。将纠删码引入云存储系统中，代替副本备份策略，以提高云存储系统的性能。实验表明该方案可以有效提高数据可靠性和空间利用率。关键词：云存储；纠删码；容错；冗余备份文献标志码：A 中图分类号：TPl81 doi：1037780issn1002833114030110l 引言随着信息化程度的不断提高，全球数据呈几何级数方式增长。在传统存储系统面对当前PB级的海量数据存储需求时，存在容量和性

6、能扩展上的瓶颈。云存储(Cloud Storage)”41因扩展性强、性价比高、容错性好等优势，得到了业界的广泛认同。云存储伴随着云计算(Cloud Computing)口。61而产生，是云计算的先驱，承担着以服务形式收集、存储和处理数据的最底层任务，上层的云平台、云服务等业务都在云存储的基础上展开。同传统的硬件存储设备相比，云存储已经发展成为由网络设备、存储设备、服务器、应用软件、公用访问接口、接入网和客户端程序等多个部分组成的一个系统”，。为保证高可用、高可靠和经济性，云存储采用可扩展的分布式文件系统，同时使用廉价的个人计算机来进行系统部署，从而使得整体存储架构能够保持极低的成本m，。存储

7、即服务理念的提出，向人们提供大量廉价存储空间成为现实。尽管云存储价格低廉，部署方便，但其推广却举步维艰。究其原因，不难得出随着云存储所支持的节点规模不断增大，面向的服务不断丰富，云存储系统中大规模节点(包括服务器，链路与交换机)的失效成为常态，数据的可靠性得不到保障，严重阻碍了云存储的发展。如何保证节点在失效的情况下，仍能为用户提供高效、容错的服务，是推广云存储发展必须解决的问题。冗余存储，即为同一份数据存储多个副本，是目前基金项目：江苏省自然科学基金重点研究专项(NoBK2011003)。作者简介：芦欣(1988一)，女，硕士研究生，主要研究方向为网络安全技术，Email：158614175

8、58163conl；刘渊(1967一)，男，教授，主要研究方向为网络流量与网络安全技术。收稿日期：20140311 修回日期：20140606 文章编号：1002833l(2016)04005605CNKI网络优先出版：20140815，http：wwwcnkinetkcmsdoi1037780issn1002-83311403-0110html万方数据芦欣，刘 渊：基于纠删码的云计算存储备份及恢复策略保障数据存储可靠性的主要手段，但传统的副本备份方法随着备份份数的增加成几何方式增长，存在占用存储空间大、存储效率低的问题。纠删码(erasure code)【9。及纠删码技术是一项用来解决通信中

9、信息传输时可靠性问题的方法，在节省物理存储空间，提高容错能力和提高数据的可靠性方面有很大的优势。本文在分析云存储系统的基础上，将纠删码技术引入到云存储系统中，代替传统的副本备份。通过与副本备份方法进行比较实验，结果表明，采用纠删码容错方案的云存储系统具有更高的数据可靠性和存储空间利用率。在此基础上提出优化方案，在恢复原文件后，对损坏的数据块进行恢复，避免重新编码所带来的额外开销。2算法理论与基础21 云存储系统云存储是通过集群应用、网格技术、分布式文件系统等，将网络中大量类型各异的存储设备整合起来，并对外提供数据存储和业务访问功能的系统，具有良好的可扩展性、容错性，以及内部实现对用户的透明等特

10、性。分布式文件系统在云存储中起着支撑性的作用，现有的云存储分布式文件系统主有GFS、HDFS、Lustre1、GPFS”、Ceph、FastDFS、PVFS、PFS和TFS等。这些分布式文件系统各具特色，但在容错机制上设计理念类似，本文以Google公司的Google File System(GFS)为例。一个GFS集群由一个主服务器(master)和大量的数据块服务器(chunkserver)构成，并被许多客户(Client)访问，如图1所示。Master和chunkserver通常是运行用户层服务进程的Linux机器，只要资源和可靠性允许，chunkserver和client可以运行在同一

11、个机器上”。当要存储一个文件时，文件被分成固定大小的块。每个块由一个不变的、全局唯一的64位的数据块句柄(chunkhandle)标识，chunkhandle在块创建时由master分配。Chunkserver将块当作Linux文件存储在本地磁盘并可以读和写由chunkhandle和位区间指定的数据。数据信。自控制信自出于可靠性考虑，每一个块被复制到多个chunkserver上。默认情况下，副本数量为3，这个值可以根据需求指定。22 RS纠删码纠删码也称为前向纠错(FEC)码u”，它的设计思想是将文件分割成不可识别的数据块，并将额外的信息添加到数据块中，通过这些经过编码后的数据块的一个子集就可

12、以恢复完整的数据集。通常情况下纠删码可以用一个三元组(n，k，)来描述，其中k为编码前数据对象被分割的块数；n为编码后的数据块个数；，为一个不小于k的整数。纠删码将k个原始数据块编码生成n个数据块，其中新生成的nk个数据块称为冗余数据，编码后的数据具有nk个数据块的容错能力，当其中任意不多于刀一k个数据块丢失时，都可以通过存活的r(r1k)个数据块进行恢复。工作过程如图2。日日日日日一日日日女个原始数据块 nk个冗余数据块囟日囟日日一日日日日囟日 日日，个存数据块 复原原始女个数据块图2纠嗣码工作流程图3 基于纠删码的备份及恢复策略31备份方案需要存储的文件F=(凡，Fl，一，F)是由固定长度

13、的数据块，(0ik一1)组成的集合，(玎，k，r)纠删码把k个原数据块编码为n(nk)个数据块。编码时选择n个长度为k的向量gf=(踟，g小，g肼n)(0i行一1)，并保证门个向量中任意k个都线性无关，则编码后的文件块为：D=gF=gf0Fo+g。1Fl+g肚刈-n(oi门一1) (1)万方数据Computer Engineering andApplications计算机工程与应用且这n个数据块中任意k个编码数据均可以重构原来的k个数据。设G=g。(0f胛一1，0尼一1)，根据公式(1)可得：GF qFl：F kDoDID。一(2)即一个(n，k，厂)线性纠删码可以表示为D=G，F，其中F=(

14、Fo，Fl，一，一)是信息数据；D=(Do，Dl，D。一1)是经过编码的数据，也称为码字(codeword)；G是nk矩阵，称作此(即，k，r)线性纠错码的生成矩阵，形如(3)；k与n的比值kn称为此线性纠错码的编码率，又称码率(rate)；(nk)k称为该编码的冗余度。G=国o，gl，邑-1)1=goo goi90(女一11glo glIgl(I1)g加一1)0 g加一I)lg(一一1)(女一1)(3)若G的任意k行组成的子矩阵G均可逆，则利用接收到的任意k个数据均可重构原来的k个信息数据。这是研究基于纠删码冗余机制的理论基础。除此之外，引入纠删码的另一个前提是纠删码采用系统码(Sysmat

15、ic Code)(系统码就是指信息位和校验位分开，编码后的码字当中包含信息序列。反之，信息位与校验位相互交叉称为非系统码)。系统码的采用使得任何生成矩阵都可通过运算转化为如式(4)的系统形式，其中J。是kk单位矩阵，P是一个一k)k矩阵。G：(钭1 00 l0 0P0o Po l尸l o P1IPn一一1o Pn一女一l O l 匕一l P1女一l1尸nt1(4)在对原来的k个数据块进行编码时，可表示为式(5)的数学形式，即生成矩阵G乘以信息数据，。在所得的码字中，其前k位由单位矩阵L决定，因此和，中各位数据相同。其余的九一k位被称为校验数据，是k个原始信息数据的线性组合。10：0P0。P1o

16、0I：R女P1女：尸月一一1o PH一女11Pn t一1，DoDI：D。一(5)采用这种系统码方式编码算法进行数据分块时，会生成较多的分块，这些分块不仅包含了数据分块还有冗余分块，这样数据分块与冗余分块的数量总和就会大于单纯的数据分块。将数据分块与冗余分块视为同等地位的分块发送给存储结点进行存储，当用户读取文件时无论是数据分块还是冗余分块，只要获得了一定数量的分块就可以重组出文件内容。由于该算法在生成冗余分块时通常都会引入纠错思想，从而极大地避免了恢复文件与源文件存在差异或无法正常重组的情况。当需要恢复文件时，在所有的咖k)个存活数据块中，任意k个数据块就可以将原文件恢复。由于生成矩阵中每个行

17、向量都与一个数据块一一对应，从，个数据块中选取k个数据块进行解码运算，则这k个数据块对应的行向量可以组成一个k阶方阵Q，其中k个数据块记作为(月o，Rl，R女一1)，Q记作即(qo，ql，q一1)。即Q与原始k个数据块相乘得到了这些存活下来的数据块，可表示为方程(6)。一R：R。(6)已知矩阵Q中任意k个向量线性无关，则矩阵Q可逆。计算Q的逆矩阵Q，用Q。1同时乘以编码方程(6)两边，即可得到原始文件F，运算过程j11(7)所示。，=QQF hF1：以一=QRoRl：R。一(7)32数据块的恢复通过上述方法，只要得到编码生成n个数据块中的任意r(r七)个数据块，就可以复原文件，。但在实际应用中

18、，一旦某个或某些节点失效，文件，的可靠性就随之下降，而重新对文件编码存储又会造成资源浪费，因而能否恢复已经损坏的原有数据块重新存储成为云存储系统容错策略选择的另一要求。在数据块复原时仍然使用恢复原文件的k个数据块，在恢复的过程中分为原始数据块和冗余数据块两种。321原始数据块设在恢复文件F过程中根据k，n，生成矩阵创建的解码矩阵为Q，存活下来的用于恢复文件的k个数据块(Ro，Rl，R)，在恢复原始数据块时，提取Q一中的第i行与完好的k个数据块进行数量积运算将k个数据块进行数量积运算，所得积再做异或运算，即可得到损坏的原始数据块。公式如下：D。=a。R=鲸：Roo缓1lRloog：一】R川(oi

19、k) (8)nn只：万方数据芦 欣，刘渊：基于纠删码的云计算存储备份及恢复策略322冗余数据块恢复由原文件生成的冗余数据块(即D。，D。仆，D。一。)时，将编码矩阵P中对应行Jp与k个数据块进行数量积运算，所得积做异或运算，即得到损坏的冗余数据块。D女+=Pf。R=P，oR00Jp，1。R10oPi女一lJR一l(0i，Ik一1) (9)33性能指标云存储系统的备份恢复策略的性能可以用编码冗余度、数据可用性和存储开销3个指标进行描述。331编码冗余度采用(玎，k，r)纠删码的冗余备份策略，编码冗余度为：旦k=l+旦二生k332存储开销(10)采用(疗，k，r)纠删码的冗余备份策略，每个文件F所

20、需要的存储空间为：333数据可用性采用(甩，k，n纠删码的冗余备份策略，文件F被分割成k个数据块，并编码为胛个数据块。假设云存储存储系统中共有个节点，当前不可用的节点数是M个。文献1516给出了系统可用性的计算方法：文件对象F的可用概率Jp，等于不可用文件块存放在不可用存储节点上的方法数乘以可用文件块存放在可用存储节点上的方法数再除以所有文件块放在所有存储节点的方法数所得的值，即：尸，烈-M从N川-MJ八N门) (12)4实验结果与分析41 实验数据实验中采用一个450 MB的视频文件，分块存储时每个节点存储数据大小为90 MB。假设组成云存储系统的若干个存储节点的失效率为20(由于实验条件有

21、限，不能模拟云存储系统中的大量存储节点，下文计算文件失效率时采用已存储数据节点失效率为20汁算，计算结果较上述给出的计算方法偏大)，进行基于RS纠删码和副本备份两种方式的备份和恢复性能的对比试验。42实验环境实验在Ubuntul304系统下，利用Code：Blocks编译环境进行冗余备份和恢复进行仿真实验。43实验结果431副本备份实验相同实验环境，副本备份数量分别取2、3、4、5、6，各进行200次实验，统汁文件失效率，结果如表I。表1 不同参数1；的剧奉备份图3。当n=9时，由分成5块的原文件生成9个数据块如豳函幽裹 曼冬1 3数掰块牛成lI：r；_随机删除4个数据块，用余下的数据块进行数

22、据恢复操作，假若所删除的数据块为Moviek1wmv、Moviek2wmv、Moviek5wmv、Moviem1wmv，泽码后的数据截图如图4所示。幽函豳豳函函囊冬I 4数据块恢艇I|豳函鳖焉裟耕一一一一姗枷枷瑚枷万方数据Computer Engineering and Applications计算机工程与应用文件Movie decodedwmv为恢复后的文件，MovieklrecoveLwrnv、Moviek2 recoveEwmv、Movie_k5 recovcLwmv、Movie ml recoveLwmv分别为采用纠删码恢复的丢失数据块文件。经检测，通过译码恢复的文件与原文件内容完全一

23、致。433对比实验通常情况下，副本备份采用备份数为3，基于纠删码的备份方案纠删码的冗余率nk不大于2，故采用复本备份数为3，胆=9，七=5的纠删码进行文件恢复的对比实验，各进行l 000次随机试验，实验结果如表3。表3常态下文件失效率对比为了更好地对比两种数据备份方式对数据可靠性的保障，采取控制变量法再次进行实验。当备份文件占用相同存储空间时(以副本备份数为3时所占用空间为基准，此时n=15，七=5)，比较两种方案的文件失效率，实验结果如表4。表4 占用相同存储空间时文件失效率对比44实验结论(1)从表1看出，副本备份方式随着副本份数的增长，所占用存储空间成倍数增长，文件失效率降低速度放缓。(

24、2)从表2看出，基于纠删码备份方式，随着n的增长，文件失效率迅速降低，刀增长到原始文件分块数目时，文件失效率趋于稳定，几乎可以保证文件完全恢复。但同时，采用纠删码编码和恢复时，由于纠删码均基于有限域计算，需要进行大量的点积、异或等运算，在进行大文件编码恢复时需要消耗较长时间，随着冗余块数的增加消耗时间呈线性增长。(3)图3、图4表明，采用纠删码可以在某些存储节点失效情况下恢复存储的文件，同时可以在不恢复原文件重新分块的情况下恢复受损的数据块。(4)从表3、表4看出，实际应用过程中副本备份方式文件失效率是基于纠删码的备份恢复方式文件失效率的4119=2158倍。基于纠删码的备份策略在占用存储空间

25、小的情况下，文件失效率明显降低。而在使用相同存储空间时，副本备份方式在文件失效率停留在较高的4时，基于纠删码备份可以达到完全恢复的程度。5结束语本文针对云存储数据可靠性问题，提出采用基于纠删码的备份方法替代副本备份方法。经过同副本备份方式对比的大量实验证实，该方法可以在占用较小存储空间的前提下显著提高文件可靠性。同时在恢复原文件过程中，可对丢失文件块进行恢复，经检测同丢失数据块完全一致，避免数据块损坏需要恢复文件后重新分块再存储的计算开销。在进行大量实验过程中，笔者发现当存储的数据较大时，基于纠删码的备份方式在编码解码过程中，会额外消耗一些时间，如何提高编码解码效率将是以后研究的重点。参考文献

26、：1Schmuck F B，Haskin R LGPFS：A shareddisk file sys-tern for large computing clustersCProceedings of theConference on File and Storage Technologies，January28-30。2002：23l-244【2】Cloud storage for cloud computjngEBOL】(2009)http：ogforgResourcesdocumentsCloudStorageForCloudCom-putingpdf【3】Raluca A ESecure

27、，searchable and efficient cloud storageEBOL(20 10)http：wwwusenixorgeven“sec09techslidespopapdf4】Cloud storage standards overview and research ideas brain-stormEBOL(2009)http：wwwpdlcmueduSDI2009MarkCarlson_CloudCMUpdf5】Hayes BCloud computingJCommunications of the ACM，2008。51(7)：9-116Knorr E，Gntman GW

28、hat cloud computing really meansEBOL201310-19】http：wwwinfoworldcomdcloudcom-putingwhat-cloudcomputingreally-means-03 17】Ghemawat S，Gobioff H，Leung S TThe google file sys-ternJOpemting Systems Review，200337(5)：29438黄晓云基于HDFS的云存储服务系统研究D】大连：大连海事大学，2010【9】慕建君，路成业，王新梅关于纠删码的研究与进展【J】电子与信息学报，2002，24(9)：1276

29、12811 0】Rizzo LEffective erasure codes for reliable computercommunication protocolsJACM SIGCOMM ComputerCommunication Review，1997，27(2)：2436(下转134页)万方数据134 2016，52(4) ComputerEngineering andApplieations计算机工程与应用f3=之=6324 6f00。2 5(40一1)：299SD314n由于三组r的值均落在拒绝域内，故拒绝原假设，故认为NFDRA算法的RMSE值和其他算法的RMSE值相比具有显著性

30、差异。4结束语本文提出的融合时间偏差信息的邻域型因子分解推荐算法，将时间偏差信息与因子分解算法等内容融合在一起有效提高了算法的推荐精度。并且其可以随时间信息的变化满足用户的推荐需求，这是传统的推荐算法所不具备的。首先，通过实验对比之前的一些推荐算法，NFDRA算法取得了较好的结果。其次，考察了性能相对接近的两种算法在精确度以及召回率和F值等指标的情况。其中该算法在准确率以及召回率方面优于传统的timeSVD+算法。最后，通过单独考察三种时间偏差因素对算法推荐的影响，确定每一种时间偏差的重要程度。下一步将继续深化该算法模型，尝试将其他的一些信息和模型融入该算法当中，比如受限波尔兹曼机等深度学习模

31、型。通过这样的方式预期取得更好的推荐结果。参考文献：1】Hamed A A，Roose R，Branicki M，et a1Time-aware twitter-based drag recommender systemC20 1 2 IEEEACM International Conference on Advances in Social Networks Analysisand Mining，20122】Linden G，Smith B，York JAmazoncorn Recommendations：Itemto-Item Collaborative FilteringJIEEE In

32、ternet Computing，2003，7：76-803】Koren YFactorization meets the neighborhood：a multifaceted collaborative filtering modelCProe of the 14thACM SIGKDD Conference，20084】4陈天奇融合特征的矩阵分解模型【D上海：上海交通大学，20135】方耀宁，郭云飞，丁雪涛，等一种融合局部结构的改进奇异值分解推荐算法【J电子信息学报，2012，48(11)：16216】Koren YCollaborative Filtering with tempora

33、l dynamicsCProc l 5th ACM SIGKDD International Conference onKnowledge Discovery and Data Mining，2009：447456。7Ren Yibo，Gong SongjieA collaborative filtering recommendation algorithm based on SVD SmoothingCProceeding of the 2009 Third International Symposium onIntelligent Information Technology Applic

34、ationWashing-ton D C，USA：IEEE Computer Socienty，2009，2：530532【8】Liang Xiang，rang QingTimedependent models in collaborative filtering based recommender systemiC2009IEEEWICACM Intermational Conference OR Web Intel1igence and Intelligent Agent Technologies，20099】BlancoFemfindez Y，L6pez-Nores MPersonali

35、zing ecorn-merce by semantics-enhanced strategies and time-awarerecommendationsC2008 Third International Workshopon Semantic Media Adaptation and Personalization，2008【1 0Salakhutdinov R，Mnih AProbabilistic matrix factorizationCNIPS07。2008：12571264。11】顾申华结合奇异值分解和时间权重的协同过滤算法J计算机应用与软件，2010，27(6)12】叶红云，

36、倪志伟，倪丽萍一种检测兴趣漂移的图结构推荐系统J】小型微型计算机系统，2012(4)13】孙光福，吴乐，刘淇，等基于时序行为的协同过滤推荐算法J】软件学报，2014，25(11)：27212733【14Oh J，Sung YTime-dependent User Profiling for TVRecommendationC20 1 2 Second International Confer-ence on Cloud and Green Computing，20 1 215】He Liang，Wu FaqingUsing a timecontextbased collab-orative f

37、iltering algorithmCIEEE International Confer-ence on Granular Computing，2009【16】丛晓琪，杨怀珍，刘枚莲基于时间加权的协同过滤算法研究【J】计算机应用与软件，2009，26(8)(上接60页)1 1】Lustre File SystemHigh-performance storage architectureand scalable cluster file system【N】White paper，2007【1 2Schmuck F，Haskin RGPFS：a shareddisk file system for

38、large computing clustersCProceedings of the FirstUSENIX Conference on File and Storage Technologies，2002：23124413Tinyf001Google文件系统(Google File System)【CLOL(20080924)http：wwwcodechinaorgcommondocgooglegfspaper14】Kim S，Fonseca R，Culler DReliable transfer on wireless15116】sensor networksCZnati T，Lee S

39、 J，Mohapatra P，edProc of the 1st IEEE Intl Conf on Sensor and Ad HOCCommunications and Networks(SECON)Santa Clara：IEEE Press。2004：449459Rizzo LEfiective erasure codes for reliable computercommunication protocolsJACM SIGCOMM ComputerCommunication Review，1997，27(2)：2436，Weatherspoon H，Kubiatowicz JErasure coding VSrepli-cation：a quantitative comparisonCSpringer-Verlag London，UK：Proc of the 1 St International Workshop Peer-toPeer Systems(IPTPS)，2002万方数据