去中心化存储下分布式低带宽多节点修复方法

李 慧，李贵洋，周 悦，江小玉，韩鸿宇

(四川师范大学 计算机科学学院，成都 610101)

1 引 言

随着信息技术的不断发展，如移动互联网、人工智能和虚拟现实等，这些技术在改变人类的认知及生活方式地同时也产生了许多关于个人行为、活动的信息.为了便于使用与研究，这些信息不仅被数字化地描述出来，而且被还持久化存储下来.公共云存储，正是一种存储大量数据信息的方式，已经被证明是大型集中式云提供商的一个有吸引力的业务模型[1].中心化存储系统因其高效性和商用性而广受欢迎，但仍存在成本较高、安全性低、隐私泄漏等问题.而去中心化存储系统通过共享世界各地(个人/公司)的闲置硬盘与带宽来组成去中心化的网络，其基于区块链技术天然的去中心化、开放、自治、匿名、可溯源、不可篡改等特性，从而真正改善“中心化存储”问题[2].

目前主流去中心化的分布式存储平台有IPFS、Sia、Storj和MaidSafe等.对标中心化云服务市场的份额大约在一万亿美金左右，预测基于区块链技术的分布式存储将是下一个千亿级市场[3].如此庞大的市场和需求吸引各大企业投资，也成为学术研究热点之一[4].而为保证数据的有效性和完整性，去中心化系统主要采用纠删码来减少存储空间和网络带宽消耗.RS(Reed-Solomon)码常常是去中心化存储系统的选择之一，如Stroj[5]部署RS(40，20)，Siacoin[6]部署RS(30，10)，而MaidSafe[7]和Filecoin[8]则采用是f(n，m)的计算方法.然而，在去中心化存储系统的节点虽然拥有充足的存储空间和CPU能力，但它们的网络带宽是有限的，所以研究如何降低纠删码修复时所占用的网络资源对促进纠删码在去中心化存储下的应用具有重要意义.

当节点失效时，为了降低修复带宽、减少修复时间，主要从编码结构、数据传输模式进行改进[9].因去中心化存储下网络结构的变化和节点的不稳定性，导致纠删码已从分布式存储下的高码率转化成低码率，单节点修复转化成多节点修复，所以本文主要优化纠删码在多节点修复的数据传输.

目前纠删码数据传输优化修复方法主要有星型结构[10](Star Structure Based Repair，SSR)和树型结构[11](Tree Structure Based Serial Repair，TSR)和集中式结构[12](Traffic Efficient Repair Scheme for Multiple Failures，TERS).当节点失效时，系统立即启动修复机制，首先需选择其他可用节点(称为新替代节点)来存储修复数据块.为了修复出原始失效数据块，新替代节点需从多个可用数据节点中(称为提供者节点)下载数据块进行计算修复.在去中心化系统的多节点修复中，串行的星型结构方式或并行的树型结构方式，并不能充分利用在修复多个失效数据块中提供者节点之间的数据冗余性和计算冗余性；而集中式结构的中心节点存在带宽瓶颈，也没有利用多节点修复并行处理方式，增加了多节点修复过程中的带宽开销，延长了修复时间.

针对目前纠删码的数据修复传输方法在去中心化系统多节点修复中存在修复成本高和修复效率低的问题，本文提出一种基于去中心化存储的分布式低带宽多节点修复方法DSMR(Distributed Structure Based Multinode Repair).

2 纠删码

纠删码是一种数据冗余备份机制，因其具有高可靠性和低存储空间等性质，常被部署在各类存储系统中以保证数据的可靠性.

纠删码通常用两个参数(n，k)来表示，即先将原始数据M分成k份大小相等的数据块D1,D2,…,Dk，再对这k个数据块进行线性组合编码，最后生成n(n=k+r)个大小不变的编码块C1,C2,…,Cn，分别存储到n个存储节点(Node)上，即为一个条带.当原始块数k大于校验块数r时，此码为高码率，即码率系数(l=k/r)>1；反之为低码率，即码率系数(l=k/r)≤1.当任意不大于r个存储节点失效时，都可通过下载任意k份未失效节点数据来解码恢复原始数据，该性质被称为MDS(maximum distance separable)属性.

2.1 纠删码的编码原理

