分布式存储中的再生码综述

分布式存储系统中通过引入冗余提高系统的可靠性,纠删码作为重要的冗余策略在分布式存储中得到越来越多的重视.分布式存储系统中,当某个存储节点失效后,需要引入新的节点来修复失效节点的数据.传统纠删码冗余策略在修复失效节点时需要传输的数据量较大近年来出现的再生码对传统纠删码进行改进以减少修复失效节点的带宽消耗.再生码引入网络编码的思想,在修复失效节点时,参与修复过程的节点首先将本节点内的数据作线性组合后再上传,最终修复带宽消耗最小 介绍了再生码的基本概念,然后介绍单节点修复再生码和合作修复再生码的编码策略,最后总结再生码的发展和研究方向     

云存储环境下分组校验纠删码冗余算法研究

在海量云存储系统中,提高存储利用率,降低冗余方案的计算复杂度是热点研究问题.分组校验纠删码冗余算法能够减少在数据重构时所需的纠删码片段,从而减少对存储网络带宽以及系统I/O的需求,降低存储系统的负载.介绍了分组校验纠删码的编码规则,参数设置,通过实验分析算法具有良好的容错能力与空间利用率,能够满足云存储系统需要的编解码性能.     

基于柯西矩阵的最小带宽再生码研究

节点的失效在大规模分布式存储系统中是常见现象.为防止数据的丢失,系统必须解决失效节点的自修复问题.利用再生码可以在无需下载整个源文件的情况下即可恢复出失效节点的数据,从而能有效节省修复带宽.本文利用柯西矩阵作为编码矩阵,构造了一种精确修复最小带宽再生码(ER-MBR),可以精确修复失效节点,并通过实例演示了在有限域上进行编码解码及节点修复的过程.理论分析和仿真实验都表明利用柯西矩阵作为编码矩阵,其算法的运算效率优于利用范德蒙矩阵或者随机矩阵.     

一类基于极图理论的局部修复编码的性质及构造

由于分布式存储系统大量使用廉价的磁盘构建,磁盘故障往往不可避免导致数据丢失.数据编码是一种防止数据丢失的必要容错机制.局部修复码与经典的最大距离可分(MDS)码相比,以一定的存储空间开销,能够有效提高数据修复的效率,降低网络带宽占用.为了降低该码的存储空间开销,本文研究以极图理论来描述该类编码.将存储节点与编码块抽象为二分图中的X、Y两类顶点,从而存储空间占用最小化等价于计算二分图中边数的极小值.这种求极值问题可以归结为Zarankiewicz问题.本文使用极值二分图对局部修复码进行建模与分析,并给出了相应的构造算法.     

多节点修复的代数几何码

最小存储再生码的每个节点具有最小的数据存储,因而是最大距离可分码,这样其节点数的上界为2^b,其中b是存储在每个节点中的数据的比特数.从理论和实践的角度来看,我们很自然地会去考虑这样的再生码:其具有接近最小的数据存储并且节点数不受此界的限制.针对这一问题,Jin等用代数几何码构造再生码,推广了Wotters和Guruswami的Reed-Solomon修复算法.本文在此基础上进行了扩展,给出了多节点修复的代数几何再生码.这推广和改进了最近一些关于再生码的结果,例如多失效节点的Reed-Solomon码和scalar MDS码.     

纠删码存储系统中数据修复性能优化研究进展与展望

纠删码被广泛应用于分布式存储系统以保存在线应用的用户数据。当部分存储节点发生故障时,纠删码存储系统需使用新的存储节点替换原有失效节点,并恢复失效的用户数据。由于需要执行数据编码、传输和读写等操作,纠删码存储系统通常需要消耗较长的时间执行数据修复操作,存储的用户数据将长期处于不可靠状态。为了保障存储数据的可靠性,研究学者提出了多种数据修复性能优化方案以减少数据修复时间。本文介绍了数据修复性能优化问题,分析了各个应用场景下主要的性能瓶颈和性能优化难点,总结了提升数据修复性能的主要技术方案和研究工作,并对数据修复性能优化研究领域的未来发展方向进行展望,为纠删码存储系统设计人员准确选择适合特定应用场景的数据修复性能优化方案提供思路。     

2类最优局部修复码的构造

局部修复码可以提高分布式存储系统中失效节点的修复效率,是分布式存储编码领域的研究热点。文章研究最优局部修复码的构造,利用二元常重量码构造了两类矩阵,并以这两类矩阵作为校验矩阵,构造了局部性为r、最小距离分别为d=5和d=6的两类最优局部修复码。     

