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

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

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

随着海量存储系统的发展和在复杂环境中的应用,存储系统的可靠性受到了严重的挑战.纠删码作为存储系统容错的主要方法越来越受到重视.首先介绍了当前典型和常见的纠删码技术的发展现状,从评价纠删码性能的各项重要指标的角度详细地对比和分析了现有的纠删码技术,给出了不同纠删码在容错能力与磁盘要求、空间利用率、编码效率、更新效率、重构效率等方面的不足和可能的改进见解,并讨论了磁盘阵列系统、P2P存储系统、分布式存储系统、归档存储系统等不同存储系统对于纠删码各类性能的差别要求,并进一步指明了当前存储系统纠删码研究中尚未解决的一些难题和未来纠删码可能的发展方向.通过分析得出,目前不同纠删码在容错能力、计算效率、存储利用率等方面都存在不同程度的缺陷,如何平衡这些影响纠删码性能的因素,设计出更高容错能力、更高计算效率及更高存储利用率的纠删码,仍是未来很长一段时间内值得不断深入研究的问题.     

分布式存储系统中的纠删码容错方法研究

HRC码是一种具有存储效率高、计算复杂度低等优点的纠删码,但其存在编解码计算开销大、实现较为复杂等不足。通过对HRC码的译码算法进行优化,提出一种新型的纠删码HRCSD。采用内外层分层结构,内部的冗余由HRC码的编码结构组成,外层采用偏移复制策略,将原始信息进行旋转存储,能够实现并行读写。实验结果表明,与三副本技术和S~2-RAID纠删码相比,HRCSD纠删码具有容错性能高、修复开销低等优势,可满足大规模分布式存储系统的容错需求。     

基于RS纠删码的信息分散算法

利用基于RS纠删码的信息分散算法可构建高顽存的分布式存储系统。RS纠删码的编/译码速率是衡量其可用性的一个重要指标。对RS纠删码的纠删原理进行了理论分析,讨论了编/译码运算所在的伽罗瓦域,基于伽罗瓦域算术运算的特征设计了双表法以提高编/译码速率。最后对该信息分散算法的效率进行了理论分析和实验测试。测试结果表明,该信息分散算法可提供18Mbps的编/译码速率,基于该测试结果分析了基于RS纠删码的信息分散算法的适用环境,指出信息分散算法未来的研究方向。     

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

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

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

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

基于多斜率码链的阵列纠删码

针对当前大多阵列纠删码容错能力偏低以及构造时需要满足的约束条件较强的问题,提出一类基于码链构造的阵列纠删码。该阵列纠删码使用不同斜率码链组织数据元素和校验元素间的关系,从而能达到理论上不受限制的容错能力;而在构造时避开了类似素数约束的强约束条件,易于实用和扩展。仿真实验结果表明,相对于RS（Reed-Solomon）码,基于多斜率码链阵列纠删码在运算效率上的提升超过了2个数量级;在固定的容错能力下,存储效率能随着条块尺寸的增加而提高。此外,该类阵列码的修复代价和更新代价为一个固定常量,不会随着系统规模的扩大或容错能力的提高而增加。     

右边正则纠删码中二部图的构造算法

通过深入研究右边正则度序列的分析性质,设计了右边正则纠删码度序列的参数优化算法.基于此算法,提出了右边正则纠删码设计中随机二部图的连边构造算法.数值结果证明了所给的度序列参数优化算法的有效性.仿真结果表明基于右边正则度序列的级联型纠删码的性能优于Tornado码.随机二部图的连边构造算法和度序列的参数优化算法有助于右边正则纠删码的设计及其工程应用.     

基于矩阵运算的最小冗余存储再生码MSRRC研究

分布式存储系统常常使用纠删码冗余技术提高数据的安全性和可靠性,从而使系统具有自修复失效数据的能力,但传统纠删码在修复失效节点时需要传输的数据量较大。再生码是纠删码的一种改进形式,它的主要特点是无需下载整个数据文件就能恢复单个节点数据,从而有效减少了数据修复时的网络带宽。相关文献证明数据修复时存在最小存储再生点(MSR),由此提出最小冗余存储再生码MSRRC。本研究主要采用数据矩阵和修复矩阵实现MSRRC再生码,通过实例详细给出再生码的实现过程,并理论证明其正确性,最后仿真实验验证了MSRRC的有效性。     

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

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