目前在去中心化存储系统中普遍采用的纠删码是线性RS码.即每一个编码块Ci都是数据块D1,D2,…,Dk的线性组合，如式(1)所示，其中系数矩阵G的大小为n×k，一般由范德蒙矩阵或柯西矩阵构成，其中gij∈Fq,(i=1,2,…,n,j=1,2,…,k)，而Fq则是大小为q的有限域(galois field).

(1)

2.2 纠删码的修复原理

当节点Nodei失效时，节点Nodei存储编码块Ci就丢失.为了修复失效编码块Ci，可以通过下载未失效编码块及组合系数，其中需要对编码时的系数矩阵进行求逆[13]，然后计算得到Ci的线性组合.对于RS码而言，修复时需要下载任意k个未失效编码块C′1,C′2,…,C′k，求得编码块的修复逆矩阵系数(ω1ω2…ωk)，ωj∈Fq,(j=1,2,…,k)，计算得到与Ci内容大小相同的编码块Hi，存储在新替代节点Node′i中，如式(2)所示.

(2)

3 分布式低带宽多节点修复方法

本节首先介绍分布式低带宽多节点修复模型DSMR，主要阐述系统中节点的不同特征和多节点修复的四大步骤；然后详细描述DSMR的重要算法，包括节点选择算法和数据传输算法.

3.1 DSMR修复模型

DSMR修复模型在RS编码基础上，利用编码在去中心化存储系统下的低码率和多节点修复性质[14]，将传统串行、集中式修复方式转化成分布式修复方式，以减少网络带宽、降低修复时间.本文通过DSMR(n,k,m)模型来说明在去中心化存储下RS码的分布式低带宽多节点修复，如图1所示.

图1 DSMR(n,k,m)修复模型图

图1中Src表示系统的根节点，完成文件编码工作，包括文件分块、数据编码和节点分发.具体先将原始数据文件M分成k个大小为α的数据块，编码产生n个相同大小数据块X1,X2,…,Xn，再分发存储在n个不同节点中.当m个节点失效时，系统启动多节点修复，其中X1,X2,…,Xn-m表示未失效的数据节点，Y1,Y2,…,Ym表示m个新替代节点，βi,j表示提供节点Xi向新替代节点Yj传输的数据量，pi,j表示新替代节点Yi向新替代节点Yj传输的数据量.Des表示系统的目标节点，通过下载任意k个节点数据，解码计算得出原始数据M.

当m个节点失效时，系统启动DSMR多节点修复模型，具体分为如下4步：

1)节点分组连接：系统首先找到m个新替代节点Y1,Y2,…,Ym.为了保证能完整修复失效节点数据，m个新替代节点一共需连接下载k个提供者节点数据.那么每个替代节点Yi(i=1,…,m)通过均分分组连接qi个未失效的提供节点X′1,X′2,…,X′k，如式(3)所示，通过判断k能否整除m来进行分组；

(3)

2)数据下载计算：每个新替代节点Yi(i=1,…,m)下载提供节点X′j(j=1,…,qi)的全部数据C′j(j=1,…,qi)和编码块对应的修复逆矩阵系数(ω1ω2…ωk)，如式(4)所示，计算得到m份与m个失效节点相关的数据集pi,u；

(4)

3)节点交互传输：新替代节点Yi(i=1,…,m)将中间结果pi,u(u=1,…,m)与其他新替代节点Yu进行数据交互，即每个新替代节点Yi(i=1,…,m)将中间数据集pi,u(u=1,…,m)保留对应的数据pi,i在本地，另外的m-1份数据{pi,1,pi,2,…,pi,m}pi,i都传输给对应的新替代节点{Y1,Y2,…,Ym}Yi；

4)计算恢复数据：每个新替代节点Yi(i=1,…,m)将m份与失效节点相关的数据pu,i(u=1,…,m)进行合并计算得到失效节点的编码块.即每个新替代节点将从其他新替代节点接收的数据{p1,i,p2,i,…,pm,i}pi,i和自身保留的数据pi,i进行合并，如式(5)所示，计算恢复出失效节点编码块Hi.

(5)

在整个DSMR修复过程中，我们发现节点的不同选择方式和数据的网络传输结构会影响去中心化存储系统下的多节点修复性能.因此，本文通过分析去中心化存储系统中节点特性和网络结构，提出以最大化节点带宽的节点选择算法、以最大化数据传输效率的数据传输算法来提高系统修复性能.

3.2 DSMR的节点选择

