英文摘要:Data de-duplication technology can be used to de-duplicate instances of the same data or similar data. Same data de-duplication includes de-duplication of fixed-length blocks, Content Defined Chunking (CDC), sliding blocks, and characteristic-based elimination of duplicate data algorithm. This technology is especially applicable in data backup systems, archival storage systems, and remote disaster recovery systems.

英文關(guān)鍵字:data de-duplication; storage; intelligent compression

基金項(xiàng)目：國家高技術(shù)研究發(fā)展(“863”)計(jì)劃(2009AA01A403)

重復(fù)數(shù)據(jù)刪除也稱為智能壓縮或單一實(shí)例存儲(chǔ),，是一種可自動(dòng)搜索重復(fù)數(shù)據(jù),，將相同數(shù)據(jù)只保留唯一的一個(gè)副本，并使用指向單一副本的指針替換掉其他重復(fù)副本,，以達(dá)到消除冗余數(shù)據(jù),、降低存儲(chǔ)容量需求的存儲(chǔ)技術(shù)。

本文首先從不同角度介紹重復(fù)數(shù)據(jù)刪除技術(shù)的分類,，然后分別介紹相同數(shù)據(jù)重復(fù)數(shù)據(jù)刪除技術(shù)和相似數(shù)據(jù)重復(fù)數(shù)據(jù)刪除技術(shù),，并介紹重復(fù)數(shù)據(jù)消除的性能提升方法，最后分析重復(fù)數(shù)據(jù)技術(shù)的應(yīng)用場景,。

1 重復(fù)數(shù)據(jù)刪除技術(shù)的分類

1.1 基于重復(fù)內(nèi)容識(shí)別方法的分類

(1)基于散列識(shí)別

該方法通過數(shù)據(jù)的散列值來判斷是否是重復(fù)數(shù)據(jù),。對(duì)于每個(gè)新數(shù)據(jù)塊都生成一個(gè)散列，如果數(shù)據(jù)塊的散列與存儲(chǔ)設(shè)備上散列索引中的一個(gè)散列匹配,，就表明該數(shù)據(jù)塊是一個(gè)重復(fù)的數(shù)據(jù)塊,。Data Domain,、飛康,、昆騰的DXi系列設(shè)備都是采用SHA-1、MD-5等類似的散列算法來進(jìn)行重復(fù)數(shù)據(jù)刪除。

基于散列的方法存在內(nèi)置的可擴(kuò)展性問題,。為了快速識(shí)別一個(gè)數(shù)據(jù)塊是否已經(jīng)被存儲(chǔ),，這種基于散列的方法會(huì)在內(nèi)存中擁有散列索引。隨著數(shù)據(jù)塊數(shù)量增加,，該索引也隨之增長,。一旦索引增長超過了設(shè)備在內(nèi)存中保存它所支持的容量，性能會(huì)急速下降,，同時(shí)磁盤搜索會(huì)比內(nèi)存搜索更慢,。因此，目前大部分基于散列的系統(tǒng)都是獨(dú)立的,，可以保持存儲(chǔ)數(shù)據(jù)所需的內(nèi)存量與磁盤空間量的平衡,。這樣的設(shè)計(jì)使得散列表就永遠(yuǎn)不會(huì)變得太大。

(2)基于內(nèi)容識(shí)別

該方法采用內(nèi)嵌在數(shù)據(jù)中的文件系統(tǒng)的元數(shù)據(jù)識(shí)別文件,，與其數(shù)據(jù)存儲(chǔ)庫中的其他版本進(jìn)行逐字節(jié)地比較,，找到該版本與第一個(gè)已存儲(chǔ)版本的不同之處并為這些不同的數(shù)據(jù)創(chuàng)建一個(gè)增量文件。這種方法可以避免散列沖突,，但是需要使用支持該功能的應(yīng)用設(shè)備以便設(shè)備可以提取元數(shù)據(jù),。

(3)基于ProtecTier VTL的技術(shù)

這種方法像基于散列的方法產(chǎn)品那樣將數(shù)據(jù)分成塊，并且采用自有算法決定給定的數(shù)據(jù)塊是否與其他數(shù)據(jù)塊的相似,，然后與相似塊中的數(shù)據(jù)進(jìn)行逐字節(jié)的比較,，以判斷該數(shù)據(jù)塊是否已經(jīng)被存儲(chǔ)。

1.2 基于去重粒度的分類

(1)全文件層次的重復(fù)數(shù)據(jù)刪除

