基于多级网络编码的多副本云数据存储

云数据存储的快速发展对数据的可用性提出了较高要求.目前,主要采用纠删码计算数据编码块进行分布式冗余数据存储来保证数据的可用性.虽然这种数据编码技术保证了存储数据的安全性并减少了额外的存储空间,但在损坏数据恢复时会产生较大的计算和通信开销提出一种基于多级网络编码的多副本生成和损坏数据恢复算法算法基于多级网络编码对纠删码的...     

云文件系统中纠删码技术的研究与实现

云文件系统凭借高性能、高扩展、高可用、易管理等特点,成为云存储和大数据的基础和核心。云文件系统一般采用完全副本技术来提升容错能力,提高数据资源的使用效率和系统性能。但完全副本的存储开销随着副本数目的增加呈线性增长,存储副本时造成额外的写带宽和数据管理开销。纠删码在没有增加过量的存储空间的基础上,通过合理的冗余编码来保证数据的高可靠性和可用性。研究了纠删码技术在云文件系统中的应用,从纠删码类型、编码对象、编码时机、数据更改、数据访问方式和数据访问性能等六个方面,对云文件系统中纠删码的设计进行了探究,以增强云文件系统的存储模型。在此基础上,设计并实现了纠删码原型系统,并通过实验证明了纠删码能有效地保障云文件系统的数据可用性,并且节省存储空间。     

一种基于重复数据删除技术的云中云存储系统

随着云存储技术的快速发展和应用,越来越多的企业和用户都开始将数据从本地转移到云存储服务提供商进行存储.但是,在享受云存储高质量服务的同时,将数据仅仅存储于单个云存储服务商中会带来一定的风险,例如云存储服务提供商的垄断、数据可用性和安全性等问题.为了解决这个问题,提出了一种基于重复数据删除技术的云中云存储系统架构,首先消除云存储系统中的冗余数据量,然后基于重复数据删除集中的数据块引用率将数据块以复制和纠删码2种数据布局方式存储在多个云存储服务提供商中.基于复制的数据布局方式易于实现部署,但是存储开销大;基于纠删码的数据布局方式存储开销小,但是需要编码和解码,计算开销大.为了充分挖掘复制和纠删码数据布局的优点并结合重复数据删除技术中数据引用的特点,新方法用复制方式存储高引用数据块,用纠删码方式存储其他数据块,从而使系统整体性能和成本达到较优.通过原型系统的实现和测试验证了相比现有云中云存储策略,新方法在性能和成本上都有大幅度提高.     

基于纠删码的动态副本冗余存储研究

为保证数据的完整性和可靠性,云存储中主要采用多副本和纠删码两种存储策略对数据进行冗余保存.针对单一冗余存储策略的不足,考虑存储开销和访问质量等方面因素,根据用户访问数据的规律,提出一种基于纠删码的动态副本冗余存储方案.采用RC纠删码来存储云中海量数据,使用曲线拟合预测访问热度,适时调整副本的数量.实验结果表明,该方案空间利用率高,能有效减小用户访问的平均延迟,提高用户访问的成功率.     

一种混合局部恢复码及Hitchhiker码的存储策略

我们正处于一个大数据的时代.如今一个分布式存储系统需要存放PB数量级数据的情况越来越常见.这些系统一般由普通商用组件构成,其出错率相对较高.由此,分布式存储系统需要保证数据的可靠性和可用性.多副本和纠删码是现在最为常用的技术.相比多副本技术,采用纠删码能在同等容错能力下大幅降低存储开销.然而,在进行数据恢复时,使用传统的纠删码(如Reed-Solomon码)会导致系统中产生大量的网络带宽消耗及磁盘读写操作,进而导致退化读延迟过高.注意到在系统中数据的访问频率呈Zipf分布,大多数数据访问只涉及到少量数据,而绝大多数数据的被访频率很低.根据这种数据访问的偏斜性,本文提出如下存储策略以解决采用纠删码的系统退化读延迟过高的问题:对被访频率高的热数据采用低恢复延迟的纠删码(如局部恢复码Local Reconstruction Code,LRC)进行编码,而对被访频率低的冷数据采用保证最小存储开销的纠删码(如Hitchhiker码)进行编码.由于热数据占据了绝大多数的数据访问,因此绝大多数的退化读也将应用在这些热数据上,这样这一策略就能在整个系统的角度获取低恢复开销的优势.同时,冷数据占据了系统绝大多数的数据量,且冷数据由保证最小存储开销的编码进行存储,因此这一策略的存储开销会很低.然而,对于混合存储策略而言,热数据可能会变冷,而冷数据也可能会变热,因此它需要配置一种编码切换过程.一个不恰当的编码切换过程会引起巨大的数据传输量,这是难以让人接受的.为了避免这一缺陷,本文提出了一种LRC和Hitchhiker码之间的高效切换算法.这一算法可以避免上述策略在部署时因冷热数据的转换出现系统瓶颈.在精心选取了两种编码并提出它们之间的高效切换算法后,本文提出的混合存储策略避免了现阶段其余混合存储策略的主要缺点.通过实验验证,此存储策略相较传统的Reed-Solomon码在退化读延迟方面降低了55.8%.在编码切换方面,切换延迟能分别降低为重新编码算法用时的13.4%及33.1%,且当数据从LRC切换为Hitchhiker码时(更为频繁出现的情况)的数据传输量能降至10%.     

