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

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

分布式存储中新型分组piggybacking框架

随着互联网技术的快速发展,全球数据量爆炸式增长对分布式存储系统的可靠性和可用性提出了严峻的挑战。Piggybacking框架作为一种高效的数据容错技术成为近年来研究的热点。目前,绝大多数piggybacking框架均以牺牲子条带数和修复度的方式来降低修复带宽,导致修复失效节点过程中所节省的数据量通常无法有效地提升磁盘读取效率。针对上述情况,提出一种新型分组piggybacking框架,在保证较低修复带宽的同时,进一步降低了子条带数和信息节点修复度,从而提升分布式存储系统的输入/输出性能。该框架将校验节点分为两个部分,信息符号和校验符号分别按照一定规则分组后依次嵌入到对应的校验节点中,设计简单。通过这种设计,可以同时有效修复信息节点和校验节点,既减少了子条带数,又使其在校验节点个数较多时拥有较强的综合修复能力。与其他piggybacking框架相比,新型分组piggybacking框架能更好地权衡修复带宽、修复度与子条带数,适合在实际系统中应用。

基于再生码的云存储系统——Ustor

当前常使用多个云共同存储数据，以保证用户数据可靠性。为减少存储成本和修复带宽，提出了一种使用功能性修复再生码（FRC）将数据编码为多个数据块，并分布于不同的云中的方法。该方法减少了多个云中单个云发生数据丢失时需要从网络上传输的数据量，并减少了修复成本，已成功地应用于所构建的云存储系统Ustor中。实验表明：与不编码比较，冗余编码给系统增加了5%~10%的响应时间开销，但可保障节点失效；FRC码编、解码和修复速度与里德-所罗门（Reed-Solomon或RS）码基本相当，256 MB大小文件编码时间差距在0.5 s以内；FRC码修复时与传统的RS码相比减少了25%以上需要下载的数据量。

二元再生码在分布式存储系统的应用

分布式存储系统以其高效的可扩展性和高可用性成为存储大数据的主要系统.为了提高可靠性,需要在分布式存储系统中引入冗余.因此如何最优化存储空间、最小化修复带宽和最小化计算复杂度是衡量冗余存储系统效率的关键问题.再生码存储是一类可以达到存储空间与网络修复带宽最佳折中的存储方法,但现有的再生码的构造方法有大量有限域的乘法运算,其高昂的计算复杂度成为用于分布式存储系统中的主要瓶颈.实验结果表明,在保留再生码优势的前提下,采用移位和异或运算取代有限域的乘法运算可以大幅度地降低计算复杂度.创新之处在于提出了二元再生码(binary regenerating codes,BRGC),并给出了构造二元再生码的两类最佳再生码,即最小带宽二元再生码和最小存储二元再生码的方法.通过评估和对比主流的RS码和基于矩阵乘法的再生码,发现BRGC在计算复杂度方面有着明显的优势,在实际海量数据的分布式存储系统中具备更好的应用价值.BRGC在修复和解码性能均优于柯西(Cauchy Reed-Solomon)码.

Locally Minimum Storage Regenerating Codes in Distributed Cloud Storage Systems

In distributed cloud storage systems, inevitably there exist multiple node failures at the same time. The existing methods of regenerating codes, including minimum storage regenerating(MSR) codes and minimum bandwidth regenerating(MBR) codes, are mainly to repair one single or several failed nodes, unable to meet the repair need of distributed cloud storage systems. In this paper, we present locally minimum storage regenerating(LMSR) codes to recover multiple failed nodes at the same time. Specifically, the nodes in distributed cloud storage systems are divided into multiple local groups, and in each local group(4, 2) or(5, 3) MSR codes are constructed. Moreover, the grouping method of storage nodes and the repairing process of failed nodes in local groups are studied. Theoretical analysis shows that LMSR codes can achieve the same storage overhead as MSR codes. Furthermore, we verify by means of simulation that, compared with MSR codes, LMSR codes can reduce the repair bandwidth and disk I/O overhead effectively.

基于非均匀循环编码的分组修复码构造

考虑到实际分布式存储系统中节点故障情况的多样性,该文提出一种基于非均匀循环编码的分组修复码(GRCNCC),使高故障率节点得到更有效的保护。具体地,根据节点故障率对存储节点进行非均匀分组,将数据块依次存入长度递增的节点分组,再使用跨条带循环编码的思路生成组编码块和全局校验块。性能分析以及实验仿真表明,GRC-NCC虽然具有高于RS码的存储开销,但与RS码和重叠分组修复码相比,该方法在故障节点修复过程中具有较低的修复带宽开销和修复局部性,且在多节点故障修复过程中性能更优,容错性更好。

基于稀疏随机矩阵的再生码构造方法