以整個(gè)文件為單位來檢測和刪除重復(fù)數(shù)據(jù),，計(jì)算整個(gè)文件的哈希值,，然后根據(jù)文件哈希值查找存儲(chǔ)系統(tǒng)中是否存在相同的文件。這種方法的好處是在普通硬件條件下計(jì)算速度非?？?；這種方法的缺點(diǎn)是即使不同文件存在很多相同的數(shù)據(jù)，也無法刪除文件中的重復(fù)數(shù)據(jù),。

(2)文件塊消冗

將一個(gè)文件按不同的方式劃分成數(shù)據(jù)塊,，以數(shù)據(jù)塊為單位進(jìn)行檢測。該方法的優(yōu)點(diǎn)是計(jì)算速度快,、對(duì)數(shù)據(jù)變化較敏感,。

(3)字節(jié)級(jí)消冗

從字節(jié)層次查找和刪除重復(fù)的內(nèi)容，一般通過差異壓縮策略生成差異部分內(nèi)容,。字節(jié)級(jí)消冗的優(yōu)點(diǎn)是去重率比較高,，缺點(diǎn)就是去重速度比較慢。

1.3 基于消冗執(zhí)行次序的分類

(1)在線式消冗

在線處理的重復(fù)數(shù)據(jù)刪除是指在數(shù)據(jù)寫入磁盤之前執(zhí)行重復(fù)數(shù)據(jù)刪除,。其最大的優(yōu)點(diǎn)是經(jīng)濟(jì)高效,，可以降低對(duì)存儲(chǔ)容量的需求,，并且不需要用于保存還未進(jìn)行重復(fù)數(shù)據(jù)刪除的數(shù)據(jù)集。在線處理的重復(fù)數(shù)據(jù)刪除減少了數(shù)據(jù)量,，但同時(shí)也存在一個(gè)問題,，處理本身會(huì)減慢數(shù)據(jù)吞吐速度。正是因?yàn)橹貜?fù)數(shù)據(jù)刪除是在寫入到磁盤之前進(jìn)行的,，因此重復(fù)數(shù)據(jù)刪除處理本身就是一個(gè)單點(diǎn)故障,。

(2)后處理式消冗

后處理的重復(fù)數(shù)據(jù)刪除，也被稱為離線重復(fù)數(shù)據(jù)刪除,，是在數(shù)據(jù)寫到磁盤后再執(zhí)行重復(fù)數(shù)據(jù)刪除,。數(shù)據(jù)先被寫入到臨時(shí)的磁盤空間，之后再開始重復(fù)數(shù)據(jù)刪除,，最后將經(jīng)過重復(fù)數(shù)據(jù)刪除的數(shù)據(jù)拷貝到末端磁盤,。由于重復(fù)數(shù)據(jù)刪除是數(shù)據(jù)寫入磁盤后再在單獨(dú)的存儲(chǔ)設(shè)備上執(zhí)行的，因此不會(huì)對(duì)正常業(yè)務(wù)處理造成影響,。管理員可以隨意制訂重復(fù)數(shù)據(jù)刪除的進(jìn)程,。通常先將備份數(shù)據(jù)保留在磁盤上再進(jìn)行重復(fù)數(shù)據(jù)刪除，企業(yè)在需要時(shí)可以更快速地訪問最近存儲(chǔ)的文件和數(shù)據(jù),。而后處理方式的最大問題在于它需要額外的磁盤空間來保存全部還未刪除的重復(fù)數(shù)據(jù)集,。

1.4 基于實(shí)現(xiàn)層次的分類

(1)基于軟件的重復(fù)數(shù)據(jù)刪除

在軟件層次，重復(fù)數(shù)據(jù)刪除可以有兩種集成方式,，即可以將軟件產(chǎn)品安裝在專用的服務(wù)器上實(shí)現(xiàn),，也可以將其集成到備份/歸檔軟件中?；谲浖闹貜?fù)數(shù)據(jù)刪除的部署成本比較低,；但是基于軟件的重復(fù)數(shù)據(jù)刪除在安裝中容易中斷運(yùn)行，維護(hù)也更加困難,。

基于軟件的重復(fù)數(shù)據(jù)刪除產(chǎn)品有EMC公司的Avamar軟件產(chǎn)品,、Symantec公司的Veritas NetBackup產(chǎn)品以及Sepaton公司的DeltaStor存儲(chǔ)軟件等。

(2)基于硬件的重復(fù)數(shù)據(jù)刪除

