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.

LRCRaft:支持节点数据快速恢复的共识协议

在支持纠删码的分布式存储系统中,最常用的编码是RS(Reed-Solomon)码.对于一个RS(k,m)编码条带,常见的配置是一个节点仅存储条带中的一个分片,这导致在节点出现故障的情况下,对其存储分片的恢复需要跨多个节点读取分片并重新编码生成恢复分片,容易造成系统网络拥塞.在需要恢复大量数据的场合,系统在恢复期间会处于较长时间的脆弱期,容错能力和吞吐量下降、读写时延升高时有发生.LRCRaft是一个基于LRC(local reconstruction code)的改进Raft共识协议,通过在Raft中引入LRC码、动态日志增补、状态机删减和分片版本一致性等机制,降低了Raft的读写时延,缩短了节点故障恢复时间.实验结果表明,相较于Raft,LRCRaft在不同恢复模式中恢复一个单节点故障数据时,恢复用时有着49.25%–74.97%的减少.

LRC码最小距离限的深入分析

为了增强最小距离限的精确性,缩小最小距离的范围,提出了两个新的最小距离限.首先,在局部修复码Singleton-like限的基础上,通过理论推导提出了第1种新的最小距离限,该新限适用于所有码字;其次,结合新提出的最小距离限和已经存在的最小距离限,推导出了第2种新的最小距离限,该新限适合更小范围码字;再次,通过理论公式推导,得出了在相同参数情况下各个最小距离限之间的关系.仿真结果表明,在相同码长、信息位和局部性的条件下,第1种新的最小距离限的性能和Singleton-like限一样好,第2种新的最小距离限优于已存在的最小距离限.

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

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

基于有限域结构的LRC码的存在性讨论

假设C是有限域Fq上的(n,k)线性码,若码字的每个分量值是其他r个分量值的函数,则称C为(n,k,r)LRC码,这里r相对于码长来说是个较小的数。基于有限域结构构造LRC码的方法通常有3种:利用有限域的加法结构、乘法结构及其子域上的向量空间结构。然而,这些构造方法不是对任意局部参数为r的LRC码都能构造。为了解决这个问题,本文通过组合代数等方法,对任意给定素数p,提出了Fq上G-多项式存在的充分条件,讨论了一类局部参数r=p2+p-1的局部恢复码的存在条件,并通过两个实例来说明相关问题。

三角形结合方案的最优局部修复码构造

局部修复码(LRCs)为用于分布式存储系统中的新型纠删码,能够有效实现海量数据的可靠高效存储,构造具有(r,t)局部性的LRCs已成为当前研究热点.为此,提出基于三角形结合方案的LRCs构造方法,可构造具有任意(r,t)局部性的二元最优LRCs.性能分析结果表明,构造的可用性t=2的LRCs达到了最优码率界,构造的具有任意局部性r>2和可用性t>2的LRCs达到了最优最小距离界.与基于近正则图及基于直积码等构造方法相比,本文构造出的LRCs在码率上表现更优且参数选择更灵活.

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

对于单容错和双容错的存储系统,在磁盘修复过程中发生的任何故障都可能引起数据丢失,导致修复失败,保证数据的修复效率对于存储系统的可靠性至关重要。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%。

基于正交拉丁方的局部修复码构造

针对目前具有(r,t)局部性的局部修复码码率较低且构造过程中计算复杂度过高的问题,提出基于正交拉丁方的二元局部修复码构造方法.根据正交拉丁方元素与矩阵位置的对应关系构造关联矩阵,得到具有全符号局部性的局部修复码(AS-LRCs),该码的码率和码长渐近边界条件,且最小距离较大.利用关联矩阵级联单位矩阵构造信息位具有(r,t=2)局部性的单校验局部修复码,该码的最小距离和码率均满足最优边界条件,为最优局部修复码.考虑到实际分布式存储系统中存在高故障率节点,利用正交拉丁方完备组构造具有信息位局部性的高可用性单校验局部修复码(IS-LRCs),可以灵活选择可用性t,提高了系统的鲁棒性与灵活性.

分布式存储中基于动态局部修复码的负载均衡研究

分布式存储系统中数据的访问存在不均衡性,大多数访问聚集在少部分数据上,便会引起系统的负载不均衡,导致部分高负载节点成为整个系统的性能瓶颈。针对此问题提出一种负载均衡的动态局部修复码(ALRC),该编码方案通过历史热度对冷热数据进行优先级确立,再对冷热数据进行动态编码,使其具备(r,t)-availability性质,让数据能够拥有额外的访问路径,借此提高热数据的并行访问性能和系统的负载均衡性,同时兼顾一定的存储效率。实验结果表明,ALRC在系统负载较不均衡时只需要相较于编码前少量的额外存储开销,便可拥有相较于原方案53%以上负载均衡度的提升,从而确保节点间的负载分布均匀,提高整个系统的性能和可靠性。

有限域F_(81)上的双恢复集的局部恢复码的构造

局部恢复码(LRC)是指码字的任意一个坐标位置的值都可以通过较少的r个其它位置的值来恢复.构造具有双恢复集的LRC码是为了解决通信中节点访问的拥堵问题.本文将在有限域F_(81)上,通过其不同的乘法子群的陪集将其正交划分,构造出码的生成集,进而赋值产生具有双恢复集的局部恢复码.进一步地,将其推广到特征为3的一般有限域上构造双恢复集的LRC码.