RS类纠删码的译码方法

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

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

纠删码消耗的存储空间较少,获得的数据可靠性较高,因此被分布式存储系统广泛采用。但纠删码在修复数据时较高的修复成本限制了其应用。为了降低纠删码的修复成本,研究人员在分组码和再生码上进行了大量的研究。由于分组码和再生码属于被动容错方式,对于一些容易出现失效的节点,采用主动容错的方式能更好地降低修复成本,维护系统的可靠性,因此,提出了一种主动容错的预测式纠删(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码构造灵活,具有很强的实际应用价值。     

基于改进型右边正则度分布序列的低密度纠删码

通过对右边正则度分布序列的详细分析之后，给出了一种改进型右边正则度分布序列．证明了基于改进型右边正则度分布序列的级联型低密度纠删码能以任意接近删除信道容量的速率进行传输．同时指出所构造的级联型低密度纠删码的码率等于给定的码率，从而克服了基于原来的右边正则度分布序列的级联型低密度纠删码只能通过增大二部图右边结点的度数使得所构造纠删码的码率逼近给定的码率这一缺点．模拟结果验证了改进型右边正则度分布序列的正确性．     

一种基于短LT码的级联编译码算法

针对实时无线通信对短纠删码的需求,提出一种短码长LT码与传统纠错码的级联方案。在综合考虑算法复杂度与纠错性能的情况下,选取RS码和卷积码的级联(RS-CC码)以构造等效删除信道,并采用实时性高的短LT码实现纠删功能。文中设计了一种适合短LT码的译码算法,同时给出了编码度分布的选取方法。仿真结果表明,与已有短喷泉码相比,文中短LT码成功译码时所需编码冗余更少,应用到级联方案后的数据传输可靠性明显提高。     

纠删码存储系统中数据修复方法综述

纠删码技术具有存储开销低的优势,然而在进行数据修复时面临修复时间长和对前端应用性能影响高的缺陷。给出纠删码技术中数据修复完成时间的计算模型,指出影响修复性能的关键因素,进而选取计算开销、读写开销、传输开销作为修复性能的评价标准;分析了现有研究工作如何降低计算、读写和传输3种开销,重点讨论了其关键性技术的优缺点;最后从修复性能、可靠性、存储开销等方面对现有编码方案进行对比,并指出未来可能的研究方向。     

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

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

基于蚁群优化算法的纠删码存储系统数据更新方案

由于纠删码具备高可用性和高存储空间有效性的特点,采用纠删码为大规模分布式存储系统提供数据持久性已成为事实标准.然而,纠删码的密集型更新操作将导致大量的数据传输和I/O开销.如何减少数据传输量,优化现有网络资源的利用率,以提高纠删码的更新效率,成为纠删码存储系统面临的重要挑战.然而,在多重服务质量(quality of service,QoS)指标下,目前对纠删码更新效率的优化研究很少.针对此问题,提出一种基于蚁群优化算法的多数据节点更新方案(ant colony optimization algorithm based multiple data nodes update scheme,ACOUS),采用2阶段数据更新方式以优化多数据节点更新过程.具体而言,基于多目标蚁群优化更新路由算法(multi-objective ant colony optimization update routing algorithm,MACOU)所构建的多目标更新树,2阶段数据更新方式能有效地进行数据增量收集和校验增量分发.大量的实验结果表明,在典型的数据中心网络拓扑结构下,与TA-Update方案相比,所提方案能够在保证算法收敛的前提下,以可忽略的计算开销为代价,将更新时延降低26%~37%.     

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

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

纠删码分片验证技术研究

纠删码分片验证技术在拜占庭环境中非常重要。分析了现有的纠删码分片验证技术。基于同态指纹技术提出了一种新的验证方法。分析结果表明,新的方法具有更好的效率。     

纠删码在分布式容错存储中的应用

在分布式存储中,海量数据被存储到同一个数据中心的不同节点或不同数据中心的节点上,数据的位置和组织方式对用户是透明的,由于面临的数据规模和用户规模更加庞大,在容错安全性上面临着严峻的挑战。本文提出一种基于纠删码的分布式存储系统模型,利用纠删码高效的编码效率和容错能力,为数据安全性保障提供了一个可靠的解决方案。