楊天明　吳海濤

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

?

一種批處理塊級數(shù)據(jù)去重方法

楊天明吳海濤

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

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

關(guān)鍵詞備份數(shù)據(jù)去重指紋查詢批處理

0引言

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

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

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

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

1系統(tǒng)架構(gòu)

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

圖1　系統(tǒng)架構(gòu)圖

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

2文件索引結(jié)構(gòu)

圖2　文件索引結(jié)構(gòu)

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

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

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

圖3　文件數(shù)據(jù)共享

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

3批處理算法

圖4　TPBS流程

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

3.1備份過程

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

數(shù)據(jù)鏈表的節(jié)點結(jié)構(gòu)為：

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

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

? address: 指紋對應的數(shù)據(jù)塊在存儲池中的存儲地址。

? size: 數(shù)據(jù)塊大小。

? next: 指向下一個節(jié)點的指針。

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

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

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

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

3.2批處理指紋查詢

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

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

3.3BP-DAG 存儲

指紋順序查詢結(jié)束后，系統(tǒng)從磁盤緩沖區(qū)中讀取指紋或數(shù)據(jù)塊為文件構(gòu)建BP-DAG。在這個過程中，系統(tǒng)查詢內(nèi)存哈希表以獲取對指紋的處理方式。對于一個從磁盤緩沖區(qū)中讀取的單元，處理如下：

? 如果是, 從H的內(nèi)存哈希表節(jié)點中讀取并把存儲到 BP-DAG，‘dc’代表數(shù)據(jù)塊。

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

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

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

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

3.4文件讀

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

4實驗結(jié)果及分析

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

表1　測試數(shù)據(jù)集

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

圖5　存儲空間消耗

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

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

圖6　備份吞吐率

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

圖7　文件恢復吞吐率

5結(jié)語

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

參考文獻

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

[2] 王樹聲.重復數(shù)據(jù)刪除技術(shù)的發(fā)展及應用[J].中興通訊技術(shù),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].信息技術(shù),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)；河南省教育廳科學技術(shù)研究重點項目(112102210446)。楊天明，高級工程師，主研領域：數(shù)據(jù)存儲。吳海濤，副教授。

中圖分類號TP333

文獻標識碼A

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