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

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

RDP码存储系统节点故障恢复的读盘优化

实际的分布式存储系统面临着频繁的磁盘故障。为了保障数据可靠性,纠删码被广泛地部署在大规模存储系统中。在基于纠删码的存储系统中,快速有效地修复故障磁盘上的数据对于维护数据可靠性有重要意义。研究最重要的容两错纠删码——RDP(Row-diagonal parity)编码的磁盘故障修复问题,优化修复过程中磁盘访问的连续性。提出的单磁盘故障修复方案在保证读取数据量最小的前提下,最大程度避免了磁盘数据的随机读取,保持数据读取的连续性。通过在实际的分布式存储系统中实验,验证了该修复方案的实际性能,证实该算法可以很好地改善混合修复方案的随机读取引起的修复速度下降问题,最终提高了修复效率。     

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

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

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

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

主动容错副本存储系统的可靠性分析模型

主动容错机制通过预先发现即将故障的硬盘来提醒系统提前迁移备份危险数据,从而显著提高存储系统的可靠性。针对现有研究无法准确评价主动容错副本存储系统可靠性的问题,提出几种副本存储系统的状态转换模型,然后利用蒙特卡洛仿真算法实现了该模型,从而模拟主动容错副本存储系统的运行,最后统计系统在某个运行时期内发生数据丢失事件的期望次数。采用韦布分布函数模拟设备故障和故障修复事件的时间分布,并定量评价了主动容错机制、节点故障、节点故障修复、硬盘故障以及硬盘故障修复事件对存储系统可靠性的影响。实验结果表明,当预测模型的准确率达到50%时,系统的可靠性可以提高1~3倍;与二副本系统相比,三副本系统对系统参数更敏感。所提模型可以帮助系统管理者比较权衡不同的容错方式以及系统参数下的系统可靠性水平,从而搭建高可靠和高可用的存储系统。     

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

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

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

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

主动容错云存储系统的可靠性评价模型

除了传统的冗余机制,主动容错技术也被用来提高存储系统的可靠性。然而,当前对主动容错云存储系统可靠性的研究工作很少,而且都局限于硬盘故障服从指数分布的假设前提。针对主动容错磁盘冗余阵列RAID-5和RAID-6云存储系统提出两个可靠性状态转移模型,并基于转移模型设计了蒙特卡洛仿真算法,评价系统在一定运行周期内发生数据丢失事件的期望个数。该算法采用韦布分布函数模拟随时间变化（降低、恒定不变、或升高）的硬盘故障率,准确评价了主动容错机制、硬盘整体故障、故障修复、潜在块故障以及磁盘清洗过程对系统可靠性的影响。所提方法可以帮助系统设计者评估不同容错机制和系统参数对云存储系统可靠性的影响,有助于创建高可靠存储系统。     

分布式存储系统最小带宽再生码研究

分布式存储系统常常使用纠删码冗余技术提高系统可靠性.为保证一定的冗余度,系统必须具有自修复能力再生失效数据.再生码是纠删码的一种改进形式,最大特点在于无需下载整个数据文件就能恢复单个节点数据,从而有效减少数据修复时的网络带宽.相关文献证明再生码数据修复时存在极值点—最小带宽再生点(MBR),由此提出最小带宽再生码MBRC.文中从数据分布、失效数据修复和数据重构三个方面描述了实现的原理,并通过构建数据矩阵和修复矩阵实现MBRC再生码.利用实例详细给出了再生码的实现过程,并理论证明正确性,最后仿真实验验证了MBRC的有效性.     

Robust Redundancy Scheme for the Repair Process: Hierarchical Codes in the Bandwidth-Limited Systems

High performance computing can be well supported by the Grid or cloud computing systems. However, these systems have to overcome the failure risks, where data is stored in the “unreliable” storage nodes that can leave the system at any moment and the nodes’ network bandwidth is limited. In this case, the basic way to assure data reliability is to add redundancy using either replication or erasure codes. As compared to replication, erasure codes are more space efficient. Erasure codes break data into blocks, encode these blocks and distribute them into different storage nodes. When storage nodes permanently or temporarily abandon the system, new redundant blocks must be created to guarantee the data reliability, which is referred to as repair. Later when the churn nodes rejoin the system, the blocks stored in these nodes can reintegrate the data group to enhance the data reliability. For “classical” erasure codes, generating a new block requires to transmit a number of k blocks over the network, which brings lots of repair traffic, high computation complexity and high failure probability for the repair process. Then a near-optimal erasure code named Hierarchical Codes, has been proposed that can significantly reduce the repair traffic by reducing the number of nodes participating in the repair process, which is referred to as the repair degree d. To overcome the complexity of reintegration and provide an adaptive reliability for Hierarchical Codes, we refine two concepts called location and relocation, and then propose an integrated maintenance scheme for the repair process. Our experiments show that Hierarchical Code is the most robust redundancy scheme for the repair process as compared to other famous coding schemes.     

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

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

Hierarchical codes: A flexible trade-off for erasure codes in peer-to-peer storage systems

Redundancy is the basic technique to provide reliability in storage systems consisting of multiple components. A redundancy scheme defines how the redundant data are produced and maintained. The simplest redundancy scheme is replication, which however suffers from storage inefficiency. Another approach is erasure coding, which provides the same level of reliability as replication using a significantly smaller amount of storage. When redundant data are lost, they need to be replaced. While replacing replicated data consists in a simple copy, it becomes a complex operation with erasure codes: new data are produced performing a coding over some other available data. The amount of data to be read and coded is d times larger than the amount of data produced, where d, called repair degree, is larger than 1 and depends on the structure of the code. This implies that coding has a larger computational and I/O cost, which, for distributed storage systems, translates into increased network traffic. Participants of Peer-to-Peer systems often have ample storage and CPU power, but their network bandwidth may be limited. For these reasons existing coding techniques are not suitable for P2P storage. This work explores the design space between replication and the existing erasure codes. We propose and evaluate a new class of erasure codes, called Hierarchical Codes, which allows to reduce the network traffic due to maintenance without losing the benefits given by traditional erasure codes.     

基于之字形解码算法优化的高效低存储ZD码

ZD码(ZigZag-decodable codes)是基于之字形解码算法设计生成的一类纠删码, 它仅需要少量的计算即可修复存储系统中的故障数据, 但需要存储相对其他纠删码更多的冗余数据以保证系统的高可靠性. 为了降低ZD码产生的存储开销, 本文通过分析当前在存储系统中使用的之字形解码的思想, 提出了一种优化的之字形解码算法. 新的解码算法能够更充分利用校验数据中的信息来完成数据修复. 基于新的解码算法, 本文相应的提出了一种新的ZD码编码方案, 由于新算法更高的信息利用率, 新的编码方案能够用更少的存储开销来满足存储系统的高可靠性. 实验结果表明, 本文提出的ZD码编码方案具有最优的存储开销, 且编解码性能远高于目前广泛使用的RS码.     

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

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

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

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

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

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