基于硬件的重復(fù)數(shù)據(jù)刪除主要由存儲(chǔ)系統(tǒng)自己完成數(shù)據(jù)的刪減,，例如：在虛擬磁帶庫系統(tǒng),、備份平臺(tái)或者網(wǎng)絡(luò)附加存儲(chǔ)(NAS)等一般目的的存儲(chǔ)系統(tǒng)中融入重復(fù)數(shù)據(jù)刪除機(jī)制，由這些系統(tǒng)自身完成重復(fù)數(shù)據(jù)刪除功能,。

基于硬件的重復(fù)數(shù)據(jù)刪除的優(yōu)點(diǎn)是高性能,、可擴(kuò)展性和相對(duì)無中斷部署，并且重復(fù)數(shù)據(jù)刪除操作對(duì)上層的應(yīng)用都是透明的,。這種設(shè)備的缺點(diǎn)就是部署成本比較高,，要高于基于軟件的重復(fù)數(shù)據(jù)刪除。

目前基于硬件的重復(fù)數(shù)據(jù)刪除系統(tǒng)主要包括VTL和NAS備份產(chǎn)品兩大類,，例如：Data Domain公司的DD410系列產(chǎn)品,、Diligent Technologies公司的ProtecTier VTL,、昆騰公司的DXi3500和DXi5500系列產(chǎn)品、飛康的VTL產(chǎn)品,、ExaGrid Systems公司的NAS備份產(chǎn)品以及NetApp的NearStore R200和FAS存儲(chǔ)系統(tǒng)。

2 相同數(shù)據(jù)重復(fù)數(shù)據(jù)刪除技術(shù)   

相同數(shù)據(jù)重復(fù)數(shù)據(jù)刪除技術(shù)是將數(shù)據(jù)進(jìn)行劃分,，找出相同的部分,，并且以指針取代相同的數(shù)據(jù)存儲(chǔ)。

2.1 相同文件重復(fù)數(shù)據(jù)刪除技術(shù)

相同文件重復(fù)數(shù)據(jù)刪除技術(shù)以文件為粒度查找重復(fù)數(shù)據(jù)[1],。如圖1所示,。相同文件重復(fù)數(shù)據(jù)刪除技術(shù)先以整個(gè)文件為單位計(jì)算出哈希值(采用SHA-1或MD5算法)，然后與已存儲(chǔ)的哈希值進(jìn)行比較,，如果發(fā)現(xiàn)相同的哈希值則認(rèn)為該文件為重復(fù)的文件,，不進(jìn)行存儲(chǔ)；否則,，該文件為新文件,，將該文件及其哈希值存儲(chǔ)到系統(tǒng)中。

EMC的Centera系統(tǒng)[2],、Windows的單實(shí)例存儲(chǔ)系統(tǒng)[3]采用了以文件為單位的數(shù)據(jù)消冗方法,。

Windows2000的單一實(shí)例存儲(chǔ)(SIS)應(yīng)用該技術(shù)對(duì)具有20個(gè)不同Windows NT映像的服務(wù)器進(jìn)行測試，結(jié)果表明總共節(jié)省了58%的存儲(chǔ)空間,。該方法的優(yōu)點(diǎn)是重復(fù)數(shù)據(jù)刪除的速度比較快,，缺點(diǎn)是不能刪除不同文件內(nèi)部的相同數(shù)據(jù)。

2.2 固定長度分塊的重復(fù)數(shù)據(jù)刪除技術(shù)

基于固定長度分塊的重復(fù)數(shù)據(jù)刪除方法如圖2所示,。將數(shù)據(jù)對(duì)象(文件)分成互不重疊的定長塊,，然后計(jì)算每個(gè)數(shù)據(jù)塊的哈希值，并將該哈希值與已存儲(chǔ)的哈希值進(jìn)行檢索比較,。如果發(fā)現(xiàn)相同的哈希值,，則認(rèn)為該數(shù)據(jù)塊是重復(fù)的數(shù)據(jù)塊，不存儲(chǔ)該數(shù)據(jù)塊,，只存儲(chǔ)其哈希值及引用信息,；否則，認(rèn)為該數(shù)據(jù)塊是新數(shù)據(jù)塊,，則存儲(chǔ)該數(shù)據(jù)塊,、其哈希值以及引用信息等等。

