一種批處理塊級數據去重方法

楊天明　吳海濤

(黃淮學院國際學院　河南 駐馬店 463000)

?

一種批處理塊級數據去重方法

楊天明吳海濤

(黃淮學院國際學院河南 駐馬店 463000)

摘要數據去重能消除備份中的冗余數據，節省存儲資源和網絡帶寬，因而成為當前數據存儲領域的研究熱點。針對常用的塊級數據去重技術指紋查詢開銷高、系統吞吐率低等問題，提出一種批處理塊級數據去重方法，通過內存緩沖區對指紋進行排序，實現磁盤索引的順序查詢。同時文件以一種雙指針有向無環圖的結構存儲在系統中，以消除文件讀時引起的隨機磁盤I/O開銷。實驗結果表明，該方法有效克服了指紋查詢的磁盤I/O瓶頸，提高了數據去重時的系統讀寫性能。

關鍵詞備份數據去重指紋查詢批處理

0引言

生產和科技的高速發展不但帶來了數據的爆炸性增長，而且使得數據的重要性日益提升。如何快速有效地對數據進行備份成為數據保護領域亟待解決的關鍵問題之一。

研究發現重復數據大量存在于信息處理和存儲的各個環節。傳統的備份技術不能有效消除重復數據，浪費了存儲空間和網絡帶寬[1]。近年來，數據去重技術迅速成為數據保護領域一個新的研究方向[2]。常用的數據去重方法把數據流或文件分成較小的數據塊，比較數據塊指紋以消除重復數據塊[3]。為了保證數據塊指紋的唯一性，一般使用安全哈希函數如MD5[4]對數據塊內容進行哈希來得到指紋。系統通過磁盤哈希表建立指紋到數據塊的映射，由于磁盤哈希表較大而不能存儲在內存中，加之指紋的極度隨機性，在備份過程中查詢指紋會導致隨機磁盤I/O[3]。以目前的磁盤技術，隨機磁盤I/O速度不會超過數百IOPS，這顯然不能滿足高性能數據備份的需要。因而，高性能數據去重的關鍵是如何有效降低指紋查詢的隨機磁盤I/O開銷。

近年來，國內外在數據去重性能方面進行了較多研究。DDFS[3]和Foundation[5]使用cache技術和布隆過濾器[15]來提高系統讀寫性能。Cache技術利用數據流的冗余局部性通過容器預取數據塊指紋來提高舊指紋在內存中的命中率，布隆過濾器則留駐在內存中預先檢測出大部分新指紋從而有效降低數據塊索引查詢的隨機磁盤I/O開銷。Sparse Indexing[6]則把數據流分成數據段，對數據段中包含的數據塊指紋進行抽樣以取得鉤子指紋，并使用稀疏索引建立鉤子指紋到包含它們的數據段之間的映射。備份新數據段時，通過稀疏索引找到和其共享鉤子指紋的舊數據段來消除新舊數據段之間的重復數據塊。稀疏索引留駐在內存中能加快查詢速度。由于僅在局部范圍內刪除重復數據塊，Sparse Indexing的數據壓縮效果較DDFS差。另外，對于冗余局部性較差的負載，DDFS 和Foundation的性能會降低而Sparse Indexing 的數據壓縮率會下降，SiLo[7]則研究了這種情況下利用備份源目錄信息整合數據流從而提高重復數據塊刪除比率和性能的技術。

本文提出了一種基于批處理的塊級數據去重方法，通過把數據備份過程分成兩個階段，實現對磁盤哈希表的順序查找和更新。該方法把數據去重從數據備份過程中分離開來從而減小數據去重對應用的影響，而批處理指紋查詢不依賴于備份流內部的冗余局部性，因而具有穩定的寫吞吐率。同時文件以一種雙指針有向無環圖BP-GAD(Bi-Pointer-based Directed Acyclic Graph)的結構存儲在系統中，消除了文件讀時引起的隨機磁盤I/O開銷，保證了較高的數據恢復性能。

1系統架構

系統架構如圖1所示，整個系統分成三部分，客戶機運行在需要備份數據的主機上，備份時從指定文件集中讀出文件送往備份服務器，恢復時從備份服務器接收文件寫到指定的恢復目錄中。備份服務器由兩大模塊構成，即TPBS(Two Phase Backup Stradity)模塊和文件讀模塊(FR)。備份時，由TPBS模塊負責接收客戶機送來的文件、對文件進行分塊并計算數據塊的MD5指紋(128 bits)、然后把數據塊和指紋緩存在本地磁盤緩沖區中。待備份作業結束后再通過批處理指紋查詢等機構把文件以BP-GAD的形式存儲到存儲池中?；謴蜁r，由FR模塊從存儲池中讀取相應的BP-GAD對文件進行重構，并把文件恢復到客戶機的指定目錄中。

