重復數據檢測在多版本數據備份中的應用

(1.中國科學院 計算技術研究所 研究生院， 北京 100080；2.聯想北京研究院 互聯網計算研究室， 北京 100085)

摘 要：分析了當前主要的重復數據檢測技術，針對多版本數據的備份/還原過程提出了重復數據檢測三級模型，有效地解決了檢測粒度和檢測開銷之間的矛盾，從而減少了多版本數據備份/還原過程中的數據傳輸量，節省了備份空間。

關鍵詞：數據備份；重復數據檢測；Rsync算法

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2009)01020603

Duplicated data detection in multiversion backup

CUI Xinghua1，DU Xiaoli1，2，ZHAO Xiaorui2

(1.Graduate School， Institute of Computing Technology， Chinese Academy of Sciences， Beijing 100080， China;2.Internet Computing Lab， Lenovo Corporate Research， Beijing 100085， China)

Abstract:This paper analyzed current technology of duplicated data detection， and designed a threetier detection model for the process of backup restore which achieved a balance between the accuracy and the cost of detection. It can reduce the data transmission and save the backup storage space.

Key words:data backup; duplicated data detection；Rsync

當前，各種信息種類繁多，信息量巨大，企業和個人用戶數據存儲量增長迅速，而這些數據信息中有很多都是重復冗余數據。無論是在用戶的多個版本文件之間還是在企業的數據服務器上，大量數據重復存在，會直接影響數據查詢和管理的效率。當對這些數據進行遠程備份或還原時，如果只是簡單地對數據進行備份和還原，一方面會對存儲空間造成極大的浪費；另一方面也會增加備份/還原過程中的數據傳輸負載。

1 重復數據處理技術

11 重復數據檢測

重復數據檢測當前主要應用于數據備份中，將相同的數據只保留惟一一個副本，并使用指向單一副本的指針替換其他重復副本，從而消除數據冗余，更加有效地對重復數據進行重用。目前的重復數據檢測技術主要有基于hash和基于內容兩種方法。

重復數據檢測可以：a)提供更大的備份容量。備份數據中包含太多的重復數據，尤其對于多版本備份系統，重復數據占整個備份容量很大的部分。b)減少了數據備份/還原時的數據傳輸量，只需要將非重復數據進行同步。c)提高數據恢復水平，方便數據恢復。不同于單純的增量備份，重復數據檢測技術能夠對系統中的數據備份進行有效的管理，當數據發生意外需要恢復時，可以快速有效地進行數據恢復。

重復數據檢測的對象可以是文件級、塊級或字節級。處理的對象粒度越小，系統越復雜；檢測數據的開銷越大，冗余程度也越小。常用的重復數據檢測粒度有兩種，即文件級和數據塊級。其中，文件級重復可以識別兩個文件名不同而內容完全相同的文件，或者不同目錄下相同的文件，從而避免相同文件的多次存儲；數據塊級重復可以在文件中搜索相同的數據塊，將相同的塊保存一個惟一的副本。

12 重復數據刪除與增量備份，數據壓縮

重復數據刪除就是通過重復數據檢測，刪除冗余文件、數據塊的過程，使得只有獨有的數據存儲在系統中。重復數據刪除通過有效減少存儲系統中的冗余數據占有，解決了存儲空間的利用效率問題。

重復數據刪除和增量備份是完全不同的概念。增量備份是指只備份變化的文件；重復數據刪除則是指只備份不重復的數據。沒有變化的數據文件中也會存在大量的重復數據。重復數據刪除也不同于普通的數據壓縮技術所采用的通過壓縮算法消除文件內冗余數據的方法，而是通過算法消除分布在存儲系統內的相同文件或數據塊。重復數據刪除技術的關鍵是只保留惟一的數據實例，在減少數據存儲量方面更加有效。

2 現有主要方案分析

21 基于內容檢測

基于內容識別的重復檢測技術的基本原理是對記錄的數據格式進行比對。在備份數據時，該技術會讀取數據并從中提取出每組備份集以及備份集中數據對象的元數據，存入到內嵌文件系統的數據庫內。當有新的數據進入時則對新的元數據與數據庫中的元數據進行版本比對[1]。

基于內容的算法可以減少計算量，并可以利用元數據之間的聯系更快地查找重復數據，但需要針對不同情況分別提取不同的元數據，實現起來比較復雜。