該方法存在的主要問題是：當(dāng)向數(shù)據(jù)對(duì)象中插入數(shù)據(jù)或者從中刪除數(shù)據(jù)時(shí),，會(huì)導(dǎo)致數(shù)據(jù)塊邊界無法對(duì)齊,，嚴(yán)重地影響重復(fù)數(shù)據(jù)刪除的效果。如圖3所示,，數(shù)據(jù)對(duì)象的版本1生成了n個(gè)定長數(shù)據(jù)塊D1,、D2……Dn,。版本2在版本1的基礎(chǔ)上插入了部分內(nèi)容(陰影部分所示)。對(duì)版本2分塊產(chǎn)生的數(shù)據(jù)塊D1,、D'2……D'n中,，只有D1是重復(fù)的數(shù)據(jù)塊，D'2……D'n都不是重復(fù)的數(shù)據(jù)塊,，使得數(shù)據(jù)對(duì)象中從插入位置到結(jié)尾的重復(fù)數(shù)據(jù)都無法被消除,，影響了消冗率。

該方法已經(jīng)在很多系統(tǒng)獲得了應(yīng)用,，典型的應(yīng)用是針對(duì)網(wǎng)絡(luò)存儲(chǔ)的Venti歸檔存儲(chǔ)系統(tǒng)[4],。該系統(tǒng)采用該技術(shù)大約節(jié)省了30%的空間。

2.3 CDC算法的重復(fù)數(shù)據(jù)刪除技術(shù)

針對(duì)上述問題,，研究者提出了采用基于內(nèi)容分塊(CDC)的重復(fù)數(shù)據(jù)刪除方法[5],。如圖4所示。該方法的思路是通過一個(gè)不斷滑動(dòng)的窗口來確定數(shù)據(jù)塊分界點(diǎn),，采用Rabin指紋算法計(jì)算滑動(dòng)窗口的指紋,，如果滿足預(yù)定條件，就將該窗口的開始位置作為數(shù)據(jù)塊的結(jié)尾,，這樣通過不斷滑動(dòng)窗口并計(jì)算指紋實(shí)現(xiàn)對(duì)數(shù)據(jù)對(duì)象的分塊,。為了避免極端情況下數(shù)據(jù)塊過長或者過短的情況，可以設(shè)定數(shù)據(jù)塊的下限和上限,。對(duì)于每一個(gè)劃分得到的數(shù)據(jù)塊,，就可以通過比較其哈希值來確定重復(fù)的數(shù)據(jù)塊，具體過程與上面描述的相同,。

因?yàn)閿?shù)據(jù)塊是基于內(nèi)容而不是基于長度確定的,，因此能夠有效地解決上述問題。當(dāng)數(shù)據(jù)對(duì)象中有內(nèi)容插入或者刪除時(shí),，如果插入或者刪除的內(nèi)容不在邊界滑動(dòng)窗口區(qū)域,，該邊界不會(huì)改變；當(dāng)插入的內(nèi)容產(chǎn)生一個(gè)新的邊界時(shí),，一個(gè)數(shù)據(jù)塊會(huì)分成兩個(gè)數(shù)據(jù)塊,，否則數(shù)據(jù)塊不會(huì)變化。如果變化的內(nèi)容發(fā)生在滑動(dòng)窗口內(nèi),，可能會(huì)破壞分界數(shù)據(jù)塊,，導(dǎo)致兩個(gè)數(shù)據(jù)塊合成一個(gè)數(shù)據(jù)塊，或者兩個(gè)數(shù)據(jù)塊之間的邊界發(fā)生變化,，產(chǎn)生新的數(shù)據(jù)塊,。因此，插入或者刪除內(nèi)容只影響相鄰的一個(gè)或者兩個(gè)數(shù)據(jù)塊,，其余數(shù)據(jù)塊不會(huì)受影響,，這就使得該方法能夠檢測出對(duì)象之間更多的重復(fù)數(shù)據(jù),。如圖5所示，當(dāng)文件中插入部分內(nèi)容后,，分塊時(shí)將該內(nèi)容劃分到一個(gè)數(shù)據(jù)塊中,，保持其后續(xù)的數(shù)據(jù)塊不變，從而保證后面重復(fù)的數(shù)據(jù)塊都能夠被刪除,。

該方法的典型應(yīng)用包括：Shark[6],、Deep Store[7]和低帶寬網(wǎng)絡(luò)系統(tǒng)LBFS。

在LBFS系統(tǒng)中,，系統(tǒng)對(duì)分塊長度加上了上下邊界長度,，以避免數(shù)據(jù)塊太長和太短的現(xiàn)象,。

2.4 基于滑動(dòng)塊的重復(fù)數(shù)據(jù)刪除技術(shù)