一种基于纠删码的数据放置容错算法

在基于纠删码技术的云存储系统中,如何选择合适的存储节点来放置经编码生成的多个冗余数据块、有效保证数据的容错性是云存储系统面临的一大挑战.提出的CHGDPS (consistent hash and greedy data placement algorithm based on sets)算法在基于划分集合的思想上,将一致性hash方法与贪婪算法相结合,极大地减少了数据传输时间.实验结果表明,该算法具有更短的总体平均访问时间和更长的平均无故障时间,提高了数据的容错性.     

网格环境下基于编码机制的数据复制研究

本文提出了基于编码机制的网格数据复制思想,通过对副本数据进行线性分组编码,并将其分散保存到网格存储节点,可形成具有纠删能力的编码子副本组.针对目前热点研究的线性分组编码,探讨基于Cauchy Reed-Solo-mon Code、Tornado Code和Random Linear Code的编码数据复制方案,通过建模手段讨论三者的副本数据访问性能和副本数据可靠性,并与传统的完整数据复制和分块数据复制进行时比分析,证明所提出的编码数据复制有着较优的综合性能.具体实验数据进一步说明,编码副本的编码开销占整个数据复制开销的较小比例,表明编码数据复制是具有可行性的技术方案.     

基于数据挖掘的存储数据纠删码容错方法仿真

在存储数据的纠删码容错中,针对传统存储数据纠删码容错方法容错速度较低的问题,提出一种基于数据挖掘的存储数据纠删码容错方法。采用数据挖掘方法对存储数据纠删码进行重构,计算存储数据纠删码的丢失片段;利用CHR算法对存储数据纠删码进行异构修复,通过建立存储数据纠删码容错模型实现存储数据的纠删码容错。为了验证存储数据纠删码容错方法的有效性,将存储数据纠删码容错方法与传统存储数据纠删码容错方法进行对比,实验结果得出:上述方法与基于流水线的存储数据纠删码容错方法、基于RapidRaid码的存储数据纠删码容错方法、基于非规则LDPC码的存储数据纠删码容错方法的容错速度分别为:286Mbps/s、262Mbps/s、243Mbps/s、232Mbps/s,比较可知,所提方法的容错速度最快,证明了上述方法的优越性。     

一种基于多层次校验的低恢复成本纠删码

随着纠删码在分布式存储系统中的实际应用,纠删码为存储系统提供了更加优秀的存储效率,但当节点丢失时,相较于传统副本技术更多的网络传输带宽开销成为了造成系统性能瓶颈的关键因素。为了解决MDS编码高带宽开销对系统性能的影响,一类新型编码方案——分组码被应用在分布式存储系统中,相较于传统MDS编码能够有效地降低节点修复时的数据传输量,从而减少网络带宽需求。在Pyramid分组码的基础上进行层次扩展,提出一种HLRC（hierarchical local repair codes）纠删码。HLRC相较于LRC引入了层次编码模型,将原始数据块构建为编码矩阵,根据层次进行分别编码,生成包含数据块范围不同的局部校验块;每个层次包含的数据块数量不同,可以保证修复节点时的低修复成本,同时还拥有较高的存储效率。HLRC相较于Pyramid拥有额外的校验块冗余,能够降低校验块出错和多节点出错时的恢复开销。在基于Ceph的分布式存储系统中的实验结果表明,HLRC与Pyramid等分组码相比,单节点修复开销最高可降低48.56%,多节点修复开销最高可降低25%。     

分布式存储系统中的低修复成本纠删码

