节点卡巴斯基授权文件

异构部分重复码的构造①孙伟,沈克勤,张鑫楠,何亚锦(长安大学信息工程学院,西安710064)通讯作者:孙伟,E-mail:1277874948@qq.
com摘要:针对分布式存储系统部分重复(FractionalRepetition,FR)码大都是同构的问题,提出了基于Hadamard矩阵和基于[7,3,4]简单图形构造异构的FR码的两种新型构造设计算法,构造方法更加简洁.
其中基于Hadamard矩阵构造存储容量异构的FR码可实现由同构经过简单变换为异构的编码方式;基于[7,3,4]简单图形构造可扩展异构FR码可实现扩展延伸.
经过与RS码理论分析对比发现,设计的两种异构FR码的修复局部性、修复带宽开销进一步降低,且可以实现故障节点精确无编码修复,修复复杂度较低,修复效率较高,减少了修复故障节点的时间.
关键词:分布式存储;部分重复码;节点修复;Hadamard矩阵;异构引用格式:孙伟,沈克勤,张鑫楠,何亚锦.
异构部分重复码的构造.
计算机系统应用,2021,30(2):226–230.
http://www.
c-s-a.
org.
cn/1003-3254/7793.
htmlConstructionofHeterogeneousFractionalRepetitionCodesSUNWei,SHENKe-Qin,ZHANGXin-Nan,HEYa-Jin(SchoolofInformationEngineering,Chang'anUniversity,Xi'an710064,China)Abstract:AimingattheproblemthatFractionalRepetition(FR)codesindistributedstoragesystemaremostlyhomogeneous,twonewsimpleralgorithmsareproposedtoconstructanddesignheterogeneousFRcodeswithdifferentstoragecapacitybasedonHadamardmatrixandbasedonsimplegraphics.
HeterogeneousFRcodeswithdifferentstoragecapacitycanbeconvertedfromhomogeneoustoheterogeneousbasedonHadamardmatrix.
ExtensibleheterogeneousFRcodebasedonsimplegraphicscanbeextended.
ItcanbefoundthroughthecomparisonwiththeoreticalanalysisofRScodesthatthedesignedheterogeneousFRcodeshavelowerrepairlocality,repairbandwidthoverhead,andrepaircomplexity.
Andthismethodcanrealizeaccurateandnon-codingrepairoffaultnodesathighrepairefficiency,reducingtherepairtimeoffaultnodes.
Keywords:distributedstorage;FractionalRepetition(FR)codes;noderepair;Hadamardmatrix;heterogeneous近些年,随着信息技术和大数据产业的发展,数据量激增,传统集中存储设备已无法满足海量数据存储要求.
分布式存储系统(DSS)应运而生,DDS是由许多廉价磁盘组成,具有成本低、可用性强和可扩展性高等突出优势.
它作为可存储大量数据的存储系统已经被许多互联网企业应用,例如Microsoft和Facebook[1,2].
然而分布式存储系统的节点易发生故障而造成数据丢失,所以故障节点的修复成为研究的重点.
主要通过复制和编码来保证数据的可靠性.
传统的DSS多采用复制(replication)策略[3],其中三副本最为常见.
将文件复制2次即得到3个副本,分别将其存储到系统的不同节点.
当有节点发生故障导致数据丢失,可以通过其他正常节点的副本进行修复.
但是其占有的存储系统开销过于庞大.
于是Dimakis提出了纠删码(erasurecodes)策略[4].
与复制策略相比,经典的纠删码具有更大的数据可靠性和较小的存储开销.
其中计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:csa@iscas.
ac.
cnComputerSystems&Applications,2021,30(2):226230[doi:10.
15888/j.
cnki.
csa.
007793]http://www.
c-s-a.
org.
cn中国科学院软件研究所版权所有.
Tel:+86-10-62661041①基金项目:陕西省自然科学基金(2019JM-386)Foundationitem:NaturalScienceFoundationofShaanxiProvince(2019JM-386)收稿时间:2020-06-30;修改时间:2020-07-27;采用时间:2020-07-31;csa在线出版时间:2021-01-27226软件技术算法SoftwareTechniqueAlgorithm最大距离可分(MaximumDistanceSeparable,MDS)码获得最优的存储开销性能.
但是纠删码修复故障节点时需要的修复带宽开销过大.
由于上述缺陷,Dimakis等[4]开创性的提出并介绍了再生码,研究发现在故障节点修复时其的修复带宽开销明显降低.
但是再生码修复故障节点时需要大量有限域的运算,计算复杂度大.
2010年Rouayheb提出了部分重复(FractionalRepetition,FR)码,FR码是一种精确最小带宽再生码,修复故障节点时的修复带宽减小,同时不需要大量有限域的运算,计算复杂度较小[5,6].
所以越来越多研究人员开始研究FR码,Ramamoorthy设计的FR码引入了组合设计的思想[7].
相继利用二部图[8],Steiner系[9]和序列[10]构造FR码.
随后研究人员又研究了FR码的修复消耗最小化[11].
部分重复码的现有编码方式节点的存储容量基本相同,同时重复度也基本相同,都属于同构编码方式,但是分布式存储系统由于设备故障,硬件差别等原因,导致存储成本不同,各个节点存储容量不同,因此需要异构编码方式.
本文提出基于Hadamard矩阵和图形分别构造异构的部分重复码的一般算法.
与现有的FR码相比,采用Hadamard矩阵和图形构造FR码更加简洁明了,其中基于Hadamard矩阵可实现由同构经过简单变换为异构编码方式;基于图形构造FR码可实现扩展延伸,若当前结构无法满足需求,可对其进行扩展,直至满足需求,而且无需改变现有结构.
经过与RS码理论分析对比发现,设计的两种异构FR码的修复局部性、修复带宽开销进一步降低,且可以实现故障节点精确无编码修复,修复复杂度较低,修复效率较高,减少了修复故障节点的时间.
1基础知识1.
1Hadamard矩阵定义1[12].
满足:;是一个n阶方阵其由1或1构成,是一个n阶单位矩阵,称为n阶Hadamard矩阵.
Hadamard矩阵具有如下性质:(1)将Hadamard矩阵的任意两行(列)交换,矩阵的任意一行(列)的所有元素乘1,得到的矩阵仍然是Hadamard矩阵.
(2)若是阶Hadamard矩阵,需要满足n是4的倍数.
本文所需的Hadamard矩阵均为标准型,即的第1行和第1列全是1.
1.
2部分重复码定义2[13].
FR码.
给定一个部分重复码,其中参数为,将重复度设为(即编码数据块复制倍),特定地,为个子集的集合,中的每一个元素都属于集合.
另外还需满足以下两个条件:1)每个子集的大小为;2)中每一个元素分别存在于的个子集中.
如果d和分别都为固定值则为同构FR码,如果d不是固定的值则为存储容量异构的FR码;如果不是固定的值则为重复度异构的FR码.
FR码的本质为将经过MDS编码后的数据块复制倍,随后将其分别放置在个不同节点中,其中同一个的编码数据块不能出现在一个节点中.
2基于Hadamard矩阵构造异构部分重复码本节基于Hadamard矩阵构造存储容量不同的异构部分重复码.
首先选一个阶的Hadamard矩阵,再将此Hadamard矩阵进行简单变换即可得到所需矩阵.
将编码数据块与矩阵进行类比联系,分布式存储系统中的节点对应矩阵的行,而不同的编码块对应于矩阵的列.
根据Hadamard矩阵,引出存储容量不同的异构FR码一般性构造算法,其具体步骤如下:步骤1.
首先采用MDS编码()对原始文件进行编码,得到n个编码数据块,其中包括k个原始数据块和个校验数据块[6];步骤2.
取一个阶标准型Hadamard矩阵(n+1为4的倍数),由式(1)对进行简单变换:矩阵中元素全为1,为标准Hadamard矩阵,得到的是一个0-1矩阵,将的第一行和第一列同时删去得到所需矩阵;步骤3.
将矩阵中第j列出现的第个1改为0得到新的矩阵,然后计算式(1):其中,,i表示第i个FR节点,表示矩阵第i行第j列的值.
其中表示异构FR码的存储节点,将2021年第30卷第2期http://www.
c-s-a.
org.
cn计算机系统应用SoftwareTechniqueAlgorithm软件技术算法227矩阵中第i行中全部的1所分别对应的列数提取出来,即可得到一个节点存储的数据块,得到节点存储容量不同的异构FR码.
具体的,选取一个12阶的Hadamard矩阵如图1所示,对其按步骤2操作得到11阶矩阵如图2所示,每一列的第个1改为0得到新的矩阵如图3所示.
随后节点对应矩阵的行,而不同的编码块对应于矩阵的列.
所以我们得到了存储容量不同的异构的FR码,每个节点的存储结构如图4所示,其节点的存储容量,编码块的重复度.
图112阶Hadamard矩阵图2K11矩阵图3K111矩阵单个节点发生故障时,可以根据存活的其他节点直接下载所需的数据,即可恢复故障节点.
例如在图4中,若第二个节点发生故障,通过下载节点恢复数据块5和11,下载恢复数据块3和7,即可完成节点的恢复;同时也可以根据节点,,分别下载数据块3,5,7,11,也可完成故障节点的恢复.
单节点发生故障可采用多种方式来恢复,同时也实现故障节点的精确无编码修复.
当两个节点发生故障时,方法同一个故障节点修复.
图4存储容量异构的FR码节点存储结构图3可扩展的异构部分重复码本小节提出一种基于简单图形构造可扩展异构部分重复码的算法,此算法可以简单对部分重复码进行扩展,如现有结构不满足已有需求需要进行扩容,则不需破坏已有的结构,只需在图形尾部直接旋转拼接图形扩展,使得FR码可扩展,具体构造步骤如下所示:步骤1.
首先采用MDS编码()对原始文件进行编码,得到个编码数据块,其中包括个原始数据块和个校验数据块[6];步骤2.
取一个简单图形,如图5所示.
图5简单代码图形步骤3.
通过简单图形构造FR码:将外围3个顶点当作存储节点,将内部的4个顶点当作数据块,数据块按照顺时针存放,临近存储节点的3个数据块存放在该存储节点.
将简单图形的外围3个顶点当作存储节点,将简单图形内部的4个顶点当作数据块,数据块按照顺时针存放,临近存储节点的3个数据块存放在该存储节点.
步骤4.
通过将简单图形旋转拼接构造可计算机系统应用http://www.
c-s-a.
org.
cn2021年第30卷第2期228软件技术算法SoftwareTechniqueAlgorithm扩展FR码:1)将扩展的简单图形的外围罗马数字代表一个节点,外围的第个点表示分布式存储系统中的第个存储节点,共有个存储节点();将与存储节点直接相连的数据块当作该存储节点存放的数据块,即可得到存储容量和重复度异构的FR码.
2)当数据块时,需要个简单图形旋转拼接,构造出具有个存储节点,个数据块的FR码.
当数据块时,需要个简单图形旋转拼接,构造出具有个存储节点,个数据块的FR码.
若构造一个具有6个存储节点,13个数据块的FR码.
可将基本图形翻转拼接3次,得到如图6所示图形,按上述方法可得到6个存储节点所存放的数据块,如图7所示,若当前结构无法满足需求,可对其进行扩展,直至满足需求,而且无需改变现有结构,如图8所示.
图6图形结构图7FR码节点存储结构图图8扩展图形结构可以看出共有6个存储节点.
存储节点N1和N5的存储容量是5,存储节点N3和N4的存储容量是7,并且重复度为2或3的一个异构的FR码.
当单个节点发生故障时,如图7中,当第二个节点发生故障时,通过下载节点恢复数据块1和4,下载恢复数据块2,来完成节点的恢复;当节点发生故障时,通过下载节点恢复数据块3,4和7,下载恢复数据块2,下载恢复数据块6和10,下载恢复数据块8,即可完成节点的恢复.
具体修复方式可选择性较大,同时实现故障节点的精确无编码修复.
4性能分析本小节对基于Hadamard矩阵构造存储容量异构的部分重复码和基于简单图形构造可扩展的异构部分重复码进行性能分析,主要考虑修复带宽开销和修复局部性方面的性能,并与常见的RS编码进行性能比较.
为了便于比较,基于Hadamard矩阵构造存储容量异构的部分重复码算法选取FR码,基于简单图形构造可扩展异构部分重复码的算法选取FR码,取.
4.
1修复带宽开销修复带宽开销指的是恢复失效节点时下载的数据量大小.
例如采用RS编码,由于RS编码恢复故障节点需要下载全部原文件,所以修复带宽开销为;采用基于Hadamard矩阵构造存储容量不同的异构部分重复码构造FR码时,发生节点故障时的修复带宽开销为或者.
为便于比较,本文选取中间值作为代表值.
在采用基于简单图形构造可扩展异构部分重复码的算法构造FR码时,发生节点故障的修复带宽开销为或者,而采用RS编码时,发生节点故障的修复带宽开销为.
由于图形特殊构造,随着节点增多修复带宽开销基本都是,所以选取其为代表值.
以上2项数据与RS码仿真对比如图9所示.
经过对比不难发现本文提出的两种异构部分重复码构造的算法,节点发生故障时修复带宽开销比RS编码明显降低.
当节点数少于16时,基于Hadamard矩阵构造的异构FR码修复带宽开销小于基于简单图形构造异构FR码.
但是当节点数逐渐增大,基于简单图形构造异构FR码的修复带宽开销小于基于Hadamard矩阵构造的异构FR码.
4.
2修复局部性发生节点故障时需要连接的存活节点数目称为修复局部性.
当发生单节点故障时,RS编码需要2021年第30卷第2期http://www.
c-s-a.
org.
cn计算机系统应用SoftwareTechniqueAlgorithm软件技术算法229连接9个节点恢复原文件用以修复故障节点,修复局部性为9;而基于Hadamard矩阵构造存储容量异构的FR码构造的FR码,单节点故障时需要连接2个或者3个节点来修复,故修复局部性为2或者3.
图9修复带宽开销对比采用基于简单图形构造可扩展异构部分重复码的算法构造FR码时,发生节点故障时需要连接2,3或者4个节点来恢复故障节点,所以修复局部性为2,3或4;而RS码发生单节点故障时,RS码修复局部性为9.
分析发现修复单个故障节点时,基于Hadamard矩阵构造存储容量异构的FR码和基于简单图形构造可扩展异构FR码的修复局部性,优于RS编码的修复局部性.
但是简单图形构造的异构FR码无法修复多节点故障,是下一步研究的方向.
5结论本文提出基于Hadamard矩阵和图形分别构造异构的部分重复码的一般算法.
与现有的FR码相比,采用Hadamard矩阵和图形构造FR码更加简洁明了,其中基于Hadamard矩阵可实现由同构经过简单变换为异构编码方式;基于图形构造FR码可实现扩展延升,若当前结构无法满足需求,可对其进行扩展,直至满足需求,且无需改变现有结构.
经过与RS码理论分析对比发现,设计的两种异构FR码的修复局部性、修复带宽开销进一步降低,性能进一步提高.
参考文献HuangC,SimitciH,XuYK,etal.
Erasurecodinginwindowsazurestorage.
Proceedingsofthe2012USENIXConferenceonAnnualTechnicalConference.
Berkeley,CA,1USA.
2012.
2.
RashmiKV,ShahNB,GuDK,etal.
A"hitchhiker's"guidetofastandefficientdatareconstructioninerasure-codeddatacenters.
Proceedingsofthe2014ACMConferenceonSIGCOMM.
Chicago,IL,USA.
2014.
331–342.
2LiuY,VlassovV.
Replicationindistributedstoragesystems:Stateoftheart,possibledirections,andopenissues.
2013InternationalConferenceonCyber-EnabledDistributedComputingandKnowledgeDiscovery.
Beijing,China.
2013.
225–232.
3DimakisAG,GodfreyPB,WuYN.
Networkcodingfordistributedstoragesystems.
IEEETransactionsonInformationTheory,2010,56(9):4539–4551.
[doi:10.
1109/TIT.
2010.
2054295]4RouayhebSE,RamchandranK.
Fractionalrepetitioncodesforrepairindistributedstoragesystems.
Proceedingsofthe48thAnnualAllertonConferenceonCommunication,Control,andComputing.
Monticello,IL,USA.
2010.
1510–1517.
5王甜甜.
分布式存储系统中部分重复码构造研究[硕士学位论文].
西安:长安大学,2019.
6OlmezO,RamamoorthyA.
Repairablereplication-basedstoragesystemsusingresolvabledesigns.
Proceedingsof201250thAnnualAllertonConferenceonCommunication,Control,andComputing.
Monticello,IL,USA.
2012.
1174–1181.
7KooJC,GillJT.
Scalableconstructionsoffractionalrepetitioncodesindistributedstoragesystems.
201149thAnnualAllertonConferenceonCommunication,Control,andComputing(Allerton).
Monticello,IL,USA.
2011.
1366–1373.
8OlmezO,RamamoorthyA.
Fractionalrepetitioncodeswithflexiblerepairfromcombinatorialdesigns.
IEEETransactionsonInformationTheory,2016,62(4):1565–1591.
[doi:10.
1109/TIT.
2016.
2531720]9BenerjeeKG,GuptaMK.
Ondresscodeswithflowers.
2015SeventhInternationalWorkshoponSignalDesignanditsApplicationsinCommunications(IWSDA).
Bengaluru,India.
2015.
108–112.
10ItaniM,SharafeddineS,ElkabbaniI.
Practicalsinglenodefailurerecoveryusingfractionalrepetitioncodesindatacenters.
2016IEEE30thInternationalConferenceonAdvancedInformationNetworkingandApplications(AINA).
Crans-Montana,Switzerland.
2016.
762–768.
11BanicaT,NechitaI.
Almosthadamardmatrices:Thecaseofarbitraryexponents.
DiscreteAppliedMathematics,2013,161(16–17):2367–2379.
12SuYS.
Pliablefractionalrepetitioncodesfordistributedstoragesystems:Designandanalysis.
IEEETransactionsonCommunications,2018,66(6):2359–2375.
[doi:10.
1109/TCOMM.
2018.
2799213]13计算机系统应用http://www.
c-s-a.
org.
cn2021年第30卷第2期230软件技术算法SoftwareTechniqueAlgorithm