在去中心化存储系统中，节点选择会影响数据修复性能的因素主要包括：一是节点负载，包括节点所承受的计算和存储负载；二是带宽大小，节点能为数据传输提供的带宽；三是网络跳数，节点之间的物理链路数目；四是节点稳定性，节点发生失效的频率.由于去中心化系统网络的实时变化，从而导致节点负载和带宽大小也发生变化，如果选取这两点作为节点选择算法的标准，使得节点选择算法也需实时计算，会额外增加了存储系统的开销.其实可用网络距离表来衡量节点间的网络跳数[15]，而且节点间的可用带宽关系也可通过网络跳数来表示.因为大部分存储系统的网络结构都采用树形拓扑来实现节点之间的通信，而一般在低层次交换机上的节点更少，高层次交换机上的节点更多，所以在同等带宽网络状态下，节点通过均分占有网络带宽，那么低层次交换机的节点实现通信的带宽就更大，需要跳转的网络距离也就越短，从而节点间的网络跳数也就更小.因此，节点间的带宽较小，则网络跳数越大；反之，节点间的带宽较大，则网络跳数越小.此外，与分布式存储系统对比，显然在去中心化存储系统中的节点稳定性更低，从而导致节点存储数据块更容易发生短暂或长久性丢失.为降低节点通信次数和节点修复重传频率，可通过BitSwap协议表[16]来衡量节点稳定性高低.对于乐于分享数据，上传数据量大，存储贡献大，节点通信次数多的这一类节点，可定为高稳定性节点.反之，对于仅仅下载数据，无过多存储贡献，节点通信次数少的这一类节点，可定为低稳定性节点.

因此在DSMR修复过程中，可依据“网络跳数”和“节点稳定性”两个指标选择节点：新替代节点和提供者节点，以减少去中心化系统的网络负载和修复时间，具体如算法1所示.

算法1.选择节点算法

输入：参数(n,k,m);待选择新替代节点列表newreplaceList；待选择提供者节点列表providerList

输出：新替代节点newreplaces；提供者节点providers；分组连接提供节点列表linkList

forifrom 1 to 2m

newreplacei← random(newreplaceList)

computecomi

Y1,Y2,…,Ym← Arrays.sort(com1,com2,…,com2m)

newreplaces.add(Y1,Y2,…,Ym)

for eachnewreplaceiin newreplaces

forjfrom 1 tok

providerj← random(providerList)

X′1,X′2,…,X′qi←Arrays.sort(hopListi)

linkListi.add(X′1,X′2,…,X′qi)

provider.add(linkListi)

providerList.delete(X′1,X′2,…,X′qi)

DSMR的节点选择算法主要分析去中心化存储系统节点的具体作用，用节点稳定性来确定新替代节点、用网络跳数来确定提供者节点，以提高系统存储数据的稳定性、缩短修复数据的路径长短.

3.3 DSMR的数据传输

在去中心化存储系统中，DSMR的数据传输主要分为两步：一是提供者节点与新替代节点之间的数据传输，二是新替代节点之间的数据传输.由于在去中心化存储系统中采用的是RS码，因此提供者节点需将存储全部数据传输给新替代节点.为保证失效编码块的有效修复，利用MDS性质可知，下载k个未失效编码块的全部数据都能修复得到失效块数据.因此，在DSMR修复过程中，m个新替代节点共同读取k个提供者节点数据，然后每个新替代节点计算出m份中间结果进行交互，最后合并恢复出每个失效节点的编码块，具体如算法2所示.

算法2.数据传输算法

输入：已选择新替代节点列表newreplaces；分组连接提供节点列表linkList

输出：修复块(H1,H2,…,Hm)

for eachnewreplaceiin newreplaces

for eachproviderjinlinkListi

Yi←C′j

forufrom 1 tom

for eachnewreplaceiin newreplaces

for eachnewreplaceuin newreplaces

ifi≠uthen

Yi←pu,i

for eachnewreplaceiin newreplaces

提供者节点与新替代节点之间的数据传输：每个替代节点Yi(i=1,…,m)通过连接qi个未失效的提供节点X′1,X′2,…,X′qi，并获取节点存储全部数据C′i.每个新替代节点接收完提供者节点的数据块，即C′1,C′2,…,C′qi，然后通过修复操作得到m个失效块的中间结果pi,u(u=1,…,m).

