基于分数阶Fourier变换的云存储系统重复数据删除算法-论文.pdf

《基于分数阶Fourier变换的云存储系统重复数据删除算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

第42卷第7期计算机科学Vo1．42No．72015年7月ComputerScienceJuly2015基于分数阶Fourier变换的云存储系统重复数据删除算法徐奕奕。唐培和(广西科技大学计算机科学与通信工程学院柳州5450O6)(武汉理工大学信息工程学院武汉430070)。摘要云存储系统的重复数据作为大量冗余数据的一种，对其有效及时地删除能保证云存储系统的稳定与运行。由于云存储系统中的干扰数据较多，信噪比较低，传统的重删算法会在分数阶Fourier域出现伪峰峰值，不能有效地对重复数据进行检测滤波和删除处理，因此提出一种改进的基于分数阶Fourier变换累积量检测的云存储系统重复数据删除算法。首先分析云存储系统重复数据删除机制体系架构，定义数据存储点的适应度函数，得到云存储节点的系统子集随机概率分布；采用经验约束函数对存储节点中的校验数据块分存，通过分数阶Fourier变换对云存储系统中的幅度调制分量进行残差信号滤波预处理。采用4阶累积量切片后置算子，把每个文件分为若干个块，针对每个文件块进行重删，进行重复数据检测后置滤波处理，实现存储资源上的重复数据检测及其删除。仿真实验表明，该算法能提高集群云存储系统计算资源的利用率，重复数据准确删除率较高，有效避免了数据信息流的干扰特征造成的误删和漏硼4，性能优越。关键词分数阶Fourier变换，云存储，重复数据中图法分类号TP311文献标识码ADOI10．11896／j．issrL1002—137)(．2015．7．038DuplicateDataRemoveAlgorithmofCloudStorageSystemBasedonFractionalFourierTransformXUYi—yi’TANGPei-he(SchoolofComputerScienceandCommunicationEngineering，GuangxiUniversityofScienceandTechnology，Liuzhou545006，China)(SchoolofInformationEngineering，WuhanUniversityofTechnology，Wuhan430070，China)。AbstractDuplicatedataofcloudstoragesystemistakenasoneofalargeamountofredundantdata，andtheeffectiveandtimelyremovecanguaranteethestabilityandoperationofcloudstoragesystem．Becauseoftheinterferenceofdata，theSNRiSlOW，thetraditionalmethodhasfalsepeaksinthefractiona1Fourierdomain，anditcannoteffectivelydetectandremovetheduplicatedataAnimprovedduplicatedataremovealgorithmofcloudstoragesystemwasproposedbasedonfractionalFouriertransfotincumulantdetection．Firstly，thedeletesystemarchitectureforcloudstoragesys—ternwastaken，thefitnessfunctionofdatastoragepointwasdefined，andsystemsubsetrandomprobabilitydistributionfunctionofthecloudstoragenodewasgotten．Theconstraintfunctionwasusedforblockingthecalibrationdataofstoragenodes，thedetectionofduplicatedataremovingprocessingwastaken，andthefractionalFouriertransformwasusedtOpreprocesstheresidualsignalfilteringincloudstoragesystem．The4ordercumulantedslicepostoperatorwasusedtOdivideeachfileintoblocks．Todeleteeachfileblock，duplicateddatadetectionpostfilteringwasobtained，anddatastorageresourcedetectionanddeletionwererealized．Simulationresultsshowthatthisalgorithmcanimprovetheutilizationefficiencyofclustercloudstoragesystemresource，andduplicatedatacanbeaccuratelyremovedwithhigherrate．Itcaneffectivelyavoidtheerrorremovingcausedbyinterferenceandleakageremoving，andithassuperiorper—fofinance．KeywordsFractionalFouriertransforlTl，Cloudstorage，Duplicatedata成为分布式文件管理系统和各类存储设计集成的重要工具和1引言载体。云系统中的重复数据是各类数据管理成本快速上升过随着计算机信息技术的飞跃发展，人类进入了信息化时程中留下的冗余数据产物，云存储系统中产生的数据量以几代，云存储系统作为信息化发展的产物，在物联网、移动互联何级数增长，导致网络带宽和存储空间资源的紧缺以及数据网和SNS等数据管理和大规模数据集成中扮演着重要角色，管理成本的快速上升，云存储系统中的冗余数据带来了高额到稿日期：2014—08—29返修日期：2014—09—28本文受广西自然科学基金青年基金项目(2O13GxNSFBAO19268)。广西科技大学自然科学基金项目(校科自1261126)，广西特色专业建设项目(GXTSZY217)，广西教育厅一般项目(YB2014208)，广西教育厅立项项目(LX2014182)资助徐奕奕(198O一)，女，博士，副教授，主要研究方向为网络存储与云存储；唐培和(1964一)，男，硕士，教授，主要研究方向为分布式计算与分布式存储。·174· 的硬件和人力成本，降低了系统的性能。为了有效满足爆炸上传文件到云端；控制器负责管理用户的请求，在元数据块与式增长的云存储系统运行数据管理的需求，减轻服务器开销，数据块的修改模式下，对每一个写请求进行基于Hash指纹研究一种有效的云存储系统重复数据删除算法，对消除数据识别的数据冗余判别；服务器便是数据上传的最终存储节点，冗余、降低系统能耗和提高存储性能具有重要意义，重复数据数据上传至服务器端时，采用延迟删除来提高系统的效率。删除技术成为云数据存储领域的一个重要的研究热点。重复数据删除算法设计中，首先需要进行文件切分，将文件切研究表明，在云存储应用系统所保存的数据中，高达分为若干数据块(Chunk)，将每个完整的文件当作一个6O的数据是冗余的，以重复数据为主导的冗余数据所占比Chunk来进行分块，得到的完整数据信息流为：例也将随着时间的推移而上升，重复数据删除作为一项应用z(+1)一眦()+c1n[’TOP一(￡)]+于存储系统上的数据管理技术，有必要结合数据特征和存储C2r2L一-z(￡)](1)规模来探讨。结合信号与信息处理的相关理论，采用数据信式中，to和t分别表示数据块边界偏移的个体极值和全局极息检测和数字滤波方法，可实现对重复数据的检测和删除_1]。值进化停滞步数；To和分别表示个体极值和全局极值需其中现有的云存储开源重删系统主要有Lessfs和要扰动的停滞步数阈值。在云存储系统中，为了适应云存储OpenDedup系统，其建立在应用层之上I2]，通过用户对数据中的多QoS偏好，重新定义数据存储点的适应度函数如下：系统状态的识别，避免了用户对底层的管理，但系统没能通过一+m++w,8(2)信息处理的方法实现对重复数据的删除，实际效果不好；wu其中，Wt+毗+Wq+一1，t代表时间(time)，c代表代价TY等人提出了基于负载均衡的云系统漂移数据删除算(cost)，q代表质量(quality)，s代表安全(security)，不同应用法l_3]，在概念学习系统的基础上，采用决策树ID3算法对重复文件在选择相同的划分策略和指纹提取方法时，各个存储子数据进行剪枝，实现重复数据删除，但该算法计算开销大，应集间将组合成一个具有层次结构树状图，得到该云存储节点用性不好；文献[-4-]中蒋海波、王晓京等人提出一种基于水平的系统子集随机概率分布函数为：纠删码的云存储数据布局和重删方法，即采用水平阵列信号w(epkq)=aXw(spkq)(3)处理技术，实现了可容3列随机重复数据的纠删码删除算法，在云存储系统中，重复数据的双随机概率分布函数的权实现对云存储数据的优化布局，但该算法需要采用水平纠删重主要依据它在所属双随机概率分布函数中出现的概率来计码扩展的方法进行线性编译，降低了丢失数据的恢复性能；文算，而所有双随机概率分布函数都是围绕一个核心概率函数献[5]对传统的水平纠删码扩展重复数据删除进行改进设计，展开的，展开结果为：对RS码进行了改造，在Galois域上进行重复查询，采用分数uI，一，^Jf_~T一，^主(vk一．^)(4)阶Fourier变换方法对急剧增加的海量重复数据进行检测滤如果将Wk按照和e的组成原则进行分解，得到重复波处理，然而该算法对高阶累积的重复数据的滤波效果不好，数据信息流的存储节点权重w(epk)，以此计算云存储集群删除性能低；文献[6]采用基于负载均衡的客户／服务器(Cli—系统的校验信息存储子集，计算公式为：ent／Server，C／S)双端重复数据删除机制，综合考虑了负载均r—。。()一If(t)d~o()dt(5)衡和动态副本管理，该算法对当期重复数据删除效果尚可，但J—一对全局收敛性较低的动态副本数据删除效果较差；文献[7]提上式表示一个具有个输入控制参量、m个输出参量分出一种基于经验模态分解和粒子滤波的数据检测算法来对云簇云存储器的校验块跨越编码，采用经验约束函数对存储节存储系统中的重复数据进行删除，由于没有对累积量特征进点中的校验数据块分存，分析云存储系统的校验数据块的重行滤波后置检测，导致对云存储系统的重复数据的删除性能复数据状态向量，由此构建云存储系统重复数据删除机制体不好，且该算法采用单节点架构，扩展性不佳，难以得到大规系，为进行云存储系统的重复数据删除算法的设计提供模型模应用。依据和总体框架。针对上述问题，本文提出一种改进的基于分数阶Fourier2．2云存储系统中重复数据流信息模型与预处理变换累积量检测的云存储系统重复数据删除算法。首先对云从上述构建的总体模型分析可见，在云存储系统中，当客存储系统重复数据删除机制体系架构进行研究，构建云存储户端发出文件存储请求时，文件服务器根据子集校验数据块系统中重复数据流信息模型与并进行信号特征预处理，采用的任务执行状态和文件读取需求进行数据文件信息分区处分数阶Fourier变换4阶累积量算法实现对重复数据删除算理，为提高集群存储系统计算资源的利用率，需要对重复数据法的改进，仿真实验验证了算法的可行性和优越性。进行删除，以提高系统的存储介质性能。构建云存储系统中重复数据流信息模型是进行重删设计的关键[，假设云存储2云存储系统重复数据删除机制体系架构与问题系统重复数据流信息的目标端信息分量为：描述／'1一(￡)一f1(6)2．1相关预备知识与体系架构采用窗函数宽度可变方法对频率分辨力进行调整，重复本文设计的云存储系统漂移数据删除体系构架分为3个数据一般都会备份到远端存储节点，可以利用重删系统中文主体：客户端(Client)、控制器(Controller)和服务器(Server)。件信息流进行相位信息评估，得到重复数据出现的概率权重客户端作为源端设备，是整个系统数据的原始提供者，客户端为：·]75· Wij一卢×w(epkq)，1(7)x—Fd·z(14)重复数据信息流通过网络传输到远端存储节点，得到输式中，出向量模型为：X=[X。(O)，X。(1)，⋯，X(N一1)](15)1其中，是NXN维矩阵，存储系统中各个节点需要创建多个xi(尼)一—，J一1，2，3(8)1TeJ线程的信息流特征编码，得到重复数据信息流矩阵各元素为：上式描述了多源进程节点的云存储系统的任务执行模Fd()Ae(j／2)cota‘m．e(j／2)oota．n2。．型。在云存储系统中，校验数据块分存到子集云存储系统中，e一』(16)得到重复数据集合为：由此实现对重复数据信息流的检测。为了进一步实现对p-{Pl，P2，⋯)，∈N(9)云存储系统中的重复数据删除性能，本文采用4阶累积量后对多个任务流中的重复数据进行在线编码调度，云存储置处理方法，对传统方法进行改进，定义云存储系统中的源端系统将启动下一存储子集，客户端向文件服务器请求源数据，节点存储数据的4阶累积量切片表达式为：得到存储系统生成校验位为：^1Nc4(r1，r2，)一∑z()(i+r1)(itZ'2)(itr3)一flow,一{l，2，⋯，}，qEN(1O)I2—1式中，q表示多个云存储节点信息流集合的特征编码位置，‰^AA^fz(r1)f2(r2一)一C2(T2)f2(Z'3一表示数据信息流的数据序列，N表示信息位总数。通过上述AAZ'I)一C2(r3)~2x(rl—r2)(17)分析，得到了云存储系统的重复数据流信息模型。本文采用^1N信息流检测和滤波处理方法，来实现对重复数据的检测和重式中，c(r)=1∑x(i)x(i+r)，在目标端重删系统中，假设』一1删处理，引入分数阶Fourier变换信号检测方案，假设云存储系^Ac(r，r2，"r3)的对角切片表达为C“(r，r，r)，那么多个客户端统中重复数据信息流为z()，分数阶Fourier变换的定义为：r∞节点的数据对角切片在分数阶Fourier域上的离散时间点x(“)一P[(￡)]一lK(￡，u)x(t)dt(11)^J—一处的检测统计量为C(，r)，则有：式中，P为分数阶Fourier域的阶，为实数，旋转角口一p／2。^^c／'’(，r)一c’(r，r，r)P[·]表示变换算子形式记号，(，“)是FRFT的变换核。=<()(雄+r))一3<()(+r)>((+这样，通过对重复数据信息流的IMF分量幅度调制的信息，r)>(18)得到信号z()的第个IMF分量，表示为：式中，表示均值，即：n—c2一r2，⋯，一l一一rn(12)N采用分数阶Fourier变换对上述云存储系统中的幅度调一1／N∑g()(19)一1制分量进行残差信号滤波预处理。通过第一次筛分后去除残上述改进算法有效利用了4阶累积量切片对云存储系统差信号，提取出满足固有模态函数的IMF分量，得到：重复数据信息流的能量聚集和噪声抑制的特性，在分数阶z()一∑+(13)Fourier变换检测形成后置处理，提高对重复数据的滤波性t—l能。以此为基础，对本文提出的分数级Fourier变换的云存储式中，C代表各IMF分量，代表残余均方差的估计值，由此系统重删算法进行改进设计。实现了对云存储系统中重复数据信息流的预处理。通过上述3．2云存储系统的重复数据删除算法的改进实现分析可见，采用传统的基于分数阶Fourier域的残差信号滤波根据上述设计的基于Fourier变换高阶累积量算法的云处理还不能有效滤除重复数据，云存储系统中过多的线程将存储系统重复数据检测滤波结果，利用4阶累积量切片后置会竞争有限的资源，导致系统性能较低，且根据传统方法解出聚集处理能力，以滤波处理后的云存储系统节点的重复数据的信息位不能有效定位重复数据的存储节点和相位信息，需信息流为输入向量，进行重删系统设计和算法实现，重复数据要进行算法改进，以提高对云存储系统的重复数据删除性能。的文件系统层设训练样本集为X—Ix-，x2，⋯，，⋯，3改进的分数阶Fourier变换重复数据删除算法的x]，其中任一训练样本为xk—Ix,，z，⋯，‰，⋯，砌]。实现在云存储的网络环境中，为了确保数据的可用性与可靠性，数据一般都会备份到远端存储节点，采用上述设计的检测滤波3．1云存储系统中重复数据信息流检测滤波的改进设计系统，得到云存储系统中的重复数据信息流的离散分数阶在上述构架的云存储系统重复数据删除总体模型中，对Fourier逆变换可表示为：传统的基于分数阶Fourier变换方法的海量重复数据检测滤—F一·X(20)波和删除算法进行改进，采用分数阶Fourier变换高阶累积量其中，F一。一。若背景噪声()具有非高斯性，则其4阶算法对重复数据进行检测处理，算法描述如下：混合累积表达为：根据式(11)定义的分数阶Fourier变换表达式，以及重复数据的丢失信息流特征，进行特征分解，实现对存储系统中的f“(r)一)，∑^()(+r)(21)J=0重复数据信息流的分数阶Fourier域构造，得到简化后的式中，y为客户端节点的数据带宽，()为云存储系统的滤波Fourier变换表达式：函数，r为重复数据重构时延，采用分数阶Fourier变换方法，·176· OZ3ll5[19]LiuHJ，WangXY．Colorimageencryptionusingspatialbit—E12]SunFY，LiuST，LiZQ，eta1．Anovelimageencryptionlevelpermutationandhigh-dimensionchaoticsystem[J]．OpticsschemebasedonspatialchaosmapEJ]．Chaos，Solitons＆Frac—Communications，2011，284(16／17)：3895—3903tals，2008，38(3)：631—640[,203KanekoK．SpatiotemporalintermittencyinCoupledMapLat-El3]RhoumaR。SoumayaM。Safya＆OCML-basedcolourimageen—tices['J]．ProgressofTheoreticalPhysics，1985，74(5)：1033—cryption[J]．Chaos，Solitons&Fractals，2009，40(1)：309—3181044[14]GuoQ，LiuZG，IAuST．ColourimageencryptionbyusingAr—[21]RhoumaR，SoumayaM，SafyaBOCML-basedcolourimageen—noldanddiscretefractiona1randomtransformsinHISspacecryption[J]．Chaos，Solitons&Fractals，2009，40(1)：309—318EJ]．OpticsandLasersinEngineering，2010，48(12)：1174—1181[22]SaharM，AmirMEColourimageencryptionbasedoncoupledE15]SaharM，AmirME．Colourimageencryptionbasedoncouplednonlinearchaoticmap[J]．Chaos，Solitons&Fractals，2009，42nonlinearchaoticmap[J]．Chaos，SolitonsandFractals，2009，42(3)：1745—1754(3)：1745—1754[23]LiuHJ，WangXY．Colourimageencryptionbasedonone-time[163WangXY，TengL，QinX．Anovelcolourimageencryptional—keysandrobustchaoticmaps[J]．Computers&MathematicsgorithmbasedonchaosI-J]．SignalProcessing，2012，92(4)：withApplications，2010，59(10)：3320—332711O1—1108[24]罗松江，丘水生．基于时空混沌和S盒的彩色图像加密算法El7]ZhangW，WongKW，YuH，eta1．Asymmetriccolorimageen—口]．电路与系统学报，2010，15(3)：117—122cryptionalgorithmusingtheintrinsicfeaturesofbitdistribu—LuoSJ，QiuSSColorimageencryptionalgorithmbasedontions[J]．CommunicationsinNonlinearScienceandNumericalspatiotemporalchaosandS-box[J-I．JournalofCircuitsandSys—Simulation，2013，18(3)：584—600terns，2010，15(3)：117—122E18]FuC。LinB，MiaoY，eta1．Anovelchaos-basedbit—levelpermu—[25]HeJ，zB，QianHF．Cryptographybasedonspatiotemporaltationschemefordigitalimageencryption_J]．OpticsCommuni—chaossystemandmultiplemaps口]．JournalofSoftware，2010，cation。2011，284(23)：5415—54235(4)：421-428(上接第177页)works，2012，10(7)：1497—1516量大小，横坐标表示6种不同文件类型，右纵坐标表示重复数I-3]wuTY，LeeWT，LinYS，eta1．Dynamicloadbalandngmecha-据删除率的大小。对6种不同格式的文件采用本文算法和传nismbasedoncloudstorage[C]fComputing，CommunicationsandApplicationsConference(ComComAp)，2012．IEEE，2012：统算法进行云存储系统重复数据删除，结果表明本文算法重102—106复数据准确删除率较高，去重的效果更佳，有效避免了数据信E4]蒋海波，王晓京，范明钰，等．基于水平纠删码的云存储数据布局息流的干扰特征造成的误删和漏删，重复数据删除准确性能方法I-J]．四川大学学报(工程科学版)，2013，45(2)：103—109较好，误删率降低了13．11，云存储系统的CPU执行时间JiangHai—bo，WangXiao-jing，FanMing-yu．ADataPlacement提高了17．8，从而展示了算法的优越性能。BasedonLevelArrayCodesinCloudStorage[J]．JournalofSi-结束语云存储系统中的重复数据是各类数据管理成本chuanUniversity(EngineegingScienceEdition)，2013，45(2)：快速上升过程中留下的冗余数据产物，云存储系统中产生的103—109数据量以几何级数增长。为了有效面对爆炸式增长的云存储E5]敖莉，舒继武，李明强．重复数据删除技术[J]．软件学报，2010，系统运行数据管理的需求，减轻服务器开销，研究了一种有效21(5)：916—929的云存储系统重复数据删除算法，对消除数据冗余、降低系统AoLi，ShuJi—wu，LiMing-qiang．DataDeduplieationTechniques能耗和提高存储性能具有重要意义[g]。本文提出一种改进的I-J]．JournalofSoftware，2010，21(5)：916—929基于分数阶Fourier变换累积量检测的云存储系统重复数据[63付印金，肖依，刘芳．重复数据删除关键技术研究进展[J]．计算删除算法，即采用4阶累积量切片实现对云存储系统重复数机研究与发展，2012，49(1)：12—20FuYing-jin，XiaoNong，LiuFang．ResearchandDevelopmenton据信息流的能量聚集和噪声抑制，进行重复数据检测后置滤KeyTechniquesofDataDeduplicaton[J]．JournalofComputer波处理，创建多个线程的信息流特征编码，实现对重复数据的ResearchandDevelopment，2012，49(1)：12—2O删除。分析研究和实验结果表明，采用本文算法能有效避免E73李渊．智能PID控制区优化仿真研究[J]．计算机仿真，2012，29数据信息流的干扰特征造成的误删和漏删，对云存储系统中(12)：180—182重复数据的检测性能较好，重复数据删除准确性高，综合性能LiYuan．ParametersOptimizationofPIDController[J]．Com—优于传统算法。puterSimulation，2012，29(12)：180—182[83谭鹏许，陈越，兰巨龙，等．用于云存储的安全容错编码口]．通信参考文献学报，2014，35(3)：109—114[1]谢平．存储系统重复数据删除技术研究综述[J]．计算机科学，TanPeng-xu，ChenYue，LanJu-long，eta1．Securefault—tolerant2O14，41(1)：22—30codeforcloudstorage[J]．JournalonCommunications，2014，35XiePing．Sureyondatadeduplicationtechniquesforstoragesys—(3)：109-114tems[J]．ComputerScience，2014，41(1)：22—30[9]TangPei-he，XuYi—yi．ResourceSchedulingStrategyBasedonI-2]MiorandiD，SicariS，PellegriniFD，eta1．Internetofthings：vi—CredibilityintheEnterpriseGloudStrorage[J]．JournalofCon—sion，applicationsandresearchchallenges[J]．AdHocNet—vergenceInformationTechnology，2012，7(16)：393—400·209·