分布式存储系统中基于Pyramid码的局部性修复编码

为了提高分布式存储系统的存储可靠性以及故障节点的修复效率,提出一种基于Pyramid码的局部性修复编码方案。该编码方案采用Pyramid码的最小可实现编码结构,划分局部修复组,确保较低的修复局部性并实现故障节点的快速修复。性能分析表明,基于Pyramid码的局部性修复编码可实现存储系统中多个故障节点的快速修复,具有较低的修复局部性,且相对于三副本复制策略以及简单再生码,基于Pyramid码的局部性修复编码在存储开销和修复带宽开销方面的性能更优。

短码长四元最优局部修复码的构造

在分布式存储系统中,当节点发生故障时局部修复码(LRC)可以通过访问少量其他节点来恢复数据,然而LRC的局部度不尽相同,该文构造了短码长且局部度较小的四元LRC。当码长不超过20,最小距离大于2时,若四元距离最优线性码的生成阵维数不超过校验阵维数,可利用其生成阵给出LRC,否则利用其校验阵给出LRC。对已构造的LRC的生成阵或校验阵,利用删除、并置等方法得到新矩阵,从而构造出190个码长n≤20,最小距离d≥2的LRC。除12个LRC外,其他LRC是局部度最优的。

分布式存储系统中基于部分重复循环码的局部修复码构造

为了进一步优化分布式存储系统故障节点修复的磁盘I/O开销和修复局部性,提出一种基于部分重复循环码的局部修复码方法。首先构造部分重复循环码(FRCC);然后在此基础上划分局部修复组;最终得到相应的局部修复码,且局部修复组内故障节点可以通过相邻节点实现协作修复,以确保较低的磁盘I/O开销和修复局部性。性能分析以及实验仿真表明,采用基于部分重复循环码的局部修复码,单节点故障的修复局部性恒为2,并且可以快速实现多个故障节点的数据重构;与三副本复制策略、简单再生码以及基于传统FRC的局部修复码相比,基于部分重复循环码的局部修复码具有更低的修复带宽开销和修复局部性,修复效率更高。

基于Hadamard矩阵构造部分重复码

针对分布式存储系统故障节点修复问题,提出一种部分重复(FR)码的构造算法。由Hadamard矩阵经过简单变换直接构造FR码。随后引入了分组思想,由8阶Hadamard矩阵构造分组FR码(HGFR),构造更加简洁直观,实现多故障节点在局部修复组内进行精确无编码修复。理论分析发现,与RS码和SRC简单再生码相比,设计的HGFR码在分布式存储系统节点发生故障时的修复局部性、修复复杂度和修复带宽开销都降低,且修复效率提高,减少了故障节点的修复时间。

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

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

基于混合型正交表构造部分重复码

考虑到分布式存储系统中数据的存储和节点修复,提出一种基于混合型正交表的异构部分重复(fractional repetition,FR)码构造算法,并证明了该异构FR码是一般好的一般部分重复(generalized fractional repetition,GFR)码。利用混合型正交表中的水平对构造关联矩阵,根据关联矩阵对数据块在存储节点进行存放。另外,利用分组的方法在混合型正交表的基础上构造分组部分重复码,可以在局部组内实现单故障节点的精确无编码修复,修复局部性为2或3,且能够对多个故障节点进行快速有效的修复。性能分析和实验仿真可知,所构造的分组FR码与RS码和简单再生码相比,在修复故障节点时具有较小的修复带宽开销和修复局部性,修复效率得到了提升。

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

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

基于Hadamard矩阵的最优局部修复码构造

现有的局部修复码大多能满足最小距离最优的边界条件,但是在满足最小距离最优情况下构造维度最优的局部修复码还比较困难。针对上述问题,提出一种基于Hadamard矩阵的最优局部修复码的构造方法,通过对Hadamard矩阵进行扩展,构造局部修复码的校验矩阵,进而通过此校验矩阵构造最优局部修复码。首先,基于Hadamard矩阵构造局部修复码的校验矩阵,通过校验矩阵构造的局部修复码的最小距离可以达到最优最小距离界,但是其维度没有达到最优维度边界条件;为进一步提高维度,将校验矩阵中的关联矩阵0和1元素互换得到新的关联矩阵,通过和新的关联矩阵级联进行扩展,构造的扩展局部修复码不仅可以达到最小距离最优,且能达到维度最优的边界条件。与现有局部修复码相比,该构造的局部修复码是最小距离和维度最优的局部修复码,且其码率也更逼近局部修复码最优码率的边界。

基于RBIBD的最优局部修复码构造

随着数据量的迅速增长,对存储海量数据的分布式存储系统的可靠性和有效性的要求日益增加。局部修复码(LRCs)具有良好的修复局部性,能够有效实现海量数据在分布式存储系统中的可靠高效存储,构造具有(r,t)局部性的局部修复码已经成为当前研究的热点。为此,提出了一种基于可分解均衡不完全区组设计(RBIBD)的最优局部修复码的构造方法,构造信息位具有(r,t)局部性的二元最优单校验LRCs。性能分析表明,构造的LRCs达到了最小距离最优边界,且在码率上表现得更优。

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

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