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
? ? ? What is Deduplication? Importance ...? With the ability to identify similarity and ...structurally dissimilar may content the exact same ...
We propose ∑-Dedupe scheme to optimize cluster deduplication by exploiting ...Similarity index structure – Container-based locality-preserved caching 12 ...
A deduplication system for integrated person-centric information systems_计算机软件及应用_IT/计算机_专业资料。国外关于行人的一篇说是论文...
A deduplication system for integrated person-centric information systems_计算机软件及应用_IT/计算机_专业资料。国外关于行人的一篇说是论文...
热门文档