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

发布时间：2021-01-11 23:18

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

【文章来源】：小型微型计算机系统. 2020,41(05)北大核心

【文章页数】：7 页

【部分图文】：

系统型(6,4)-MDS码

在本文中，将以系统型(n,k)-MDS码作为基础码，用{aj=(a1,j,a2,j，…，ak,j)T}jm=1表示包含m个实例的原始数据，并且以未被编码的形式存储在k个系统节点上，根据图2(a)中介绍的Piggybacking框架，则具有Piggybacking框架的系统型MDS码如图2(b)所示．2.3 RSR-II码

由于篇幅所限，RSR-II码的编码构造及修复算法详见文献[13]．下面给出RSR-II码的例子，该例子以系统型(13,9)-M DS码作为基础码，校验节点的个数为r=4，因此实例数为2r-3=5．首先，对基础码添加piggybacks后如图3(a)所示，然后，在同一节点的不同实例间进行可逆线性变换，得到最终的编码结果如图3(b)所示．由系统节点数为k，校验节点数为r的RSR-II码修复算法可知，为修复一个系统节点，需要在有限域上求解r-1个方程，而RSR-II码添加piggybacks的规则导致了其中r-2个方程为属于同一个方程组的方程，为使得方程组总是有解的，便在编码过程中引入了长度为k的向量．但是，随着校验节点数r的不断增大，不仅由公式(1)公式(2)计算向量的乘法计算量会随之增大，而且所解方程组中方程的数量也会随之增大，这显然会增加编码复杂度和修复复杂度．

【参考文献】：
期刊论文
[1]分布式存储系统中的纠删码容错方法研究[J]. 孙黎,苏宇,张弛,张涛.  计算机工程. 2019(11)
[2]Erasure coding for distributed storage: an overview[J]. S.B.BALAJI,M.Nikhil KRISHNAN,Myna VAJHA,Vinayak RAMKUMAR,Birenjith SASIDHARAN,P.Vijay KUMAR.  Science China（Information Sciences）. 2018(10)
[3]分布式存储中的纠删码容错技术研究[J]. 王意洁,许方亮,裴晓强.  计算机学报. 2017(01)



本文编号：2971667