图因子分解的故障节点快速修复_余春雷.pdf

图因子分解的故障节点快速修复余春雷1,3,王娥2,刘星1,谢锐1,冉彪11(四川文理学院智能制造学院,达州635002)2(长安大学信息工程学院,西安710064)3(智能制造产业技术研究院,达州635002)通信作者:余春雷,E-mail:摘要:为了提高分布式存储系统中故障节点的修复效率,提出一种新的部分重复(fractionalrepetition,FR)码的构造算法.该算法利用完全图的因子分解进行构造,称为 CGFBFR(completegraphfactorizationbasedFR)码.该算法首先对完全图进行因子分解,分解完成以后确定完全图的因子分解个数,根据需要存储数据块的重复度来选择完全图的因子个数,将完全图选中的因子所有顶点当做分布式存储系统中需要存储的数据块,然后对选中因子图的边进行标记,标记的边当做分布式数据节点进行存储.最后根据选中的因子的顶点和边生成编码矩阵,在分布式存储系统中按照编码矩阵中的数据对数据块分别进行存储.实验仿真结果显示,本文提出的一种新的部分重复码构造算法,与分布式存储系统中的里所(reed-solomon,RS)码、简单再生码(simpleregeneratingcodes,SRC)以及最新的循环可变部分重复(variablefractionalrepetition,VFR)码相比,在系统修复故障节点时,能够快速地修复故障节点,有效降低了故障节点的修复带宽开销、修复局部性、修复复杂度,而且构造过程简单,同时可以灵活选择构造参数,广泛适用于分布式存储系统中.关键词:图因子分解;完全图;存储节点;修复;部分重复码;故障诊断引用格式:余春雷,王娥,刘星,谢锐,冉彪.图因子分解的故障节点快速修复.计算机系统应用,2023,32(2):394399.http:/www.c-s- Repair of Faulty Nodes Based on Graph FactorizationYUChun-Lei1,3,WANGE2,LIUXing1,XIERui1,RANBiao11(SchoolofIntelligentManufacturing,SichuanUniversityofArtsandScience,Dazhou635002,China)2(SchoolofInformationEngineering,ChanganUniversity,Xian710064,China)3(IntelligentManufacturingIndustryTechnologyResearchInstitute,Dazhou635002,China)Abstract:Toimprovetheefficiencyofrepairingfaultynodesinadistributedstoragesystem,thisstudyproposesanewconstructionalgorithmforfractionalrepetition(FR)codes.Thealgorithmresortstothefactorizationofthecompletegraphfornodeconstruction,andthenodesconstructedarereferredtoascompletegraphfactorizationbasedFR(CGFBFR)nodes.Specifically,thecompletegraphisfactorized,andthenumberoffactorsgeneratedfromthecompletegraphafterthefactorizationiscompletedisdetermined.Thenumberoffactorsofthecompletegraphisselectedaccordingtotherepetitiondegreesofthedatablocksthatneedtobestored.Alltheverticesoftheselectedfactorsofthecompletegraphareregardedasthedatablocksthatneedtobestoredinthedistributedstoragesystem.Then,theedgesoftheselectedfactorgrapharemarkedandstoredasdistributeddatanodes.Finally,anencodingmatrixisgeneratedwiththeverticesandedgesoftheselectedfactors,andthedistributedstoragesystemstoresthedatablocksrespectivelyaccordingtothedataintheencodingmatrix.TheexperimentalsimulationresultsshowthatcomparedwiththeReed-Solomon(RS)codes,thesimpleregeneratingcodes(SRCs),andthelatestcyclicvariableFR(VFR)codesinthe计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(2):394399doi:10.15888/ki.csa.008969http:/www.c-s-中国科学院软件研究所版权所有.Tel:[phone]基金项目:陕西省重点研发计划(2021GY-019),智能制造产业技术研究院开放基金(ZNZZ2106)收稿时间:2022-06-15;修改时间:2022-09-07;采用时间:2022-09-14;csa 在线出版时间:2022-11-04CNKI 网络首发时间:2022-11-16394研究开发ResearchandDevelopmentdistributedstoragesystem,thecodesgeneratedbythenewFRcodeconstructionalgorithmproposedinthisstudycanquicklyrepairthefaultynodewhenthesystemrepairsthenode.Theproposedalgorithmcanbewidelyappliedtodistributedstoragesystemsasitreducestherepairbandwidthoverhead,repairlocality,andrepaircomplexityofthefaultynode,providesasimpleconstructionprocess,andallowsflexibleselectionofconstructionparameters.Key words:graphfactorization;completegraph;storagenode;repair;fractionalrepetition(FR)codes;faultdiagnosisn如今的社会是一个互联网高速发展的社会,大量互联网公司和政府部门每天运营中产生海量的数据1,数据的价值和重要性不言而喻,因此如何维护数据的可靠性和稳定性2,3是急需要解决的关键技术.现有的集中式存储主要靠数据服务器和存储设备4.但是集中式存储,设备价格昂贵,而且需要大量的管理时间以及维护成本5.集中式存储一旦遭到破坏,数据将永久毁灭.相较于集中式存储,具有可扩展、设备成本低、高性能、易用性的分布式存储系统成为目前主流存储系统6.分布式存储对数据的存储采用的策略是复制策略和纠删码策略7,8.复制策略就是把需要存储的原始文件复制 份,然后对复制的所有数据进行存储,通过复制的副本数据来保障数据的可靠性,当出现数据损坏,可以直接复制副本数据快速修复,整个过程简单易实施,但复制策略的缺陷是存储开销大9.与复制策略相比,纠删码策略只需要存储少量的编码数据块.使系统的存储开销得到有效地降低,同时纠删码策略通过编码产生的校验数据块,使系统具有更好的容错性.但在分布式存储系统中通过纠删码对故障节点进行修复时,系统需要消耗较大的修复带宽开销10.目前里所(reed-solomon,RS)码和磁盘阵列码11等典型的纠删码被广泛应用于分布式存储系统中.如图 1 所示为RS 编码和重构原理过程.当其中任意一个数据块发生故障,都可以通过解码恢复出故障数据块.针对复制策略和纠删码策略等局限性12,13,研究者通过研究发现在存储开销跟修复带宽开销之间折中,提出简单再生码(simpleregeneratingcodes,SRC)的编码方式14.简单再生码是通过大量的有限域运算编码构造15.不需要消耗大量的存储开销,并且在修复故障节点时,只需要连接相应节点就可以修复数据,修复带宽开销较低.但修复过程需大量解码运算,使得修复过程非常复杂,修复时间增多,而且还需要连接多个节点进行修复,因此修复局部性高16.部分重复(fractionalrepetition,FR)码17无需进行有限域运算,同时也可以降低节点存储开销18.在对故障节点修复时,具有较低的修复局部性和修复带宽开销19,20.因此,部分重复码被广泛研究.目前主流的 FR码构造方法有如下几种:基于正则图、分组设计21及可分解设计22,但构造过程复杂,且不能灵活选择部分重复码的构造参数,不适应实际的存储系统23,24.因此提出基于完全图图因子分解的部分重复(completegraphfactorizationbasedFR,CGFBFR)码的构造算法.B13B14B15B12B11B23B24B25B22B21B33B34B35B32B310010001000100000001000001D3D4D5D2D1C3C2C1D3D4D5D2D1CDnBD=D3D4D5D2D1D=000100000110000C3C1D3D5D2Survivorsm+nB1图 1RS 编码和重构原理1图的因子分解GG=(V,E)HGV(H)V(G)E(H)E(G)H GHGnKnGG图的因子分解是图分解的一种方法,记图 表示为,图 为图 的子图,满足且,记为.若 V(H)=V(G),图是图 的生成子图.对于 阶完全图记为,图 的阶就是图 所有的顶2023年第32卷第2期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发395点个数.GF1,F2,FnV(Fi)=V(G)Gni=1E(Fi)=E(G)E(Fi)E(Fj)=(i j)Fi(i=1,2,n)GGmGm如果图,可以分解成生成子图,且,图 分解的每个生成子图满足,称这些生成子图为 的因子,称为图 的因子分解.若每个分解出来的因子都是 正则图时,则称图 是可 因子分解的.2部分重复码的构造(n,k,d)nd kk n在分布式存储系统(distributedstoragesystem,DSS)中,其中 表示存储节点个数,即分布式系统中存储数据的节点.是修复故障节点时连接的节点个数,表示恢复出原文件需要节点个数.(n,k,d)(n,d,)nN=N1,Nnn=1,2,(n,d,)定义 1.在系统中25,部分重复码可以由 个子集的集合表示,是数据块的重复度,每个子集中的符号均属于符号集.该部分重复码的构造过程满足如下条件.d|Ni|=d(1 i n)(1)每个节点存储 个数据块,即.nN(2)中的每个元素都出现于中 个不同的子集.(n,d,)=ndmn在FR 码的构造过程中,其中参数满足,首先对原文件进行分割为 个数据块,如图 2 所示,分别为数据块m0到m8,其次通过最大距离可分(maximumdistanceseparable,MDS)码对 m0到 m8进行编码,产生 m0到 m8、P9等编码数据块,P9为校验块数据块,保护数据的可靠性.然后采用复制策略,对 m0到 m8、P9等编码数据块复制 份,最后通过部分重复码的内部构造算法把所有的数据块存储在 个节点里.MDSCodeN1m1m2m3m0N4m5m7p9m2N3m4m7m8m1N2m4m5m6m0N5m6m8p9m3(m0,m8)(m0,m8,m9)图 2部分重复码构造过程3基于图因子分解的部分重复码的构造本文提出一种新的部分重复码的构造算法,通过完全图的因子分解进行构造,构造过程简单,同时也解决了传统 FR 码存在的不足.具体构造步骤如下.K2kG步骤 1.对完全图的图 做可 1 因子分解,得到F1,F2,FlGvi(1 i n)di(1 i n)l,图 中的每个顶点视为分布式存储系统中需要存储的数据块,其中 满足公式如下:l=(2n)!2nn!(1)di(1 i n)(1 l)GF(1 l)(l)步骤 2.确定分布式存储系统中 FR 码构造过程每个数据块的重复度.因为图 的所有顶点都包含于每个因子之中,因此可以构造种重复度为 的 FR 码.F1,F2,Fle(1 n)步骤 3.在分解的所有因子中,根据数据块的重复度,选择任意 个因子的边分别编号为.m,i(1 n,1 i n)m,iN(1 n)m,idi(1 i 2n)m,i步骤 4.构造数据矩阵,通过数据矩阵对部分重复码进行构造,的横坐标代表部分重复码的存储节点,在数据矩阵中,对矩阵中相应数字为 1 的编码数据块进行存储,其中数据矩阵构造公式如下:m,i=1,若vi与e相关联0,其他情况(2)K6(1 15)=3F1,F2,F15F1,F2,F3F1,F2,F3e(1 9)具体地,可以对进行因子分解,然后构造一个重复度为的 FR 码.如果取重复度,因此可以在所有因子中任选 3 个进行构造数据矩阵,这里我们在 15 个因子中选取,然后对选中因子的边进行依次编号为,如图 3 所示.v5v1v6v1v6v2v1v6e5v3v2v4v3v2v4v5v3v4v5e1e2e3e4e6e7e8e9F1F3F2K6图 3的部分因子分解m1通过图 2,我们可根据式(2)求出数据矩阵如下:m1=100010010001001100010010100100001001000101001010110000计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第2期396研究开发ResearchandDevelopmentN(1 9)m1di(1 i 6)K6=3(153)基于完全图因子分解的部分重复码如图 4 所示,部分重复码的存储节点为数据矩阵的横坐标,对标记为 1 数据块进行存储.利用的可 1 因子分解,重复度的 FR 码的构造方法总共有种.因此,CGFBFR 码具有灵活的参数选择性,而且有多种构造方法.d2d5d1d4d3d6d1d5d2d6d3d4d4d6d3d5d1d2N1N3N2N4N5N6N7N8N9K6图 4基于因子分解的 CGFBFR 码4性能分析K2k对基于完全图可 1 因子分解构造的 CGFBFR码与目前分布式系统主要研究的 RS 码、SRC 以及最新的循环可变部分重复(variablefractionalrepetition,VFR)码性能进行分析.M=2000 Mb tf=3(k+3,k)表 1 给出了 SRC、RS 码、三副本、以及 VFR 码与 CGFBFR 码几种编码方案性能的分析.为了便于比较,文件大小取,为单位时间内寻址时间,SRC 的子文件数,且 CGFBFR 码外部编码采用码.表 1编码方案的性能分析编码方案(n,k,f)SRC(n,k)RSCGFBFR三副本VFR存储开销(f+1)M/kM/k2M/kM3M/k修复复杂度(f 1)(f+1)k2+k000寻址时间(f 1)(f+1)tM(k2+k)tMtMtMtM 4.1 修复带宽开销(n,k,f)f+1M/fkf(n,k,f)(f+1)M/k(n,k)M3M/kM/k2M/k在修复故障节点时下载的数据量就是修复带宽开销.当单节点故障时,如表 2 所示,若采用SRC,因为 SRC 每个节点存储的数据块为,每一个数据块的大小是,修复时需要从其他数据节点下载个数据块,因此SRC 修复单节点故障的带宽开销为;RS 码修复时需要靠原文件修复故障节点,所以带宽开销为;对于 VFR 码,单节点故障时,修复带宽开销为.对于 CGFBFR 码,每个节点存放的数据块大小为 2,数据块每个的大小为,因此 CGFBFR 码修复带宽开销为.当两个节点发生故障时,如表 2 所示,(n,k)RS 编MMM2M/k4M/k码在修复数据时仍需要通过原文件来修复故障节点,因此修复带宽开销仍为.对于(n,k,f)SRC,修复带宽开销为.VFR 码的两节点故障时修复带宽开销也为.对于 CGFBFR 码,为单个存储节点存储开销,因此是两节点故障时的修复带宽开销.图 5 给出了 4 种编码方式的修复带宽开销,显而易见,CGFBFR码的修复带宽更低.表 2编码方案的性能分析编码方案(n,k,f)SRC(n,k)RS CGFBFRVFR修复带宽开销单节点故障(f+1)M/kM2M/k3M/k两节点故障MM4M/kM修复局部性单节点故障2fk22两节点故障kkmax4k3+1202224262830323436384002004006008001 0001 2001 4001 6001 8002 0002 200修复带宽开销(Mb)CGFBFRVFR原始数据块 k(n,k)RS(n,k,f)SRC图 5单节点故障的修复带宽开销对比 4.2 修复局部性2f(2f n)2f(n,k)k当分布式存储系统中出现单节点故障时,如图 6所示.对于(n,k,f)SRC 需要个节点修复故障节点,因此(n,k,f)SRC 系统中修复局部性为;对于RS 码的修复局部性是;VFR 码单节点故障故障修复局部性为 2;采用 CGFBFR 码,修复故障节点需要连接的节点数为 2,因此 CGFBFR 码修复局部性为 2.kk(n,k)k(n,k)kK/3+1图 7 给出了两节点故障时,4 种不同的编码修复局部性.对于(n,k,f)SRC,恢复原文件需要 存储节点,通过原文件对故两节点故障进行修复,因此(n,k,f)SRC修复局部性是;对于RS 码需要连接 个节点恢复原文件,然后再对两故障节点进行修复,所以RS码的修复局部性也是;VFR 码的两节点修复局部性为.对于 CGFBFR 码的修复局部性最大 4.2023年第32卷第2期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发3972022242628303234363840051015202530354045原始数据块 k修复局部性CGFBFRVFR(n,k)RS(n,k,f)SRC图 6单节点故障修复局部性2022242628303234363840051015202530354045原始数据块 k修复局部性CGFBFRVFR(n,k)RS(n,k,f)SRC图 7两节点故障修复局部性 4.3 修复复杂度k21k2+kO(2k2+k1)(f 1)(f+1)O(f21)对于 RS 码,在分布式存储系统中修复故障节点时,系统需要经过次有限域加法运算,次有限域乘法运算,因此 RS 码在修复单节点的故障时它的修复复杂度为.对于 SRC,系统需要执行次异或运算,所以 SRC 的修复复杂度为.对于 CGFBFR 码,不需要经过有限域运算和异或运算,直接通过复制数据就可以进行修复,因此CGFBFR 码相比于 RS 码和 SRC 具有较低修复复杂度,能够快速修复故障节点,降低修复时间.5结论本文提出一种 CGFBFR 码能够满足分布式存储系统的实际需求,提高了分布式存储系统中故障节点的修复效率,并且能够灵活的选择构造参数.在修复故障节点时,CGFBFR 相较于分布式存储系统中其他编码,在修复局部性、修复复杂度、修复带宽开销都有较大的性能提升.更加具有发展的前景和应用背景.参考文献SiddiqaA,KarimA,GaniA.Bigdatastoragetechnologies:Asurvey.FrontiersofInformationTechnology&ElectronicEngineering,2017,18(8):10401070.1MazumdarS,SeyboldD,KritikosK,et al.Asurveyondatastorage and placement methodologies for cloud-big dataecosystem.Journal of Big Data,2019,6(1):15.doi:10.1186/s40537-019-0178-32LvZ,LiX,LvH,et al.BIMbigdatastorageinWebVRGIS.IEEE Transactions on Industrial Informatics,2019,16(4):25662573.3LiRN,SongTY,MeiB,et al.Blockchainforlarge-scaleInternet of Things data storage and protection.IEEETransactionsonServicesComputing,2019,12(5):762771.doi:10.1109/TSC.2018.28531674Yang Y,Zheng XH,Guo WZ,et al.Privacy-preservingsmartIoT-basedhealthcarebigdatastorageandself-adaptiveaccess control system.Information Sciences,2019,479:567592.doi:10.1016/j.ins.2018.02.0055Liang W,Fan YK,Li KC,et al.Secure data storage andrecovery in industrial blockchain network environments.IEEETransactionsonIndustrialInformatics,2020,16(10):65436552.doi:10.1109/TII.2020.29660696Lee OT,Akash GJ,Kumar SDM,et al.Storage nodeallocation methods for erasure code-based cloud storagesystems.ArabianJournalforScienceandEngineering,2019,44(11):91279142.doi:10.1007/s13369-019-03983-87KnauftE,GogginEJ,LiRC,et al.Automaticallyremovingdependencyonslowdisksinadistributedstoragesystem:US,10168942.2019-01-01.8余春雷,王静,王秘,等.图因子分解的部分重复码构造.中国科技论文,2019,14(11):12601264.9VaishampayanVA.Latticeerasurecodesoflowrankwithnoisemargins.Proceedingsofthe2018IEEEInternationalSymposiumonInformationTheory(ISIT).Vail:IEEE,2018.961965.10BalajiSB,KrishnanMN,VajhaM,et al.Erasurecodingfordistributedstorage:Anoverview.ScienceChinaInformationSciences,2018,61(10):100301.doi:10.1007/s11432-018-9482-611余春雷,王静,杨成福,等.哈夫曼树的异构部分重复码构造.北京邮电大学学报,2021,44(6):116121.12Papailiopoulos DS,Dimakis AG,Cadambe VR.Repairoptimal erasure codes through hadamard designs.IEEETransactionsonInformationTheory,2013,59(5):30213037.doi:10.1109/TIT.2013.224181913计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第2期398研究开发ResearchandDevelopmentGoparaju S,Fazeli A,Vardy A.Minimum storageregeneratingcodesforallparameters.IEEETransactionsonInformationTheory,2017,63(10):63186328.doi:10.1109/TIT.2017.269066214Kralevska K,Gligoroski D,Jensen RE,et al.HashTagerasurecodes:Fromtheorytopractice.IEEETransactionsonBigData,2018,4(4):516529.doi:10.1109/TBDATA.2017.274925515朱兵,李挥,陈俊,等.基于可分组设计的部分重复码研究.通信学报,2015,36(2):98105.doi:10.11959/j.issn.1000-436x.201503816AhmadI,WangCC.Flexiblefractionalrepetitioncodesfordistributedstoragenetworks.Proceedingsofthe56thAnnualAllerton Conference on Communication,Control,andComputing(Allerton).Monticello:IEEE,2018.805812.17Zhu B.A study on universally good fractional repetitioncodes.IEEECommunicationsLetters,2018,22(5):890893.doi:10.1109/LCOMM.2018.281339118Porter A,Silas S,Wootters M.Load-balanced fractionalrepetitioncodes.Proceedingsofthe2018IEEEInternationalSymposiumonInformationTheory(ISIT).Vail:IEEE,2018.20722076.19WangJ,WangTT,LiuXY,et al.Locallyrepairablecodesbased on fractional repetition codes in distributed storagesystems.14thInternationalConferenceonWireless20Communications,Networking and Mobile Computing(WiCOM2018).Lancaster,PA:DEStechPublications,Inc.,2018,306:578587.Dukes PJ,Lamken ER,Ling ACH.Resolvable groupdivisibledesignswithlargegroups.TheElectronicJournalofCombinatorics,2016,23(4):4.24.doi:10.37236/543521Zhu B,Zhang SG,Wang WP.Expandable fractionalrepetitioncodesfordistributedstoragesystems.Proceedingsof the 2021 IEEE Information Theory Workshop(ITW).Kanazawa:IEEE,2021.15.22ZhuB,ShumKW,LiH,et al.Ontheoptimalreconstructiondegreeoffractionalrepetitioncodes.Proceedingsofthe2019IEEE International Symposium on Information Theory(ISIT).Paris:IEEE,2019.15571561.23SuYS.Optimalpliablefractionalrepetitioncodesthatarelocally recoverable:A bipartite graph approach.IEEETransactionsonInformationTheory,2019,65(2):985999.doi:10.1109/TIT.2018.287628424AghayevA,WeilS,KuchnikM,et al.Filesystemsunfitasdistributedstoragebackends:Lessonsfrom10yearsofCephevolution.Proceedings of the 27th ACM Symposium onOperating Systems Principles.Huntsville:ACM,2019.353369.25(校对责编:牛欣悦)2023年第32卷第2期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发399