22 全文件hash

對整個文件進行hash計算，當需要對文件進行同步（備份/還原）時，將當前文件的hash值與已備份過的文件hash值進行比較來判斷當前文件是否發生了變化，進而決定是否需要傳輸文件數據來進行同步[2]。

基于文件hash的重復數據刪除可以識別兩個文件名不同而內容完全相同的文件，或者不同目錄下的相同文件，從而避免相同文件的多次存儲，計算速度非常快；缺點是粒度太大，不能檢測到不同文件之間的相同數據塊，節省存儲空間的效果有限。

23 基于數據塊hash

231 數據塊長度固定

將文件分為固定大小的數據塊并分別進行hash操作，將各個數據塊的偏移位置和hash值寫入索引信息中，通過hash值的比較來判斷數據塊是否屬于重復數據塊。

當進行數據備份/還原時，將當前文件所有的數據塊hash值信息與已有的文件備份的數據塊hash信息進行比較，以判斷文件是否發生了變化。如果數據發生變化，只需要將偏移位置或hash值發生了變化的數據塊進行同步。

固定大小數據塊處理的優點是算法簡單、實現方便；缺點是文件變化點之后位置上的數據塊都會受到影響，會因為偏移位置的變化而被誤判為非重復數據。

232 數據塊可變大小

文件被分為大小可變的數據塊，數據塊的大小在一個規定的最小值和最大值之間。可變大小的數據塊用一個滑動窗口來劃分，當滑動窗口的hash值與一個基準值相匹配時就創建一個分塊，這樣數據塊的尺寸分布就可達到一個希望的情形。

基準值可以采用Rabin指紋進行計算，在確定數據塊邊界的同時，計算整個所劃分的數據塊的hash值并存儲。算法描述如下[3，4]：

預先定義好的兩個整數D和r，r

Rabin指紋技術也存在一些缺陷：粒度太大，指紋與指紋之間數據塊比較大，如果以此為根據來區分檢測冗余數據，無法有效地發現文件中的小塊冗余數據，即使大數據塊之間只有很小的不同，整個大塊也會被檢測為非冗余塊。對相似文件使用Rabin指紋來發現重復數據的效果比較好。

24 Rsync算法

Rsync算法是一種比較成熟的文件比較和同步算法，可在很細的粒度上檢測到重復數據塊[5，6]。算法描述如圖2所示。



假設機器S上有文件的舊備份A′，機器C上有文件的當前版本A，現在要將當前版本備份到S上：

a）將文件A分割成一組不重疊的固定大小為N Byte的數據塊（最后一塊可能會比N小）；

b）對每個數據塊生成hash值，生成數據塊hash值庫，并發送給S；

c）S通過搜索文件A′所有大小為N的數據塊(偏移量可以任選，不一定是N的倍數)，來尋找與文件A的某一數據塊有著相同hash值的數據塊；

d）根據上述文件比對的結果，S向C發送一系列的命令，要求C向其發送沒有重復的數據塊，從而傳輸盡可能少的冗余數據來進行同步。

Rsync算法中分隔文件和搜索文件中所有定長數據塊的工作可以互換來做，不同的只是計算負載是在客戶端還是服務端。在上述描述中，計算的負載在服務端。

Rsync算法也有一定的缺陷：首先，Rsync要查找到所有的重復數據，必須對文件從頭到尾進行滑動窗口掃描，掃描時間長，計算負載大；其次，每次文件內容發生變化時，即使發生變化的內容很少，由于Rsync算法無法快速定位文件發生變化的區域，都需要對文件重新進行掃描來確定發生變化的區域。

3 三級檢測模型

31 使用Rabin指紋快速定位變化數據塊

可以利用Rabin指紋的特性來定位文件中發生變化的數據塊。對于文件的兩個版本，因為指紋的連續性特點，如果其對應的指紋對的內容和間距沒有發生變化，則說明指紋對間的數據塊內容沒有發生變化。利用這個特點，可以通過一次Rabin指紋計算快速定位出發生變化的數據塊，如圖3所示。

首先用Rabin指紋算法掃描文件，記錄指紋信息和指紋在文件中的偏移位置信息。

當文件發生改動以后，重新掃描文件，生成新的指紋集，與已有的指紋信息進行比較：

a）若指紋信息相同，偏移位置相同，說明該指紋之前的數據塊的內容沒有發生變化；

