文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 互联网 > Silo_ a similarity-locality based near-exact deduplication scheme with low ram overhead and high
侵权投诉

Silo_ a similarity-locality based near-exact deduplication scheme with low ram overhead and high

SiLo:ASimilarity-LocalitybasedNear-ExactDeduplicationSchemewith

LowRAMOverheadandHighThroughput

WenXia

wx.hust@gmail.com

HongJiang

jiang@cse.unl.eduDanFeng dfeng@hust.edu.cnYuHua ,

csyhua@hust.edu.cn

SchoolofComputer,HuazhongUniversityofScienceandTechnology,Wuhan,China

WuhanNationalLabforOptoelectronics,Wuhan,China

Dept.ofComputerScienceandEngineering,UniversityofNebraska-Lincoln,Lincoln,NE,USAAbstract

DataDeduplicationisbecomingincreasinglypopularinstoragesystemsasaspace-ef cientapproachtodatabackupandarchiving.Mostexistingstate-of-the-artdeduplicationmethodsareeitherlocalitybasedorsim-ilaritybased,which,accordingtoouranalysis,donotworkadequatelyinmanysituations.Whiletheformerproducespoordeduplicationthroughputwhenthereislittleornolocalityindatasets,thelattercanfailtoiden-tifyandthusremovesigni cantamountsofredundantdatawhenthereisalackofsimilarityamong les.Inthispaper,wepresentSiLo,anear-exactdeduplicationsys-temthateffectivelyandcomplementarilyexploitssim-ilarityandlocalitytoachievehighduplicateelimina-tionandthroughputatextremelylowRAMoverheads.ThemainideabehindSiLoistoexposeandexploitmoresimilaritybygroupingstronglycorrelatedsmall lesintoasegmentandsegmentinglarge les,andtoleveragelocalityinthebackupstreambygroupingcon-tiguoussegmentsintoblockstocapturesimilaranddu-plicatedatamissedbytheprobabilisticsimilaritydetec-tion.Byjudiciouslyenhancingsimilaritythroughtheex-ploitationoflocalityandviceversa,theSiLoapproachisabletosigni cantlyreduceRAMusageforindex-lookupandmaintainaveryhighdeduplicationthrough-put.OurexperimentalevaluationofSiLobasedonreal-worlddatasetsshowsthattheSiLosystemconsistentlyandsigni cantlyoutperformstwoexistingstate-of-the-artsystem,onebasedonsimilarityandtheotherbasedonlocality,undervariousworkloadconditions.

eachuniquelyidenti edbya20-byteSHA-1hashsig-nature,alsocalleda ngerprint[21].Itremovesdupli-catechunksbycheckingtheir ngerprints,whichavoidsabyte-by-bytecomparison.Datadeduplicationnotonlyreducesthestoragespaceoverheads,butalsominimizesthenetworktransmissionofredundantdatainthenet-workstoragesystem[19].

Oneofthemainchallengesforcentralizedbackupservicesbasedondeduplicationisthescalabilityof ngerprint-indexsearch.Forexample,tobackupadatasetof800TBandassuminganaveragechunksizeof8KB,atleast2TBof ngerprintshavetobegenerated,whichwillbetoolargetobestoredinthememory.Sincetheaccesstoon-diskindexisatleast1000timesslowerthanthattoRAM,thefrequentaccessestoon-disk n-gerprintsarenotacceptableforbackupservicesandhavebecomethemainperformancebottleneckofsuchdedu-plicationsystems.

MostoftheexistingsolutionsaimtomakethefulluseofRAM,byputtingthehot ngerprintsintoRAMtominimizeaccessestoon-diskindexandimprovethethroughputofdeduplication.Therearetwoprimaryap-proachestoscalingdatadeduplication:localitybasedaccelerationofdeduplication,andsimilaritybaseddedu-plication.Locality-basedapproachesexploittheinherentlocalityinabackupstream,whichiswidelyusedinstate-of-the-artdeduplicationsystemssuchasDDFS[26]andChunkStash[8].Localityinthiscontextmeansthatthechunksofabackupstreamwillappearinapproximatelythesameorderineachfullbackupwithahighproba-bility.ExploitationofthislocalityincreasestheRAMutilizationandreducestheaccessestoon-diskindex,thusalleviatingthediskbottleneck.Similarity-basedap-proachesaredesignedtoaddresstheproblemencoun-teredbylocality-basedapproachesinbackupstreamsthateitherlackorhaveveryweaklocality(e.g.,incre-mentalbackups).Theyexploitdatasimilarityinsteadoflocalityinabackupstream,andreducetheRAMus-agebyextractingsimilarcharacteristicsfromthebackup

1Introduction

Astheamountoftheimportantdatathatneedstobedigitallystoredgrowsexplosivelytoaworldwidestor-agecrisis,datadeduplication,aspace-ef cientmethod,hasgainedincreasingattentionandpopularityindatastorage.Itsplits lesintomultiplechunksthatare

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email