针对已有的再生码编码方案的运算是基于有限域GF(q)、运算复杂度高、效率低的问题,提出了一种将GF(2)上的稀疏随机矩阵和乘积矩阵框架相结合的再生码构造方法。首先,将文件数据矩阵式排布后根据编码矩阵进行行异或运算;其次,节点失效后,参与帮助节点根据失效节点的编码向量编码本地数据并发送至修复节点;最后,修复节点根据接收到的数据译码出失效节点原有的数据。实验结果表明修复带宽至多只有传统纠删码修复方案的1/10,相比基于传统范德蒙编码矩阵的再生码,编码速率提升了70%,译码恢复速率提升了50%,方便了再生码在大规模存储系统中的应用。

分布式存储中的克隆piggybacking框架

随着5G技术的快速发展,分布式存储系统凭借低成本、高可用性、高吞吐量和海量存储能力等特点,越来越受到人们的青睐。由于节点众多,节点故障频发,因此采用一定的数据容错技术来保证数据的可靠性尤为重要。近年来,piggybacking框架以其优异的修复性质受到了广泛关注。从piggybacking框架的修复度入手,为了同时降低修复带宽和修复度,提出了克隆piggybacking框架。与其他piggybacking框架不同,该框架只对一组节点进行嵌入设计和修复分析,其他组内对应节点通过克隆的方式简化设计过程。根据“一个节点的信息符号尽可能地只嵌入一个子条带”的设计思想,权衡修复带宽和修复度。与现有的piggybacking框架相比,克隆piggybacking框架设计简单,进一步降低了信息节点的修复带宽。

一种基于分布式存储系统的Piggyback码

随着大数据时代的来临,纠删码在分布式存储系统中有着越来越重要的应用.Piggyback码作为纠删码的一种,因其同时具有高效率存储和低修复带宽的优点而成为近年来的研究热点,RSR-Ⅱ码作为Piggyback码中在减少修复带宽方面最典型的码,因其修复过程中需要进行有限域上方程组的求解,使得编码复杂度和修复复杂度过高.针对这个问题,提出了一种新的Piggyback码,并给出了其一般性构造和修复算法,该码基于分布式存储系统中广泛使用的系统型M DS码,通过结合Piggybacking框架的核心思想,构造了新的piggybacks添加规则,有效避免了有限域上的方程组求解问题.对比分析表明,新的Piggyback码既保持了RSR-Ⅱ码较低的平均修复带宽率,还具有更低的编码复杂度和修复复杂度.

数据中心中路由编码的可行性研究

修复带宽最优并不代表修复通信量也是最优的,后者与物理网络拓扑有着密切联系.本文基于路由编码的思想减少修复通信量.首先,基于信息流图对物理网络中数据的传递过程进行建模,证明得出了满足路由编码可行的充要条件,并发现路由编码可以基于再生码实现.然后,针对数据中心网络设计的特点,为Fat-tree设计了一个工作在应用层的协议来生成修复树,为CamCube设计了一个启发式算法来生成修复树.关于最小存储再生码的数据修复过程的仿真实验表明,路由编码可以有效地降低修复通信量,2种修复树生成方案在各自适合的网络中均有较好性能:在帮助节点数较小时,Fat-tree和CamCube中的修复通信量分别降低了大约50%和30%.

基于(k+2,k)MSR的多容错低修复带宽编码

传统(k+2,k)最小存储再生码(MSR)在双节点失效的情况下,会有较高的修复带宽。为此,提出一种多容错编码方案。通过引入4个备份校验节点,使编码的上下部分均形成最小存储再生码结构。仿真结果表明,与现有的(k+2,k)MSR方案相比,该方案能降低双节点失效时的修复带宽。

一种分布式存储系统环境下的数据持有性验证方法

为了在分布式环境下进行数据持有性验证并保持较低的修复带宽,该文在引入再生码的基础上,提出了一种分布式环境下的数据持有性验证方案。该方案利用再生码来进行数据持有性验证,并在修复阶段再次进行持有性验证以抵抗污染攻击。通过理论分析,该方案既保持了再生码修复带宽低的优势,且相比于经典方案降低了计算开销,节省了存储空间。该文还提供了方案的安全性证明,通过安全性及性能分析表明该方案是可行的。

基于分布式存储的OHitchhiker码

为推进纠删码在分布式存储系统中的应用,研究提高系统修复效率的算法。Hitchhiker码作为一种最新的具有最优存储空间和较低修复成本的纠删码,已在Hadoop等分布式系统中部署实现。针对目前Hitchhiker码采用均分的数据分配模式,存在网络带宽浪费的问题,提出一种最优分配的Hitchhiker编码(optimal allocation of Hitchhiker,OHitchhiker)。通过在编码的分配环节引入一种动态选择分配算法,使得OHitchhiker码可以针对不同(n,k)值选择具有最小修复代价的编码结构。理论分析以及实验结果验证了OHitchhiker码在保持较低存储空间的同时,进一步降低了下载带宽。

去中心化存储下分布式低带宽多节点修复方法