內(nèi)容劃分塊方法解決了字節(jié)插入和刪除的問題,，但是引入了變長塊的存儲(chǔ)問題。在存儲(chǔ)系統(tǒng)中,，邊長塊的存儲(chǔ)組織比較復(fù)雜,。針對(duì)該問題，出現(xiàn)了基于滑動(dòng)塊重復(fù)數(shù)據(jù)刪除檢測消除方法[8],。該方法如圖6所示,，解決了定長塊和內(nèi)容劃分塊所存在的問題。

滑動(dòng)塊方法采用了Rsync Checksum算法和滑動(dòng)窗口方法進(jìn)行分塊,。Rsync Checksum算法具有計(jì)算速度快,、效率高的優(yōu)點(diǎn)。計(jì)算的Checksum值與以前存儲(chǔ)的Checksum值進(jìn)行比較,，如果匹配,，則與計(jì)算數(shù)據(jù)塊的SHA-1值進(jìn)行比較來檢測重復(fù)數(shù)據(jù)。

如果發(fā)現(xiàn)重復(fù)數(shù)據(jù)塊,，則將重復(fù)數(shù)據(jù)塊記錄下來,，并移動(dòng)滑動(dòng)窗口滑過該重復(fù)塊，繼續(xù)進(jìn)行重復(fù)數(shù)據(jù)檢測,。另外,，還要將從上個(gè)塊結(jié)尾到新檢測的重復(fù)塊之間的數(shù)據(jù)塊記錄并存儲(chǔ)下來。當(dāng)Checksum值或者哈希值沒有匹配上,，繼續(xù)數(shù)據(jù)檢測過程,。如果在發(fā)現(xiàn)重復(fù)塊之前滑動(dòng)窗口移動(dòng)的距離達(dá)到定長塊的長度，則計(jì)算該塊的哈希值,，并將該值存儲(chǔ)下來供將來的數(shù)據(jù)塊進(jìn)行校驗(yàn),。

滑動(dòng)塊方法通過檢測對(duì)象的每一個(gè)塊解決數(shù)據(jù)插入問題。如果部分內(nèi)容插入數(shù)據(jù)對(duì)象,，只有周圍的塊發(fā)生變化,，后面的塊仍然能夠通過該算法識(shí)別和檢測,。同理，當(dāng)刪除部分內(nèi)容時(shí),，該部分內(nèi)容之后的數(shù)據(jù)塊不會(huì)受到影響,，仍然可以采用該方法進(jìn)行檢測。

2.5 基于Fingerdiff算法的重復(fù)數(shù)據(jù)刪除技術(shù)

針對(duì)基于內(nèi)容的分塊(CDC)算法額外存儲(chǔ)空間開銷比較大的問題,，研究者提出了Fingerdiff算法,，其核心思想是將沒有變化的塊盡可能的合并，以減少數(shù)據(jù)塊的元數(shù)據(jù)所占用的存儲(chǔ)空間,。該技術(shù)包括3個(gè)主要過程：(1)一個(gè)文件按照CDC算法進(jìn)行數(shù)據(jù)塊劃分,；(2)每個(gè)子塊按照Fingerdiff設(shè)置最大子塊數(shù)進(jìn)行合并；(3)每個(gè)塊用Hash函數(shù)計(jì)算出它的指紋值,，然后對(duì)比已存儲(chǔ)的數(shù)據(jù)塊指紋值,，如果檢測到相同的指紋值，則刪除其對(duì)應(yīng)的數(shù)據(jù)塊,，否則將大塊進(jìn)行拆分,，找到最小的不同數(shù)據(jù)塊進(jìn)行存儲(chǔ)，其余塊仍然保持合并狀態(tài),。

2.6 基于數(shù)據(jù)特征的重復(fù)數(shù)據(jù)消除算法

CDC的劃分塊策略雖然在一定程度上解決了定長塊所存在的問題,，但是針對(duì)特定類型的數(shù)據(jù)文件，仍然無法獲得較好的數(shù)據(jù)塊劃分,。針對(duì)該問題,，出現(xiàn)了基于數(shù)據(jù)特征的數(shù)據(jù)塊劃分策略。例如針對(duì)PPT類型文件的劃分策略,，根據(jù)PPT文件的格式按每頁P(yáng)PT劃分成不同的數(shù)據(jù)塊,，從而有效地將相同的PPT頁面消除。另外有人提出了根據(jù)數(shù)據(jù)類型動(dòng)態(tài)選擇不同分塊策略的重復(fù)數(shù)據(jù)刪除技術(shù),，例如針對(duì)PPT文件和DOC文件采用基于文件特征的重復(fù)數(shù)據(jù)消除策略,，針對(duì)可執(zhí)行文件采用定長塊的分塊策略。

