重復(fù)數(shù)據(jù)刪除技術(shù)現(xiàn)狀及發(fā)展方向

1、重復(fù)數(shù)據(jù)刪除技術(shù)重復(fù)數(shù)據(jù)刪除技術(shù)的現(xiàn)狀與發(fā)展方向現(xiàn)狀與發(fā)展方向朱立谷中國傳媒大學(xué)計(jì)算機(jī)學(xué)院，北京100024(email:lgzhu@cuc.)1.概述概述重復(fù)數(shù)據(jù)刪除(datadeduplication)也稱為智能壓縮(intelligentcompression)或單一實(shí)例存儲(singleinstancestage)，是一種可自動搜索重復(fù)數(shù)據(jù)，將相同的數(shù)據(jù)只保留唯一的一個副本，并使用指向單一副本的指針替換掉其它重復(fù)副本，以達(dá)到消除

2、數(shù)據(jù)冗余、降低存儲容量需求的存儲技術(shù)。常見的重復(fù)數(shù)據(jù)刪除有兩種：文件復(fù)制消除可以識別兩個文件名不同但是內(nèi)容完全相同的文件，或者不同目錄下相同的文件，可以避免相同文件的多次存儲；數(shù)據(jù)塊冗余消除比文件復(fù)制消除的存儲效率更高，它可以在文件中搜索相同的數(shù)據(jù)塊，將相同的塊保存一個唯一的副本。重復(fù)數(shù)據(jù)刪除是一種獨(dú)特存儲技術(shù)，分析師認(rèn)為它可能是存儲行業(yè)最重要的一項(xiàng)新興技術(shù)，將改寫存儲行業(yè)的經(jīng)濟(jì)規(guī)則：借助于重復(fù)數(shù)據(jù)刪除技術(shù)，使得實(shí)際存檔的數(shù)據(jù)呈幾何級別

3、遞減，用戶的存檔數(shù)據(jù)所占用的空間將會縮減為現(xiàn)在的5%，從而大幅削減存儲成本。2.2.重復(fù)數(shù)據(jù)刪除重復(fù)數(shù)據(jù)刪除的技術(shù)技術(shù)原理原理重復(fù)數(shù)據(jù)刪除利用文件之間和文件內(nèi)的相同和相似性，處理的粒度可以文件、數(shù)據(jù)塊、字節(jié)甚至位，處理粒度越細(xì)，刪除冗余數(shù)據(jù)越多，存儲容量減少越大，但處理消耗的計(jì)算資源更多。2.12.1文件相似性文件相似性為了理解文件相似性對重復(fù)數(shù)據(jù)刪除效率的重要性，首先我們看看相似性與存儲量之間的關(guān)系。數(shù)據(jù)的相似性變化范圍極大，壓縮效率

4、變化范圍也很大，然而，文件相似性和文件壓縮量之間的關(guān)系是相同的。使用不同版本的Linux的源代碼來評估文件相似性，對gzip壓縮（僅文件內(nèi)壓縮）與delta壓縮（文件內(nèi)文件間壓縮）進(jìn)行比較，結(jié)果見圖1：在8萬多個文件(1GB大小)中，有相當(dāng)多的文件具有很高的相似性，事實(shí)上，很多是相同的，gzip壓縮后文件體積減少到原來的25％到30％，delta壓縮后文件體積減少到原來的4%。這表明利用文件相似性對文件內(nèi)和文件間壓縮大有好處，對文件內(nèi)和

5、文件間的冗余數(shù)量進(jìn)行刪除實(shí)現(xiàn)高壓縮是可能的，即使包含壓縮計(jì)算產(chǎn)生的索引數(shù)據(jù)，因?yàn)檫@些數(shù)據(jù)不足原始數(shù)據(jù)總大小的1％。MD5和SHA1可以說是目前應(yīng)用最廣泛的Hash算法。MD5(RFC1321)是對輸入以512位分組，其輸出是4個32位字的級聯(lián)，盡管MD5被破解過，但仍然比較安全；SHA1產(chǎn)生長度為160位的Hash值，因此抗窮舉(brutefce)性更好。Hash算法可以看作管道，文件內(nèi)容從一端流入，文件或數(shù)據(jù)塊的Hash就從另一端流出

6、，如圖2所示。在存儲領(lǐng)域中，Hash算法首先被應(yīng)用于內(nèi)容尋址存儲（ContentAddreeableStage，CAS），它用于在存儲系統(tǒng)中唯一地表征特定的數(shù)據(jù)實(shí)體，稱為內(nèi)容地址（ContentAddress，CA）或數(shù)字指紋（fingerprint）。在CAS中，通過Hash實(shí)現(xiàn)一種獨(dú)特文件尋址與定位方法，并有效地消除文件復(fù)制。這可以說是重復(fù)數(shù)據(jù)刪除技術(shù)的一個開端，不過在重復(fù)數(shù)據(jù)刪除技術(shù)中，一個文件可以計(jì)算一個Hash，也可以分成多個

7、數(shù)據(jù)塊計(jì)算多個Hash。2.2.2.22.2全文件全文件HashHash用整個文件進(jìn)行Hash，然后對不同文件的Hash進(jìn)行排序，將相同的文件找出。這種方法好處是：在普通硬件條件下計(jì)算速度非常快，加州大學(xué)的研究表明，SHA1是83MBS，而MD5是227MBS；如果對很多文件進(jìn)行了處理，可以檢測到所有相同的文件，節(jié)省存儲空間是巨大的。這種方法的主要缺點(diǎn)是：即使不同文件存在很多相同的數(shù)據(jù)，也不能被檢測和實(shí)現(xiàn)冗余消除。2.22.2.3.3文

8、件分塊文件分塊HashHash文件分塊Hash的類似于數(shù)據(jù)壓縮技術(shù)，從本質(zhì)上講，數(shù)據(jù)壓縮就是要消除信息冗余。早期的數(shù)據(jù)壓縮技術(shù)就是基于編碼上的優(yōu)化技術(shù)，對信息進(jìn)行編碼時，如果為出現(xiàn)概率較高的字符串賦予較短的編碼，為出現(xiàn)概率較低的字母賦予較長的編碼，總的編碼長度就能縮短不少。統(tǒng)計(jì)文件里面的字符串概率要消耗很長的計(jì)算時間，實(shí)際的方法是采用自適應(yīng)編碼的方式，也就是在壓縮的時候統(tǒng)計(jì)字符串的概率?，F(xiàn)在應(yīng)用更多的數(shù)據(jù)壓縮技術(shù)是字典型的模式壓縮。字典

9、壓縮算法就是構(gòu)造一本實(shí)際的字典，通用算法使用的動態(tài)創(chuàng)建字典方法，把每一個第一次出現(xiàn)的字符串放入字典中，并用一個數(shù)字來表示，這個數(shù)字與此字符串在字典中的位置有關(guān)，并將這個數(shù)字存入壓縮文件中，如果這個字符串再次出現(xiàn)時，即可用表示它的數(shù)字來代替，并將這個數(shù)字存入文件中，壓縮完成后將串表丟棄。字典型的數(shù)據(jù)壓縮方式壓縮比例遠(yuǎn)遠(yuǎn)比編碼上的優(yōu)化的壓縮要高，而且這種壓縮算法無論是在壓縮還是在解壓的執(zhí)行效率都比編碼優(yōu)化壓縮要高得多。字典型數(shù)據(jù)壓縮的關(guān)鍵問