纠删码技术是分布式存储系统中典型的数据容错方法,与多副本技术相比,能够以较低的存储开销提供较高的数据可靠性;然而,纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题,提出一种编码简单的低修复成本的纠删码——旋转分组修复码（RGRC）。RGRC首先将多个条带组合成条带集,然后利用条带之间的关联关系对条带集内的数据块进行分层旋转编码,以此得到相应的冗余块。RGRC大幅度地减少了单节点修复过程中所需要读取和传输的数据量,从而能节省大量的网络带宽资源。同时RGRC在解决单节点修复成本高的问题时,依然保留着较高的容错能力,且为满足分布式存储系统的不同需求,可以灵活地权衡系统的存储开销和修复成本。在分布式存储系统中进行的对比实验分析结果展示,与其他常用的RS（Reed-Solomon）码、LRC（Locally Repairable Codes）、basic-Pyramid、DLRC（Dynamic Local Reconstruction Codes）、pLRC（proactive Locally Repairable Codes）、GRC（Group Repairable Codes）、UFP-LRC（Unequal Failure Protection based Local Reconstruction Codes）相比,RGRC只需要增加少量的存储开销,就能降低单节点修复14%~61%的修复成本,同时减少14%~58%的修复时间。     

分布式存储系统中的低修复成本纠删码

纠删码技术是分布式存储系统中典型的数据容错方法，与多副本技术相比，能够以较低的存储开销提供较高的数据可靠性；然而，纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题，提出一种编码简单的低修复成本的纠删码——旋转分组修复码（RGRC）。RGRC首先将多个条带组合成条带集，然后利用条带之间的关联关系对条带集内的数据块进行分层旋转编码，以此得到相应的冗余块。RGRC大幅度地减少了单节点修复过程中所需要读取和传输的数据量，从而能节省大量的网络带宽资源。同时RGRC在解决单节点修复成本高的问题时，依然保留着较高的容错能力，且为满足分布式存储系统的不同需求，可以灵活地权衡系统的存储开销和修复成本。在分布式存储系统中进行的对比实验分析结果展示，与其他常用的RS（Reed-Solomon）码、LRC（Locally Repairable Codes）、basic-Pyramid、DLRC（Dynamic Local Reconstruction Codes）、pLRC（proactive Locally Repairable Codes）、GRC（Group Repairable Codes）、UFP-LRC（Unequal Failure Protection based Local Reconstruction Codes）相比，RGRC只需要增加少量的存储开销，就能降低单节点修复14%~61%的修复成本，同时减少14%~58%的修复时间。     

一种云存储系统数据持久存储机制

针对云存储中的可靠性产生的担忧,提出一种云存储系统完善的数据存储保障机制,以保证系统的高可靠性和数据的高可用性。在处理与数据持久存储的相关的数据分片、数据分发、完整性检查以及冗余数据的维护中,引入基于纠删码的数据冗余机制,与传统的复制冗余方案相比,能够在获得相同的数据可用性时降低存储空间和网络带宽的开销多达50%以上。采用基于缓冲区的分段读入编码对纠删码算法进行优化后,提高了对文件分片与合并的平均编码速率。     

医学影像云存储模型的研究与设计

为解决早期云计算模型对医学小文件存储出现的单节点问题,数据高冗余造成数据的不一致性以及检索效率低等方面的问题,提出一种新型云存储模式。模型中,引入BWFS算法实现优化海量医学小文件序列化合并,优化纠删码算法实现数据块编码,减少数据块的冗余存储,而且引入位图索引技术与HBase索引结合形成新型并行索引策略,优化HBase主索引的缺点。实验表明,新型存储模型通过使用BWFS算法和纠删码技术减少了集群主控节点的内存消耗,在保证数据快速恢复的情况下,减少了集群数据的冗余存储,并行索引技术提高了医学数据影像的检索效率。     

基于Tornado码的存储冗余算法研究

纠删码是提供数据高可用性的重要方法。与传统纠删码相比较,Tornado码是基于稀疏矩阵的级连纠删码,通过异或操作完成编解码,实现纠错功能。经实验分析,在存储系统中采用Tornado码进行数据冗余,可以有效的加快编解码速度和减少存储空间的消耗,并提供较高的纠错能力。     

异构环境下纠删码的数据修复方法综述*

在大规模云存储系统中,由于磁盘或网络故障造成的存储节点失效事件频发,系统需要数据冗余技术以保证数据的可靠性和可用性。纠删码,相对于副本方式而言,能大大提高存储空间的利用率,但纠删码在冗余数据修复方面的代价较副本方式高很多。目前针对纠删码的冗余数据修复研究大都无差别对待每个存储节点,然而实际分布式存储系统中,节点通常存在带宽资源、计算资源、存储容量资源等方面的差异性,这些资源的异构性对冗余数据修复性能影响很大。本文指出影响修复性能的关键因素,选取带宽开销、磁盘访问开销、修复时间、参与修复的节点数量和修复代价作为修复性能的评价标准;分析了现有研究方法如何降低这五种开销,重点讨论了这些方法的优缺点;阐述当前异构分布式存储系统中纠删码修复技术的研究现状;最后指出纠删码数据修复技术中尚未解决的一些难题和未来纠删码修复技术可能的发展方向。     