b)若指紋信息相同，但與前一個指紋的相對偏移位置發生了變化或者增加了新的指紋，說明該指紋之前的數據塊內容發生了變化，標記該數據塊為變化數據塊；

c)若指紋信息缺失，說明指紋區的數據發生了變化，繼續掃描下一個指紋。

32 三級檢測模型

在對數據進行遠程備份/還原過程中，帶寬往往是影響數據同步速度的主要原因，如果在不大量增加客戶端計算開銷的情況下，需提高同步文件與目標文件之間的重復數據檢測效率，就可以大幅減少同步時的數據傳輸量，提高備份/還原速度。

針對上述特點，本文提出了數據同步時的重復數據三級檢測模型，通過快速找出重復數據，實現數據的快速同步。

在所設計的模型中，服務端有三個索引信息庫：文件版本庫中存有備份服務端所有文件的版本信息、文件各版本與對應數據塊的索引信息；指紋庫中存有備份服務端的所有文件經過Rabin指紋計算之后生成的指紋信息（指紋值和偏移位置），Rsync庫中存有服務器端所有文件經Rsync計算后生成的數據塊集。檢測流程如圖4所示。

文件第一次進行備份時，服務端對文件屬性（文件名、大小、最后修改時間、文件摘要）進行計算并記錄；然后使用Rabin指紋算法對文件進行掃描并分塊，將Rabin指紋值和相應的偏移位置放入指紋庫中。

對客戶端文件的新版本進行備份時：

a）將新文件的屬性信息與所有已備份文件的信息進行比較，看是否有相同文件，或名稱不同、內容相同的文件。如果有，則不需要實際的傳輸數據，只需更新文件信息庫內容，將新文件信息索引指向已存的相同文件。

b)如果沒有發現重復文件，則用Rabin指紋算法來對新文件進行掃描分塊，并與已有的文件指紋庫和相對應的偏移位置進行比較。標記所有發生了變化的數據塊。

c)如果變化的數據量小或者帶寬充足，則直接同步對應的數據塊內容即可，如圖5所示。

假設文件A在初始狀態（S1）生成了備份文件A′，當文件A發生插入修改（S2，S3），刪除修改后（S4），生成新備份文件A″：

(a)文件A′根據Rabin 指紋算法，生成6個指紋，文件被劃分為7個數據塊，指紋以{M1， M2， …， M6}表示，數據塊以{C1，C2，C3，C4，C5，C6，C7}表示；

(b)發生插入修改，如S2所示，新插入的數據位于C4中，如果（C4 + 新插入的數據塊）經過Rabin指紋計算，為一個chunk（未產生新的指紋），僅需傳輸C8數據塊，在服務端更新版本庫和指紋庫，得到A″；

（c）插入修改，如S3所示，如果插入的數據導致原來一個chunk劃分為兩個chunk，僅需傳輸C9和C10 兩個數據塊，在服務端更新版本庫和指紋庫，得到A″；

（d）刪除修改，如S4所示，如果刪除的數據塊影響了一個指紋，導致原來兩個chunk合并為一個chunk，則僅需傳輸C11，在服務端更新版本庫和指紋庫后，得到A″。

d）如果變化數據量大或者備份帶寬緊張，則使用Rsync算法來對差異數據塊進行同步：將客戶端發生變化的數據塊分割成大小為N的小數據塊，計算各個小數據塊的hash值后發送到服務端，與服務端Rsync庫中的數據作比較，找出重復數據，將服務端沒有的小數據塊傳送給服務端，完成同步。

e）最后將所傳送數據的指紋信息和Rsync信息加入相應的索引庫中，更新版本庫、指紋庫、Rsync庫。

還原過程與上述過程類似，只是將要還原成的文件版本作為源文件，將本地版本同步為備份版本。



三級檢測模型在基本達到Rsync算法的重復數據檢測粒度的情況下，大大提高了檢測的效率，通過逐步縮小比較對象，快速鎖定變化范圍，減輕了計算負載，極大地提高了重復數據檢測在文件備份過程中的可用性和效率。同時，因為指紋庫和Rsync庫的計算與生成均在服務端完成，所以不會給客戶端帶來較多額外的計算負擔。

33 實驗結果

為了評價三級檢測模型的實際運行效果，本文分別使用簡單差異文件復制、Rabin指紋分塊hash、Rsync同步算法，以及本三級模型對指定的文件集合（17 827個文件，511 GB）進行同步對比實驗。