圖1　系統架構圖

數據塊以其指紋為索引存儲在存儲池中，指紋到數據塊存儲地址的映射通過磁盤哈希表建立。磁盤哈希表共包含2n個桶，每個桶占用一個磁盤扇區，包含若干個索引項，每個索引項存儲一個“指紋->地址”映射。取指紋的前n位為桶號把此指紋映射到相應的桶中。

2文件索引結構

圖2　文件索引結構

一般文件系統采用地址指針建立文件索引，這樣文件訪問速度很快，但地址指針和數據塊內容無關，無法實行數據去重。以數據塊指紋為指針的索引結構如Venti哈希樹[8]和HDAGs[9]能消除冗余數據并實現數據塊共享，但數據訪問時必須通過查詢磁盤哈希表獲得地址指針，文件讀寫性能較差。為了綜合兩種指針的優點，本文使用一種雙指針索引結構BP-GAD，如圖2所示。

圖2為一個文件F的BP-GAD，圖中用雙箭頭表示BP-GAD指針。一個BP-GAD 指針是一個四元組< type, fingerprint, address, size >，其中‘type’表示節點類型，‘fingerprint’表示節點指紋，‘address’表示節點在存儲池中的存儲地址，而‘size’表示節點大小。顯然< type, fingerprint> 是一個哈希指針，而< address, size >是一個地址指針。BP-GAD有三種不同類型的節點，分別是數據塊、索引塊和根塊。一個BP-GAD有一個唯一的根塊，根塊包括文件的元數據M(F)域和BP-GAD指針域。對于較小的文件，其數據塊指針可以直接放在根塊中，對于大文件，有可能需要使用多個索引塊以構成一個層次性的索引結構來對文件進行索引。索引塊存放BP-GAD指針，它是變長塊，可以設定其最大大小，比如16 KB。

BP-GAD中的哈希指針是惟一的。由于內容相同的節點哈希指針也相同，這保證了系統中不會存儲重復的節點。如若文件內部或文件之間有相同的節點(索引塊或數據塊)，這些節點在物理上只存儲一次，在邏輯上通過哈希指針共享。圖3所示為兩個文件共享索引塊和數據塊的情況。

圖3　文件數據共享

BP-GAD并不是樹形結構，而是有向無環圖，因為一個兒子節點可能擁有多個父節點。BP-GAD能有效提高文件讀性能。在備份過程中，僅將文件的根塊存儲在元數據庫中，恢復文件時，根塊被讀入內存中，系統根據根塊所包含的地址指針直接讀取索引塊或數據塊，而不需要查詢磁盤哈希表來獲得地址，因而能有效減輕讀文件的隨機磁盤I/O開銷。

3批處理算法

圖4　TPBS流程

為了克服備份中的磁盤瓶頸，把數據備份過程分成備份過程和去重過程兩個階段，這樣便于對磁盤哈希表進行批處理查找和更新，有效提高備份速度。流程如圖4所示。

3.1備份過程

在備份過程中，系統對文件進行分塊、計算數據塊指紋，并把指紋插入一個內存哈希表中，同時把數據塊和指紋暫存到磁盤緩沖區。內存哈希表共2m(m≥20)個桶，每個桶里存放一個鏈表指針。鏈表中存儲映射到本桶中的指紋。哈希時，取指紋的前m比特作為桶號把指紋映射到相應桶里。

數據鏈表的節點結構為：

? tag: 標識符，用以指示備份過程中本指紋的狀態。

? fingerprintTail: 本指紋的后108比特，因為前20比特隱含在桶號中，故這里只需要存儲指紋的后108比特。

? address: 指紋對應的數據塊在存儲池中的存儲地址。

? size: 數據塊大小。

? next: 指向下一個節點的指針。

備份時，對一個到來的指紋H，系統檢查內存哈希表，如果哈希表中無H，則把H插入內存哈希表中，并把H和其相應的數據塊D(H)，即 追加到磁盤緩沖區中；如果內存哈希表中有H，則把追加到磁盤緩沖區中。