新替代节点之间的数据传输：每个新替代节点Yi(i=1,…,m)先将修复自身数据的中间块pi,i存储在当前节点之中，再把剩下m-1个中间块{pi,1,pi,2,…,pi,u}pi,i发给新替代节点{Y1,Y2,…,Ym}Yi.每个新替代节点在收到其他新替代节点发来的所有中间块数据pu,i(u=1,…,m)，最后进行线性组合得到失效块数据Hi.

DSMR的多节点数据修复传输模型，如图2所示.其中，m个新替代节点{Y1,…,Ym}与k个提供者节点{X1,…,Xk}以并行模式进行传输，与单节点SSR星型结构不同的是，DSMR中的k个提供者节点只需要传输一次数据即可修复m个失效节点，大大减少了数据传输量.与多节点TERS集中结构不同的是，DSMR中不存在中心节点，每个新替代节点均分连接提供者节点组进行数据传输，节点相互不影响、可并行传输，降低数据传输时间和节点负载.由于新替代节点需要通过原始编码块计算出m个失效节点的中间结果，而TSR树形结构最大特点就是中间节点会进行组合计算，这会导致传输的原始数据不完整，所以DSMR的数据传输不能使用树形结构.

图2 DSMR数据传输示意图

在DSMR的数据传输过程中，每个提供者节点Xi将存储的全部数据βi,j=α都发送给新替代节点Yj.新替代节点在计算失效数据块时采用RS码的计算修复方式，得到m个中间组合结果，从而新替代节点Yi向新替代节点Yj传输的数据量pi,j=1.因此在DSMR修复过程中，修复m个节点所需传输的数据量为kα+(m-1)m.

在DSMR修复过程中，利用分组传输和计算交互的方法极大地降低了去中心化存储系统中多节点修复带宽过高的问题.通过选择节点分组连接、数据下载计算、节点交互传输和计算恢复数据四个步骤完成了分布式低带宽多节点修复.

4 对比分析结果

本节先通过理论分析SSR、TERS和DSMR多节点修复模型的存储开销和修复带宽；再以实验方式测试多节点修复过程中的平均修复时间，通过失效节点数、条带数和码率系数三方面来对比DSMR与其他典型修复方法的性能以验证在多节点修复过程中的优势.

4.1 理论对比

在多节点修复过程中，影响RS码在去中心化系统中应用的两个因素分别是存储成本和修复成本.控制编码的存储成本是所有存储系统的标准要求之一，越低的存储成本能直接降低系统成本，而较少的修复带宽开销能降低系统网络负载、增强系统稳定性.而RS码的多节点修复包括数据传输和数据计算.

数据传输：随着去中心化系统的逐渐发展，用户的不断加入，那么系统的数据容量也就逐渐增多，从而导致平均节点数据失效次数变大.当修复过程中需传输大量数据时，频繁的操作则会影响去中心化存储系统中的数据访问效率，造成网络资源紧缺.

数据计算：在多节点修复过程中包括不同计算步骤.对比单节点串行修复方式和多节点集中式修复方式，DSMR主要通过并行传输计算和数据交互计算来修复所有失效节点.因为在多节点失效修复中节点的数据计算存在重叠，DSMR可通过分组连接数据块与相应系数并行计算从而提高数据的计算效率.此外，DSMR修复能大幅度减少数据传输量，因为m个新替代节点共下载k个数据块即可修复，同时新替代节点间只需传输m个中间计算结果.

具体来讲，三种修复方法的存储成本和修复成本对比，如表1所示.

表1 修复方法的存储成本和修复成本对比

Table 1 Repair methods of storage and repair costs

修复方法存储成本修复成本SSRnαmkαTERSnα(k+m-1)αDSMRnαkα+m(m-1)

1)SSR：在串行星型修复中，当m个节点失效后，每个新替代节点从k个提供者节点下载k份数据块来修复，其中每个节点的数据存储量为α，每个失效块修复带宽为kα，而SSR 以串行方式逐渐修复m个失效块.因此SSR的存储开销为nα，修复m个块的总带宽开销为ΦSSR=mkα.

2)TERS：在多节点集中式修复中，所有m个失效块都在新替代节点中选取中心节点完成修复，然后由中心节点传输已修复数据块给其他新替代节点，所以中心节点与提供者节点之间的数据传输量和新替代节点之间的数据传输量都为α.因此，TERS的存储开销为nα，修复m个块的总带宽开销为ΦTERS=(k+m-1)α.