3 相似數(shù)據(jù)重復(fù)數(shù)據(jù)刪除技術(shù)

除了通過刪除完全相同的數(shù)據(jù)可以實(shí)現(xiàn)數(shù)據(jù)消冗外,，還可以通過相似數(shù)據(jù)的檢測與編碼節(jié)省存儲(chǔ)空間,，提高存儲(chǔ)空間的利用率。相似數(shù)據(jù)重復(fù)數(shù)據(jù)刪除包括相似數(shù)據(jù)檢測和編碼兩個(gè)階段,。相似數(shù)據(jù)檢測技術(shù)有以下3種,。

Shingle檢測技術(shù)通過為每個(gè)文檔提取一組特征[9]，從而將文檔相似性問題簡化為集合相似性問題,。Shingle檢測技術(shù)簡單易實(shí)現(xiàn),，適用范圍廣，但它的計(jì)算開銷很高，而且檢測相似數(shù)據(jù)的精度取決于Shingle的取樣技術(shù),，容易出現(xiàn)較大的偏差,。

Bloom Filter是一種用位數(shù)組表示的集合[10]，支持查詢某個(gè)元素是否在該集合當(dāng)中,。Bloom Filter彌補(bǔ)了Shingle檢測技術(shù)難度高計(jì)算開銷大的缺陷,，在性能和相似數(shù)據(jù)精度之間取得了平衡。Bloom Filter進(jìn)行數(shù)據(jù)匹配是通過位操作的,，所以可以快速匹配,，而且計(jì)算開銷很小。

通過模式匹配挖掘數(shù)據(jù)的特征,，也可以進(jìn)行相似數(shù)據(jù)的檢測,。模式匹配技術(shù)的匹配算法是利用一定數(shù)量的公共字串來進(jìn)行文件間的相似性查找與判別。該檢測技術(shù)需要對(duì)整個(gè)文件掃描,，所以開銷也比較大,。

在相似數(shù)據(jù)檢測技術(shù)基礎(chǔ)上，對(duì)有較大相似度的數(shù)據(jù)進(jìn)行編碼處理,，同樣能為整個(gè)系統(tǒng)節(jié)省大量的存儲(chǔ)空間,。相似數(shù)據(jù)壓縮技術(shù)存在著編碼效率和適用范圍的問題,。

4 重復(fù)數(shù)據(jù)刪除的性能提升技術(shù)

重復(fù)數(shù)據(jù)刪除技術(shù)在提高存儲(chǔ)空間利用率的同時(shí),，為系統(tǒng)數(shù)據(jù)訪問性能帶來了一定影響。這是因?yàn)橹貜?fù)數(shù)據(jù)的檢測過程序要耗費(fèi)大量的系統(tǒng)資源,，嚴(yán)重影響了存儲(chǔ)系統(tǒng)訪問性能,。針對(duì)該問題，目前也出現(xiàn)了一系列的解決方案,。

針對(duì)內(nèi)存空間無法容納所有數(shù)據(jù)索引的問題,，Data Domain采用了三級(jí)查詢機(jī)制[11]：Bloom Filter過濾、Hash緩沖查詢和Hash文件查詢,。首先在內(nèi)存中的Bloom Filter中進(jìn)行查找,。一個(gè)Bloom filter用一個(gè)m位向量來概括在塊索引中n個(gè)塊指紋值的存在信息。如果Bloom filter指出這個(gè)塊不存在,，則這個(gè)塊一定不存在,。如果Bloom filter指出該數(shù)據(jù)塊存在，表明該數(shù)據(jù)塊可能存在,，再到Hash緩存中進(jìn)行查找,，如果存在則說明該數(shù)據(jù)塊存在，否則再到磁盤上去查詢,。對(duì)于數(shù)據(jù)在磁盤上的組織采用了基于流的塊排列技術(shù),，以有效利用數(shù)據(jù)的局部特性，提高緩存的命中率。

針對(duì)數(shù)據(jù)訪問局部性特征不明顯的系統(tǒng),，研究者提出了基于文件相似性的特點(diǎn)來降低重復(fù)數(shù)據(jù)刪除過程中的查詢次數(shù),，以提高重復(fù)數(shù)據(jù)刪除性能；另外,，有人也采用了兩階段的重復(fù)數(shù)據(jù)刪除機(jī)制[12],，通過將隨機(jī)的小磁盤I/O調(diào)整為序列化的大的磁盤I/O提高重復(fù)數(shù)據(jù)刪除的吞吐率；還有人采用了兩層次的索引技術(shù)來降低磁盤I/O次數(shù)[13],，提高重復(fù)數(shù)據(jù)刪除的吞吐率,。