为扩展纠删码在区块链中的应用,研究了去中心化存储系统中的修复机制,发现系统中RS码存在多节点修复成本高、效率低的问题.针对这个问题,本文提出一种更契合去中心化网络环境下的多节点修复传输模型DSMR,充分利用RS码在修复多节点时的数据冗余性和计算冗余性.通过节点稳定性和网络跳数来选择节点、构造数据传输并行结构、分组修复计算和节点数据交互四个步骤,以最大化数据传输效率、较低带宽开销和较短修复时间完成了去中心下分布式低带宽多节点修复工作.理论及实验结果表明,在任意(n,k)参数下,分布式多节点修复传输机制在保持较低存储空间地同时进一步降低修复带宽、减少修复时间.

与副本结合的部分再生码

(n,k,d)再生码允许存储节点传送所存数据的线性组合以及增加修复入度d,显著地降低了修复带宽,但是引入了更多的参与节点数及磁盘I/O。针对这一不足,提出了一种将复制方式与再生码结合的(n,k,d,λ,θ)部分再生码,并得到了与再生码类似的阈值函数和2个特殊点——最小存储量点和最小修复带宽点。部分再生码可以综合利用修复入度d和副本因子θ同时降低修复带宽和磁盘I/O。当所有的节点存储量相等时,部分再生码的单点修复带宽和磁盘I/O均优于再生码。定量比较的结果也显示,在最小存储量点,部分再生码比再生码有更低的平均修复带宽和平均磁盘I/O;在最小修复带宽点,部分再生码有更低的平均磁盘I/O以及与再生码相近的平均修复带宽。更重要的是,部分再生码适用于d≤n-2的所有情形。

通过复制方式降低修复带宽的新再生码

再生码通过允许节点传送所存数据的线性组合并增加修复入度,显著地降低了修复带宽,但是增加了参与节点数和磁盘I/O。针对这一缺点,首先通过分析再生码的阈值函数得到一个定理,指出了降低阈值函数的一个充要条件;然后根据该定理构造出了结合复制方式的新再生码。新再生码不增加修复入度也能降低阈值函数,与再生码类似,也有两个特殊点——最小存储量点和最小修复带宽点。通过对两个特殊点的定性与定量分析,发现新再生码可以利用复制来降低单节点修复带宽,并且平均修复带宽和平均磁盘I/O也会减少。

一种参数可变的最小存储再生码

参数为(n,k,B,d,t)的功能性修复最小存储再生码采用(n,k)删除码策略,依靠d个帮助节点修复t个节点的失效。出于存储空间、修复带宽、可修复节点数等因素的考虑,需要将一个参数为(n1,k1,B,d1,t1)的功能性修复再生码转换为另一个参数为(n2,k2,B,d2,t2)的功能性修复再生码,并且希望这个转换过程能够以最小下载数据量的代价进行。针对此问题,采用逻辑节点和物理节点相结合的方法,构造了一种可变参数的功能性修复再生码,证明了该码可以在不同参数组之间相互转换,而且在转换过程中使用最小下载数据量。

一种均衡分配的修复校验节点的Piggybacks捎带设计

针对最初的减少校验节点修复带宽的Piggybacks捎带设计存在的问题,提出了一种均衡分配的Piggybacks捎带设计(Balanced-Allocation Piggybacks Adding,BAPA).首先,通过分析给出了新的Piggybacks捎带规则,在此基础上得出了能进一步减少校验节点修复带宽的Piggybacking设计BARSR-Ⅰ和BARSR-Ⅱ.然后,给出了BARSR-Ⅰ和BARSR-Ⅱ中校验节点的修复过程以及平均修复带宽率的推导值.最后,给出了BARSR-Ⅰ和BARSR-Ⅱ下的编码复杂度和修复复杂度.通过与现有的Piggybacking设计对比分析表明,BARSR-Ⅰ和BARSR-Ⅱ能有效的减少校验节点的修复带宽.

一种基于纠删码的多节点失效修复算法

纠删码作为分布式系统中重要的数据容错技术,在失效数据的修复领域有着广泛应用。但现有的纠删码算法大多针对单节点修复,修复成本较高,且未考虑新生节点间的信息传递,给多失效节点的修复带来不便。基于此,提出一种基于纠删码的多节点失效修复算法,该算法在新生节点中利用节点选择策略选取中心节点为根节点,并依据链路带宽分别与供应节点和剩余新生节点构建最大修复树,从而降低数据修复时长。实验结果表明,与现有的BHS和SSR串行修复等方法相比,该算法能有效提高多失效节点的修复效率,验证了算法的有效性。

具有健康节点协作的高效多节点修复方案

针对分布式存储中多节点再生修复的修复带宽和可靠性问题,提出了一种具有健康节点协作的多节点修复方案.该方案在修复模型上做出了相应改进,通过健康节点间的协作把上述问题做了折中.给出了具体的多节点修复过程和相应再生码的构造,用信息流图求得最大流最小割集来说明其最小边界.结果表明,在确保修复带宽最低的条件下使修复时间同步,修复过程更简便,最重要的是所需传输信道更少,保证了修复的可靠性.