节点www.vtigu.com

SCIENTIASINICAInformationis中国科学:信息科学2020年第50卷第12期:1834–1849c2020《中国科学》杂志社www.
scichina.
cominfocn.
scichina.
com论文一种近似最优的分布式存储系统磁盘修复算法孙婧1*,梁松涛2,路新江31.
华东政法大学互联网+法律大数据平台,上海2016202.
七牛信息技术有限公司富媒体部,上海2004333.
百度研究院商业智能实验室,北京100085*通信作者.
E-mail:jingsuncs@126.
com收稿日期:2019–01–04;修回日期:2019–04–12;接受日期:2019–08–13;网络出版日期:2020–11–20国家重点研发项目(批准号:2018YFC0830900,2018YFC0830903)资助摘要如何提升分布式存储系统中磁盘修复的速度,一直是磁盘修复问题中的难点.
优化的途径有两种:一种是通过对解码算法的优化,减少修盘数据的传输量.
另外一种方法是通过对修盘过程中数据流的调度,最大化地利用节点的计算能力、传输能力,进而加速修盘进程.
本文从数据流的调度出发,根据数据流图和拓扑结构,计算出了节点的近似最优的修盘数据比例,并依照此比例,设计了分布式存储系统下的近似最优修盘调度算法(NOPT).
对于主流的两种Reed-Solomon(RS)编码方式,本文做了等价性证明,并给出了编码转换矩阵.
通过大量实验仿真可以看出,在预知系统拓扑的前提下,可以显著地减少通过交换机的流量,进而缩短修盘的时间.
关键词Reed-Solomon码,磁盘修复技术,分布式存储系统1引言根据应用场景的不同,分布式系统分为3类:对象存储系统、块存储系统和文件存储系统.
对象存储系统常作为公有云的一部分为用户提供服务,如阿里云的OSS1)、Amazon的S32)、腾讯的COS3)和七牛的KODO4)等对象存储为海量的图片、视频提供了方便的存储和访问机制,通过一些约定的接口或规范,用户可以对数据进行读写.
对象存储一般不支持随机读写,数据都是以append方式写入.
块存储则常用在可以随机读写的场景下,例如数据库场景、网络云盘等.
甚至于,在块存储之上,也可以提供对象存储或文件存储的功能,如开源分布式系统ceph(既支持块存储,也支持对象存储).
非开源1)Aliyun:oss.
https://cn.
aliyun.
com/product/oss.
2)Amazon:s3.
https://aws.
amazon.
com/cn/s3/.
3)Tencent:cos.
https://cloud.
tencent.
com/product/cos.
4)Qiniu:kodo.
https://www.
qiniu.
com/products/kodo.
引用格式:孙婧,梁松涛,路新江.
一种近似最优的分布式存储系统磁盘修复算法.
中国科学:信息科学,2020,50:1834–1849,doi:10.
1360/N112019-00004SunJ,LiangST,LuXJ.
Anapproximatelyoptimaldiskrepairalgorithmfordistributedstoragesystems(inChinese).
SciSinInform,2020,50:1834–1849,doi:10.
1360/N112019-00004中国科学:信息科学第50卷第12期块存储系统一般都作为网络云盘使用.
在块存储的基础上,可以对接多种类型的协议,如网络文件系统(nfs,samba,ftp等).
分布式文件系统是最常用的存储系统.
因为直接实现了文件语义,所以分布文件的系统的应用场景比较广泛,其中一个,就是作为数据源,为云计算提供支撑.
常见的分布式文件系统有GoogleFileSystem[1],HadoopDistributedFileSystem[2]等.
而无论哪种类型的分布式存储系统,因为硬件故障或软件的原因导致某些数据丢失是一种必然会发生的事情.
所以保证数据可靠性是实现分布式系统重点考虑的一个问题.
常见的方法有两种,副本和纠删码.
相比副本的方式,纠删码在成本和数据可靠性上占据优势.
最常用的纠删码是RS码.
作为底层的存储技术,条带化技术是基于纠删码的存储系统必然用的一种设计方式.
而当磁盘发生故障的时候,如何使用条带化技术恢复故障下数据,则成为一个研究的热点.
当单个磁盘发生故障后,减少磁盘修复时间的方法主要分两类:一类是减少磁盘的修复带宽[37],另一类是减少修复过程中,跨交换机的数据传输量.
第一类主要通过实现新的纠删码的编解码算法,且修复过程中对同一节点数据的再编码,达到减少交换机之间的传输量[810]的目的.
Dimakis等[3]通过对修复过程中数据流的分析,使用最大流最小割原理,证明了通过网络编码的方法可以实现磁盘的最优带宽修复,提出了再生码(regeneratingcode)的概念.
我们用[n,k,d]表示一种再生码,且满足(1)n个节点中的任意k个节点都可以重构所有的数据;(2)任意一个故障节点都可以由其他d个节点完成修复.
Dimakis在文献[3]中虽然证明了磁盘修复带宽的理论边界,但并没有给出确定性构造方法.
Rashmi等[11]利用矩阵积算法构造了能够满足所有[n,k,d2k2]参数的最小带宽修复的再生码.
矩阵积算法在修复带宽上虽然达到了理论界的最优值,但在存储系统中,却因需要将一个数据块切分成指数级别的分片而难以实现.
文献[12]则通过节点分组,设计了局部重构码(localreconstructioncode,LRC).
LRC的校验节点分为两类,一类属于局部分组,一类属于全局分组.
这种设计可以显著减少磁盘修复时的带宽,并且易于在系统中实现.
该编码已经应用到了WindowsAzure存储系统中[13].
文献[14]提出了一种满足任意[n,k,r,t]参数下的LRC编码构造方法,其中r是编码的局部性,t是编码的可用性.
文献[15]则提出了一种新的基于局部重构的并发再生码,这种方法具有更高的编解码吞吐量.
以上的编码都没有考虑系统的拓扑,比如磁盘修复的时候数据如何经过交换机,影响磁盘修复的瓶颈点等问题.
交换机的带宽在修盘过程中总是稀缺的资源,流量常常称为瓶颈点,尤其是核心交换机,在修复过程中承担着比较大的压力.
若能够减少交换机之间的数据传输,则修盘的时间也将得到优化.
Shen等[16]设计的基于分段解码的CAR算法,在修复过程中,将同一个交换机内的同一条带的数据按照分段解码的理论做聚合编码,而后将编码后的数据块替代未编码前的多个数据块,通过上层的交换机进行传输,这样可以显著地减少交换机的流量.
文献[17]则设计了双再生码(doubleregeneratingcodes,DRC),将编码构造与存储系统的拓扑结合,降低磁盘修复的时间.
我们从上述的第2个角度出发,通过修盘任务的调度,减少交换机传输带宽的方式来优化修盘的时间.
本文的贡献总结如下:(1)基于三层拓扑结构,我们通过数据流的分析,给出了最优修复时间求解方法.
并且根据系统存储节点的数据量,给出了近似最优的自修复比例计算方式.
(2)我们拓展了RS分段解码算法的理论,给出了基于生成多项式和基于生成矩阵两种RS码的等价性,并且给出了具体的编码转换方法,分段解码可以减少通过交换机的数据量.
(3)基于近似最优修复比例的计算思路,我们设计了新的近似最优修盘调度算法(NOPT),通过修盘实验可以看出,NOPT可以显著地减少修盘过程中经过交换机的数据量,进而达到优化修盘时间的目的.
1835孙婧等:一种近似最优的分布式存储系统磁盘修复算法图1(网络版彩图)存储系统模型Figure1(Coloronline)Storagesystemmodel图2(网络版彩图)条带存储模型Figure2(Coloronline)Stripestoragemodel2系统模型分布式存储系统中,与用户数据存储相关的存储方式有两种:一种是中心化的(多数存储系统仍然采用中心化的方式),一种是去中心化的(如Ceph5)存储系统通过crush算法进行数据存储位置的映射).
去中心化有众多的优点,如不再需要额外的存储空间和相应的机制去记录与文件存储相关的元数据信息;IO访问的时候,不再需要与文件存储位置相关的元数据的查询;集群的规模不再受限于CPU、内存和磁盘的约束,可以无限地扩展.
去中心化并非没有坏处,尤其是一致性Hash算法在扩容时带来的局部数据的迁移问题,仍然会给系统带来较大的网络及磁盘访问的开销.
在系统整体负载比较高的时候,尤其考验系统设计的架构能力和异常处理能力.
所以如EMC,NetApp等大部分商用的存储系统仍然采用中心化的方式,记录文件的元数据信息.
本文的磁盘修复模型建立在中心化的存储系统之上.
这里先介绍与修盘流程相关的对象存储模型.
2.
1分布式存储模型不同的分布式存储系统的存储模型各不相同.
忽略掉具体的实现细节,分布式存储系统的模型可以抽象为图1.
存储系统采用3层的结构:最顶层为核心层交换机,控制着跨交换机的数据通信流.
中间层为接入层交换机,与存储系统具有某种功能的节点直连.
第3层为存储系统的计算节点、存储节点和其他节点(监控节点等).
在某些存储系统中,会将计算功能和存储功能合并为一个节点,比如ceph的OSD节点,可以作为我们系统模型的一种特例.
存储节点属于IO密集型,主要负责对磁盘进行读写操作.
而计算节点则属于CPU密集型,负责数据的迁移、修复、回收等任务的处理和RS的编解码.
其他节点比如监控节点,控制存储系统的拓扑结构、监控系统状态、控制修盘流程甚至于控制迁移流程等功能.
存储系统的设计理念不同,监控节点的功能也会不一样.
所以,我们忽略掉监控节点的细节.
2.
2基于RS码的条带存储模型RS码是一种广泛应用在存储系统的编码.
RS码的使用,对存储系统的成本、可靠性等都带来了显著的提升,已经成为了分布式存储系统中必然使用的一种技术.
当然,系统需要解决使用RS码带来的CPU开销高、系统元数据设计复杂、一致性等问题.
基于条带的存储技术同样已经成为了分布式存储系统的模板.
我们忽略元数据设计的细节,单独地抽象出条带存储的概念,如图2所示.
5)ceph.
https://ceph.
com.
1836中国科学:信息科学第50卷第12期图3(网络版彩图)故障盘修复模型Figure3(Coloronline)Brokendiskrepairmodel图2给出了以条带为单元的存储方式,数字编号一样的属于同一个条带.
如图2中的(4,2)RS码,同一个条带的各个分片存储在不同的rack中,见编号为1的数据分片.
基于RS的特性,系统可以抵抗rack级别的故障,即当nk个rack的损坏或丢失,数据不会丢失.
这里的rack是一个虚拟的概念,可以为一个磁盘、一台主机、一个机架,或是数据中心.
如何定义rack,与分布式存储系统设计的目标相关.
分片的大小根据系统架构的设计而不同,一般是KB或MB级别.
如HDFS系统默认的数据块大小为64MB.
2.
3磁盘修复模型我们所讨论的磁盘修复过程基于前面描述的存储模型.
图3给出了一个故障盘修复的数据流图.
图3采用(5,4)的编码方式,共有6个存储节点,其中节点6发生了故障.
监控节点获取坏盘信息后,解析坏盘的条带信息,并生成对应的修盘任务.
计算节点主动或者被动地与监控节点进行通信,尝试做条带级别的修复.
如图3所示,计算节点5得到了修盘的任务,而后解析条带中没有损坏的块的信息,从存储节点1,3,4,5中读取对应的数据块,通过解码,就可以计算出存储节点6中的损坏的数据块.
解码完成后,会将数据存储一个新的位置,可能是热备盘,可能存储节点6新换的盘,也可能是通过分配算法,分配的系统中某个还有空闲容量的磁盘,不同的存储系统存储的方式不尽相同.
所以我们后面的分析中,只进行到解码完成,不再考虑后继的存储问题.
2.
4符号定义如果没有特别说明,本文后面用到的符号定义如表1所示.
3设计实现3.
1原理在分布式存储系统的生产环境中,如果数据中心达到了PB甚至EB的规模,会需要更多的接入层交换连接计算节点和存储节点.
我们至顶向下地分析存储的拓扑结构,以期望得出磁盘的修复会存在什么样的性质.
1837孙婧等:一种近似最优的分布式存储系统磁盘修复算法表1符号定义Table1SymboldenitionSymbolDenitionSiThestoragenodeintThenumberofaccessswitchesntsThenumberofswitchesassociatedwithstoragenodesparticipatinginonerepairprocessntcThenumberofswitchesassociatedwithcomputationalnodesparticipatinginonerepairprocessncThenumberofcomputationalnodesncThenumberofcomputationalnodesparticipatinginonerepairprocessnsThenumberofstoragenodesparticipatinginonerepairprocessnsiThenumberofstoragenodesconnectedwithaccessswitchinciThenumberofcomputationalnodesconnectedwithaccessswitchiWTheamountofdatawaitingforrepairingdsiTheamountofdatarelatedtobrokendiskforstoragenodeiVsDiskreadrateVliDatatransmissionratefromtheaccessswitchitothecoreswitchVmiDatatransmissionratefromthecoreswitchtotheaccessswitchiVhThemaximumthroughputofthecoreswitchVtiThemaximumthroughputoftheaccessswitchi定理1(核心交换机的最小修盘时间)设D为修盘过程中经过核心交换机的数据流量.
令Vli为第i个为接入层交换机向核心层交换机的传输速率,则当第i个交换机传输的数据量Di为D∑nj=1VljVli的时候,修盘时间能够达到最小值,且时间为D∑nj=1Vlj.
证明用反证法证明.
设修盘时间t=dsi,WβVci(∑nci=1Vci)dsi,WβVci∑nci=1Vci(9)3.
2RS码的分段解码算法及等价性理论通过对修复过程中经过交换机的数据量的调度,可以优化修盘时间.
而RS码的分段解码算法同样可以减少修复过程中的数据传输量,编解码实现见CAR算法[16].
分布式系统中常用的RS码编解码的实现分两种:一种是基于生成矩阵,一种是基于生成多项式.
CAR算法采用基于生成矩阵的RS分段解码算法.
下面我们通过对生成多项式的RS码的分析,指出其无法使用分段解码的原因,并且通过等价性的证明,推导出与任一RS生成多项式等价的生成矩阵,从而可以间接地采用分段解码的算法减少修盘过程中的数据传输量.
RS码基于生成多项式的解码算法的步骤可以总结如下:(1)计算伴随式多项式(syndromespoly-nomial).
伴随式多项式可以快速地判断接收到的编码信息是否存在错误.
(2)构造错误定位多项式(errorlocatorpolynomial).
错误定位多项式用来定位哪些位置的数据出现了错误.
(3)根据错误定位多项式的根确定错误的位置.
比如,Chien[18]搜索的方法.
(4)纠错.
用Forney[19]算法纠正错误的信息,并从错误的信息位减去该值.
标准的RS解码过程中,可以不用知道错误位置及出错的个数.
通过上述步骤2对错误定位多项式的构造,并且在步骤3对错误定位多项式求解后,就可以确定错误的位置及数目.
最后,通过步骤41841孙婧等:一种近似最优的分布式存储系统磁盘修复算法的Forney算法求出出错的信息位,并且完成纠错.
而在分布式存储系统中有广泛的错误鉴别机制,能够确定错误的位置.
事实上,我们无法通过标准的解码算法在交换机层面节省带宽,理论分析如下.
设α有限域GF(pr)的本源元,RS码的传输多项式s(x)和生成多项式定义g(x)分别定义为s(x)=n1∑i=0cixi,g(x)=nk∏j=1(xαi),(10)其中传输多项式s(x)的前k项的系数为数据位,而后面的nk项为校验位.
根据生成多项式的定义,s(x)能够被g(x)整数,则可以得到s(αi)=0,其中i={1,2,nk}.
假设某些存储节点的磁盘出现坏盘,则存储的数据无法取出,我们假设该数据为0,接收多项式和错误多项式可以定义如下:r(x)=s(x)+e(x),e(x)=n1∑i=0eixi.
(11)因非出错的信息位ei=0,所以e(x)的单项式的个数为错误的个数.
如果只有一个坏盘,e(x)是单项式.
设出现错误的个数为ν,则e(x)可以简化为e(x)=ν∑k=1eikxik.
(12)通过解码,找到对应位置ik和错误eik.
因分布式存储系统中ik是已知的,所以只要解出eik即可.
如果坏盘的个数是1,则对应的码字中只有一个位置错误,是可以通过读取其他n1个位置的信息解出eik.
这个很容易证明,因α是g(x)的根,所以s(α)=0.
即αnk∑k1i=0α=∑nk1j=0bi,从这个表达式中可以直接解码出出错的信息位.
但从传输带宽的角度,需要n1个节点都输出一份数据.
这样会给带宽造成很大的压力.
而对(n,k)RS码来说,确定错误的位置后,能够纠错的最大值为nk,所以,我们可以通过标记nk个错误的码字,来降低传输的修盘带宽.
设编码中有nk个错误的码字.
如果错误码字的个数为n如果错误码字的个数超过nk,则直接返回解码失败.
定义伴随式Sj如下:Sj=r(αj)=s(αj)+e(αj)=0+e(αj)=ν∑k=1eik(αj)ik,j=1,2,nk.
(13)则只要能够解出来ν个eik,就可以修复出错的码字.
但根据Forney[19]算法,同一个交换机下的存储节点需要发送出去ν个Sik,k∈{1,2,ν},通过核心交换机传输的数据量并没有减少.
所以,我们这里可以将生成多项式的编码方法转换成基于生成矩阵的方法.
下面,我们证明基于生成多项式和生成矩阵方法的等价性.
不失一般性,我们使用g(x)=(x1)(xα)(xα1xαnk1)作为生成多项式,且定义m(x)=∑ki=0mixki1,b(x)=xnkm(x)(modg(x)),(14)则xnkm(x)=q(x)g(x)+b(x).
进而可得s(x)=xnkm(x)b(x).
(15)令b(x)=∑nk1i=0bixnki1,则s(x)=(m0,m1,mk1,b0,bnk1).
在GF(28)内,α=α,则编码后的码字为(m0,m1,mk1,b0,bnk1).
1842中国科学:信息科学第50卷第12期引理2对于g(x)任意的根β,有βnkm(β)=b(β).
证明因xnkm(x)b(x)=g(x)d(x)s(x)是生成多项式g(x)的整数倍,所以βnkm(β)=b(β).
引理3(生成多项式与生成矩阵的等价关系)对于g(x)=(x1)(xα)(xα1xαnk1)的生成多项式,设G(x)为RS码的校验位的生成矩阵,且n2k1,则G(x)=A1Λ[A|B],(16)其中A=11···11α···αnk1.
.
.
.
.
.
···.
.
.
1αnk1···α(nk1)(nk1),(17)Λ=1αnk···α(nk1)(nk),(18)B=1···1αnk···αk1α2(nk)···α2(k1).
.
.
···.
.
.
α(nk1)(nk)···α(nk1)(k1).
(19)证明根据引理2可知,m(1)=b(1),(20)αnkm(α)=b(α),(21).
.
.
α(nk)(nk1)m(αnk1)=b(αnk1),(22)即Λ[A|B][m0,m1,mk1]t=A[b0,b1,bnk1]t.
(23)然后可得该定理通过上面的引理,我们可以将基于生成多项式的解码算法转换成基于生成矩阵的算法,而后采用RS分段解码算法,间接地达到优化交换机传输带宽的目的.
1843孙婧等:一种近似最优的分布式存储系统磁盘修复算法3.
3算法实现近似最优修盘算法的实现包括3个子算法:(1)最优自修复比例的求解算法;(2)磁盘修复任务调度算法;(3)计算节点修复算法.
算法1的目的是计算出每个存储节点参与自修复的数据比例,设为αi.
算法第1行,由定理3,获取求解存储系统最优修复盘时间的函数.
算法的第29行,通过迭代的方式,获取每个存储节点最优的参与自修复的数据比例β及参与修复的计算节点的个数nc.
算法中step为迭代的步长,可以根据系统的实际情况而定.
显然,step越小,得到的(β,nc)越精确.
第1117行,根据引理1,对近似最优自修复的数据比例进行调整.
Algorithm1Theoptimalself-repairratioalgorithmInput:(k,W,Vsi,Vci,ns,nc,dsi);Output:(α1,α2,αns);1:f(β,nc)=min{(k1)Wβ∑nsi=1Vsi,kW(1β)∑nci=ns+1Vci};2:(fmin,βmin,ncmin,step)=(∞,0,0,0.
01);3:foreachnci∈[ns,nc]do4:forβv=0;βv1;βv+=stepdo5:iff(βv,nci)第2步,等待计算节点的连接,根据集群的状况动态地为计算节点分配修复任务,并且在任务完成后,及时地更新分配状态.
第2步使用了allocTask和nishTask两个函数,见算法3和4,分别实现了监控节点分配任务和完成任务的逻辑.
allocTask对任务的调度是基于对diskWeight集合的控制而完成的.
算法2的第315行,对所有条带参与修复的k个数据块进行了选择.
选择的原则是,尽可能地增加关联的diskId.
因为参与修复的磁盘越多,均衡到每个磁盘上,参与修复的数据量就越少,并发度也就越高.
第1929行,监控节点被动地等待计算节点领取修盘任务.
被动的方式有助于计算节点根据自己的负载情况按需地完成修盘任务.
修盘算法的第3个子算法是计算节点的修复算法,见算法5.
第46行,算法可以自主地选择是否采用CAR算法进行解码时传输带宽的优化,如果选择,则存储系统内需要实现基于RS的分段解码.
前面的等价性已经证明,无论采用基于生成多项式的方法,还是基于生成矩阵的方法,其本质上是等价的.
所以无论是否采用分段解码算法,我们都可以找到等价的解码实现.
第711行,计算节点完成了指定stripeId的修盘任务,并且通知监控节点,对已完成修复的任务进行处理.
1844中国科学:信息科学第50卷第12期Algorithm2Therepairtaskschedulingalgorithm1:Findallthe{stripeId}ofthebrokendiskdiskId;2:LetdiskWeightbeamapstructurethatkeyisdiskIdandvalueisrepairingblockscountofbrokendisk;3:forallstripeIdin{stripeId}do4:foreachi∈{1,n}do5:ifafteraddingtheiblockintothemapdiskWeight,thecapacityofmapismorethanbeforethen6:Chooseblockiforstriperepair;7:else8:Skipblocki;9:endif10:endfor11:ifthenumberofchooseblockssatisfykAlgorithm3allocTask(inti)1:ns=len(diskWeight);2:cs=ncns,letcsbenumberofcomputenodethatnothandleself-repairtasks;3:ifiakeyofmapdiskWeightthen4:Letαibetheratioofself-repairtaskswhichhavebeenallocbefore;5:ifαi<αithen6:returnaself-repairtaskfornodei;7:elseifαi<αi<1,andthelastalloctimeoftaskfordiskWeight[i]exceedsaparticularvaluethen8:returnaself-repairtaskfornodei;9:elseifαi<αi<1,andthelastalloctimeoftaskfordiskWeight[i]lessthanaparticularvaluethen10:returnnil;11:endif12:elseifnodeiisacomputenodeincsthen13:returnarandomrepairtask;14:else15:Setcomputenodeibeabackupnodeforrepair;16:returnnil.
17:endif1845孙婧等:一种近似最优的分布式存储系统磁盘修复算法Algorithm4nishTask(inti)1:RefreshdiskWeight,andmodifyαi;2:ifthekeyofdiskWeightisemptythen3:Reporttherepairprocesswhichhasbeennished;4:endifAlgorithm5Repairalgorithmforcomputenode1:repeat2:ifthecomputenodeacquireanon-niltaskfrommonitornodethen3:Decodetherepairtask;4:iffragmentRSdecodealgorithmisusedthen5:DecodebyCAR([16])algorithm;6:else7:Bystripeid,ndallthehostsrelativetokblocks;8:Readkblocks;9:Settheindexofbrokendiskbejinstripe,decodebyRSalgorithmwhichcodeiscreatedbygeneratematrix;10:Putthejblocktonewallocdisk(themonitorwillallocnewdisksforbrokenblocks);11:SendanishTaskrequesttomonitornode;12:endif13:else14:Thethreadsleepforawhile;15:endif16:until4实验评估实验评估的指标包括两个:(1)通过交换机的数据总量,(2)修盘时间.
实验环境共有30个host.
每个host包括4个计算节点和4个存储节点.
为了实现方便,我们将计算节点和存储节点进行合并,统称为计算节点.
每个计算节点对应一块960G的SATA盘,用作数据存储.
系统盘则采用了320G的SSD盘.
内存均为16G,CPU统一为IntelXeon,X54723.
00GHz.
系统均为Ubuntu14.
04.
存储单元数据块的大小为4MB,验证的数据量为500个条带.
实验采用3种不同参数的RS码,分别为(4,2),(6,3)和(10,4),这3种编码在分布式存储系统中使用的最为频繁.
其中(4,2)RS方案采用3个接入层交换机的拓扑结构,(6,3)RS方案采用5个接入层交换机的拓扑结构,而(10,4)RS则采用10个接入层交换机的拓扑结构.
对应的存储节点的数目分别为12,20,40个.
条带经过RS编码后的存储规则是:同一个条带组内的不同块,可以存储在同一个接入层交换机内,但不在一个存储节点上.
我们设定接入层的交换机最大带宽为10MB/s,核心层的交换机最大带宽为20MB/s.
交换机的带宽设定,通过软件层的限流算法实现.
其中,服务的通信机制是通过go-micro6)框架实现,ec库则采用golang版本的实现7).
实验通过随机洗牌的方法,将500个条带分配到各个存储节点上,而后随机地标记一个坏盘,然后对坏盘进行修复.
需要注意的是,仿真存储系统中数据的总容量为500个条带,但单个坏盘的数据量要小于这个值.
而且集群越大,单个坏盘涉及到的条带个数会越少.
为了使时间更具普遍意义,我们重复多次随机地设置坏盘,实验中的数据取其均值.
经过20次坏盘修复实验,我们得到了实验数据,见图6和7.
其6)go-micro.
https://micro.
mu.
7)go-ec.
https://github.
com/klauspost/reedsolomon.
1846中国科学:信息科学第50卷第12期图6修盘时延Figure6Repairtime图7数据流量Figure7Datathroughput中,图7统计了数据流的3个指标:自修复数据量、接入层交换机的数据量和核心层交换机的数据量.
图6中,RND算法采用的是随机分配条带的策略(这种策略在存储系统中比较常用),即计算节点根据自己的负载,主动地向监控节点请求修盘任务.
监控节点则随机地派分任务给计算节点.
从图6可以看出,相比RND算法,NOPT算法的修盘时间缩短了20.
3%35.
5%.
修盘时延减少最主要的原因,是因为在这个用例中,交换机的流量,是整体修盘过程中的瓶颈点.
减少接入层交换机和核心交换机的数据流量,就可以显著地减少修盘的时间.
图7统计了(4,2)RS的数据流量.
相比RND算法,NOPT算法在分配任务的过程中,显著地提高了自修复任务的比例,可参见自修复流量.
需要注意的是,自修复流量+接入层交换机流量=坏盘涉及条带的总修复数据量.
因为在坏盘相同的情况下,前两部分的流量和是相等的,所以,我们通过调度,能够分配多少任务进行自修复,就能够避免多少的流量流经交换机,进而加快修盘的进程.
除了分析经过交换机的传输量与修盘时间的关系外,我们对是否计算节点越多,磁盘的修复时间得到的优化就越大这个问题进行了仿真实验.
我们部署了3组验证方案,采用了一致的(6,3)RS码.
3组方案交换机的个数分别为10,20和30.
我们通过分配算法,将数据存储到10个交换机下.
测试前,根据3种不同的方案,选择不扩容、扩容10个交换机及计算节点和扩容20个交换机及计算节点.
实验数据如图8,每种方案中,统计3种算法带来的实验结果.
第1种是基于随机调度算法的修盘时间,第2种是基于最优自修复比例的求解算法(算法1),但是对计算节点的个数不加限制下的修盘时间.
第3种是基于算法1的修盘时间.
由数据可以得出:并不是参与修复的计算节点越多,修盘时间就越少.
当参与修复的计算节点个数超过最优值,将会导致更多的修盘数据流经过交换机,所以修盘时间反而更长.
5总结随着硬件存储容量不断地变大,修盘时间长的问题一直是分布式存储系统中的难题.
虽然通过纠删码的编解码构造(例如regeneratingcode)可以优化修盘的数据量,但同样存在着难以在系统中实现等问题.
本文从分布式存储系统的拓扑结构出发,通过对数据流的分析,推导出了近似最优的修盘传输量,并由此设计了近似最优的磁盘修复算法.
通过对修盘任务的调度,可以显著地减少通过交换机的修盘流量,进而减少修盘时间.
1847孙婧等:一种近似最优的分布式存储系统磁盘修复算法图8自由计算节点个数对修盘的影响Figure8Theinuenceofthenumberofcomputenodesagainstdiskrepair我们通过仿真验证了算法的有效性及优势.
后面,我们会将算法逐步地移植到生产环境下的存储系统中,例如ceph,swift等.
通过对任务的调度,减少修盘的带宽,并通过分段解码的算法,减少通过交换机的带宽.
任务调度及编解码算法的构造仍然是我们需要做进一步深入研究的重点.
参考文献1GhemawatS,GobioH,LeungST.
TheGooglelesystem.
SIGOPSOperSystRev,2003,37:29–432ShvachkoK,KuangH,RadiaS,etal.
Thehadoopdistributedlesystem.
In:ProceedingsofIEEE26thSymposiumonMassStorageSystemsandTechnologies(MSST),2010.
10:1–103DimakisAG,GodfreyPB,WuY,etal.
Networkcodingfordistributedstoragesystems.
IEEETransInformTheor,2010,56:4539–45514RashmiKV,ShahNB,GuD,etal.
A"hitchhiker's"guidetofastandecientdatareconstructioninerasure-codeddatacenters.
SIGCOMMComputCommunRev,2015,44:331–3425RashmiKV,NakkiranP,WangJ,etal.
Havingyourcakeandeatingittoo:jointlyoptimalerasurecodesforI/O,storage,andnetwork-bandwidth.
In:Proceedingsofthe13thUSENIXConferenceonFileandStorageTechnologies,2015.
81–946XuLH,BruckJ.
X-code:MDSarraycodeswithoptimalencoding.
IEEETransInformTheor,1999,45:272–2767XuS,LiR,LeePPC,etal.
SinglediskfailurerecoveryforX-code-basedparallelstoragesystems.
IEEETransComput,2014,63:995–10078ChowdhuryM,KandulaS,StoicaI.
Leveragingendpointexibilityindata-intensiveclusters.
SIGCOMMComputCommunRev,2013,43:231–2429DeanJ,GhemawatS.
MapReduce:simplieddataprocessingonlargeclusters.
CommunACM,2008,51:107–11310LiR,HuY,LeePPC.
Enablingecientandreliabletransitionfromreplicationtoerasurecodingforclusteredlesystems.
IEEETransParallelDistribSyst,2017,28:2500–251311RashmiKV,ShahNB,KumarPV.
Optimalexact-regeneratingcodesfordistributedstorageatthemsrandmbrpointsviaaproduct-matrixconstruction.
IEEETransInformTheor,2011,57:5227–523912HuangC,SimitciH,XuY,etal.
Erasurecodinginwindowsazurestorage.
In:ProceedingsofPresentedasPartofthe2012USENIXAnnualTechnicalConference,2012.
15–2613CalderB,WangJ,OgusA,etal.
Windowsazurestorage:ahighlyavailablecloudstorageservicewithstrongconsistency.
In:Proceedingsofthe23rdACMSymposiumonOperatingSystemsPrinciples.
NewYork:ACM,2011.
1848中国科学:信息科学第50卷第12期143–15714ZhangY,KanH.
Locallyrepairablecodeswithstrictavailabilityfromlinearfunctions.
SciChinaInfSci,2018,61:10930415XuQQ,XiWY,YongKL,etal.
CRL:ecientconcurrentregenerationcodeswithlocalreconstructioningeo-distributedstoragesystems.
JComputSciTechnol,2018,33:1140–115116ShenZ,ShuJ,LeePPC.
Reconsideringsinglefailurerecoveryinclusteredlesystems.
In:Proceedingsofthe46thAnnualIEEE/IFIPInternationalConferenceonDependableSystemsandNetworks(DSN).
NewYork:IEEE,2016.
323–33417HuY,LiX,ZhangM,etal.
Optimalrepairlayeringforerasure-codeddatacenters.
ACMTransStorage,2017,13:1–2418ChienR.
CyclicdecodingproceduresforBose-Chaudhuri-Hocquenghemcodes.
IEEETransInformTheor,1964,10:357–36319ForneyG.
OndecodingBCHcodes.
IEEETransInformTheor,1965,11:549–557AnapproximatelyoptimaldiskrepairalgorithmfordistributedstoragesystemsJingSUN1*,SongtaoLIANG2&XinjiangLU31.
InternetPlusLawBigDataPlatform,EastChinaUniversityofPoliticalScienceandLaw,Shanghai201620,China;2.
RichMediaDept.
,QiniuInformationTechnologyCo.
,Ltd,Shanghai200433,China;3.
TheBusinessIntelligenceLab,BaiduResearchCenter,Beijing100085,China*Correspondingauthor.
E-mail:jingsuncs@126.
comAbstractEectivelyreducingdiskrepairtimefordistributedstoragesystemsisanopenproblem.
Generally,therearetwodirections,i.
e.
,constructingbettererasurecodestoreducediskrepairthroughput,anddispatchingrepairtaskstoreducethedataowinswitches.
Inthispaper,byanalyzingtherepairdataow,weprovideanapproximatelyoptimaldiskrepairtime.
WealsoprovethebestratioofstoragenodesforrepairingandpresenttheNOPTrepairalgorithm.
Wealsoprovetheequivalenceofthetwodecodingalgorithms.
Theresultsofsimulationexperimentsdemonstratethattherepairtimeisimprovedsignicantlyandrepairtracisreducednotably.
KeywordsReed-Solomoncode,diskrepairalgorithm,distributedstoragesystemsSunJINGwasbornin1985.
Shere-ceivedherPh.
D.
degreeincomputersciencefromFudanUniversityin2015andperformedpostdoctoralstudiesinsoftwareengineeringatFudanUniver-sity.
SheiscurrentlyalecturerattheEastChinaUniversityofPoliticalSci-enceandLaw.
Herresearchincludesdatamining,distributedstoragesys-tems,machinelearning,andbigdata.
SongtaoLIANGwasbornin1985.
HereceivedhisPh.
D.
degreeincom-putersciencefromFudanUniversityin2015.
HehaspreviouslyworkedatHuaweiTechnologiesCo.
Ltdandiscurrentlyworkingonobjectstoragede-signatQiniuTechnologies.
Hiscurrentresearchincludeserasurecoding,dis-tributedstoragesystems,andmachinelearning.
XinjiangLUwasbornin1984.
HereceivedhisPh.
D.
degreefromNorth-westernPolytechnicalUniversity,Xi'an,Chinain2018.
Heiscurrentlyare-searcheratBaidu.
Hisresearchinter-estsincludemobileintelligence,urbancomputing,anddatamining.
1849