基于分布式存储系统的Reed-Solomon算法优化

随着存储规模的增大和信息节点的增多,基于分布式存储系统的磁盘发生故障的概率越来越高。为了增强系统的可靠性,我们通过RS算法引入冗余数据。随后该研究针对传统RS码的生成矩阵做出了一些改进,使得生成矩阵1的数目减少,优化了编码解码的速度。     

基于多维立方体网络的内存存储系统设计与研究

针对OLDI应用的联动特性和低延迟、高带宽、高吞吐量等需求,介绍了一种新型的内存存储系统Mem-ory X,其核心机制是掌握存储在内存存储节点中的数据.将数据备份到网络磁盘中的大量存储节点,然后以相对较低的存储成本实现高I/O性能和故障恢复,支持大数据处理的能效优化.     

一种副本复制和纠错码融合的云存储文件系统容错机制

在云存储技术中,云存储文件系统的数据容错十分重要,直接关系到整个系统的可用性。该文通过对有中心的分布式文件系统进行分析,提出了双机热备的元数据管理节点容错技术和块副本与基于纠删编解码算法相结合的存储节点容错技术,为云存储文件系统设计了双重保险的容错机制。实验结果表明,该机制大大提高了云存储系统的可靠性,并提高了磁盘空间利用率。     

云存储系统的能耗优化节点管理方法

为节省云存储系统的能耗,文中考虑在云存储系统利用率较低时关闭部分存储节点.为了保证部分存储节点关闭时数据的可用性,针对如何选择云存储系统中可以关闭的节点集合问题,设计了基于辅助节点的贪心算法,并针对异构云存储系统的能耗优化问题,提出了面向异构云存储系统的能耗优化贪心算法.模拟实验结果表明,文中提出的面向异构系统的能耗优化贪心算法能较好地降低异构云存储系统的能耗,其性能明显优于一般的贪心算法,从而验证了所提算法的有效性.     

采用弧映射的双层对象分布算法

针对由混合存储设备组成的对象存储系统中数据对象分布时间开销过大的问题,提出了支持权值和副本机制的弧映射双层对象分布(TMHR)算法。该算法利用存储系统批量扩容、删除的特点,将存储系统内存储节点划分为多个子集群,采用可扩展的子集群哈希(SHFC)算法将数据对象按概率分布到子集群上以保证分布的公平性;在子集群内采用随机置换算法将数据对象等概率分布到节点上以降低数据对象分布时间开销。实验结果表明:与一致性哈希算法和随机切片算法相比,TMHR算法的数据对象分布时间分别缩短了20%和28%;数据对象的分布也更加接近理论情况;在存储节点数变化后,存储系统能够迁移较少的数据对象以进行重新均衡。该算法满足公平性、高效性、简洁性和自适应性,可以降低存储系统I/O路径的时延,提高存储系统性能,较适用于异构混合对象存储系统。     

基于优化Raptor码的水下传感器网络可靠传输机制

针对水声通信带宽低、时延长、误码率高、多普勒效应显著等特征,分析了传统可靠传输机制在水下传感器网络应用的局限性,提出了基于数字喷泉码-优化Raptor码的水下传感器网络可靠传输机制.采用反馈控制对Raptor码内码的鲁棒孤子分布和多项式描述的Shokrollahi度分布进行优化设计,降低了编码包平均度.进一步对Raptor码的内码—弱化的LT码(Luby transform codes)的编解码进行优化,实现了快速的编解码.基于优化Raptor 码的可靠传输机制采用反馈控制,动态评估信道删除概率,从而提高编解码和通信效率.通过Aqua-Sim仿真工具对提出的可靠传输机制与基于编码的多跳协同可靠数据传输(coding based multi-hop coordinated reliable data transfer,CCRDT)机制进行仿真对比.结果表明,所提出的可靠传输机制明显降低了传输开销,提高了数据吞吐量.     

基于链路带宽的分布式存储系统框架及动态负载均衡技术

针对在节点间进行数据传输、备份等操作时,不同节点间链路带宽将限制分布式存储系统的性能的问题,借鉴软件定义网络及云存储技术的基本思想,通过对控制流与数据流的分离,提出了一种基于链路带宽的分布式存储系统框架及动态负载均衡技术.所提出框架中,在分布式数据节点之外引入一个中心控制节点,该节点掌握全局网络视图,全局网络视图中既包括数据存储表记录存储数据的分布,又包括当前链路带宽情况.在用户读取数据时,根据数据存储表确定需要的数据存放于哪些数据存储节点,指派相应的数据存储节点根据路由表发送数据包,并实时监测网络中的链路带宽负载情况,及时调整数据的传输路径.仿真验证所提架构和算法可以有效解决海量数据在不同位置的分配调度,以及缩短用户对大量数据提取的响应时间及提升存储速率等问题.      