1）實驗平臺 兩臺PC機（CPU為P4 3.0 GHz，內存為1 GB，操作系統為Windows XP）分別模擬客戶端和服務端，以Venti系統作為服務端數據塊的存儲和管理系統。

2）性能指標 a）差異數據的傳輸量——考察重復數據的檢測效率，傳輸量越小，說明對重復數據的重用效果越好；b）同步時間——考察算法優劣的直觀指標，反映了算法是否在重復數據檢測與計算開銷之間找到了好的平衡點。

3）實驗設計 因為在實時對文件進行修改和備份時，數據進行同步的時間較短，受隨機波動影響比較大，無法準確表示實際的同步速度，所以對各種方案的同步時間和同步速度的測算通過拉大備份時間間距，在差異數據量較大的情況下再進行統計，以下實驗的備份時間間隔分別取一周、兩周和一個月（彼此之間不重疊）。

4）實驗結果 首先統計了文件級別的差異文件數據總量和使用不同同步方案所實際傳輸的差異數據量（表1）。

表1傳輸數據量對比

對比項同步算法一周后備份兩周后備份一月后備份

數據變化量

差異文件總量170 MB98 MB283 MB

變化文件個數76個57個116個

數據傳輸量

差異文件復制170 MB98 MB283 MB

Rabin64 MB38 MB121 MB

Rsync27 MB21 MB40 MB

三級模型34 MB22 MB57 MB

各個同步方案所需的同步時間與同步速度（實際差異數據的同步速度），如表2所示。

表2 同步時間與同步速度對比

性能指標同步算法一周后備份兩周后備份一月后備份

差異復制53 s26 s81 s

同步時間Rabin分塊51 s30 s100 s

Rsync29 s24 s47 s

三級模型30 s19 s53 s

差異復制3.2 MB/s3.8 MBps3.5 MBps

同步速度Rabin分塊125 MBps127 MBps121 MBps

Rsync0.91 MBps0.87 MBps0.85 MBps

三級模型1.12 MBps1.15 MBps1.07 MBps

通過上述實驗結果可以看出：a）在多版本備份中應用重復數據檢測技術，相對于所增加的計算時間開銷，減少的數據傳輸更為可觀，大大提高了整體的同步速度，減少了同步時間。b)通過重復數據檢測技術減少了實際的差異數據傳輸量，相應也就減少了對服務端的存儲資源占用，減輕了多版本備份系統的存儲負載。c)本文所提出的三級檢測模型，通過逐層縮小重復數據檢測的粒度，有效地平衡了檢測粒度和計算負載，對提升數據同步的整體速度效果明顯。

4 結束語

將重復數據三級檢測模型運用到數據備份的過程之中，一方面能夠減少數據備份/還原時的數據傳輸量，節約對備份帶寬的使用；另一方面，可以有效地改善服務端對重復數據塊的管理復雜度，當數據發生變化時，只需要更新相應的版本庫、指紋庫和Rsync庫，增加新增數據塊的索引即可。相對于增加的少量計算開銷，所節省的存儲和帶寬資源更為可觀。

本模型目前主要用于數據文件的多個版本之間，不同文件之間也可能存在很高的相似度，如何快速地通過Rabin指紋集的相似度來判斷文件相似度，進而擴大三級比較模型的數據對象范圍是下一步需要改進的地方。

參考文獻：

［1］

DENEHY T E，HSU W W.Duplicate management for reference data[R].[S.l.]:IBM，2004:140.

［2］QUINLAN S，DORWARD S.Venti: a new approach to archival storage[C]//Proc of the 2002 Conference on File and Storage Technologies（FAST）.Monterey，California:[s.n.]，2002:89101.

[3]DENEHY T E，HSU W W.Reliable and efficient storage of reference data[R].[S.l.]:IBM，2003:126.

[4]MUTHITACHAROEN A，CHEN B，MAZIERES D. A lowbandwidth network file system[C]//Proc of Symposium on Operating Systems Principles.2001:915.

[5]TRIDGELL A.Efficient algorithms for sorting and synchronization[D].[S.l.]:The Australian National University， 1999:1927.

[6]DOUGLIS F，IYENGAR A.Applicationspecific deltaencoding via resemblance detection[C]//Proc of USENIX Annual Technical Conference.2003:1530.