分析現(xiàn)有技術(shù)可以看出，提高重復(fù)數(shù)據(jù)刪除吞吐率的關(guān)鍵是降低磁盤I/O次數(shù)?，F(xiàn)有方法都是通過各種策略來盡量減少數(shù)據(jù)塊檢索過程中磁盤的I/O次數(shù),。

5 重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用

5.1 數(shù)據(jù)備份系統(tǒng)

重復(fù)數(shù)據(jù)刪除技術(shù)為數(shù)據(jù)保護(hù)領(lǐng)域帶來革命性突破，有效地改善了磁盤數(shù)據(jù)保護(hù)的成本效益,。因?yàn)樵趥鹘y(tǒng)數(shù)據(jù)保護(hù)中無法實(shí)現(xiàn)重復(fù)數(shù)據(jù)刪除,，往往采用廉價(jià)的磁帶庫作為備份設(shè)備，而磁帶備份在備份窗口,、恢復(fù)速度方面難以滿足用戶的需求?，F(xiàn)在，基于磁盤的數(shù)據(jù)保護(hù)方案如虛擬磁盤庫(VTL)被廣泛采用,，并且在未來會(huì)繼續(xù)增長,。備份到VTL或其他基于磁盤的備份已經(jīng)縮小了備份窗口，改善了備份和恢復(fù)能力,，但由于數(shù)據(jù)量的不斷增加,，人們所要備份的數(shù)據(jù)越來越多，面臨容量膨脹的壓力,。重復(fù)數(shù)據(jù)刪除技術(shù)的出現(xiàn),，為最小化存儲(chǔ)容量找到有效的方法。

5.2 歸檔存儲(chǔ)系統(tǒng)

重復(fù)數(shù)據(jù)刪除技術(shù)對(duì)歸檔存儲(chǔ)非常重要,。由于參考數(shù)據(jù)的數(shù)量不斷增長,，而法規(guī)遵從要求數(shù)據(jù)在線保留的時(shí)間更長，并且由于高性能需求需要采用磁盤進(jìn)行歸檔,，因此,，企業(yè)一旦真正開始進(jìn)行數(shù)據(jù)的歸檔存儲(chǔ)就面臨成本問題。理想的歸檔存儲(chǔ)系統(tǒng)應(yīng)能滿足長期保存歸檔數(shù)據(jù)的需求,，并且總擁有成本也要低于生產(chǎn)環(huán)境,。重復(fù)數(shù)據(jù)刪除技術(shù)通過消除冗余實(shí)現(xiàn)高效率的歸檔存儲(chǔ)，從而實(shí)現(xiàn)最低的成本,。目前,，歸檔存儲(chǔ)系統(tǒng)的重復(fù)數(shù)據(jù)刪除技術(shù)主要是基于Hash的方法，產(chǎn)品的銷售理念是以內(nèi)容尋址存儲(chǔ)(CAS)技術(shù)為主，分為純軟件和存儲(chǔ)系統(tǒng)兩類,。

5.3 遠(yuǎn)程災(zāi)備系統(tǒng)

在遠(yuǎn)程災(zāi)備系統(tǒng)中,，需要將大量的數(shù)據(jù)遷移到異地的系統(tǒng)中。隨著數(shù)據(jù)量的不斷增長,，數(shù)據(jù)傳輸?shù)膲毫υ絹碓酱?，通過重復(fù)數(shù)據(jù)刪除技術(shù)在數(shù)據(jù)傳輸前檢測并刪除重復(fù)的數(shù)據(jù)，可以有效地減少傳輸?shù)臄?shù)據(jù)量,，提高數(shù)據(jù)傳輸速度,，例如飛康的MicroScan軟件就采用了該技術(shù)。

6 結(jié)束語

隨著數(shù)字信息的爆炸式增長,，所存在的重復(fù)數(shù)據(jù)越來越多,，造成了存儲(chǔ)資源的極大浪費(fèi)。重復(fù)數(shù)據(jù)消除技術(shù)的出現(xiàn)在很大程度上緩解了該問題,，該技術(shù)也得到了越來越廣泛的認(rèn)可,。本文綜合地介紹了重復(fù)數(shù)據(jù)消除技術(shù)的概念和發(fā)展現(xiàn)狀，介紹了重復(fù)數(shù)據(jù)消除技術(shù)的應(yīng)用場景,，探討了重復(fù)數(shù)據(jù)消除的發(fā)展趨勢,。

