英文摘要: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
基金項目：國家高技術研究發展(“863”)計劃(2009AA01A403)
重復數據刪除也稱為智能壓縮或單一實例存儲，是一種可自動搜索重復數據，將相同數據只保留唯一的一個副本，并使用指向單一副本的指針替換掉其他重復副本，以達到消除冗余數據、降低存儲容量需求的存儲技術。
本文首先從不同角度介紹重復數據刪除技術的分類，然后分別介紹相同數據重復數據刪除技術和相似數據重復數據刪除技術，并介紹重復數據消除的性能提升方法，最后分析重復數據技術的應用場景。
1 重復數據刪除技術的分類
1.1 基于重復內容識別方法的分類
(1)基于散列識別
該方法通過數據的散列值來判斷是否是重復數據。對于每個新數據塊都生成一個散列，如果數據塊的散列與存儲設備上散列索引中的一個散列匹配，就表明該數據塊是一個重復的數據塊。Data Domain、飛康、昆騰的DXi系列設備都是采用SHA-1、MD-5等類似的散列算法來進行重復數據刪除。
基于散列的方法存在內置的可擴展性問題。為了快速識別一個數據塊是否已經被存儲，這種基于散列的方法會在內存中擁有散列索引。隨著數據塊數量增加，該索引也隨之增長。一旦索引增長超過了設備在內存中保存它所支持的容量，性能會急速下降，同時磁盤搜索會比內存搜索更慢。因此，目前大部分基于散列的系統都是獨立的，可以保持存儲數據所需的內存量與磁盤空間量的平衡。這樣的設計使得散列表就永遠不會變得太大。
(2)基于內容識別
該方法采用內嵌在數據中的文件系統的元數據識別文件，與其數據存儲庫中的其他版本進行逐字節地比較，找到該版本與第一個已存儲版本的不同之處并為這些不同的數據創建一個增量文件。這種方法可以避免散列沖突，但是需要使用支持該功能的應用設備以便設備可以提取元數據。
(3)基于ProtecTier VTL的技術
這種方法像基于散列的方法產品那樣將數據分成塊，并且采用自有算法決定給定的數據塊是否與其他數據塊的相似，然后與相似塊中的數據進行逐字節的比較，以判斷該數據塊是否已經被存儲。
1.2 基于去重粒度的分類
(1)全文件層次的重復數據刪除
以整個文件為單位來檢測和刪除重復數據，計算整個文件的哈希值，然后根據文件哈希值查找存儲系統中是否存在相同的文件。這種方法的好處是在普通硬件條件下計算速度非常快；這種方法的缺點是即使不同文件存在很多相同的數據，也無法刪除文件中的重復數據。
(2)文件塊消冗
將一個文件按不同的方式劃分成數據塊，以數據塊為單位進行檢測。該方法的優點是計算速度快、對數據變化較敏感。
(3)字節級消冗
從字節層次查找和刪除重復的內容，一般通過差異壓縮策略生成差異部分內容。字節級消冗的優點是去重率比較高，缺點就是去重速度比較慢。
1.3 基于消冗執行次序的分類
(1)在線式消冗
在線處理的重復數據刪除是指在數據寫入磁盤之前執行重復數據刪除。其最大的優點是經濟高效，可以降低對存儲容量的需求，并且不需要用于保存還未進行重復數據刪除的數據集。在線處理的重復數據刪除減少了數據量，但同時也存在一個問題，處理本身會減慢數據吞吐速度。正是因為重復數據刪除是在寫入到磁盤之前進行的，因此重復數據刪除處理本身就是一個單點故障。
(2)后處理式消冗
后處理的重復數據刪除，也被稱為離線重復數據刪除，是在數據寫到磁盤后再執行重復數據刪除。數據先被寫入到臨時的磁盤空間，之后再開始重復數據刪除，最后將經過重復數據刪除的數據拷貝到末端磁盤。由于重復數據刪除是數據寫入磁盤后再在單獨的存儲設備上執行的，因此不會對正常業務處理造成影響。管理員可以隨意制訂重復數據刪除的進程。通常先將備份數據保留在磁盤上再進行重復數據刪除，企業在需要時可以更快速地訪問最近存儲的文件和數據。而后處理方式的最大問題在于它需要額外的磁盤空間來保存全部還未刪除的重復數據集。
1.4 基于實現層次的分類
(1)基于軟件的重復數據刪除
在軟件層次，重復數據刪除可以有兩種集成方式，即可以將軟件產品安裝在專用的服務器上實現，也可以將其集成到備份/歸檔軟件中。基于軟件的重復數據刪除的部署成本比較低；但是基于軟件的重復數據刪除在安裝中容易中斷運行，維護也更加困難。
基于軟件的重復數據刪除產品有EMC公司的Avamar軟件產品、Symantec公司的Veritas NetBackup產品以及Sepaton公司的DeltaStor存儲軟件等。
(2)基于硬件的重復數據刪除
基于硬件的重復數據刪除主要由存儲系統自己完成數據的刪減，例如：在虛擬磁帶庫系統、備份平臺或者網絡附加存儲(NAS)等一般目的的存儲系統中融入重復數據刪除機制，由這些系統自身完成重復數據刪除功能。
基于硬件的重復數據刪除的優點是高性能、可擴展性和相對無中斷部署，并且重復數據刪除操作對上層的應用都是透明的。這種設備的缺點就是部署成本比較高，要高于基于軟件的重復數據刪除。
目前基于硬件的重復數據刪除系統主要包括VTL和NAS備份產品兩大類，例如：Data Domain公司的DD410系列產品、Diligent Technologies公司的ProtecTier VTL、昆騰公司的DXi3500和DXi5500系列產品、飛康的VTL產品、ExaGrid Systems公司的NAS備份產品以及NetApp的NearStore R200和FAS存儲系統。
2 相同數據重復數據刪除技術
相同數據重復數據刪除技術是將數據進行劃分，找出相同的部分，并且以指針取代相同的數據存儲。
2.1 相同文件重復數據刪除技術
相同文件重復數據刪除技術以文件為粒度查找重復數據[1]。如圖1所示。相同文件重復數據刪除技術先以整個文件為單位計算出哈希值(采用SHA-1或MD5算法)，然后與已存儲的哈希值進行比較，如果發現相同的哈希值則認為該文件為重復的文件，不進行存儲；否則，該文件為新文件，將該文件及其哈希值存儲到系統中。
EMC的Centera系統[2]、Windows的單實例存儲系統[3]采用了以文件為單位的數據消冗方法。
Windows2000的單一實例存儲(SIS)應用該技術對具有20個不同Windows NT映像的服務器進行測試，結果表明總共節省了58%的存儲空間。該方法的優點是重復數據刪除的速度比較快，缺點是不能刪除不同文件內部的相同數據。
2.2 固定長度分塊的重復數據刪除技術
基于固定長度分塊的重復數據刪除方法如圖2所示。將數據對象(文件)分成互不重疊的定長塊，然后計算每個數據塊的哈希值，并將該哈希值與已存儲的哈希值進行檢索比較。如果發現相同的哈希值，則認為該數據塊是重復的數據塊，不存儲該數據塊，只存儲其哈希值及引用信息；否則，認為該數據塊是新數據塊，則存儲該數據塊、其哈希值以及引用信息等等。
該方法存在的主要問題是：當向數據對象中插入數據或者從中刪除數據時，會導致數據塊邊界無法對齊，嚴重地影響重復數據刪除的效果。如圖3所示，數據對象的版本1生成了n個定長數據塊D1、D2……Dn。版本2在版本1的基礎上插入了部分內容(陰影部分所示)。對版本2分塊產生的數據塊D1、D'2……D'n中，只有D1是重復的數據塊，D'2……D'n都不是重復的數據塊，使得數據對象中從插入位置到結尾的重復數據都無法被消除，影響了消冗率。
該方法已經在很多系統獲得了應用，典型的應用是針對網絡存儲的Venti歸檔存儲系統[4]。該系統采用該技術大約節省了30%的空間。
2.3 CDC算法的重復數據刪除技術
針對上述問題，研究者提出了采用基于內容分塊(CDC)的重復數據刪除方法[5]。如圖4所示。該方法的思路是通過一個不斷滑動的窗口來確定數據塊分界點，采用Rabin指紋算法計算滑動窗口的指紋，如果滿足預定條件，就將該窗口的開始位置作為數據塊的結尾，這樣通過不斷滑動窗口并計算指紋實現對數據對象的分塊。為了避免極端情況下數據塊過長或者過短的情況，可以設定數據塊的下限和上限。對于每一個劃分得到的數據塊，就可以通過比較其哈希值來確定重復的數據塊，具體過程與上面描述的相同。
因為數據塊是基于內容而不是基于長度確定的，因此能夠有效地解決上述問題。當數據對象中有內容插入或者刪除時，如果插入或者刪除的內容不在邊界滑動窗口區域，該邊界不會改變；當插入的內容產生一個新的邊界時，一個數據塊會分成兩個數據塊，否則數據塊不會變化。如果變化的內容發生在滑動窗口內，可能會破壞分界數據塊，導致兩個數據塊合成一個數據塊，或者兩個數據塊之間的邊界發生變化，產生新的數據塊。因此，插入或者刪除內容只影響相鄰的一個或者兩個數據塊，其余數據塊不會受影響，這就使得該方法能夠檢測出對象之間更多的重復數據。如圖5所示，當文件中插入部分內容后，分塊時將該內容劃分到一個數據塊中，保持其后續的數據塊不變，從而保證后面重復的數據塊都能夠被刪除。
該方法的典型應用包括：Shark[6]、Deep Store[7]和低帶寬網絡系統LBFS。
在LBFS系統中，系統對分塊長度加上了上下邊界長度，以避免數據塊太長和太短的現象。
2.4 基于滑動塊的重復數據刪除技術
內容劃分塊方法解決了字節插入和刪除的問題，但是引入了變長塊的存儲問題。在存儲系統中，邊長塊的存儲組織比較復雜。針對該問題，出現了基于滑動塊重復數據刪除檢測消除方法[8]。該方法如圖6所示，解決了定長塊和內容劃分塊所存在的問題。
滑動塊方法采用了Rsync Checksum算法和滑動窗口方法進行分塊。Rsync Checksum算法具有計算速度快、效率高的優點。計算的Checksum值與以前存儲的Checksum值進行比較，如果匹配，則與計算數據塊的SHA-1值進行比較來檢測重復數據。
如果發現重復數據塊，則將重復數據塊記錄下來，并移動滑動窗口滑過該重復塊，繼續進行重復數據檢測。另外，還要將從上個塊結尾到新檢測的重復塊之間的數據塊記錄并存儲下來。當Checksum值或者哈希值沒有匹配上，繼續數據檢測過程。如果在發現重復塊之前滑動窗口移動的距離達到定長塊的長度，則計算該塊的哈希值，并將該值存儲下來供將來的數據塊進行校驗。
滑動塊方法通過檢測對象的每一個塊解決數據插入問題。如果部分內容插入數據對象，只有周圍的塊發生變化，后面的塊仍然能夠通過該算法識別和檢測。同理，當刪除部分內容時，該部分內容之后的數據塊不會受到影響，仍然可以采用該方法進行檢測。
2.5 基于Fingerdiff算法的重復數據刪除技術
針對基于內容的分塊(CDC)算法額外存儲空間開銷比較大的問題，研究者提出了Fingerdiff算法，其核心思想是將沒有變化的塊盡可能的合并，以減少數據塊的元數據所占用的存儲空間。該技術包括3個主要過程：(1)一個文件按照CDC算法進行數據塊劃分；(2)每個子塊按照Fingerdiff設置最大子塊數進行合并；(3)每個塊用Hash函數計算出它的指紋值，然后對比已存儲的數據塊指紋值，如果檢測到相同的指紋值，則刪除其對應的數據塊，否則將大塊進行拆分，找到最小的不同數據塊進行存儲，其余塊仍然保持合并狀態。
2.6 基于數據特征的重復數據消除算法
CDC的劃分塊策略雖然在一定程度上解決了定長塊所存在的問題，但是針對特定類型的數據文件，仍然無法獲得較好的數據塊劃分。針對該問題，出現了基于數據特征的數據塊劃分策略。例如針對PPT類型文件的劃分策略，根據PPT文件的格式按每頁PPT劃分成不同的數據塊，從而有效地將相同的PPT頁面消除。另外有人提出了根據數據類型動態選擇不同分塊策略的重復數據刪除技術，例如針對PPT文件和DOC文件采用基于文件特征的重復數據消除策略，針對可執行文件采用定長塊的分塊策略。
3 相似數據重復數據刪除技術
除了通過刪除完全相同的數據可以實現數據消冗外，還可以通過相似數據的檢測與編碼節省存儲空間，提高存儲空間的利用率。相似數據重復數據刪除包括相似數據檢測和編碼兩個階段。相似數據檢測技術有以下3種。
Shingle檢測技術通過為每個文檔提取一組特征[9]，從而將文檔相似性問題簡化為集合相似性問題。Shingle檢測技術簡單易實現，適用范圍廣，但它的計算開銷很高，而且檢測相似數據的精度取決于Shingle的取樣技術，容易出現較大的偏差。
Bloom Filter是一種用位數組表示的集合[10]，支持查詢某個元素是否在該集合當中。Bloom Filter彌補了Shingle檢測技術難度高計算開銷大的缺陷，在性能和相似數據精度之間取得了平衡。Bloom Filter進行數據匹配是通過位操作的，所以可以快速匹配，而且計算開銷很小。
通過模式匹配挖掘數據的特征，也可以進行相似數據的檢測。模式匹配技術的匹配算法是利用一定數量的公共字串來進行文件間的相似性查找與判別。該檢測技術需要對整個文件掃描，所以開銷也比較大。
在相似數據檢測技術基礎上，對有較大相似度的數據進行編碼處理，同樣能為整個系統節省大量的存儲空間。相似數據壓縮技術存在著編碼效率和適用范圍的問題。
4 重復數據刪除的性能提升技術
重復數據刪除技術在提高存儲空間利用率的同時，為系統數據訪問性能帶來了一定影響。這是因為重復數據的檢測過程序要耗費大量的系統資源，嚴重影響了存儲系統訪問性能。針對該問題，目前也出現了一系列的解決方案。
針對內存空間無法容納所有數據索引的問題，Data Domain采用了三級查詢機制[11]：Bloom Filter過濾、Hash緩沖查詢和Hash文件查詢。首先在內存中的Bloom Filter中進行查找。一個Bloom filter用一個m位向量來概括在塊索引中n個塊指紋值的存在信息。如果Bloom filter指出這個塊不存在，則這個塊一定不存在。如果Bloom filter指出該數據塊存在，表明該數據塊可能存在，再到Hash緩存中進行查找，如果存在則說明該數據塊存在，否則再到磁盤上去查詢。對于數據在磁盤上的組織采用了基于流的塊排列技術，以有效利用數據的局部特性，提高緩存的命中率。
針對數據訪問局部性特征不明顯的系統，研究者提出了基于文件相似性的特點來降低重復數據刪除過程中的查詢次數，以提高重復數據刪除性能；另外，有人也采用了兩階段的重復數據刪除機制[12]，通過將隨機的小磁盤I/O調整為序列化的大的磁盤I/O提高重復數據刪除的吞吐率；還有人采用了兩層次的索引技術來降低磁盤I/O次數[13]，提高重復數據刪除的吞吐率。
分析現有技術可以看出，提高重復數據刪除吞吐率的關鍵是降低磁盤I/O次數。現有方法都是通過各種策略來盡量減少數據塊檢索過程中磁盤的I/O次數。
5 重復數據刪除技術的應用
5.1 數據備份系統
重復數據刪除技術為數據保護領域帶來革命性突破，有效地改善了磁盤數據保護的成本效益。因為在傳統數據保護中無法實現重復數據刪除，往往采用廉價的磁帶庫作為備份設備，而磁帶備份在備份窗口、恢復速度方面難以滿足用戶的需求。現在，基于磁盤的數據保護方案如虛擬磁盤庫(VTL)被廣泛采用，并且在未來會繼續增長。備份到VTL或其他基于磁盤的備份已經縮小了備份窗口，改善了備份和恢復能力，但由于數據量的不斷增加，人們所要備份的數據越來越多，面臨容量膨脹的壓力。重復數據刪除技術的出現，為最小化存儲容量找到有效的方法。
5.2 歸檔存儲系統
重復數據刪除技術對歸檔存儲非常重要。由于參考數據的數量不斷增長，而法規遵從要求數據在線保留的時間更長，并且由于高性能需求需要采用磁盤進行歸檔，因此，企業一旦真正開始進行數據的歸檔存儲就面臨成本問題。理想的歸檔存儲系統應能滿足長期保存歸檔數據的需求，并且總擁有成本也要低于生產環境。重復數據刪除技術通過消除冗余實現高效率的歸檔存儲，從而實現最低的成本。目前，歸檔存儲系統的重復數據刪除技術主要是基于Hash的方法，產品的銷售理念是以內容尋址存儲(CAS)技術為主，分為純軟件和存儲系統兩類。
5.3 遠程災備系統
在遠程災備系統中，需要將大量的數據遷移到異地的系統中。隨著數據量的不斷增長，數據傳輸的壓力越來越大，通過重復數據刪除技術在數據傳輸前檢測并刪除重復的數據，可以有效地減少傳輸的數據量，提高數據傳輸速度，例如飛康的MicroScan軟件就采用了該技術。
6 結束語
隨著數字信息的爆炸式增長，所存在的重復數據越來越多，造成了存儲資源的極大浪費。重復數據消除技術的出現在很大程度上緩解了該問題，該技術也得到了越來越廣泛的認可。本文綜合地介紹了重復數據消除技術的概念和發展現狀，介紹了重復數據消除技術的應用場景，探討了重復數據消除的發展趨勢。
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.
王樹鵬，哈爾濱工業大學博士畢業；中科院計算所助理研究員，中科院計算所海量數據存儲保護研究課題組組長；已發表學術論文20余篇，申請專利10余項。