局部修复码的最优构造

分布式存储系统采用冗余策略来确保数据的可靠性和可用性,局部修复码(locally repairable codes,LRC)引起了广泛的关注,极大地减少了数据修复过程中所连接的节点数,在数据存储中作用极大.每个信息码元可以从其他t个不相交的集合中修复,且每个集合大小为r,称此类码具有(r,t)局部度.从校验矩阵入手,提...     

存储系统中的局部修复阵列码模型

对于单容错和双容错的存储系统,在磁盘修复过程中发生的任何故障都可能引起数据丢失,导致修复失败,保证数据的修复效率对于存储系统的可靠性至关重要。RDP码在进行单盘故障修复时使用混合恢复算法能减少25%的读取总量,但是在进行双盘故障修复时需读取所有的元素。针对目前难以同时提升单双盘故障修复效率的问题,对RDP码进行拓展,提出了一种具有局部修复性质的阵列码模型——DRDP码。DRDP码在RDP码的基础上将部分数据列按水平线进行异或计算生成局部水平校验列,并将其参与到全局校验列的编码计算中,从而缩短了修复链,使其拥有局部修复的功能。通过理论分析,DRDP码拥有良好的编译码复杂度和更新效率,大幅节省了单盘故障修复读取开销,并对双盘故障修复读取开销进行了优化,同时能修复75%三盘故障的情况。实验结果表明,与RDP码、LRRDP码和RDP(p,3)码相比,DRDP码的编码时间可节省8.23%～32.89%、单盘故障修复时间可节省7.08%～35.01%、双盘故障修复时间可节省5.07%～29.26%。     

具有多个相交修复集的局部修复码的新构造

局部修复码可以通过仅访问很少的有效节点完成故障节点的修复。作为局部修复码的推广,具有可用性的局部修复码允许每个节点拥有多个不相交的修复集,这种特性对于分布式存储系统的部署非常有利,但是其中的可用性会降低其码率上界。对该类编码进行了推广,使同一节点的不同修复集可以相交较小的次数,这使得码率得以提升,并令该类编码具有负载平衡特性。将具性质较好的文献[14]提出的WZL码推广至修复集可以相交的情况,提高了码率,并且该构造的最小距离也优于文献[10]中关于此类编码的构造。     

基于sunflower的局部修复码构造

针对目前构造达到C-M界的二元局部修复码(LRC)的相关研究已经较为充分,但在一般域上还相对较少的问题,研究了一般域上LRC的构造.首先,提出了通过射影几何理论确定sunflower中元素个数的方法.其次,通过不相交局部修复组刻画LRC,从而清楚地描述LRC的码长、维数和局部度等参数.最后,在具有不相交局部修复组的校验...     

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

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

一类精确修复多个节点的简单再生码

海量数据环境下要求存储系统具有高扩展性、高可靠性和低成本等特点。大规模存储系统的节点因数目巨大而易频繁失效,为保证节点的可用性,系统会利用冗余数据对失效节点进行修复。作为一种新的容错技术,再生码可有效降低分布式存储系统中失效节点修复时需要的下载数据量。基于简单再生码,为分布式存储系统设计一种新的编码方式。它不仅可容忍多个节点同时出错并进行修复,而且编码形式简单并具有较高的码率。     

分布式存储中基于局部修复码的负载均衡方法

针对分布式存储中热数据访问性能低下的问题,提出一种基于局部修复码（LRC）的负载均衡方法,采用编码的方式规避节点的集中式访问,并提高热数据的访问效率。首先,利用平衡不完全区组设计（BIBD）构造一类适用于小规模存储系统的特殊LRC,从而为编码数据提供多种访问方式;然后,分别基于里所（RS）码和随机阵列码将LRC推广到更大规模,并使它满足存储系统一定的容错需求;最后,提出一种热数据访问算法以降低热数据的访问压力,并结合合理的数据布局方案实现存储系统在高频访问场景下的负载均衡。理论分析和实验结果表明,所提方法能以极小的代价实现负载均衡,明显优于传统方法中利用多副本及最大距离可分（MDS）码实现的负载均衡方法,尤其是解决了因冷热数据访问不均带来的负载失衡问题,可以有效提高热数据存储系统的访问效率。     

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

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

低维五元最优线性码的局部修复度分析

