![点击分享此内容可以赚币 分享](/master/images/share_but.png)
图因子分解的故障节点快速修复_余春雷.pdf
《图因子分解的故障节点快速修复_余春雷.pdf》由会员分享,可在线阅读,更多相关《图因子分解的故障节点快速修复_余春雷.pdf(6页珍藏版)》请在咨信网上搜索。
1、图因子分解的故障节点快速修复余春雷1,3,王娥2,刘星1,谢锐1,冉彪11(四川文理学院智能制造学院,达州635002)2(长安大学信息工程学院,西安710064)3(智能制造产业技术研究院,达州635002)通信作者:余春雷,E-mail:摘要:为了提高分布式存储系统中故障节点的修复效率,提出一种新的部分重复(fractionalrepetition,FR)码的构造算法.该算法利用完全图的因子分解进行构造,称为 CGFBFR(completegraphfactorizationbasedFR)码.该算法首先对完全图进行因子分解,分解完成以后确定完全图的因子分解个数,根据需要存储数据块的重复度
2、来选择完全图的因子个数,将完全图选中的因子所有顶点当做分布式存储系统中需要存储的数据块,然后对选中因子图的边进行标记,标记的边当做分布式数据节点进行存储.最后根据选中的因子的顶点和边生成编码矩阵,在分布式存储系统中按照编码矩阵中的数据对数据块分别进行存储.实验仿真结果显示,本文提出的一种新的部分重复码构造算法,与分布式存储系统中的里所(reed-solomon,RS)码、简单再生码(simpleregeneratingcodes,SRC)以及最新的循环可变部分重复(variablefractionalrepetition,VFR)码相比,在系统修复故障节点时,能够快速地修复故障节点,有效降低了
3、故障节点的修复带宽开销、修复局部性、修复复杂度,而且构造过程简单,同时可以灵活选择构造参数,广泛适用于分布式存储系统中.关键词:图因子分解;完全图;存储节点;修复;部分重复码;故障诊断引用格式:余春雷,王娥,刘星,谢锐,冉彪.图因子分解的故障节点快速修复.计算机系统应用,2023,32(2):394399.http:/www.c-s- Repair of Faulty Nodes Based on Graph FactorizationYUChun-Lei1,3,WANGE2,LIUXing1,XIERui1,RANBiao11(SchoolofIntelligentManufacturing
4、,SichuanUniversityofArtsandScience,Dazhou635002,China)2(SchoolofInformationEngineering,ChanganUniversity,Xian710064,China)3(IntelligentManufacturingIndustryTechnologyResearchInstitute,Dazhou635002,China)Abstract:Toimprovetheefficiencyofrepairingfaultynodesinadistributedstoragesystem,thisstudypropose
5、sanewconstructionalgorithmforfractionalrepetition(FR)codes.Thealgorithmresortstothefactorizationofthecompletegraphfornodeconstruction,andthenodesconstructedarereferredtoascompletegraphfactorizationbasedFR(CGFBFR)nodes.Specifically,thecompletegraphisfactorized,andthenumberoffactorsgeneratedfromthecom
6、pletegraphafterthefactorizationiscompletedisdetermined.Thenumberoffactorsofthecompletegraphisselectedaccordingtotherepetitiondegreesofthedatablocksthatneedtobestored.Alltheverticesoftheselectedfactorsofthecompletegraphareregardedasthedatablocksthatneedtobestoredinthedistributedstoragesystem.Then,the
7、edgesoftheselectedfactorgrapharemarkedandstoredasdistributeddatanodes.Finally,anencodingmatrixisgeneratedwiththeverticesandedgesoftheselectedfactors,andthedistributedstoragesystemstoresthedatablocksrespectivelyaccordingtothedataintheencodingmatrix.Theexperimentalsimulationresultsshowthatcomparedwith
8、theReed-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:+86-10-62661041基金项目:陕西省重点研发计划(2021GY-019),智能制造产业技术研究院开放
9、基金(ZNZZ2106)收稿时间:2022-06-15;修改时间:2022-09-07;采用时间:2022-09-14;csa 在线出版时间:2022-11-04CNKI 网络首发时间:2022-11-16394研究开发ResearchandDevelopmentdistributedstoragesystem,thecodesgeneratedbythenewFRcodeconstructionalgorithmproposedinthisstudycanquicklyrepairthefaultynodewhenthesystemrepairsthenode.Theproposedalgo
10、rithmcanbewidelyappliedtodistributedstoragesystemsasitreducestherepairbandwidthoverhead,repairlocality,andrepaircomplexityofthefaultynode,providesasimpleconstructionprocess,andallowsflexibleselectionofconstructionparameters.Key words:graphfactorization;completegraph;storagenode;repair;fractionalrepe
11、tition(FR)codes;faultdiagnosisn如今的社会是一个互联网高速发展的社会,大量互联网公司和政府部门每天运营中产生海量的数据1,数据的价值和重要性不言而喻,因此如何维护数据的可靠性和稳定性2,3是急需要解决的关键技术.现有的集中式存储主要靠数据服务器和存储设备4.但是集中式存储,设备价格昂贵,而且需要大量的管理时间以及维护成本5.集中式存储一旦遭到破坏,数据将永久毁灭.相较于集中式存储,具有可扩展、设备成本低、高性能、易用性的分布式存储系统成为目前主流存储系统6.分布式存储对数据的存储采用的策略是复制策略和纠删码策略7,8.复制策略就是把需要存储的原始文件复制 份,然后
12、对复制的所有数据进行存储,通过复制的副本数据来保障数据的可靠性,当出现数据损坏,可以直接复制副本数据快速修复,整个过程简单易实施,但复制策略的缺陷是存储开销大9.与复制策略相比,纠删码策略只需要存储少量的编码数据块.使系统的存储开销得到有效地降低,同时纠删码策略通过编码产生的校验数据块,使系统具有更好的容错性.但在分布式存储系统中通过纠删码对故障节点进行修复时,系统需要消耗较大的修复带宽开销10.目前里所(reed-solomon,RS)码和磁盘阵列码11等典型的纠删码被广泛应用于分布式存储系统中.如图 1 所示为RS 编码和重构原理过程.当其中任意一个数据块发生故障,都可以通过解码恢复出故障
13、数据块.针对复制策略和纠删码策略等局限性12,13,研究者通过研究发现在存储开销跟修复带宽开销之间折中,提出简单再生码(simpleregeneratingcodes,SRC)的编码方式14.简单再生码是通过大量的有限域运算编码构造15.不需要消耗大量的存储开销,并且在修复故障节点时,只需要连接相应节点就可以修复数据,修复带宽开销较低.但修复过程需大量解码运算,使得修复过程非常复杂,修复时间增多,而且还需要连接多个节点进行修复,因此修复局部性高16.部分重复(fractionalrepetition,FR)码17无需进行有限域运算,同时也可以降低节点存储开销18.在对故障节点修复时,具有较低的
14、修复局部性和修复带宽开销19,20.因此,部分重复码被广泛研究.目前主流的 FR码构造方法有如下几种:基于正则图、分组设计21及可分解设计22,但构造过程复杂,且不能灵活选择部分重复码的构造参数,不适应实际的存储系统23,24.因此提出基于完全图图因子分解的部分重复(completegraphfactorizationbasedFR,CGFBFR)码的构造算法.B13B14B15B12B11B23B24B25B22B21B33B34B35B32B310010001000100000001000001D3D4D5D2D1C3C2C1D3D4D5D2D1CDnBD=D3D4D5D2D1D=0001
15、00000110000C3C1D3D5D2Survivorsm+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
16、=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,部分重复码可以由 个子集的集合表示,是数据块的重复度,每个子集中的符号均属于
17、符号集.该部分重复码的构造过程满足如下条件.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等编码数据块复制 份,最后通过部分重复码的内部构造算法把所有的数据块存储在 个节点里.M
18、DSCodeN1m1m2m3m0N4m5m7p9m2N3m4m7m8m1N2m4m5m6m0N5m6m8p9m3(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)
19、(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,F1
20、5F1,F2,F3F1,F2,F3e(1 9)具体地,可以对进行因子分解,然后构造一个重复度为的 FR 码.如果取重复度,因此可以在所有因子中任选 3 个进行构造数据矩阵,这里我们在 15 个因子中选取,然后对选中因子的边进行依次编号为,如图 3 所示.v5v1v6v1v6v2v1v6e5v3v2v4v3v2v4v5v3v4v5e1e2e3e4e6e7e8e9F1F3F2K6图 3的部分因子分解m1通过图 2,我们可根据式(2)求出数据矩阵如下:m1=100010010001001100010010100100001001000101001010110000计 算 机 系 统 应 用http:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 因子 分解 故障 节点 快速 修复 春雷
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。