一种面向纠删码技术的云存储可靠性机制

在云存储中,数据可以分为三种类型:读频繁、写频繁以及冷数据。对不同类型的数据设置不同的编码机制:对读频繁数据采用多副本技术,频繁写的数据采用单文件编码方案,冷数据采用跨文件编码方案。在云存储系统中提出了一种新的纠删码技术的可靠性机制—魔方码,该编码易于实现,具备高的容错性并且相比多副本机制可以减少资源的消耗。以HDFS上的一个RAID包为基础,实现魔方码的原型,并添加BlaumRoth、RDP以对比测试。虽然各种编码各有优缺点,通过单机和集群测试RAID-5、BlaumRoth、RDP和魔方码的编译码速度,魔方码译码速度比现有最优RAID-6编码RDP码提高了一个数量级。同时,针对大规模分布式系统提出了一种三维纠删码,可以容任意7个错误。总之,测试结果显示魔方码相比三份副本技术,在减少一半资源消耗的同时可以保证高的可用性和可靠性。     

分布式存储系统中的预测式纠删码研究

纠删码消耗的存储空间较少,获得的数据可靠性较高,因此被分布式存储系统广泛采用。但纠删码在修复数据时较高的修复成本限制了其应用。为了降低纠删码的修复成本,研究人员在分组码和再生码上进行了大量的研究。由于分组码和再生码属于被动容错方式,对于一些容易出现失效的节点,采用主动容错的方式能更好地降低修复成本,维护系统的可靠性,因此,提出了一种主动容错的预测式纠删(Proactive basic-Pyramid,PPyramid)码。PPyramid码利用硬盘故障预测方法来调整basic-Pyramid码中冗余块和数据块之间的关联,将预测出的即将出现故障的硬盘划分到同一小组,使得在修复数据时,所有的读取操作在小组内进行,从而减少读取数据块的个数,节省修复成本。在基于Ceph搭建的分布式存储系统中,在修复多个硬盘故障时,将PPyramid码与其他常用的纠删码进行对比。实验结果表明,相比basic-Pyramid码,PPyramid码能降低6.3%~34.9%的修复成本和减少7.6%~63.6%的修复时间,相比LRC码、pLRC码、SHEC码、DLRC码,能降低8.6%~52%的修复成本和减少10.8%~52.4%的修复时间。同时,PPyramid码构造灵活,具有很强的实际应用价值。     

基于纠删码的云计算存储备份及恢复策略

如何保障云存储系统中数据的可靠性是云计算领域的热点问题。副本备份技术是保障数据可靠性的重要手段,但是存在占用存储空间大、存储效率低等问题。纠删码能够提供优化的数据冗余度,以防止数据丢失,恰当地使用纠删码可以提高空间的利用效率并获得较好的数据保护效果,在通讯方面已经得到广泛应用。将纠删码引入云存储系统中,代替副本备份策略,以提高云存储系统的性能。实验表明该方案可以有效提高数据可靠性和空间利用率。     

RS类纠删码的译码方法

RS(Reed-Solomon)码可以根据应用环境构造出任意容错能力的码字,有很好的灵活性,且使用RS纠删码作为容错方法的存储系统能达到理论最优的存储效率.但是,与异或(exclusive-OR,XOR)类纠删码相比,RS类纠删码译码计算的时间开销过大,这又很大程度上阻碍了它在分布式存储系统中的使用.针对这一问题,提出了一类RS纠删码的译码方法,该方法完全抛弃了当前大多RS类纠删码译码方法中普遍使用的矩阵求逆运算,仅使用计算复杂度更小的加法和乘法,通过构造译码变换矩阵并在此矩阵上执行相应的简单的矩阵变换,能够直接得出失效码元由有效码元组成的线性组合关系,从而降低译码计算复杂度.最后,通过理论证明了该方法的正确性,并且针对每种不同大小的文件,进行3种不同大小文件块的划分,将划分得到的数据块进行实验,实验结果表明:在不同的文件分块大小情况下,该新译码方法较其他方法的译码时间开销更低.     

图书馆云存储系统中一种自适应容错策略

云存储的优势吸引着越来越多的图书馆采用云存储解决馆藏数字资源的存储需求。但随着海量数据的增长,云存储节点的失效概率越来越大。单一的容错策略,如单一的复制或纠删码,不可避免地存在一些缺点,不能满足当今容错技术的需要。因此,根据馆藏文献访问的频率和大小,提出了一种自适应切换的容错策略,该策略可以在整个生命周期中动态地选择复制方案或纠删码方案。实验结果表明,该方案较单一复制策略节约了43%的存储空间,较单一纠删码策略提升了52%的节点故障恢复时间。