图因子分解的故障节点快速修复

为了提高分布式存储系统中故障节点的修复效率, 提出一种新的部分重复(fractional repetition, FR)码的构造算法. 该算法利用完全图的因子分解进行构造, 称为CGFBFR (complete graph factorization based FR)码. 该算法首先对完全图进行因子分解, 分解完成以后确定完全图的因子分解个数, 根据需要存储数据块的重复度来选择完全图的因子个数, 将完全图选中的因子所有顶点当做分布式存储系统中需要存储的数据块, 然后对选中因子图的边进行标记, 标记的边当做分布式数据节点进行存储. 最后根据选中的因子的顶点和边生成编码矩阵, 在分布式存储系统中按照编码矩阵中的数据对数据块分别进行存储. 实验仿真结果显示, 本文提出的一种新的部分重复码构造算法, 与分布式存储系统中的里所(reed-solomon, RS)码、简单再生码(simple regenerating codes, SRC)以及最新的循环可变部分重复(variable fractional repetition, VFR)码相比, 在系统修复故障节点时, 能够快速地修复故障节点, 有效降低了故障节点的修复带宽开销、修复局部性、修复复杂度, 而且构造过程简单, 同时可以灵活选择构造参数, 广泛适用于分布式存储系统中.     

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

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

分布式存储中精确修复最小带宽再生码的性能研究

分布式存储系统为保证数据可靠性,需要对数据进行冗余存储来应对由于节点失效所带来的数据不可靠性.基于矩阵积构造的精确修复最小带宽再生码除了能够显著降低系统的存储冗余,而且编码的构造参数之间没有约束限制,还能够显著降低修复带宽的开销,具有广阔的应用前景.然而,基于此编码方案所设计的分布式存储系统的性能开销并没有得到充分的研究和分析.针对该编码在分布式存储系统中数据上传、修复、下载3个阶段,分别比较CPU使用率、文件大小、缓冲区大小以及有限域大小对上述3个阶段中运算速度的影响,发现通过对相关参数进行合理配置,可以使得基于相应编码方案的分布式存储系统能够获得良好的运行性能.     

基于节点共边的异构部分重复码构造

为了满足分布式存储系统的动态存储和异构存储, 本文提出一种基于节点共边的异构部分重复码(heterogeneous fractional repetition codes based on node common edge, HFRC-NCE)的构造算法. 具体地, 将MDS码编码后的数据块分为冷数据块和热数据块, 结...     

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

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

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

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

一类精确修复多个错误的Suh-Ramchandram码*

再生码因能有效的减少修复带宽更适用于分布式存储系统。利用干扰对齐技术,对于任意的参数 满足 且 ,Suh和Ramchandram构造了一类修复一个失效节点时,可达到最优修复带宽的最小存储再生码。 Chen和Shum证明了对于参数满足 的Suh-Ramchandram再生码,可以合作修复多个失效节点。基于Suh-Ramchandram再生码,给出了参数为 的编码结构,并说明这种参数为 的最小存储再生码为一类可修复多个失效节点的Suh-Ramchandram 再生码,而且这类码在修复单个或多个节点的失效时均可达到最优的修复带宽。     

应用于分布式存储系统的准循环再生码构造方案

传统纠错码编码方案能够提高系统容错能力,但在数据修复时会占用大量带宽。为此,基于循环结构,构造一种面向分布式存储系统的准循环最小存储再生码。根据该准循环再生码的冗余系数向量权重和修复带宽边界,设计一种改进的节点修复算法,证明其修复带宽在最好情况能达到最小割下界,在最坏情况下也优于最大距离可分码的修复带宽。实验结果表明,该再码构造方案不仅节省存储空间,而且具有构造简单、运算代价低和修复带宽小等特点。     

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

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

基于简单再生码的分段编码方案

简单再生码将可容多错的RS纠删码与简单的异或运算相结合,在达到容忍任意n－k个节点故障可靠性的基础上,可以实现对单个失效节点的高效快速修复。对简单再生码的失效节点修复过程进行改进,提出一种新的基于简单再生码的分段编码方案,将f个具有相同下标的编码块分成两段,将每段中的编码块进行异或操作,生成一个新的校验块。对该方案的存储开销、磁盘读取的开销以及修复带宽开销进行性能分析和仿真实验,结果表明提出的基于简单再生码的分段编码方案在增加少量存储开销的同时,其修复带宽和磁盘读取的开销性能有了很大程度的优化,进一步验证了改进方案的正确性和有效性。     

异构部分重复码的构造

