英文摘要: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.

英文關鍵字:data de-duplication; storage; intelligent compression

基金項目：國家高技術研究發(fā)展(“863”)計劃(2009AA01A403)

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

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

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

1.1 基于重復內容識別方法的分類

(1)基于散列識別

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

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

(2)基于內容識別

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

(3)基于ProtecTier VTL的技術

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

1.2 基于去重粒度的分類

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

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

(2)文件塊消冗

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

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

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

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

(1)在線式消冗

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

(2)后處理式消冗

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

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

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

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

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

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

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

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

目前基于硬件的重復數(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存儲系統(tǒng)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3 遠程災備系統(tǒng)

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

6 結束語

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

7 參考文獻

[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è)大學博士畢業(yè)；中科院計算所助理研究員，中科院計算所海量數(shù)據(jù)存儲保護研究課題組組長；已發(fā)表學術論文20余篇，申請專利10余項。