3)DSMR：在分布式多节点修复中，当m个节点失效后，m个新替代节点通过分组共连接k个提供者节点下载数据组合计算，然后节点间通过数据交互完成修复.其中提供者节点向新替代节点传输数据为α，新替代节点之间传输的数据量为m-1.因此，DSMR的存储开销为nα，修复m个块的总带宽开销为ΦDSMR=kα+m(m-1).

综上对比可知，在去中心化存储系统的RS(n，k，m)编码中，SSR、TERS和DSMR的存储开销保持不变；在多节点修复过程中，DSMR采用分组并行交互修复方法，使得总的带宽开销最小，即平均修复一个数据块所传输的数据量最小.

4.2 实验对比

实验基于NS3事件驱动模拟器，模拟一个去中心化存储系统，由一系列不同网络带宽和稳定性的节点组成.实验目标是选择在不同RS编码参数下关注DSMR与其他典型修复方法在修复时间方面的对比.由于在去中心化存储中会设置不同失效块阈值来判断是否启动修复，因此选取平均修复时间t来评判修复方法的优劣.

实验考虑一种混合计时器/阈值(T/TH)策略来模拟去中心化存储下启动修复的方式.根据以下情况触发修复操作规则：

1)当一个节点失效并且可用节点数e较小或等于TH：e≤TH→立即执行已失效块的修复.

2)当一个节点失效并且e>TH→等待时间T时，如果失效节点仍然不可用，则转向判断条件1.

对于每一组测试，条带数s分别取1，2，4，6各做一组实验，以考察条带数对测试结果的影响；失效节点数目m分别取2，4，6，8各做一组实验，以考察失效节点个数对测试结果的影响；编码系数l(k/r)分别取1，0.8，0.5，0.3各做一组实验，以考察RS编码参数对测试结果的影响.在NS3模拟器中，通过控制变量法来对比SSR、TSR和DSMR三种修复方法的平均修复时间t.

图3表示在RS(n=30,k=10,r=20)时，失效节点数m和条带数s变化的平均修复时间对比.从整体上看，在同等条带数s下，随着一个条带中失效节点数m的不断增加，DSMR的平均修复时间t也随着减少.因为在编码参数(n,k)不变的情况下，失效节点数m越多，平均分组数也就越多，使得每个新替代节点连接提供者节点数也就越少，节省带宽就越多，那么平均修复时间t也就减少.从局部上看，通过任意子图可发现，随着条带数s的增加，DSMR的平均修复时间t也随着减少.因为在条带数s较小时，修复过程中所需传输的数据总量也较少，没有充分利用多节点并行修复效率.而随着条带数s的不断增加，修复所需数据量不断增多，整体的并行效率也就提高，那么平均修复时间t就逐渐减少.而随着失效节点数m的增加、条带数s的增加，SSR的平均修复时间保持不变且最多、TERS的平均修复时间随着减少但缓慢.

图3 失效节点数m和条带数s变化的平均修复时间对比

图4表示在RS(n=30,s=4)时，失效节点数m和码率系数l变化的平均修复时间对比.从整体上看，随着编码系数l的减小，SSR、TERS和DSMR方法的修复时间t也随之减少.因为当n不变时，编码系数l变小时，意味着k就变小，那么新替代节点连接的节点数就更少，而节点之间传输数据量一样.所以随着k的减小，用以修复的数据总量也将减少，因此DSMR方法的平均修复时间t会随着编码系数l的减小而减少.从局部上看，当编码系数l相同时，随着失效节点m的增大，TERS和DSMR的平均修复时间t逐渐减小，而SSR的平均修复时间t保持不变.

综上对比可知，在任意条带数、失效节点数和码率系数的变化情况下，DSMR的平均修复时间t始终在三种修复方法中保持最少.

图4 失效节点数m和码率系数l变化的平均修复时间对比

5 总 结

针对RS码的数据修复传输方法在去中心化系统多节点修复中存在修复成本高和修复效率低的问题，本文提出一种分布式低带宽多节点修复方法DSMR.基于网络跳数选择稳定性节点以充分利用去中心化存储系统的节点可用带宽，通过均分分组连接和并行数据传输来读取节点数据，最后利用节点交互数据传输方法来修复多个失效块.理论及实验结果表明，对比典型的编码修复方法，在任意条带数、失效节点数和码率系数变化的情况下，DSMR方式保持较低存储空间地同时进一步降低修复带宽、减少修复时间.