单向环网络上数据存储问题的研究

研究了单向环网络上的数据存储问题,得到了每个用户重构全部原始数据的带宽下界,并由此定义了最优重构分布存储方案. 接着讨论了最优重构分布存储系统中损坏节点的修复问题,得到了修复一个损坏节点所需带宽的紧的下界. 进一步指出在最优重构分布存储系统中,每个损坏节点都能够用最优带宽进行修复. 特别地,给出了一个新颖的基于欧几里得除法的最优构造方法.     

大数据存储中的容错关键技术综述

不断增长的海量数据需要被可靠存储,而分布式存储系统庞大的节点规模和数据规模,大大提升了发生节点失效的概率,容错技术成为大数据存储中不可忽视的关键技术.文中介绍了数据容错的两种基本策略：复制和纠删码,并分别总结了将这两种容错策略具体应用于大数据存储时所面对的问题和相关解决技术,如与基于复制的容错技术相关的副本系数设置、副本放置策略、副本一致性策略、副本修复策略和纠删码领域的再生码技术等.     

局部修复码综述

分布式存储系统因其海量存储能力、高扩展性和低成本等特性受到广泛开发和使用.如何有效保障数据可靠性也成为当前分布式存储系统重点关注的问题之一.局部修复码是目前广泛使用的保障数据可靠性的手段.介绍国际上目前比较热门的三类局部修复码,即经典的局部修复码、再生码和极大局部修复码,并重点介绍这三类码的最优性质.     

基于粒子群优化算法的云数据均衡放置策略

在拥有多个存储节点的云数据存储系统中,保持云存储系统的负载均衡水平为一个合理的值和最小化数据检索的时间是一个值得研究的问题。本文提出一种基于粒子群优化算法的云数据均衡放置策略(balanced placement strategy of cloud data based on particle swarm optimization algorithm, BPCD),首先,给出一种云存储系统模型;其次,引入基尼系数作为衡量该系统负载均衡水平的指标,结合数据检索时间目标函数构建多目标约束优化模型;再次,采用粒子群优化算法对问题进行求解,主要包括数据节点编码与参数设置、种群初始化、粒子群空间搜索、算法迭代4个过程;最后,将本文算法与传统云数据放置算法进行对比分析。仿真实验表明,本文提出的云数据均衡放置策略在优化云存储系统的负载水平和数据检索时间方面具有良好的效果。     

一种基于节点映射关系的云数据安全代理访问机制

随着移动终端多媒体技术的发展,用户逐渐将本地数据通过各种网络备份到云存储服务器上.云平台在提供廉价便捷的数据存储服务的同时也存在数据安全防护问题,尤其是密文数据访问控制完全依赖于云服务商.为了防止数据被非授权用户和半可信云存储提供商的非法访问,提出一种基于节点映射关系的CP-ABE属性加密算法,即通过属性管理降低权限管理的复杂度.在密文访问控制机制中引入密钥授权中心和安全代理实现存储服务与安全服务异地存储,保证在开放环境下云存储系统中数据的安全性.实验结果表明,这种属性管理机制在少量的系统开销下实现了数据存储与密钥存储的分离,具有较高的应用价值.     

BDCode:一种面向大数据存储系统的纠删码算法

针对含有大量数据的大数据存储系统,提出了一种基于编码技术的面向大数据备份的优化算法(BDCode).该算法通过对不同编解码服务器设置不同的虚拟节点存储组来保证系统的可用性,节点和数据块的并行解码计算提高了系统中数据损坏时的恢复效率.实验表明,所提出基于编码的大数据系统备份机制可以提高系统的存储利用率,并行解码方式的引入能加速减少数据损坏时的恢复时间,并能达到零号的系统负载均衡;此外不同的用户设置不同的编码参数,增加了大数据系统的鲁棒性.实验通过设置不同的数据块m和校验块k的比例来提升利用率,并行解码速度相比以前的串行提高近两倍.使用BDCode比CRS编码效率平均高36.1%,解码效率平均高19.3%;比RS码编码效率平均高58.2%,解码效率平均高33.1%.