7 參考文獻(xiàn)

[1] BOBBARJUNG D R, JAGANNATHAN S, DUBNICKI C. Improving Duplicate Elimination in Storage Systems [J]. ACM Transactions on Storage, 2006, 2(4):424-448.
[2] GUNAWI H S, AGRAWAL N, ARPACI-DUSSEAN A C, et al. Deconstructing Commodity Storage Clusters [C]//Proceedings of the 32nd International Symposium on Computer Architecture (ISCA’05), Jun 4-8, 2005, Madison, WI, USA. Los Alamitos, CA, USA: IEEE Computer Society, 2005: 60-71.
[3] BOLOSKY W J, CORBIN S, GOEBEL D, et al. Single Instance Storage in Windows 2000 [C]//Proceedings of the 4th USENIX Conference on File and Storage Technologies(FAST’05),Dec 13-16,2005, San Francisco, CA,USA. Berkeley, CA, USA: USENIX Association, 2005:13-24.
[4] QUINLAN S, DORWARD S. Venti: A New Approach to Archival Storage [C]//Proceedings of the 2nd USENIX Conference on File and Storage Technologies(FAST’02), Jan 28-30,2002, Monterey, CA,USA. Berkeley, CA, USA: USENIX Association, 2002:89-101.
[5] POLICRONIADES C, PRATT I. Alternatives for Detecting Redundancy in Storage Systems Data [C]//Proceedings of the 2004 USENIX Annual Technical Conference (USENIX’04), Jun 27-Jul 2, 2004, Boston, MA,USA. Berkeley, CA, USA: USENIX Association, 2004:73-86.
[6] ANNAPUREDDY S, FREEDMAN M J, MAZIERES D. Shark: Scaling File Servers Via Cooperative Caching [C]//Proceedings of the  2nd  Symposium on Networked Systems Design and Implementation(NSDI'05),Mar 2-4,2004, Boston, MA, USA. Berkeley, CA, USA: USENIX Association, 2005:129-142.
[7] YOU L, POLLACK K, LONG D. Deep Store: An Archival Storage System Architecture [C]//Proceedings of the 21st IEEE International Conference on Data Engineering(ICDE’05), Apr 5-8, 2005, Tokyo, Japan. Los Alamitos, CA, USA: IEEE Computer Society, 2005: 804-815.
[8] BRODER A Z. Identifying and Filtering Near-duplicate Documents [C]//Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching(CPM’00), Jun 21-23, 2000, Montreal, Canada. Berlin, Germany: Springer-Verlag, 2000:1-10.
[9] DOUGLIS F, IYENGAR A. Application-specific Delta encoding Via Resemblance Detection [C]//Proceedings of the 2003 USENIX Annual Technical Conference (USENIX’03), Jun 9-14, 2003, San Antonio, TX,USA. Berkeley, CA, USA: USENIX Association, 2003:113-126.
[10] BRODER A Z, MITZENMACHER M. Network Applications of Bloom Filters: A Survey [J]. Internet Mathematics, 2003, 1(4):485-509.
[11] ZHU B, LI K, PATTERSON H. Avoiding the Disk Bottleneck in the Data Domain Deduplication File System [C]//Proceedings of the 6th USENIX Conference on File and Storage Technologies(FAST’08), Feb 26-29, 2008, San Jose, CA, USA. Berkeley, CA, USA: USENIX Association, 2008: 1-14.
[12] YANG T, JIANG H, FENG D, et al. DEBAR: A Scalable High-performance De-duplication Storage System for Backup and Archiving [R]. TR-UNL-CSE-2009-0004.St Lincoln, NE, USA: University of Nebraska-Lincoln.2009.
[13] BHAGWAT D, ESHGHI K, LONG D E, et al. Extreme Binning: Scalable, Parallel Deduplication for Chunk-based File Backup [C]//Proceedings of the 17th IEEE International on Modeling, Analysis & Simulation of Computer and Telecommunication Systems(MASCOTS’09), Sep 21-23,2009, London, UK. Piscataway, NJ, USA: IEEE, 2009.
 
王樹鵬，哈爾濱工業(yè)大學(xué)博士畢業(yè),；中科院計(jì)算所助理研究員,，中科院計(jì)算所海量數(shù)據(jù)存儲(chǔ)保護(hù)研究課題組組長；已發(fā)表學(xué)術(shù)論文20余篇,，申請(qǐng)專利10余項(xiàng),。