针对分布式存储系统部分重复(FractionalRepetition,FR)码大都是同构的问题,提出了基于Hadamard矩阵和基于[7,3,4]简单图形构造异构的FR码的两种新型构造设计算法,构造方法更加简洁.其中基于Hadamard矩阵构造存储容量异构的FR码可实现由同构经过简单变换为异构的编码方式;基于[7,3,...     

一种基于网络编码的云存储系统

存储空间、修复带宽和更新带宽是云存储系统的3个重要指标,系统设计往往需要在这些性能度量之间取折衷。为了降低存储空间、修复带宽、更新带宽以及系统复杂度,文中提出了一种基于网络编码的云存储系统。该系统结构为m*n数据阵列的形式,n列表示n个存储节点,其中k个节点用于存储原始数据,称为系统部分;另外(n－k)个节点用于存储校验字符,称为非系统部分。数据阵列的m行对应m个系统形式的(n,k)最大距离可分(MDS)码,每个源数据符号只参与它所在行的编码,不参与其他行的编码,这种系统结构大幅降低了编译码的复杂度。该系统可以承受最多(n－k)个节点的失效,此外,当单节点失效时,由于使用了系统形式的MDS码,可以使用干扰对齐技术进一步缩减修复带宽。与现有的某些云存储系统相比,该系统明显降低了存储空间、修复带宽和更新带宽等资源消耗,性能得到大幅提升。     

拜占庭容错纠删码分布式存储协议

研究了从数据密集大部分拜占庭容错分布式存储协议使用复制技术,但是当存储的数据块很大时,复制技术要求大量的存储空间并占用网络带宽,效率低下。采用纠删码技术则将数据块编码为长度相同的分片,然后把各个分片分别存储在对应的存储节点上,这样可以节省存储空间和网络带宽。拜占庭容错纠删码分布式存储需要额外的开销、附加的服务器甚至要版本化存储,才能保证数据的一致性。通过对通常的情况进行优化,采用新颖的机制并引入同态指纹检验码,使得需要最少的服务器、最小的额外计算量和最小的通信回合数目,达到了低开销,并且可以保证时间戳不跳跃。     

基于Harary图生成树的部分重复码构造

针对部分重复码的有效修复问题,本文基于Harary图生成树构造出了一种新型的部分重复(Fractional Repetition based on Spanning trees of Harary graph,FRSH)码.实验结果表明,相较于现有的里所(Read-Solomon,RS)码和简单再生码(Simple Regeneration Codes,SRC),FRSH码在修复带宽开销、修复局部性等方面得到了更低的开销,且改善了修复效率,并将故障节点的修复时间缩短.     

异构去中心化存储中的LRC-RS混合编码

为解决去中心化存储中应用相同参数的低码率RS(Reed-Solomon codes)码导致的修复带宽较高和稳定节点资源浪费的问题,提出LRC-RS混合编码的编码策略.通过将节点按可信度分类,让高可信节点使用LRC编码,低可信节点使用低码率的RS编码,降低修复带宽和减少稳定节点存储开销.理论联系实验结果表明,在同等的冗余...     

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

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

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

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

X再生码:一类适用于云存储的准确修复编码

通过将(n,k)-RS编码和X编码结合,为云存储系统设计一类新的准确修复编码——X再生码。它具有容忍n-k个节点故障的可靠性,并且当系统中单个或者两个节点出现故障时,仅需从少量的节点下载数据块,使用简单的异或运算即可修复。对X再生码的存储代价、修复带宽、修复局部性(修复过程中需要连接的节点数)和编码率进行分析,并与RS编码、SRC以及LRC进行对比。结果显示,X再生码在一个或者两个节点故障时,修复局部性以及修复带宽上都具有显著的优势,并能达到任意高的编码率。     

基于矩阵变换和可调节环的部分重复码构造

目前在构造部分重复码(Fractional Repetition Codes, FRC)的研究方法中发现, 大多数是基于同构的分布式存储系统, 但实际的存储系统往往需要满足异构的特性. 为此, 本文提出了两种构造异构FRC的方法, 一种是基于矩阵变换构造的异构FRC, 该方法用于构造重复度为2, 节点存储容量异构的FRC, 相比用正则图构造的同构FRC, 具有算法计算复杂度低, 更符合现实存储系统的优点; 另外, 本文还提出了运用可调节环构造FRC的方法, 用于构造重复度为2或3的FRC, 即可得到节点存储容量同构的FRC也可得到异构的FRC. 与现有的FRC对比分析, 发现本文构造的FRC在节点存储容量上具有异构的特点, 修复局部性好, 同时构造算法运算复杂度低, 可以大范围的选择参数, 构造结构简单直观.