重復(fù)數(shù)據(jù)刪除技術(shù)研究綜述

ISSN1000-9825,CODENRUXUEWJournalofSoftware,Vol.21,No.5,May2010,pp.916?929doi:10.3724/SP.J.1001.2010.03761?byInstituteofSoftware,theChineseAcademyofSciences.Allrightsreserved.E-mail:jos@Tel/Fax:+86-10-62562563*重復(fù)數(shù)據(jù)刪除技術(shù)1(清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,北京100084)2(清華大學(xué)信息科學(xué)與技術(shù)國(guó)家實(shí)驗(yàn)室(籌),北京100084)DataDeduplicationTechniquesAOLi1,SHUJi-Wu1,2+,LIMing-Qiang11(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,China)2(NationalLaboratoryforInformationScienceandTechnology(TNList),TsinghuaUniversity,Beijing100084,China)+Correspondingauthor:E-mail:shujw@AoL,ShuJW,LiMQ.Datadeduplicationtechniques.JournalofSoftware,2010,21(5):916?929./1000-9825/3761.htmAbstract:Datadeduplicationtechnologiescanbedividedintotwocategories:a)identicaldatadetectiontechniques,andb)similardatadetectionandencodingtechniques.Thispaperpresentsasystematicsurveyonthesetwocategoriesofdatadeduplicationtechnologiesandanalyzestheiradvantagesanddisadvantages.Besides,sincedatadeduplicationtechnologiescanaffectthereliabilityandperformanceofstoragesystems,thispaperalsosurveysvariouskindsoftechnologiesproposedtocopewiththesetwoaspectsofproblems.Basedontheanalysisofthecurrentstateofresearchondatadeduplicationtechnologies,thispapermakesseveralconclusionsasfollows:a)Howtominedatacharacteristicinformationindatadeduplicationhasnotbeencompletelysolved,andhowtousedatacharacteristicinformationtoeffectivelyeliminateduplicatedataalsoneedsfurtherstudy;b)Fromtheperspectiveofstoragesystemdesign,itstillneedsfurtherstudyhowtointroducepropermechanismstoovercomethereliabilitylimitationsofdatadeduplicationtechniquesandreducetheadditionalsystemoverheadscausedbydatadeduplicationtechniques.Keywords:networkstoragesystem;duplicatedata;dataelimination;reliability;performance摘要:重復(fù)數(shù)據(jù)刪除技術(shù)主要分為兩類:相同數(shù)據(jù)的檢測(cè)技術(shù)和相似數(shù)據(jù)的檢測(cè)與編碼技術(shù),系統(tǒng)地總結(jié)了這兩類技術(shù),并分析了其優(yōu)缺點(diǎn).此外,由于重復(fù)數(shù)據(jù)刪除技術(shù)會(huì)影響存儲(chǔ)系統(tǒng)的可靠性和性能,又總結(jié)了針對(duì)這兩方面的問題提出的各種技術(shù).通過對(duì)重復(fù)數(shù)據(jù)刪除技術(shù)當(dāng)前研究現(xiàn)狀的分析,得出如下結(jié)論:a)重復(fù)數(shù)據(jù)刪除中的數(shù)據(jù)特性挖掘問題還未得到完全解決,如何利用數(shù)據(jù)特征信息有效地消除重復(fù)數(shù)據(jù)還需要更深入的研究;b)從存儲(chǔ)系統(tǒng)設(shè)計(jì)的角度,如何引入恰當(dāng)?shù)臋C(jī)制打破重復(fù)數(shù)據(jù)刪除技術(shù)的可靠性局限并減少重復(fù)數(shù)據(jù)刪除*SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60873066(國(guó)家自然科學(xué)基金);theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2009AA01A403(國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863));theSpecializedResearchFundfortheDoctoralProgramofHigherEducationofChinaunderGrantNo.200800030027(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金)Received2008-06-04;Revised2008-12-29;Accepted2009-10-09敖莉等:重復(fù)數(shù)據(jù)刪除技術(shù)917技術(shù)帶來的額外系統(tǒng)開銷也是一個(gè)需要深入研究的方面.性;性能中圖法分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A隨著數(shù)字信息量的爆炸式增長(zhǎng),數(shù)據(jù)占用空間越來越大;在過去的10年里,很多行業(yè)提供的存儲(chǔ)系統(tǒng)容量從數(shù)十GB發(fā)展到數(shù)百TB,甚至數(shù)PB[1].隨著數(shù)據(jù)的指數(shù)級(jí)增長(zhǎng),企業(yè)面臨的快速備份和恢復(fù)的時(shí)間點(diǎn)越來越多,管理保存數(shù)據(jù)的成本及數(shù)據(jù)中心空間和能耗也變得越來越嚴(yán)重.研究發(fā)現(xiàn),應(yīng)用系統(tǒng)所保存的數(shù)據(jù)中高達(dá)60%是冗余的,而且隨著時(shí)間的推移越來越多[1].為了緩解存儲(chǔ)系統(tǒng)的空間增長(zhǎng)問題,縮減數(shù)據(jù)占用空間,降低成本,最大程度地利用已有資源,重復(fù)數(shù)據(jù)刪除技術(shù)已成為一個(gè)熱門的研究課題.一方面,利用重復(fù)數(shù)據(jù)刪除技術(shù)可以對(duì)存儲(chǔ)空間的利用率進(jìn)行優(yōu)化,以消除分布在存儲(chǔ)系統(tǒng)中的相同文件或者數(shù)據(jù)塊.另一方面,利用重復(fù)數(shù)據(jù)刪除技術(shù)可以減少在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量,進(jìn)而降低能量消耗和網(wǎng)絡(luò)成本[2],并為數(shù)據(jù)復(fù)制大量節(jié)省網(wǎng)絡(luò)帶寬.隨著重復(fù)數(shù)據(jù)刪除技術(shù)的發(fā)展,該技術(shù)大量應(yīng)用于存儲(chǔ)備份和歸檔系統(tǒng)中,該系統(tǒng)中的重復(fù)數(shù)據(jù)刪除模塊負(fù)責(zé)對(duì)數(shù)據(jù)內(nèi)容進(jìn)行比對(duì)分析,查找出冗余數(shù)據(jù),并將其元數(shù)據(jù)反饋給存儲(chǔ)服務(wù)接口,最后將不重復(fù)的數(shù)據(jù)存入到存儲(chǔ)介質(zhì)中.重復(fù)數(shù)據(jù)刪除技術(shù)主要分為以下兩大類:(1)相同數(shù)據(jù)檢測(cè)技術(shù).相同數(shù)據(jù)主要包括相同文件及相同數(shù)據(jù)塊兩個(gè)層次.完全文件檢測(cè)(wholefiledetection,簡(jiǎn)稱WFD)技術(shù)主要通過hash技術(shù)[3]進(jìn)行數(shù)據(jù)挖掘;細(xì)粒度的相同數(shù)據(jù)塊主要通過固定分塊(fixed-sizedpartition,簡(jiǎn)稱FSP)檢測(cè)技術(shù)[4]、可變分塊(content-definedchunking,簡(jiǎn)稱CDC)檢測(cè)技術(shù)[4?7]、滑動(dòng)塊(slidingblock)技術(shù)[8]進(jìn)行重復(fù)數(shù)據(jù)的查找與刪除.(2)相似數(shù)據(jù)檢測(cè)和編碼技術(shù).利用數(shù)據(jù)自身的相似性特點(diǎn),通過shingle技術(shù)[8?12]、bloomfilter技術(shù)[6,13?15]和模式匹配技術(shù)[16,17]挖掘出相同數(shù)據(jù)檢測(cè)技術(shù)不能識(shí)別的重復(fù)數(shù)據(jù);對(duì)相似數(shù)據(jù)采用delta技術(shù)[10,11,18,19]進(jìn)行編碼并最小化壓縮相似數(shù)據(jù),以進(jìn)一步縮減存儲(chǔ)空間和網(wǎng)絡(luò)帶寬的占用.上述這些技術(shù)使得共享數(shù)據(jù)塊的文件之間產(chǎn)生了依賴性,幾個(gè)關(guān)鍵數(shù)據(jù)塊的丟失或錯(cuò)誤可能導(dǎo)致多個(gè)文件的丟失和錯(cuò)誤發(fā)生,因此它同時(shí)又會(huì)降低存儲(chǔ)系統(tǒng)的可靠性,為此,一些研究者又引入了冗余復(fù)制技術(shù)[7,20]和糾刪碼技術(shù)[12]等來提高重復(fù)數(shù)據(jù)刪除系統(tǒng)的可靠性.另外,因數(shù)據(jù)的檢測(cè)對(duì)比等過程導(dǎo)致大量的計(jì)算開銷,重復(fù)數(shù)據(jù)刪除技術(shù)對(duì)存儲(chǔ)系統(tǒng)的性能影響也很大,為此,一些研究者提出了一些關(guān)鍵技術(shù),如減輕磁盤瓶頸技術(shù)[21]、提高數(shù)據(jù)搜索速度的技術(shù)[22]和提高相似數(shù)據(jù)編碼速度的技術(shù)[19].基于目前的研究現(xiàn)狀,還有一些需要深入研究的方面,比如,如何充分挖掘數(shù)據(jù)的內(nèi)在特性,提出更為高效的重復(fù)數(shù)據(jù)刪除技術(shù),如何提高重復(fù)數(shù)據(jù)刪除系統(tǒng)的可靠性,如何提高重復(fù)數(shù)據(jù)刪除技術(shù)的性能,如何融合各種現(xiàn)有技術(shù),提高重復(fù)數(shù)據(jù)刪除技術(shù)的通用性、可擴(kuò)展性和自適應(yīng)性,等等.本文第1節(jié)討論相同數(shù)據(jù)檢測(cè)的各項(xiàng)技術(shù),并分析各技術(shù)的優(yōu)缺點(diǎn)和適用性.第2節(jié)首先討論用于相似數(shù)據(jù)檢測(cè)的各項(xiàng)技術(shù)及其特點(diǎn),然后介紹對(duì)相似數(shù)據(jù)進(jìn)行編碼的delta技術(shù).第3節(jié)介紹目前重復(fù)數(shù)據(jù)刪除技術(shù)的可靠性研究,并分析每種技術(shù)的特點(diǎn).第4節(jié)討論重復(fù)數(shù)據(jù)刪除技術(shù)的性能研究,分析為平衡系統(tǒng)空間和時(shí)間開銷所采用的一些技術(shù)方案及特點(diǎn).第5節(jié)對(duì)本文進(jìn)行總結(jié).1相同數(shù)據(jù)檢測(cè)技術(shù)相同數(shù)據(jù)檢測(cè)技術(shù)是將數(shù)據(jù)進(jìn)行劃分,找出相同的部分,并且以指針取代相同數(shù)據(jù)的存儲(chǔ).1.1完全文件檢測(cè)技術(shù)WFD技術(shù)是以文件為粒度查找重復(fù)數(shù)據(jù)的方法.如圖1所示,首先對(duì)整個(gè)文件進(jìn)行hash計(jì)算,然后將該值與已存儲(chǔ)的hash值進(jìn)行比較,如果檢測(cè)到相同的值,則僅將文件用指針替換,不進(jìn)行實(shí)際存儲(chǔ),否則存儲(chǔ)新文件.研究者將hash算法引入到重復(fù)數(shù)據(jù)刪除技術(shù)中,是利用了hash值可以唯一地表征特定的數(shù)據(jù)實(shí)體,通過hash技術(shù),數(shù)據(jù)被標(biāo)志為一個(gè)固定大小的值,比較該值,就可以判別數(shù)據(jù)的重復(fù)性.目前MD5和SHA1是應(yīng)用最NoStorehashvalueComparetostoredhashvalueDuplicateNoStorehashvalueComparetostoredhashvalueDuplicatedetectionJournalofSoftware軟件學(xué)報(bào)Vol.21,No.5,May2010廣泛的Hash算法[10,11],兩者的抗沖突性都比較好.FileMD5orSHAhashMatchMatch?YesFig1WFDtechniqueWindows2000的SIS(singleinstancestorage)[3]應(yīng)用該技術(shù)對(duì)具有20個(gè)不同WindowsNT映像的服務(wù)器進(jìn)行測(cè)試,結(jié)果表明總共節(jié)省了58%的存儲(chǔ)空間.基于hash算法的完全文件檢測(cè)技術(shù)具有兩個(gè)優(yōu)勢(shì):(1)在普通硬件下計(jì)算速度很快,加州大學(xué)研究表明[23],SHA-1是83MB/S,而MD5是227MB/S;(2)可以檢測(cè)到所有完全相同的文件,節(jié)省存儲(chǔ)空間較大.但是,該方法也有兩個(gè)主要缺點(diǎn):(1)對(duì)于較大的數(shù)據(jù)集,需要比較的范圍大,耗時(shí)多;(2)不能檢測(cè)不同文件內(nèi)部的相同數(shù)據(jù).1.2基于FSP算法的塊檢測(cè)技術(shù)完全文件檢測(cè)技術(shù)不能用于文件內(nèi)部的重復(fù)數(shù)據(jù)查找,因此有研究者提出了更細(xì)粒度——塊級(jí)別的重復(fù)數(shù)據(jù)檢測(cè).基于固定尺寸劃分算法(FSP)的相同數(shù)據(jù)塊檢測(cè)技術(shù)是使用固定大小的分塊策略在存儲(chǔ)系統(tǒng)中識(shí)別相同數(shù)據(jù)的方法,如圖2所示.該方法分3個(gè)步驟:(1)提供一個(gè)已經(jīng)預(yù)先定義好的塊的大小(該值獨(dú)立于所存取的數(shù)據(jù)內(nèi)容),所有文件均按照這個(gè)固定的塊大小進(jìn)行劃分[4];(2)每個(gè)劃分好的數(shù)據(jù)塊均通過哈希算法(MD5或SHA1)得到一個(gè)指紋值;(3)將該值與已存儲(chǔ)的塊指紋值進(jìn)行比對(duì),如果檢測(cè)到相同的值,則刪除其代表的數(shù)據(jù)塊,否則存儲(chǔ)新的數(shù)據(jù)塊.ComparetostoredhashvaluesFilestorehashvalueDuplicatedetectedMatchfound?NoFig.2IdenticaldatachunkdetectiontechniquebasedonFSPalgorithm[7]FSP檢測(cè)技術(shù)[7]基于FSP算法的相同數(shù)據(jù)塊檢測(cè)技術(shù)已應(yīng)用在很多領(lǐng)域,并具有如下兩個(gè)特征:(1)縮減存儲(chǔ)空間,如針對(duì)數(shù)據(jù)歸檔的網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)Venti[24]應(yīng)用該技術(shù)減少了大約30%的存儲(chǔ)空間;(2)減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量,如虛擬機(jī)優(yōu)化系統(tǒng)[25]通過該技術(shù)加速了在低帶寬網(wǎng)絡(luò)上的數(shù)據(jù)傳輸并改進(jìn)了內(nèi)存的性能.此外,基于FSP算法的相同數(shù)據(jù)檢測(cè)技術(shù)還可以提供很高的處理速度,適合于在交互性的環(huán)境中應(yīng)用[5].但是它也具有一定的局限性:對(duì)編輯和修改的序列很敏感,對(duì)于插入問題(在原來的數(shù)據(jù)流中某處插入少量新字節(jié),其他部分不變)和刪除問題(在原來的數(shù)據(jù)流中某處刪除少量新字節(jié))處理十分低效,不能智能地根據(jù)文件自身內(nèi)容的變化和文件之間的關(guān)聯(lián)關(guān)系進(jìn)行調(diào)整與優(yōu)化,基于此,研究者們提出了可變塊大小劃分的檢測(cè)技術(shù).1.3可變分塊檢測(cè)技術(shù)1.3.1基于CDC算法的檢測(cè)技術(shù)CDC算法是應(yīng)用Rabin指紋將文件分割成長(zhǎng)度大小不一的分塊策略[4,20].與固定分塊策略不同的是,它對(duì)文敖莉等:重復(fù)數(shù)據(jù)刪除技術(shù)919件進(jìn)行塊劃分的方法是基于文件內(nèi)容的,因此數(shù)據(jù)塊大小是可變的,如圖3所示,其過程有兩步:(1)一個(gè)文件按照CDC算法分為若干數(shù)據(jù)塊.圖3顯示了一個(gè)數(shù)據(jù)流或一個(gè)文件以及由虛垂直線表示的塊邊界.CDC算法首先從文件頭開始,將固定大小(互相重疊)的滑動(dòng)窗口中的數(shù)據(jù)看成組成文件的各個(gè)部分.在窗口的每個(gè)位置,該窗口中數(shù)據(jù)的一個(gè)指紋(Fingerprint)被計(jì)算出來.在實(shí)際中,鑒于Rabin指紋[26]計(jì)算的高效性及Rabin指紋函數(shù)的隨機(jī)性(對(duì)任意數(shù)據(jù)呈現(xiàn)出均勻分布),研究者們多使用其計(jì)算滑動(dòng)窗口內(nèi)容的指紋值.當(dāng)指紋滿足某個(gè)條件時(shí),如當(dāng)它的值模某個(gè)指定的整除數(shù)為0時(shí),則把此時(shí)窗口的位置作為塊的邊界.重復(fù)這個(gè)過程,直到整個(gè)文件數(shù)據(jù)都被分為塊.(2)劃分出的每個(gè)塊用hash函數(shù)(MD5[27],SHA-1[28]或更高的SHA標(biāo)準(zhǔn)[29]函數(shù))計(jì)算出它的指紋值并與已存儲(chǔ)的數(shù)據(jù)塊進(jìn)行對(duì)比,如果檢測(cè)到相同的指紋值,則刪除其代表的數(shù)據(jù)塊,否則存儲(chǔ)新的數(shù)據(jù)塊.Filesbreakpoint?StorehashvalueComparetostoredhashvaluesDuplicatedetectedSlidewindowFingerprintMatchfound?ChunkNoNoFig.3IdenticaldatachunkdetectiontechniquebasedonCDCalgorithm[7]CDC塊檢測(cè)技術(shù)[7]PPPastaPastiche備份系統(tǒng)[31]、基于值的網(wǎng)絡(luò)緩存系統(tǒng)[32]、DeepStore歸檔存儲(chǔ)系統(tǒng)[23]和低帶寬網(wǎng)絡(luò)系統(tǒng)LBFS[2]中.在LBFS中,系統(tǒng)針對(duì)數(shù)據(jù)分塊可能出現(xiàn)的病態(tài)現(xiàn)象(滑動(dòng)窗口數(shù)據(jù)的指紋值不能符合條件,因此塊的邊界不能確定,導(dǎo)致塊過大)進(jìn)行了改進(jìn),將塊大小進(jìn)行了限定,給出數(shù)據(jù)大小分塊的上、下限.綜上,根據(jù)CDC算法的特性,無論是插入還是刪除一小部分字節(jié),都只會(huì)影響一到兩個(gè)塊,其余的塊保持不變,即CDC方法在兩個(gè)相似對(duì)象(只相差幾個(gè)字節(jié))之間可以檢測(cè)出更多的冗余.但是,CDC算法也存在一定的局限性,它劃分的粒度絕大部分取決于期望塊的設(shè)定.如果該值設(shè)置得較小,那么,雖然粒度較細(xì),重復(fù)數(shù)據(jù)查找較為精確,但是額外存儲(chǔ)每塊信息的開銷很大;反之,如果該值設(shè)置得較大,則粒度過粗,重復(fù)數(shù)據(jù)刪除的效果不好.所以,如何權(quán)衡精確查找和額外開銷是一個(gè)難點(diǎn).1.3.2基于fingerdiff算法的檢測(cè)技術(shù)為了彌補(bǔ)CDC算法額外存儲(chǔ)空間開銷大的缺陷,研究者提出了fingerdiff算法[4],其核心思想是將沒有變化的塊盡可能地合并,以減少各個(gè)數(shù)據(jù)塊的元數(shù)據(jù)占用的存儲(chǔ)空間.應(yīng)用fingerdiff算法進(jìn)行相同數(shù)據(jù)塊檢測(cè)過程包含3個(gè)步驟:(1)一個(gè)文件按照CDC算法進(jìn)行子塊**的劃分.(2)每個(gè)子塊按照fingerdiff設(shè)置的最大子塊數(shù)進(jìn)行合并.(3)每個(gè)塊用hash函數(shù)計(jì)算出它的指紋值,然后對(duì)比已存儲(chǔ)的數(shù)據(jù)塊指紋值,如果檢測(cè)到相同的指紋值,則刪除其對(duì)應(yīng)的數(shù)據(jù)塊;否則將大塊進(jìn)行拆分,找到最小的不同數(shù)據(jù)塊進(jìn)行存儲(chǔ),其余塊仍然保持合并狀態(tài).以上CDC算法和fingerdiff算法的檢測(cè)技術(shù)存在兩個(gè)不足之處:(1)在可變分塊檢測(cè)過程中,對(duì)于一個(gè)文件對(duì)間較小的隨機(jī)改變,效果不好,兩種算法的適應(yīng)性很差;(2)兩種技術(shù)中數(shù)據(jù)塊的劃分都是根據(jù)內(nèi)容可變的,但該值在很大程度上取決于算法中期望塊大小的設(shè)定,而期望塊大小的選擇依賴于文件相似性程度和文件修改的位置,這對(duì)相同數(shù)據(jù)檢測(cè)的性能影響很大.因此,可以通過深入挖掘數(shù)據(jù)特征規(guī)律,自適應(yīng)地調(diào)整數(shù)據(jù)塊的大小,選擇符合數(shù)據(jù)特征和性能指標(biāo)的最佳塊大小.**子塊是組成塊的單位.在fingerdiff算法中用CDC算法劃分出的塊稱為子塊,之后子塊合并生成的塊稱為塊.920JournalofSoftware軟件學(xué)報(bào)Vol.21,No.5,May20101.4滑動(dòng)塊檢測(cè)技術(shù)滑動(dòng)塊檢測(cè)技術(shù)結(jié)合了固定塊大小檢測(cè)技術(shù)和可變塊大小檢測(cè)技術(shù)的優(yōu)點(diǎn),塊大小固定,管理簡(jiǎn)單[4].文獻(xiàn)[6]通過測(cè)試發(fā)現(xiàn),對(duì)大的簇,CDC的重復(fù)數(shù)據(jù)檢測(cè)性能較好,而滑動(dòng)塊技術(shù)對(duì)細(xì)粒度匹配更適用.如圖4所示,基于滑動(dòng)塊技術(shù)的相同塊檢測(cè)過程有4步:(1)一個(gè)文件用rsync求和校驗(yàn)(checksum)函數(shù)[33]和固定塊大小的滑動(dòng)窗口來計(jì)算文件對(duì)象的每個(gè)重疊塊的求和校驗(yàn)值.(2)對(duì)于每個(gè)塊,比較求和校驗(yàn)值與先前存儲(chǔ)的值.(3)若匹配,則利用更嚴(yán)格的SHA-1算法對(duì)塊進(jìn)行hash計(jì)算,并將SHA-1hash值與先前存儲(chǔ)的值進(jìn)行比較,從而進(jìn)行冗余檢測(cè).如果檢測(cè)到數(shù)據(jù)冗余,將其記錄后,滑動(dòng)窗口越過這個(gè)冗余塊繼續(xù)前移.而且先前已經(jīng)被劃分的塊和最近被檢測(cè)到冗余之前的這個(gè)碎片需要被記錄并且存儲(chǔ).(4)如果求和校驗(yàn)值或hash值不能匹配,則滑動(dòng)窗口繼續(xù)前移.如果滑動(dòng)窗口已經(jīng)移動(dòng)了一個(gè)塊大小的距離,但是仍然無法匹配到任何已經(jīng)被存儲(chǔ)的塊,則需要對(duì)這個(gè)塊進(jìn)行求和校驗(yàn)和SHA-1hash計(jì)算,并存儲(chǔ)在各自的表中,用作以后塊的比較對(duì)象.FilesComparetostoredchecksumvaluesMatchNoComparetostoredhashvaluesDuplicatedetectedSlidewindowMatchfound?Checksumfound?NoFig.4Identicaldatachunkdetectiontechniquebasedonslidingblockingmethod[7]圖4基于滑動(dòng)分塊方法的相同數(shù)據(jù)塊檢測(cè)技術(shù)[7]滑動(dòng)塊檢測(cè)技術(shù)的特點(diǎn)是對(duì)插入問題和刪除問題處理高效,并能檢測(cè)到更多的冗余數(shù)據(jù).(1)插入問題:如果一小部分字節(jié)被插入到一個(gè)對(duì)象中,則只有周圍的塊會(huì)改變,其他的塊仍將被識(shí)別出來并被匹配,并且一個(gè)長(zhǎng)度等于插入的字節(jié)數(shù)的碎片會(huì)產(chǎn)生出來.(2)刪除問題:刪除一小部分字節(jié)也會(huì)產(chǎn)生一個(gè)長(zhǎng)度等于塊大小減去被刪除部分字節(jié)長(zhǎng)度的碎片,其他塊不受影響.但滑動(dòng)塊檢測(cè)技術(shù)也存在一個(gè)不足:在插入和刪除問題中都會(huì)引入碎片,如何能夠準(zhǔn)確識(shí)別改變的數(shù)據(jù),不影響匹配數(shù)據(jù)塊,從而少產(chǎn)生額外的碎片將是一個(gè)研究的難點(diǎn).1.5小結(jié)本節(jié)介紹了相同數(shù)據(jù)檢測(cè)的5種技術(shù),重復(fù)數(shù)據(jù)的存在形式中有很大一部分是完全相同的數(shù)據(jù).文獻(xiàn)[5]采用具有不同相關(guān)性的數(shù)據(jù)集評(píng)估了完全文件(WFD)、固定分塊(基于FSP算法)、可變分塊檢測(cè)技術(shù)(基于CDC算法)檢測(cè)相同數(shù)據(jù)的效果,并給出了在變化的數(shù)據(jù)類型上使用這些方法所獲得的效果.如圖5所示,針對(duì)不同的測(cè)試集,WFD技術(shù)、基于FSP的檢測(cè)技術(shù)、基于CDC的檢測(cè)技術(shù)在數(shù)據(jù)類型比較分散的數(shù)據(jù)集上檢測(cè)效果都不佳,僅檢測(cè)到17%~30%的相同數(shù)據(jù),而在有潛在關(guān)聯(lián)關(guān)系的數(shù)據(jù)集中,基于CDC的檢測(cè)技術(shù)可檢測(cè)到60%左右的相同數(shù)據(jù),但WFD技術(shù)和基于FSP的檢測(cè)技術(shù)僅檢測(cè)到20%~30%的相同數(shù)據(jù).同時(shí),文獻(xiàn)[7]針對(duì)塊級(jí)別的相同數(shù)據(jù)檢測(cè)技術(shù),在IBM實(shí)驗(yàn)室真實(shí)數(shù)據(jù)集上測(cè)試,給出了基于FSP的檢測(cè)技CDCslidingblock集,Slidingblock技術(shù)在冗余度檢測(cè)和網(wǎng)絡(luò)存儲(chǔ)節(jié)省量上達(dá)到最優(yōu),基于CDC的檢測(cè)技術(shù)次之,基于FSP的檢測(cè)技術(shù)相對(duì)最差.而在額外存儲(chǔ)開銷方面(storageoverhead),Slidingblock技術(shù)為提取數(shù)據(jù)所引入的元數(shù)據(jù)等額外存儲(chǔ)開銷最多,最高達(dá)60%左右,基于FSP的檢測(cè)技術(shù)次之,最多引入50%的額外存儲(chǔ)開銷,基于CDC的檢測(cè)技術(shù)效果最佳,引入的存儲(chǔ)開銷相對(duì)最低.綜上所述,目前還沒有一種方法可以在所有數(shù)據(jù)集上都產(chǎn)生較好的結(jié)果,同時(shí)每種技術(shù)所需要的額外處理和存儲(chǔ)空間以及具體數(shù)據(jù)集的使用模式和典型的負(fù)載,都對(duì)檢測(cè)技術(shù)的選擇起著至關(guān)重要的影響.RateofduplicatebytesdetectedNetstoragereclaimed(Percentoftotalbytes)DuplicatesRateofduplicatebytesdetectedNetstoragereclaimed(Percentoftotalbytes)Duplicatesdetected(Percentoftotalbytes)Storageoverhead(Percentoftotalbytes)Duplicatesdetected(Percentoftotalbytes)DuplicatesdetectedContenttchunkingSimpletblocking48Blocksizeofexpectedchunksize(KB)SlidingblockingContenttchunkingSimpltblocking.6.50.80WFWFDFSPCDCDatesetwithstrongDatesetwithcorrelatedhighdiversityFig.5PerformancecomparisonofWFDtechniqueandidenticaldatachunkdetectiontechniquesbasedonFSPalgorithmandCDCalgorithm[5]圖5WFD技術(shù)與基于FSP算法和基于CDC算法的相同數(shù)據(jù)塊檢測(cè)技術(shù)的性能比較[5]Duplicatesdetected2520 55002 2(a)Ratioofduplicatebytesdetectedonthesamedataset(a)相同數(shù)據(jù)集下檢測(cè)出的重復(fù)字節(jié)率Netstoragereclaimed5050481632Blocksizeofexpectedchunksize(KB)(c)Netstoragereclaimedonthesamedataset(c)相同數(shù)據(jù)集下回收的凈存儲(chǔ) StorageoverheadSlidingSlidingblockingContenttchunkingSimpltblocking.0481632Blocksizeofexpectedchunksize(KB)(b)Storageoverheadonthesamedataset(b)相同數(shù)據(jù)集下的存儲(chǔ)開銷40Simpleblocking40ContentchunkingSlidingblocking0200Email-1Email-2Email-3 Email0Email-1Email-2Email-3Dataset(d)Ratioofduplicatebytesdetectedonsixdifferentdatasets(d)6種不同數(shù)據(jù)集下檢測(cè)出的重復(fù)字節(jié)率Fig.6PerformancecomparisonofidenticaldatachunkdetectiontechniquesbasedonFSPalgorithm,CDCalgorithm,andslidingblockingmethod[7]FSPCDC數(shù)據(jù)塊檢測(cè)技術(shù)的性能比較[7]為此,可得出如下結(jié)論:(1)目前,沒有一種方法可以作為通用的檢測(cè)技術(shù),因此,如何找到一個(gè)在時(shí)間開銷、空間開銷和匹配精度上都最佳的技術(shù)將是一個(gè)研究難點(diǎn);(2)如何在融合各技術(shù)特征的同時(shí),對(duì)數(shù)據(jù)特性進(jìn)行充分的分析和挖掘,找到其規(guī)律性來為系統(tǒng)開銷的縮減提供一種技術(shù)支持,也將是一個(gè)值得研究的問題.922JournalofSoftware軟件學(xué)報(bào)Vol.21,No.5,May20102相似數(shù)據(jù)檢測(cè)和編碼技術(shù)***從上一節(jié)的討論中可以看出,因?yàn)閿?shù)據(jù)自身相似性的特點(diǎn),除了刪除完全相同的數(shù)據(jù)可以縮減空間以外,研究發(fā)現(xiàn)相似數(shù)據(jù)的檢測(cè)和編碼處理也可以大幅度地減少存儲(chǔ)空間,提高各種資源的利用率[10,11].2.1相似數(shù)據(jù)檢測(cè)技術(shù)2.1.1基于shingle的檢測(cè)技術(shù)在相似性檢測(cè)搜索中,理論上可以用像unixdiff這樣的程序把查詢文檔和系統(tǒng)中所有文檔進(jìn)行逐一比較[16],找到所有與其相似的文檔.但這種做法效率很低.為此,研究者們提出為每個(gè)文檔提取一組特征,這樣,文檔相似性問題就簡(jiǎn)化為集合相似性問題,如基于shingle的相似數(shù)據(jù)檢測(cè)技術(shù).目前,關(guān)于數(shù)據(jù)集合相似性的定義有多種表示形式,文獻(xiàn)[9]的定義如下:一個(gè)數(shù)據(jù)段D(可以是文件、數(shù)據(jù)塊等)中一個(gè)連續(xù)的子序列稱為一個(gè)shingle,D中所有大小為w的shingle)Bw)Bw包含性定義為由公式(1)、(2)可以看出,數(shù)據(jù)相似性rw(A,B)與w的取值和文件的大小有關(guān).設(shè)數(shù)據(jù)的大小為B,則S(D,w)中包含的shingle的個(gè)數(shù)為B?w+1,當(dāng)B較大時(shí),單純地對(duì)數(shù)據(jù)中所有shingle進(jìn)行相似性處理使得系統(tǒng)的開銷],因此研究者又提出了3種對(duì)shingle進(jìn)行取樣的技術(shù):Min-Wise[9,19],Modm[6]和Mins[12].Min-Wise技術(shù)是通過將shingle的長(zhǎng)度w和整數(shù)值進(jìn)行映射產(chǎn)生隨機(jī)哈希的公共集,在此相同的模式下進(jìn)行隨機(jī)最小獨(dú)立置換的采樣,從而得到采樣集合.Modm技術(shù)是通過在與Min-Wise同樣的公共映射集中選擇所有模m為0的哈希值對(duì)應(yīng)的shingle組成取樣集合.Mins技術(shù)同樣也是先將shingle和整數(shù)集進(jìn)行映射,然后從中選擇最小s個(gè)元素組成取樣集合.基于shingle的檢測(cè)技術(shù)已應(yīng)用到AltaVista搜索引擎[8]、基于群的大規(guī)模文件壓縮技術(shù)[19]、模糊文件塊匹配研究[12]和REBL(redundancyeliminationattheblocklevel)[11]的冗余消除技術(shù)中.為了將系統(tǒng)開銷最小化,REBL在Min-Wise的基礎(chǔ)上做了進(jìn)一步的優(yōu)化取樣.通過大量的實(shí)際應(yīng)用,研究者們發(fā)現(xiàn)shingle及Min-Wise,Modm和Mins技術(shù)簡(jiǎn)單易實(shí)現(xiàn),且適用性廣,但仍然存在一定的缺陷[6]:(1)shingling(Min-Wise,Modm,Mins)用兩個(gè)特征集的交集計(jì)算文件的相似性和包含性,計(jì)算開銷很高.(2)特征集的大小(shingle數(shù))決定了檢測(cè)相似數(shù)據(jù)的精度,其值又取決于shingling的取樣技術(shù),而取樣自身的誤差使得結(jié)果可能出現(xiàn)較大的偏差.2.1.2基于bloomfilter的檢測(cè)技術(shù)Bloomfilter[14]是一種集合的表示方法,能夠支持成員查詢(查詢某元素是否在該集合中).將bloomfilter技術(shù)引入到相似數(shù)據(jù)檢測(cè)中,可以彌補(bǔ)shingle中應(yīng)用特征集交集計(jì)算文件相似性所導(dǎo)致的高計(jì)算開銷,在性能與相似性匹配精度之間取得平衡.在副本同步消除冗余的技術(shù)[6]中,系統(tǒng)應(yīng)用bloomfilters進(jìn)行文件相似性檢測(cè),其中每個(gè)文件被看作是bloomfilter中定義的一個(gè)集合,它的元素是文件按照CDC算法所劃分出塊的指紋值.有相同指紋值集合的文件由相同的bloomfilter表示.相應(yīng)地,相似的文件在它們的bloomfilter中有大量共同的1.因?yàn)閎loomfilter存在一個(gè)有限的錯(cuò)誤匹配概率的特性,文獻(xiàn)[6]的作者證明了在他們所提出的CDC與bloomfilter相結(jié)合的技術(shù)中,錯(cuò)誤匹配的位的部分取決于bloomfilter的大小.***本文中,編碼技術(shù)是指相似數(shù)據(jù)檢測(cè)后最終存儲(chǔ)的技術(shù).與通常所說的哈夫曼編碼不同,該技術(shù)主要是用差分技術(shù)進(jìn)行編碼.敖莉等:重復(fù)數(shù)據(jù)刪除技術(shù)923大量數(shù)據(jù)集測(cè)試表明,bloomfilter應(yīng)用于相似性檢測(cè)時(shí),有以下幾個(gè)優(yōu)勢(shì):(1)bloomfilter對(duì)遠(yuǎn)程副本(存儲(chǔ)和傳輸)系統(tǒng)來說很具有吸引力,這些系統(tǒng)中元數(shù)據(jù)開銷通常很小.(2)bloomfilter使得快速匹配成為可能,因?yàn)槠ヅ涫前次慌c操作.(3)因?yàn)閎loomfilter是一個(gè)集合的完整表示,而不是一個(gè)確定性樣本(如shingling),所以它們可以有效地確定包含關(guān)系,如tar文件和庫.(4)因?yàn)閎loomfilter有較低的元數(shù)據(jù)開銷,所以可以進(jìn)一步與滑動(dòng)塊技術(shù)或CDC技術(shù)結(jié)合以減少匹配空間.但是,在眾多優(yōu)點(diǎn)之下,bloomfilter也存在著一個(gè)問題:在相似性檢測(cè)中,組成bloomfilter的元素集合是文件特征提取后的集合,而這些元素間的全排列順序沒有在bloomfilter的考慮范圍之內(nèi),這可能導(dǎo)致相似性的判斷與真實(shí)情況有所偏離.2.1.3基于模式匹配的檢測(cè)技術(shù)在相似數(shù)據(jù)檢測(cè)技術(shù)中,基于shingle及其變種的技術(shù)和bloomfilter成為發(fā)展的主流,但是也有部分學(xué)者研究模式匹配技術(shù)挖掘數(shù)據(jù)的特征,進(jìn)行相似數(shù)據(jù)檢測(cè).當(dāng)前,模式匹配技術(shù)的研究主要集中在兩個(gè)方面:單模式匹配和多模式匹配[17].單模式匹配算法和多模式匹配算法都是利用一定數(shù)量的公共子串進(jìn)行兩個(gè)文件間的相似性查找和判別.多模式匹配算法已應(yīng)用在大型文件系統(tǒng)中進(jìn)行相似數(shù)據(jù)的查找[16].綜合以上3種數(shù)據(jù)相似性檢測(cè)技術(shù)的研究可知,bloomfilter技術(shù)在系統(tǒng)時(shí)間開銷、空間開銷和匹配精度上比shingle技術(shù)略占優(yōu)勢(shì),而模式匹配技術(shù)需進(jìn)行文件的整體掃描.同時(shí),數(shù)據(jù)相似性檢測(cè)技術(shù)是刪除重復(fù)數(shù)據(jù)的重要組成部分,充分了解數(shù)據(jù)相似性匹配的規(guī)律,快速而準(zhǔn)確地找到相似的數(shù)據(jù)塊是決定重復(fù)數(shù)據(jù)刪除效果的重要因素.因此,從存儲(chǔ)系統(tǒng)性能的角度而言,亟待展開相似性檢測(cè)技術(shù)的適用性和系統(tǒng)開銷的實(shí)際研究.2.2相似數(shù)據(jù)編碼技術(shù)研究表明,在已有相似性檢測(cè)技術(shù)的基礎(chǔ)上,對(duì)具有較大相似度的數(shù)據(jù)進(jìn)行編碼處理,可以為整體系統(tǒng)節(jié)省大量的存儲(chǔ)空間[18].當(dāng)前,相似數(shù)據(jù)編碼技術(shù)主要為Delta編碼,它是通過用一個(gè)文件給另一個(gè)文件編碼的方式進(jìn)行數(shù)據(jù)的壓縮.這種編碼壓縮適用的范圍非常廣,其中包括存儲(chǔ)數(shù)據(jù)的多個(gè)版本、顯示差別、合并變化、發(fā)布更新、存儲(chǔ)備份、轉(zhuǎn)換視頻流等領(lǐng)域.diffdelta編碼技術(shù)Unix的diff[34,35]是生成delta編碼的經(jīng)典算法.它在版本控制和配置管理系統(tǒng)中使用最為廣泛.Diff算法的主要思想是通過考慮整行[34]來找到最長(zhǎng)公共子串的估計(jì)值.它并不檢查字節(jié)位置的所有可能的組合,因此比計(jì)算字節(jié)級(jí)別的最長(zhǎng)公共子串(longestcommonsubsequence,簡(jiǎn)稱LCS)要快很多.對(duì)兩個(gè)字符串,LCS的含義[18]是同時(shí)包含在這兩個(gè)字符串里的一個(gè)最長(zhǎng)字符序列,LCS的長(zhǎng)度是這兩個(gè)字符串相似性的很好的度量.版本控制系統(tǒng)SCCS(sourcecodecontrolsystem)和RCS(revisioncontrolsystem)[36,37]都應(yīng)用diff算法來存儲(chǔ)和顯示差別,RCS還用它進(jìn)行合并.通過存儲(chǔ)相對(duì)于一個(gè)基本版本的delta值,這些系統(tǒng)與存儲(chǔ)每個(gè)版本的整體的系統(tǒng)相比節(jié)省了大量的磁盤空間.但是diff算法有其局限性.它僅適用于文本文件的差異查找編碼,并且其粒度僅限于行查找(diff算法只能找到共同的行).當(dāng)對(duì)二進(jìn)制代碼進(jìn)行版本控制,而不僅僅是源文件文本時(shí),diff算法必須先把二進(jìn)制代碼映射為文本,然后再應(yīng)用diff.bdiffdelta編碼技術(shù)如今需要管理的數(shù)據(jù)有很多都是二進(jìn)制源文件格式[18],例如Word處理器文件,電子數(shù)據(jù)表數(shù)據(jù),電子和機(jī)械CAD數(shù)據(jù),聲音和圖像,然而,基于diff算法的編碼技術(shù)只能處理文本文件,因此研究者們針對(duì)這個(gè)問題提出了一種新的算法bdiff[18].Bdiff是一種壓縮算法,它與diff一樣,應(yīng)用了LCS度量方法,但它對(duì)任何字節(jié)流類型都適用,是Tichy提出的塊移動(dòng)算法的修改版本[38].文獻(xiàn)[18]通過實(shí)驗(yàn)對(duì)diff,bdiff和vdelta的性能進(jìn)行了比較,如圖7所示.從圖7可以看出,bdiff算法在文本文件和目標(biāo)文件的壓縮率上均優(yōu)于diff算法[18],但壓縮速率比diff算法要慢.Compressionratio(%)EncodingCompressionratio(%)EncodingtimeratioObject(a)ResultantcompressionratioforGNUGCCtextfilesandobjectfiles(a)對(duì)GNUGCC文本文件和對(duì)象文件的總壓縮率ObjectJournalofSoftware軟件學(xué)報(bào)Vol.21,No.5,May2010diffbdifdiffbdiffvdelta...100diffbdifdiffbdiffvdelta..0TText(b)RelativeencodingtimeratioforGNUGCCtextfilesandobjectfiles(b)對(duì)GNUGCC文本文件和對(duì)象文件的相對(duì)編碼速率Fig.7Performancecomparisonofdiff,bdiffandvdelta[18]fbdiffvdelta基于vdelta的delta編碼技術(shù)Vdelta是一種結(jié)合數(shù)據(jù)壓縮和數(shù)據(jù)差異的新技術(shù),同樣也應(yīng)用了LCS度量方法,對(duì)任何字節(jié)流類型都適用.Vdelta也是Tichy提出的塊移動(dòng)算法的改進(jìn)[38].它借鑒1978年Ziv-Lempel的壓縮技術(shù)的數(shù)據(jù)解析方法,使用哈希表方式建立索引,而不是bdiff中的后綴樹方式.經(jīng)大量測(cè)試分析,Vdelta和bdiff在壓縮率上都優(yōu)于diff算法[18],如圖7所示.對(duì)文本文件,bdiff和vdelta壓縮率較為接近,而對(duì)目標(biāo)代碼bdiff的壓縮效果最好.在壓縮速率上,vdelta壓縮時(shí)間最少,速度最快.2.3小結(jié)鑒于文件之間的相似性原理[9],利用以上各種檢測(cè)和編碼技術(shù)可以使數(shù)據(jù)占用空間大幅度縮減,但每種技術(shù)都有其各自的特點(diǎn)和不足.相似性檢測(cè)技術(shù)存在著如何平衡檢測(cè)精度和系統(tǒng)開銷的問題,而相似性編碼技術(shù)存在著編碼效率和適用范圍的問題.分析目前的研究現(xiàn)狀,可以得出如下結(jié)論:(1)目前,相似性檢測(cè)的3種技術(shù)在系統(tǒng)時(shí)間開銷、空間開銷和匹配精度上各有優(yōu)勢(shì),但是沒有一種技術(shù)同時(shí)具有這3個(gè)方面的特點(diǎn),如何融合這3種技術(shù)將是一個(gè)研究的難點(diǎn);(2)因相似性檢測(cè)技術(shù)在自身設(shè)計(jì)上存在局限性,如何通過結(jié)合統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘領(lǐng)域的各種技術(shù)(聚集、維規(guī)約、特征子集選擇、特征創(chuàng)建等)以及綜合考慮簡(jiǎn)單匹配系數(shù)相似、Jaccard系數(shù)相似、余弦相似等多種相似度來打破當(dāng)前各技術(shù)的局限,還需要進(jìn)一步研究;(3)在相似性編碼技術(shù)中,新的壓縮理論與技術(shù)和更有效的數(shù)學(xué)模型不斷出現(xiàn),如何通過引進(jìn)壓縮算法開發(fā)新的技術(shù),更有效地優(yōu)化儲(chǔ)存空間的使用,還需要進(jìn)一步研究.3重復(fù)數(shù)據(jù)刪除技術(shù)的可靠性研究重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用,使文件最終以共享數(shù)據(jù)對(duì)象或數(shù)據(jù)塊的引用集合存儲(chǔ).盡管該項(xiàng)技術(shù)與傳統(tǒng)的跨文件壓縮方法相比有很高的壓縮率,但它降低了存儲(chǔ)系統(tǒng)的可靠性,因?yàn)閹讉€(gè)關(guān)鍵數(shù)據(jù)塊的丟失或錯(cuò)誤可能導(dǎo)致許多文件的丟失和錯(cuò)誤發(fā)生.為了彌補(bǔ)這一缺陷,一些研究者對(duì)其可靠性進(jìn)行了深入的研究[7,12,20,23].3.1冗余復(fù)制技術(shù)一些研究者提出通過消除冗余所節(jié)省空間的一部分復(fù)制一些塊[7,20,23],策略性地增加冗余來提高系統(tǒng)可靠性.鑒于單純?yōu)樗袛?shù)據(jù)增加冗余所導(dǎo)致的大量空間消耗,研究者們提出了不同的處理方法:(1)提出根據(jù)塊的重要度來決定塊的重復(fù)度[7,20,23],它按照基于塊權(quán)重的復(fù)制方法來增加數(shù)據(jù)冗余.在該技敖莉等:重復(fù)數(shù)據(jù)刪除技術(shù)925術(shù)中設(shè)定即使一個(gè)塊只有一個(gè)依賴關(guān)系,也必須被保護(hù).所以其啟發(fā)式規(guī)則為每個(gè)塊保存至少兩個(gè)復(fù)制.文獻(xiàn)[20]提出的該可靠性技術(shù)模型不會(huì)影響重復(fù)數(shù)據(jù)刪除技術(shù)帶來的存儲(chǔ)空間的節(jié)約,它利用合適的啟發(fā)式規(guī)則和參數(shù)變化,占用大約一半的存儲(chǔ)空間,取得了比傳統(tǒng)跨文件壓縮方法更高的可靠性.(2)針對(duì)引用數(shù)據(jù)進(jìn)行冗余復(fù)制,即對(duì)實(shí)際有用的數(shù)據(jù),而非傳統(tǒng)的所有數(shù)據(jù)[7].研究發(fā)現(xiàn),引用數(shù)據(jù)或內(nèi)容固定的數(shù)據(jù)占據(jù)了日常數(shù)據(jù)量的大部分,并且增長(zhǎng)迅速[7].而引用數(shù)據(jù)的特征是存在大量的相似數(shù)據(jù),且不能被改變,并且需要保持很長(zhǎng)的時(shí)間.因此文獻(xiàn)[7]提出了一個(gè)針對(duì)引用數(shù)據(jù)實(shí)現(xiàn)的可靠性存儲(chǔ)系統(tǒng).該系統(tǒng)通過管理數(shù)據(jù)的唯一塊可靠、高效地存儲(chǔ)大量的相似數(shù)據(jù),并允許被選擇的數(shù)據(jù)被高效刪除.其中系統(tǒng)可靠性的設(shè)計(jì)是基于塊與塊之間的信息內(nèi)容來管理數(shù)據(jù)存儲(chǔ)的.(3)在不同應(yīng)用或?qū)哟紊显黾尤哂鄶?shù)據(jù)提高系統(tǒng)的可靠性.RAID[39]是通過引進(jìn)冗余并以此保證存儲(chǔ)系統(tǒng)的可靠性.OceanStore[40]對(duì)持久數(shù)據(jù)提高全局的連續(xù)訪問,并使用自動(dòng)復(fù)制策略來提高系統(tǒng)可靠性.FARSITE[41]是一個(gè)分布式系統(tǒng),它通過復(fù)制文件系統(tǒng)的元數(shù)據(jù)來提供可靠性.3.2糾刪碼技術(shù)在存儲(chǔ)系統(tǒng)中,單純地通過增加完全副本冗余來提高系統(tǒng)的可靠性并不能保證在錯(cuò)誤出現(xiàn)時(shí),數(shù)據(jù)仍具有持久性和可靠性.因此一些研究者提出利用糾刪碼技術(shù)對(duì)數(shù)據(jù)做一定的冗余來增加系統(tǒng)的可靠性[12].糾刪碼技術(shù)是指將要存儲(chǔ)的數(shù)據(jù)切分為k個(gè)部分,然后通過編碼算法變換為n(n>k)個(gè)部分,其中任意k′(k′≥k)個(gè)部分可以用來恢復(fù)原始數(shù)據(jù)[42].當(dāng)k′=k時(shí),稱編碼算法具有最大距離分割性質(zhì)(maximumdistanceseparable,簡(jiǎn)稱MDS).糾刪碼主要分為4大類:ReedSolomonCodes,ParityArrayCodes,Parity-checkCodes和LDPC(lowdensityparitycheck)Codes.其中,ReedSolomonCodes是基于有限域運(yùn)算的,后三者主要是基于XOR運(yùn)算.每種糾刪碼(erasurecodes)都有其各自的優(yōu)缺點(diǎn):(1)ReedSolomon碼:①M(fèi)DS碼,具有最優(yōu)的存儲(chǔ)利用率;②容錯(cuò)能力k′可以為任意數(shù);③數(shù)據(jù)出度總是大于k′,從而有較高的更新(update)復(fù)雜度;④復(fù)雜的代數(shù)運(yùn)算.(2)ParityArray碼:主要是通過單元的二維空間幾何分布構(gòu)成的,適用于RAID系統(tǒng).(3)Parity-check碼:從奇偶校驗(yàn)碼發(fā)展而來的多維碼,特點(diǎn)是簡(jiǎn)單且完全基于XOR運(yùn)算,容易實(shí)現(xiàn),且更新(update)和解碼(decode)等操作都具有較好的局部性,其缺點(diǎn)是非MDS,主要適合于大規(guī)模存儲(chǔ)系統(tǒng).(4)LDPC碼:基于Tanner圖發(fā)展起來的一維碼,其構(gòu)造主要是基于圖論和蒙特卡洛法.其優(yōu)點(diǎn)是可以完全用XOR運(yùn)算實(shí)現(xiàn),并且其存儲(chǔ)利用率接近MDS.其解碼算法主要是采用迭代方法實(shí)現(xiàn),可以達(dá)到很高的容錯(cuò)能力,但是容錯(cuò)能力越高,其構(gòu)造越不規(guī)則,從而導(dǎo)致不易實(shí)現(xiàn).目前在重復(fù)數(shù)據(jù)刪除系統(tǒng)中應(yīng)用糾刪碼技術(shù)來提高系統(tǒng)可靠性的研究還較為簡(jiǎn)單,僅局限于ReedSolomon糾刪碼,因此,如何引入其他糾刪碼技術(shù)提高系統(tǒng)可靠性,將有待進(jìn)一步的研究.3.3小結(jié)通過上述論述可知,提高系統(tǒng)可靠性的兩種主要技術(shù)本質(zhì)上都是基于增加冗余數(shù)據(jù),但又有其各自的適用范圍和技術(shù)特點(diǎn):(1)冗余復(fù)制技術(shù)主要是完全副本拷貝,在進(jìn)行相同數(shù)據(jù)塊檢測(cè)和刪除時(shí),應(yīng)用該技術(shù)適度地加入冗余,可在保證節(jié)省磁盤空間和網(wǎng)絡(luò)帶寬的前提下,增加系統(tǒng)的可靠性.(2)糾刪碼技術(shù)主要是通過差分控制編碼,進(jìn)行數(shù)據(jù)的檢錯(cuò)和糾錯(cuò),相對(duì)于完全副本方式,糾刪碼帶來了一定的計(jì)算量,也增加了系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的復(fù)雜度.但在一定情況下,它也能在增加較少冗余數(shù)據(jù)的情況下提供與完全副本方式相同的可靠性.因此,如何挖掘數(shù)據(jù)的各種特性,針對(duì)不同的數(shù)據(jù)類型,設(shè)計(jì)有效的度量方式,適度地增加副本或校驗(yàn)碼以高效地提高系統(tǒng)的可靠性,是一個(gè)需要深入研究的問題.(3)因重復(fù)數(shù)據(jù)刪除技術(shù)固有的風(fēng)險(xiǎn)——硬件故障引起的災(zāi)難性數(shù)據(jù)丟失,單純地利用增加冗余數(shù)據(jù)的方法效果不佳,因此需要引入其他機(jī)制,如RAID-5奇偶校驗(yàn)、不同數(shù)據(jù)替代、錯(cuò)誤檢測(cè)與恢復(fù)等技術(shù),同時(shí)結(jié)合硬件和故障統(tǒng)計(jì)數(shù)據(jù),如磁盤的故障間平均時(shí)間,解決數(shù)據(jù)分布或塊存儲(chǔ)問題,以提高系統(tǒng)的可靠性.JournalofSoftware軟件學(xué)報(bào)Vol.21,No.5,May20104重復(fù)數(shù)據(jù)刪除技術(shù)的性能研究數(shù)據(jù)的檢測(cè)對(duì)比等過程都需要消耗大量的系統(tǒng)資源,嚴(yán)重影響存儲(chǔ)系統(tǒng)中數(shù)據(jù)訪問的性能.因此,為了提高系統(tǒng)性能,研究者們提出了一些解決方案.4.1減輕磁盤瓶頸技術(shù)在重復(fù)數(shù)據(jù)刪除系統(tǒng)中,為了節(jié)約成本,一些系統(tǒng)僅有少量的內(nèi)存,因而不能支持所有的數(shù)據(jù)索引一次性地進(jìn)入內(nèi)存進(jìn)行檢測(cè),從而導(dǎo)致了大量的磁盤訪問.針對(duì)這種情況,文獻(xiàn)[21]中描述了DataDomain重復(fù)數(shù)據(jù)刪除文件系統(tǒng)中用于減輕磁盤瓶頸的3種技術(shù):摘要向量、基于流的塊排列和局部性保持.應(yīng)用這3種技術(shù),實(shí)現(xiàn)了一個(gè)高吞吐率、低開銷的相同塊刪除存儲(chǔ)系統(tǒng).(1)摘要向量技術(shù)摘要向量技術(shù)用于減少在磁盤中查找不存在塊的次數(shù).摘要向量可以看作是一種處于內(nèi)存中,對(duì)塊索引的摘要.如果摘要向量指出一個(gè)塊不在索引內(nèi),則不需要進(jìn)一步查找.如果摘要向量指出這個(gè)塊在塊索引中,那么很有可能這個(gè)塊就在塊索引內(nèi),但并不是一定的,因?yàn)檎蛄坷肂loomfilter來實(shí)現(xiàn),一個(gè)Bloomfilter用一個(gè)m位向量來概括在塊索引中n個(gè)塊指紋值的存在信息,且Bloomfilter的特點(diǎn)是允許錯(cuò)誤肯定(認(rèn)為一個(gè)不在集合中的元素在集合中)的存在.因?yàn)檎蛄渴窃趦?nèi)存中的數(shù)據(jù)結(jié)構(gòu),所以系統(tǒng)關(guān)機(jī)后,會(huì)將其寫到disk上,啟動(dòng)后,又會(huì)從disk上讀入內(nèi)存中.為了處理停電和不正常的關(guān)機(jī)情況,系統(tǒng)會(huì)周期性地將摘要向量備份到磁盤上,并設(shè)置檢查點(diǎn).當(dāng)恢復(fù)時(shí),系統(tǒng)會(huì)載入最近備份的副本,并處理從最近一個(gè)檢查點(diǎn)添加到系統(tǒng)中的數(shù)據(jù),將其信息加入到摘要向量中.(2)基于流的塊排列技術(shù)基于流的塊排列技術(shù)(stream-informedsegmentlayout,簡(jiǎn)稱SISL)為塊數(shù)據(jù)和塊描述符提供了更好的空間局部性,并且使局部cache緩存成為可能.SISL主要特點(diǎn)是針對(duì)同一個(gè)數(shù)據(jù)流,使得新數(shù)據(jù)塊被存放在一起,塊描述符也被存放在一起.SISL能夠帶來以下益處:①當(dāng)同一個(gè)數(shù)據(jù)流的多個(gè)數(shù)據(jù)塊被寫入到同一個(gè)容器中時(shí),在進(jìn)行讀取操作重建這個(gè)數(shù)據(jù)流時(shí),可以大幅減少磁盤I/O次數(shù),使系統(tǒng)達(dá)到較高的讀性能.②在同一數(shù)據(jù)流中,相鄰新數(shù)據(jù)塊的塊描述符和壓縮數(shù)據(jù)分別被線性地裝入相同容器的元數(shù)據(jù)段和數(shù)據(jù)段.這種裝入方法為其后相似的數(shù)據(jù)流提供了一種訪問局部性,使得cache的局部緩存工作更有效.③元數(shù)據(jù)段和數(shù)據(jù)段分開存儲(chǔ),而且元數(shù)據(jù)段比數(shù)據(jù)段要小得多.(3)局部性保持技術(shù)系統(tǒng)利用局部性保持技術(shù)(localitypreservedcaching,簡(jiǎn)稱LPC)來加速辨認(rèn)重復(fù)塊的過程.針對(duì)重復(fù)數(shù)據(jù)檢測(cè),傳統(tǒng)的Cache并不適用于緩存指紋值、哈希值或者描述符,因?yàn)橹讣y值在本質(zhì)上是隨機(jī)的.因此,如果沒有進(jìn)行完全的索引訪問,預(yù)言下一個(gè)塊的索引位置是非常困難的,從而也導(dǎo)致了傳統(tǒng)cache的命中率是非常低的.LPC的應(yīng)用使得塊重復(fù)局部性提高,如果一個(gè)塊是重復(fù)的,那么附近的塊很可能已經(jīng)被緩存了.實(shí)驗(yàn)結(jié)果表明,在重復(fù)數(shù)據(jù)刪除的現(xiàn)實(shí)環(huán)境中,把以上3種技術(shù)結(jié)合在一起,可以省去99%的磁盤訪問.這些CPU柜,即可達(dá)到100MB/s的單工流吞吐率和210MB/s的雙工流吞吐率[30].4.2提高數(shù)據(jù)搜索速度的技術(shù)重復(fù)數(shù)據(jù)的檢測(cè)比對(duì)過程給系統(tǒng)帶來了巨大的時(shí)間開銷.當(dāng)數(shù)據(jù)的所有特征存在于1個(gè)索引中時(shí)會(huì)導(dǎo)致系統(tǒng)的可擴(kuò)展性差,同時(shí)導(dǎo)致特征值匹配的時(shí)間開銷過大,因此一些研究者提出了提高數(shù)據(jù)搜索匹配速度的關(guān)鍵技術(shù):把索引分片為多個(gè)小索引,并存儲(chǔ)在多個(gè)服務(wù)器上,增加搜索的可擴(kuò)展性及可并行性[22].同時(shí),當(dāng)有新文檔加入系統(tǒng)時(shí),選擇一部分分片服務(wù)器來存儲(chǔ)它的特征;在重復(fù)數(shù)據(jù)搜索時(shí),也只在一部分分片服務(wù)器上查詢.為了加速搜索的速度,文獻(xiàn)[22]提出了一個(gè)新的索引分片和文檔路由策略.它將一個(gè)文檔的所有特征路由在一起,而并不把文檔的每個(gè)特征獨(dú)立地路由.在吸收文檔時(shí),文檔路由策略用特征提取算法提取出文檔的特征集,基于這些特征,選擇一部分索引分片.文檔被路由到這些分片上,并加入那里的索引中.在查詢時(shí),用同樣的特敖莉等:重復(fù)數(shù)據(jù)刪除技術(shù)927征提取和文檔路由算法選擇查詢的分片,在所選擇的分片上查詢?cè)撐臋n的特征,并把結(jié)果進(jìn)行歸并.實(shí)驗(yàn)結(jié)果表明,快速搜索技術(shù)解決了數(shù)據(jù)匹配中時(shí)間復(fù)雜度較高的問題,并且擴(kuò)展性很好,對(duì)搜索結(jié)果的準(zhǔn)確性和回取的影響很小.4.3提高相似數(shù)據(jù)編碼速度的技術(shù)在對(duì)大規(guī)模文件使用delta壓縮時(shí),一些研究者發(fā)現(xiàn)Delta壓縮技術(shù)雖然能夠有效地減少數(shù)據(jù)的占用空間[19],但因delta壓縮簡(jiǎn)潔地描述某一文件相對(duì)于另一文件的編碼,使得數(shù)據(jù)最終壓縮比與參考文件的選擇存在密切的關(guān)系.因此,文獻(xiàn)[19]研究了一種優(yōu)化的delta編碼技術(shù),為基于群的Delta壓縮提出一種新的框架.在這種框架下,使用文本群技術(shù)以削剪可能出現(xiàn)雙delta編碼的圖,使得在帶權(quán)有向圖中計(jì)算有最大權(quán)重分支的編碼效率較低的問題得到改善.基于群的Delta壓縮編碼技術(shù)的基本思想是將完全圖G修剪成稀疏子圖G′,然后在這個(gè)子圖中找到最佳delta編碼方案.經(jīng)實(shí)驗(yàn)測(cè)試,對(duì)集合的基于群的delta壓縮與對(duì)每個(gè)文件單獨(dú)使用tar和gzip進(jìn)行壓縮相比,在壓縮率上有重大的改進(jìn).4.4小結(jié)本節(jié)介紹了重復(fù)數(shù)據(jù)刪除技術(shù)的性能研究情況,各項(xiàng)技術(shù)都在不同程度上提高了系統(tǒng)的性能.(1)減輕磁盤瓶頸的幾種技術(shù)在DataDomain的重復(fù)數(shù)據(jù)刪除文件系統(tǒng)下實(shí)現(xiàn),減少了98.94%的磁盤訪問[21],且該技術(shù)具有可擴(kuò)展性和通用性.(2)提高數(shù)據(jù)搜索速度的技術(shù)主要是解決了數(shù)據(jù)匹配中時(shí)間復(fù)雜度較高的問題.它利用增加服務(wù)器的方法來解決.(3)提高相似數(shù)據(jù)編碼速度的技術(shù)對(duì)系統(tǒng)的時(shí)間和空間開銷均有一定的改善,對(duì)該技術(shù)局限于每個(gè)目標(biāo)文件相對(duì)于一個(gè)單獨(dú)的參照文件進(jìn)行編碼壓縮處理的情況,并且只將壓縮和解壓作為一個(gè)整體集合考慮,不允許單個(gè)文件加到集合中或者從集合中取回.分析目前的研究現(xiàn)狀,我們可以得出如下結(jié)論:(1)目前,在重復(fù)數(shù)據(jù)刪除系統(tǒng)中,提高系統(tǒng)性能的各關(guān)鍵技術(shù)均有一定的缺陷.如何借鑒已有技術(shù)的優(yōu)點(diǎn),設(shè)計(jì)高效通用的技術(shù)方案,將系統(tǒng)空間時(shí)間開銷綜合起來考慮,需要更深入的研究.(2)在提高相似數(shù)據(jù)編碼速度的技術(shù)中,因編碼參考文件選擇的重要性,如何將單一參考文件進(jìn)行擴(kuò)展,利用一些新的局部最小求解算法,如螞蟻算法、擬物算法等,選擇最佳的參考文件進(jìn)行編碼,大幅度提高壓縮率,優(yōu)化儲(chǔ)存空間的使用也是一個(gè)值得研究的問題.5結(jié)束語隨著數(shù)字信息的爆炸式增長(zhǎng),重復(fù)數(shù)據(jù)的存在形式有很多,從文件級(jí)和數(shù)據(jù)塊級(jí)完全相同的數(shù)據(jù)到字節(jié)級(jí)的相似數(shù)據(jù)都存在著可探究的空間.針對(duì)相同文件,研究者提出利用hash技術(shù)提取文件特征進(jìn)行全文件數(shù)據(jù)的檢測(cè)和匹配,然而由于比較粒度較粗,不能檢測(cè)和消除實(shí)現(xiàn)更多的相同數(shù)據(jù)的冗余,于是,研究者又提出了基于塊的相同數(shù)據(jù)檢測(cè)技術(shù)(如,固定塊大小、可變塊大小和滑動(dòng)塊檢測(cè)技術(shù)),但這些技術(shù)沒有有效利用細(xì)粒度數(shù)據(jù)相似的特性,在某種程度上降低了重復(fù)數(shù)據(jù)匹配的性能,因此,一些研究者們又提出了字節(jié)級(jí)別的相似數(shù)據(jù)刪除技術(shù),其中包括shingle、bloomfilter、模式匹配檢測(cè)技術(shù)和delta編碼技術(shù).與此同時(shí),因重復(fù)數(shù)據(jù)刪除技術(shù)導(dǎo)致的系統(tǒng)可靠性和性能問題,一些研究者又針對(duì)重復(fù)數(shù)據(jù)刪除技術(shù)的可靠性和性能進(jìn)行了研究.在此基礎(chǔ)上,本文綜合分析了目前重復(fù)數(shù)據(jù)刪除各項(xiàng)技術(shù)研究的現(xiàn)狀,探討了重復(fù)數(shù)據(jù)刪除的發(fā)展趨勢(shì).從目前的研究來看,我們可以得出如下結(jié)論:(1)如何挖掘不同類型的數(shù)據(jù)特性,快速而準(zhǔn)確地檢測(cè)到重復(fù)數(shù)據(jù),同時(shí)具有較低的空間開銷,仍然存在著可探究的空間.(2)因數(shù)據(jù)相似性檢測(cè)技術(shù)設(shè)計(jì)上存在一定的局限性,如何在融合各技術(shù)特征的同時(shí),通過結(jié)合統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘領(lǐng)域的各種技術(shù),對(duì)數(shù)據(jù)特性進(jìn)行充分的分析和挖掘,找到其規(guī)律性的認(rèn)識(shí)來彌補(bǔ)重復(fù)數(shù)據(jù)刪除技術(shù)上的不足,提高整體系統(tǒng)的性能,還需要進(jìn)一步研究.(3)因新的壓縮理論與技術(shù)或更有效的數(shù)學(xué)模型不斷出現(xiàn),如何通過引進(jìn)壓縮算法開發(fā)新的技術(shù)或?qū)⒁延屑夹g(shù)結(jié)合在一起,有效地優(yōu)化儲(chǔ)存空間,還需要進(jìn)一步研究.(4)已有的可靠性技術(shù)是基于增加冗余數(shù)據(jù)的,其技術(shù)模型具有簡(jiǎn)單、高效的特點(diǎn),但在存儲(chǔ)開銷和系統(tǒng)性能方面存在一定的局限性.因此,如何針對(duì)不同的數(shù)據(jù)類型,適度地JournalofSoftware軟件學(xué)報(bào)Vol.21,No.5,May2010增加冗余數(shù)據(jù)來提高系統(tǒng)的可靠性或引入其他機(jī)制的可靠性設(shè)計(jì),還需要進(jìn)一步研究.(5)在重復(fù)數(shù)據(jù)刪除的過程中,額外增加的系統(tǒng)開銷是不可忽略的,在實(shí)際應(yīng)用過程中,常常需要在簡(jiǎn)單性和性能兩方面做出折衷選擇.因此,如何在融合各種現(xiàn)有技術(shù)的同時(shí),提供通用性、可擴(kuò)展性和自適應(yīng)性,盡可能地減少重復(fù)數(shù)據(jù)檢測(cè)和刪除所帶來的系統(tǒng)開銷,還需要進(jìn)一步研究.References:[1]McKnightJ,AsaroT,BabineauB.Digitalarchiving:End-Usersurveyandmarketforecast2006-2010.2006./ESGPublications/ReportDetail.asp?ReportID=591[2]MuthitacharoenA,ChenB,MaziéresD.Alow-bandwidthnetworkfilesystem.In:Proc.ofthe18thACMSymp.onOperatingSystemPrinciples(SOSP2001).NewYork:ACMPress,2001.174?187.[3]BoloskyWJ,CorbinS,GoebelD,DouceurJR.SingleinstancestorageinWindows2000.In:Proc.ofthe4thUsenixWindowsSystemSymp.Berkeley:USENIXAssociation,2000.13?24.[4]BobbarjungDR,JagannathanS,DubnickiC.Improvingduplicateeliminationinstoragesystems.ACMTrans.onStorage,2006,2(4):424?448.[5]PolicroniadesC,PrattI.Alternativesfordetectingredundancyinstoragesystemsdata.In:Proc.ofthe2004USENIXAnnualTechnicalConf.(USENIX2004).Berkeley:USENIXAssociation,2004.73?86.[6]JainN,DahlinM,TewariR.Taper:Tieredapproachforeliminatingredundancyinreplicasynchronization.In:Proc.ofthe4thUsenixConf.onFileandStorageTechnologies(FAST2005).Berkeley:USENIXAssociation,2005.281?294.[7]DenehyTE,HsuWW.Duplicatemanagementforreferencedata.IBMResearchReport,RJ10305(A0310-017),IBMResearchDivision,2003.[8]BroderAZ.Identifyingandfilteringnear-duplicatedocuments.In:GiancarloR,SankoffD,eds.Proc.ofthe11thAnnualSymp.onCombinatorialPatternMatching.London:Springer-Verlag,2000.1?10.[9]BroderAZ.Ontheresemblanceandcontainmentofdocuments.In:CarpentieriB,DeSantisA,VaccaroU,StorerJA,eds.Proc.oftheCompressionandComplexityofSEQUENCES1997.Washington:IEEEComputerSocietyPress,1997.21?29.[10]DouglisF,IyengarA.Application-Specificdeltaencodingviaresemblancedetection.In:Proc.ofthe2003USENIXAnnualTechnicalConf.(USENIX2003).Berkeley:USENIXAssociation,2003.113?126.[11]KulkarniP,DouglisF,LavoieJD,TraceyJM.Redundancyeliminationwithinlargecollectionsoffiles.In:Proc.ofthe2004UsenixAnnualTechnicalConf.(USENIX2004).Berkeley:USENIXAssociation,2004.59?72.[12]HanB,KeleherP.Implementationandperformanceevaluationoffuzzyfileblockmatching.In:Proc.ofthe2007USENIXAnnualTechnicalConf.(USENIX2007).Berkeley:USENIXAssociation,2007.199?204.[13]BloomBH.Space/timetrade-offsinhashcodingwithallowableerrors.CommunicationsoftheACM,1970,13(7):422?426.[doi:10.1145/362686.362692][14]BroderAZ,MitzenmacherM.Networkapplicationsofbloomfilters:Asurvey.InternetMathematics,2003,1(4):485?509.[15]MitzenmacherM.Compressedbloomfilters.IEEE/ACMTrans.onNetworking(TON),2002,10(5):604–612.[doi:10.1109/TNET.2002.803864][16]ManberU.Findingsimilarfilesinalargefilesystem.In:Proc.oftheUSENIXWinter1994TechnicalConf.Berkeley:USENIXAssociation,1994.1–10.[17]WuS,ManberU.Agrep—Afastapproximatepattern-matchingtool.In:Proc.oftheUSENIXWinter1992TechnicalConf.Berkeley:USENIXAssociation,1992.153–162.[18]HuntJJ,VoKP,TichyWF.Deltaalgorithmsanempiriecalanalysis.ACMTrans.onSoftwareEngineeringandMethodology,1998,7(4):192–214.[doi:10.1145/279310.279321][19]OuyangZ,MemonN,SuelT,TrendafilovD.Cluster-Baseddeltacompressionofacollectionoffiles.In:Proc.ofthe3rdInt’lConf.onWebInformationSystemsEngineering.Washington:IEEEComputerSocietyPress,2006.257–266.[20]BhagwatD,PollackK,LongDDE,SchwarzT,MillerEL,ParisJF.Providinghighreliabilityinaminimumredundancyarchivalstoragesystem.In:Proc.ofthe14thInt’lSymp.onModeling,Analysis,andSimulationofComputerandTelecommunicationSystems(MASCOTS2006).Washington:IEEEComputerSocietyPress,2006.413–421.[21]Zhu