局部修复码应用于分布式存储系统中,其码字的任意位发生错误都可通过读取该码字其他若干位予以修复。根据该特性,围绕三维、四维最优码展开研究,通过讨论已知特殊最优码的相关参数,同时分析已知最优码生成矩阵列向量之间的线性关系,使用矩阵变换、矩阵拼接、删截等方法,构造五元域上所有的三维、四维最优码。在此基础上,分析该码尽可能小的局部修复度,并通过C-M界判定局部修复度的最优性,得到距离最优的局部修复度。     

云存储系统中的预测式局部修复码

为了保证客户访问数据的高可用性,一些云存储系统开始采用一类新型编码,即局部修复编码(locally repairable codes, LRC).例如Windows Azure和Facebook的HDFS RAID.与Reed-Solomon码相比,LRC修复效率高,因为它将每个条带的数据块分成多个组,每个组内额外生成一个校验块,因而组内就可以对单个故障块进行修复.LRC假设每组大小相同,这意味着每个故障块的修复所产生的组内数据传输量是相同的.但是,对于那些更易出现故障的磁盘,它们所造成丢失的数据块理应被系统更有效地修复.借助基于决策树的磁盘故障预测方法来动态调整LRC中组的大小,从而构造一类预测式LRC(proactive LRC, pLRC),使得即将发生故障的磁盘存储的数据块所在的组的长度变小,以便这些数据块可以在更小的组内进行更快地修复,同时保持和传统LRC相同的存储开销和编码结构.不仅通过MTTDL建模分析pLRC的可靠性,还在Facebook的Hadoop HDFS平台中实现了pLRC并进行了性能测试.结果表明,比起LRC,pLRC的可靠性最多可提升113%,同时降级读和磁盘修复性能最多可提高46.8%和47.5%.     

一种新的三容错最大距离可分阵列码

随着海量存储系统的发展,双容错数据布局已不能满足系统对可靠性要求.在双容错行对角线奇偶码的基础上,只增加1冗余校验列,提出一种新的3容错最大距离可分阵列码.采用二元矩阵给出了新的阵列码代数编码定义,并通过基二元矩阵变换,给出结构简单易于软硬件实现的译码算法.并理论上证明新阵列码具有最大距离可分编码特性,空间利用率达到了3容错编码最优.与现有其它3容错编码进行比较,分析结果表明新码的编译码效率,小写性能,以及平衡性的综合性能达到最优.     

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

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

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

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

去中心化的安全分布式存储系统

提出一种去中心化的安全分布式存储系统。通过公钥加密和单钥加密相结合的方法,提高存储数据的保密性。对每个数据源使用不同的对称密钥进行分布式加密,采用分布式纠删码对加密后的数据进行编码。使用RS多项式编码和List Decoding译码方法存储加密的对称密钥,以保证系统的鲁棒性。分析结果表明,该方案的计算复杂度较低。     

基于最大秩距离码的公钥密码系统

秩距离码及最大秩距离码的概念是由Gabidulin首先提出的,由于秩距离的特点,利用秩距离码构造的各种密码体制和认证系统的安全性比汉明距离度量的码更高。利用最大秩距离码,提出了新的McElience公钥密码系统,讨论了其可行性及安全性,证明了它比基于纠错码的McElience公钥密码系统更安全。而且,通过引入单向杂凑函数,使密码系统能有效的抗击消息重发攻击和相关消息攻击。     

纠错码和秩距离码的一些新的构造方法

给出一般纠错码和秩距离码的一些新的构造方法,求出了构造的各种码的生成矩阵。指出了最大秩距离Reed-Solomon码和最大秩距离BCH码为新构造的秩距离码的特殊情况。     

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

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

一种计算级联Z形码最小距离的方法

提出一种有效的计算级联Z形码最小距离的方法。该方法将多维的级联Z形码并行地分成两个低维数的分量码,其中有一个分量码的维数固定为2,然后找出所有能在该二维分量码中产生低于某个已知的最小距离上限的输入序列,再验证这些序列在整个码中产生的距离,从而找出最小距离。从最后数字结果来看,使用普通的个人计算机,该方法能够在111小时内为码率为1/2的级联Z形码找出最小距离20,而在38小时内为码率为1/3的级联Z形码找到最小距离26。