對于周期性備份作業，內存哈希表能預先存放前一次作業的指紋，以便于在備份階段消除相鄰作業間的重復數據。

設內存哈希表桶大小為b字節，桶數為2m，鏈表節點大小為q字節，平均每個桶存儲的節點數為u，則哈希表內存開銷為(b+uq)2m字節。又設數據塊平均大小為C字節，則(b+uq)2m字節的內存哈希表能支持約uC×2m字節的備份數據量。

取典型值m=23，b=4，q=25，u=2，C=1024×8，則內存哈希表內存開銷為(4+2×25)×223字節(432 MB)，支持的物理數據量為2×1024×8×223字節(128 GB)。由于備份數據本身包含的冗余數據量一般很大，實際處理的邏輯數據量會遠大于128 GB。故使用約432 MB的內存，每次能處理大于128 GB的備份數據量。

3.2批處理指紋查詢

若內存哈希表和磁盤索引分別包含m和n(m

對于一個指紋H，如果在磁盤哈希表的桶中查找到了，則其內存哈希表節點的‘tag’標記為‘舊’，并把它的地址指針從磁盤哈希表的桶中復制到其內存哈希表節點中；如果其在磁盤哈希表中沒有找到，則其內存哈希表節點的‘tag’標記為‘新’，表明是新指紋。批處理查詢要求一次處理的指紋量不能太少，否則影響效率。如果單個作業較小，可以一次為多個作業進行指紋查詢。

3.3BP-DAG 存儲

指紋順序查詢結束后，系統從磁盤緩沖區中讀取指紋或數據塊為文件構建BP-DAG。在這個過程中，系統查詢內存哈希表以獲取對指紋的處理方式。對于一個從磁盤緩沖區中讀取的單元，處理如下：

? 如果是, 從H的內存哈希表節點中讀取并把存儲到 BP-DAG，‘dc’代表數據塊。

? 如果是, 查詢內存哈希表中H的節點，如果為‘舊’，則丟棄數據塊D(H)，從H的內存哈希表節點中讀取 < address, size> 并把 存儲到BP-DAG。

? 如果為‘新’，則把數據塊 D(H) 寫入存儲池，把存儲地址指針< address, size> 寫到H的內存哈希表節點中， 把存儲到 BP-DAG。

對于小文件，BP-DAG指針直接存儲在其根塊中，對于大文件，BP-DAG指針則遞歸地存儲在索引結構中。對于索引塊的存儲，必須計算其指紋，并查詢磁盤哈希表以確定是否為新指紋，如果是新指紋，則索引塊被寫到存儲池，如果是舊指紋，則索引塊被丟棄，系統中原存在的索引塊被共享。由于索引塊的數量比數據塊的數量少得多，索引塊查詢的磁盤I/O開銷不大。

BP-DAG存儲完畢后，內存哈希表中所有的新指紋都獲得了地址指針，這時候，系統順序讀取磁盤索引，按照內存哈希表記錄的新指紋對磁盤索引進行順序更新。更新操作完成后，內存哈希表銷毀，數據去重過程結束。

3.4文件讀

文件的讀過程是一個讀取BP-DAG并對文件進行重構的過程。為了便于文件讀操作，建立了文件恢復索引：按照被備份的目錄結構生成一個相同的目錄結構，目錄里的文件只有文件名，無內容。 每個文件名對應一個索引項，記錄此文件的根塊在存儲池中的地址。備份完成后，用戶得到一個和原目錄結構相同但無文件內容的目錄結構?；謴蜁r，只要瀏覽此目錄，選擇要恢復的目錄或文件即可。用戶指定了恢復目錄后，系統讀取目錄中文件的索引項，得到其根塊地址，按照根塊地址從存儲池中讀取組成文件的數據塊，重構文件，并把文件恢復到指定的目錄中。

4實驗結果及分析

為了測試數據去重算法性能，和傳統備份軟件Bacula以及沒有實現指紋查詢優化的數據去重算法進行比較。測試數據來自離線瀏覽器Offline Explorer Enterprise V6.9從網址www.163.com搜集的網頁和文件，搜集深度為2。搜集數據按照時間順序分為如表1的6個數據集，共8817個文件，約1.39 GB數據，平均文件大小約165 KB。

表1　測試數據集

圖5所示為備份數據集所消耗存儲空間的對比，圖中Dedup為沒有實現指紋查詢優化的數據去重算法，TPBS為本文提出的批處理塊級數據去重算法，數據去重平均分塊大小8 KB。Bacula消耗存儲空間1425.8 MB，Dedup和TPBS分別僅消耗存儲空間415.9、424.3 MB，數據去重效果明顯。TPBS較Dedup多消耗8.4 MB存儲空間，用于BP-DAGs索引開銷。

圖5　存儲空間消耗

圖6所示為備份吞吐率對比。Dedup備份wy-v1達到了和Bacula、TPBS差不多的速度，是因為第一次備份，系統中無舊數據，無須查詢指紋。Dedup備份其他數據集速度很慢，僅達到平均0.95 MB/s。而TPBS采用批處理指紋查詢，并且在備份階

段可以通過預先載入相鄰數據集指紋的方式消除部分冗余數據，其達到了高于Bacula的吞吐率。

圖6　備份吞吐率

圖7所示為文件恢復對比。雖然TPBS的文件恢復速度沒有Bacula快，但采用BP-DAG技術后，文件恢復速度較Dedup有了明顯提高。

圖7　文件恢復吞吐率

5結語

本文描述了一種基于批處理的塊級數據去重方法，該方法把數據去重過程從數據備份過程中分離出來從而降低了數據去重對應用的影響，同時通過批處理消除了指紋查詢和更新的隨機磁盤I/O開銷。文件以雙指針有向無環圖的形式存儲在系統中，既有利于文件間的數據共享，又有效提高了文件的讀性能。在未來的工作中，我們將致力于提高批處理數據去重的可擴展性，以滿足大規模分布式數據存儲系統的備份需求。

參考文獻

[1] 賀翔.一種基于NDMP的塊級備份和數據管理方法及其實現[D].中國科學院,2006.

[2] 王樹聲.重復數據刪除技術的發展及應用[J].中興通訊技術,2010,16(5):9-14.

[3] Zhu B,Li H,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,2008:269-282.

[4] 魏曉玲.MD5加密算法的研究及應用[J].信息技術,2010,35(7):145-151.

[5] Rhea S,Cox R,Pesterev A.Fast, inexpensive content-addressed storage in foundation[C]//Proceedings of the 2008 USENIX Annual Technical Conference,Boston,Massachusetts,June 2008:143-156.

[6] Lillibridge M,Eshghi K,Bhagwat D,et al.Sparse indexing: Large scale, inline deduplication using sampling and locality[C]//Proceedings of the 7th USENIX Conference on File And Storage Technologies,2009:111-123.

[7] Xia W,Jiang H,Feng D,et al.Silo:a similarity-locality based near-exact deduplication scheme with low ram overhead and high throughput[C]//Proceedings of the 2011 USENIX Annual Technical Conference,2011:26-28.

[8] Quinlan S,Dorward S.Venti:a new approach to archival storage[C]//Proceedings of the USENIX Conference on File And Storage Technologies,January 2002:89-101.

[9] Eshghi K,Lillibridge M,Wilcock L,et al.Jumbo store:Providing efficient incremental upload and versioning for a utility rendering service[C]//Proceedings of the 5th USENIX Conference on File And Storage Technologies,2007:22-38.

A CHUNK-BASED DE-DUPLICATION METHOD BASED ON BATCH PROCESS

Yang TianmingWu Haitao

(CollegeofInternational,HuanghuaiUniversity,Zhumadian463000,Henan,China)

AbstractData de-duplication technology, which eliminates the redundant data from backups to save network bandwidth and storage resources, has become a hot research topic in current data storage field. The commonly used chunk-based de-duplication technology suffers from high overhead in fingerprint lookup and low system throughput. In light of this, the paper proposes a chunk-based de-duplication method using batch process, which sorts the fingerprints in memory buffer to achieve the sequential lookup of disk indexes. Moreover, the files are stored to the system in a structure of bi-pointer-based directed acyclic graphs so as to eliminate random small disk I/O costs caused by file read. Experimental results show that this method breaks the disk I/O bottleneck of fingerprint lookup and hence improves read-write performance of the system during data de-duplication.

KeywordsBackupData de-duplicationFingerprint queryBatch process

收稿日期：2014-12-08。河南省科技項目(142300410288，132400 411178)；河南省教育廳科學技術研究重點項目(112102210446)。楊天明，高級工程師，主研領域：數據存儲。吳海濤，副教授。

中圖分類號TP333

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.012