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

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

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

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

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

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

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

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

分布式存储方案的设计与研究

针对基于纠删码的分布式存储方法中信息分割算法IDA在运算中涉及构造拆分矩阵,计算开销大,且单纯基于纠删码的方案无法确保所存储数据的完整性、机密性等特性,只能够容忍系统中存在的良性故障,无法容忍入侵者的恶意入侵。提出了分布式系统中一种基于Tornado码的浏览器-服务器工作模式的数据存储方案。在数据写入过程中通过构造编码后数据分块的Hash值级联（即数字指纹）,并与每个数据分块一起分布在存储服务器集中的不同服务器中,当需要读出时对分块及数据指纹进行验证,然后利用Tornado译码方法恢复原始文件,即可实现Byzantine环境数据的完整性保护,并提高了系统的容错能力。     

分布式存储方案的设计与研究

针对基于纠删码的分布式存储方法中信息分割算法IDA在运算中涉及构造拆分矩阵,计算开销大,且单纯基于纠删码的方案无法确保所存储数据的完整性、机密性等特性,只能够容忍系统中存在的良性故障,无法容忍入侵者的恶意入侵.提出了分布式系统中一种基于Tomado码的浏览器-服务器工作模式的数据存储方案.在数据写入过程中通过构造编码后数据分块的Hash值级联(即数字指纹),并与每个数据分块一起分布在存储服务器集中的不同服务器中,当需要读出时对分块及数据指纹进行验证,然后利用Tomado译码方法恢复原始文件,即可实现Byzantine环境数据的完整性保护,并提高了系统的容错能力.     

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

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

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

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

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

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

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

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

减少重建数据量的冗余编码技术研究

为防止硬件故障或机器宕机导致的数据丢失,冗余编码技术被广泛应用于分布式存储系统中来保证数据的可靠性。然而,传统的冗余编码技术,如里德-所罗门码,存在着重建数据量大的问题。副本技术在重建丢失数据时只需要读取和传输丢失的数据,而冗余编码需要读取和传输更大的数据量,从而消耗更多的磁盘I/O带宽和网络带宽。因此,基于冗余编码的分布式存储系统在重建数据时将消耗更长的时间,从而将整个系统长时间暴露在一种降级的模式下,进而增加了发生永久性数据丢失的风险。为解决这个问题,减少重建数据量的冗余编码技术不断被提出,然而只有这些冗余编码与传统的里德-所罗门码的比较,缺少它们在存储系统的综合比较。系统地从减少重建数据量等几个重要方面研究了这些减少重建数据量的冗余编码技术,从而为实际系统中采用合适的编码提供重要参考和依据。     

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

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

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

纠删码技术是分布式存储系统中典型的数据容错方法,与多副本技术相比,能够以较低的存储开销提供较高的数据可靠性;然而,纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题,提出一种编码简单的低修复成本的纠删码——旋转分组修复码（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%的修复时间。     

RS类纠删码的译码方法

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

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

纠删码技术是分布式存储系统中典型的数据容错方法，与多副本技术相比，能够以较低的存储开销提供较高的数据可靠性；然而，纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题，提出一种编码简单的低修复成本的纠删码——旋转分组修复码（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%的修复时间。     

基于简单再生码的带宽感知的分布式存储节点修复优化

分布式存储系统为保证可靠性会采用一定存储冗余策略如多副本策略、纠删码策略.纠删码相对于副本具有存储开销小的优点,但节点修复网络开销大.针对修复网络开销优化,业界提出再生码与以简单再生码为代表的局部可修复码,显著降低了修复网络开销.然而,现有基于编码的分布式容错存储方案大都假设节点处于星型逻辑网络结构中,忽略了实际的物理网络拓扑结构和带宽信息.为实现拓扑感知的容错存储优化,相关研究在纠删码和再生码修复过程结合网络链路带宽能力,建立树型修复路径,进一步提高了修复效率.但由于编码和修复过程的差异性,上述工作并不适合于简单再生码修复.针对该问题,本文结合实际物理网络拓扑结构,将链路带宽能力引入到简单再生码的修复过程中,对带宽感知的简单再生码修复优化技术开展研究.论文建立了带宽感知节点修复时延模型,提出了基于最优瓶颈路径和最优修复树的并行修复树构建算法.并通过实验对所提算法性能进行了评估.实验结果表明,与星型修复方式相比,论文所提算法有效地降低了节点修复时延,提高了修复效率.     

多副本动态更新数据无重复挖掘仿真

网络动态更新时,需要存储和传输大量数据,有时还会对网络更新数据重复复制,产生副本,浪费大量存储空间、减缓传输速度,产生网络拥堵、数据泄露等现象。针对这些问题提出一种多副本动态更新数据无重复挖掘。先依据网络数据特性构建多副本动态更新数据模型,再采用密文方法对更新数据做加密处理,并存储到网络服务器中,最后利用密文防御特性将该数据重复部分挖掘,并做解密处理,保证了网络服务器中的动态更新数据都是无重复的。实验结果表明,多副本动态更新数据无重复挖掘,可以有效避免数据泄露、传输速度慢、拥挤等问题,实现了多副本动态更新数据的无重复。     

Fault-tolerant enhanced bijective soft set with applications

As an extension of the soft set, the bijective soft set can be used to mine data from soft set environments, and has been studied and applied in some fields. However, only a small proportion of fault data will cause bijective soft sets losing major recognition ability for mining data. Therefore, this study aims to improve the bijective soft set-based data mining method on tolerate-fault-data ability. First some notions and operations of the bijective soft set at a β-misclassification degree is defined. Moreover, algorithms for finding an optimal β, reductions, cores, decision rules and misclassified data are proposed. This paper uses a real problem in gaining shoreline resources evaluation rules to validate the model. The results show that the proposed model has the fault-tolerant ability, and it improves the tolerate-ability of bijective soft set-based data mining method. Moreover, the proposed method can help decision makers to discover fault data for further analysis.