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.

Construction of Minimum Bandwidth Regenerating Codes with Combinatorial Design

We study the construction of minimum bandwidth regenerating code with combinatorial design. At first, a method of constructing minimum storage regenerating （MBR） codes is presented, which can tolerate only one-node failure. Then, we give examples to explain the code. Finally, we discuss the case of repairing multiple nodes, and analyze the performance with an example.

一类新的(k+2,k)Hadamard MSR码

为降低分布式存储系统中节点的存储量,构造了一类新(k+2,k)Hadamard MSR码.该码的每个编码矩阵皆对应于2个值,供其对角元素选取.在编码矩阵中,这2个值循环出现,且不同的矩阵,循环出现的周期不同.基于这一特性构造了节点的修复方案,将失效节点中的α个数据分成α/2组,每一组重建2个数据,其他k+1个节点为每一组各提供1个数据.证明了若新码编码矩阵的对角元素可取的2个值不相等,则可最优修复系统节点;若所有编码矩阵对角元素可取的2个值的和为同一不为0的值,则可最优修复第1个校验节点;若所有编码矩阵对角元素可取的2个值的逆的和为1,则可最优修复第2个校验节点.新码的节点存储量降低到了Hadamard MSR码的理论界,可最优修复任意系统节点和1个校验节点.

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

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

基于Hadamard向量的新型(k+2,k)MSR码

在分布式存储系统中,再生码是一种能够最优修复节点丢失数据的编码策略.在存储空间有限的前提下,设计出一种高码率的最小存储再生码可以进一步提高存储空间的利用率.利用Hadamard向量设计出一种新型高码率最小存储再生码,实现最优精确修复所有系统节点数据.这种新的编码策略将Hadamard向量进行变型,同时改变了Hadamard向量放置在编码矩阵中的位置.与原有的(k+2,k)Hadamard MSR码策略不同,将编码矩阵中的Hadamard向量从主对角线位置移至非主对角线上时,能够减少修复过程中有限域上的运算次数.从而使这种新型再生码策略在能够精确修复系统节点数据的同时,进一步降低数据修复过程中的计算复杂度.

低复杂度的最小冗余再生码的矩阵构造方法

针对现有的基于矩阵的最小冗余再生码的构造方法中存在的编码和重构复杂度高及参数选择受到限制的问题,设计了一种矩阵实现的最小冗余再生码的构造方法.该方法通过改变数据矩阵和修复向量的结构,能够有效地减少最小冗余再生码的编码和数据重构的复杂度,同时参数的选择更加简单和灵活.

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

再生码因能有效地减少修复带宽,更适用于分布式存储系统。利用干扰对齐技术,对于任意的参数(n,k,d),满足n≥2k且d≥2k-1。Suh和Ramchandran构造了修复一个失效节点时,可达到最优修复带宽的最小存储再生码。基于Suh-Ramchandran再生码,重新描述了参数(n=2k+1;k)下的编码结构,并说明这种码为一类可修复多个失效节点的再生码,且在修复单个或多个失效节点时均可达到最优的修复带宽。

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

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

基于功能性最小存储再生码的数据可恢复验证方案

针对云存储环境下数据完整性验证机制中的数据可恢复验证方案(proof of retrievability,POR)存在的损坏数据检测时间长和数据恢复开销大的问题,设计了一种基于功能性最小存储再生码(functional minimum storage regenerating,FMSR)的数据可恢复验证FMSR-POR方案。方案对用户数据进行分块后分别进行FMSR编码,将编码后的数据块存储到云上,通过“挑战应答”协议对编码块进行完整性验证和数据块损坏定位,利用FMSR码特性对损坏数据块进行修复。实验证明,基于FMSR编码的POR方案可以支持动态的数据操作,能够以较高的效率进行损坏数据块定位和修复,且数据修复带宽开销有所减少。

云存储系统中基于MSR码的局部性修复编码

为了提高分布式云存储系统的存储可靠性和故障节点修复效率,提出一种基于最小存储再生码的局部性修复编码方案.具体地,构造适用于云存储的系统最小存储再生码,以此码为局部码构造局部性修复编码,确保最大距离可分性质和简单修复特性.性能分析和仿真结果表明,该局部性修复编码方案可实现云存储系统中多个故障节点的快速修复,具有较低的修复局部性,相对于三副本复制方式和简单再生码,该局部性修复编码方案在存储开销和修复带宽开销方面的性能更优.

基于分布式计算的数字化校园云存储网络安全策略研究

针对传统校园云存储网络存在存储系统扩展性差,数据安全性低,节点读写压力大的问题,提出一种基于分布式计算的数字化校园云存储网络安全策略。首先,基于最小存储再生码(MSR)的多失效节点修复场景,推广单失效节点修复拓扑方案;然后在其基础上引入允许对集群中高可用带宽链路进行复用的原理,设计一种新的多失效节点修复拓扑方案;最后将多节点修复问题抽象为一个以修复时延和修复流量为目标函数的带约束优化问题,采用混合遗传算法进行最优求解。结果表明,在相同的存储规模下,相较于传统的采用再生码的星型修复方案,提出的多节点修复方案的修复时延明显降低了10%~30%;本方案的修复流量仅为传统边不相交树型修复方案的30%~40%。由此说明,提出的方案可有效增强存储系统扩展性和安全性,降低多节点读写压力,具有一定的可行性。