孫虎威，靳嘉偉，張 晶，龔 鳴

(重慶大學 光電技術及系統(tǒng)教育部重點實驗室，重慶400044)

進入21世紀以來，在科技飛速發(fā)展的同時，數(shù)據(jù)信息的產生也在急劇增長。據(jù)悉，企業(yè)的數(shù)據(jù)量平均年度增長率為50%左右，部分數(shù)據(jù)的冗余率卻在60%以上。這使得備份時需消耗大量的時間和空間去存儲重復的數(shù)據(jù)，資源浪費十分嚴重。為了實時存儲大量有效的信息，針對物理磁帶庫存儲容量小和效率低等不足，人們引進了虛擬磁帶庫技術，將高速磁盤陣列仿真成磁帶格式，節(jié)省了磁帶機上帶、定位、退帶等機械動作時間，同時無需擔心機械手故障、磁頭耗損或磁帶受潮等問題。節(jié)省成本的同時提高了備份和恢復速度，實現(xiàn)了實時有效地存儲海量數(shù)據(jù)信息。

盡管虛擬磁帶庫在應對數(shù)據(jù)存儲時發(fā)揮了巨大作用，但是仍不能滿足市場需求。如何對存儲在虛擬磁帶庫系統(tǒng)中的數(shù)據(jù)進行重新壓縮從而更有效地利用存儲空間，便成為了如今研究的熱門課題。而重復數(shù)據(jù)刪除技術作為目前企業(yè)熱捧的技術之一，在數(shù)據(jù)壓縮處理和存儲領域具有很大的應用空間。本文提出了重復數(shù)據(jù)刪除算法在虛擬磁帶庫系統(tǒng)中的一種應用方案。

1 相關概念和算法介紹

1.1 重復數(shù)據(jù)刪除算法

重復數(shù)據(jù)刪除算法又名智能壓縮算法，是一種通過消除冗余重復數(shù)據(jù)減少存儲需求的方法。

重復數(shù)據(jù)刪除算法有多種分類方法。按照重復內容識別方法分類可分為三種：基于內容散列識別、基于內容識別和基于Hyper-factor識別；而基于消除冗余執(zhí)行次序的分類則可以分為在線式消冗和后處理式消冗兩種；基于去重粒度分類可分為文件級、數(shù)據(jù)塊級和字節(jié)級消冗三種[1]。本文在虛擬磁帶庫系統(tǒng)的應用主要采用基于散列識別方法的數(shù)據(jù)塊級后處理式消冗方案。

1.2 數(shù)據(jù)分塊算法

基于數(shù)據(jù)塊級的分塊算法主要有定長切分、CDC切分和滑動塊切分三種[2]。

定長分塊算法(Fixed-Size Partition)主要采用預先分配好的塊對文件進行切分，并計算弱校驗值和MD5強校驗值。該算法的優(yōu)點是簡單、性能高，但它對數(shù)據(jù)插入和刪除非常敏感，處理十分低效，不能根據(jù)內容變化作調整和優(yōu)化。

CDC(Content-Defined Chunking)算法是一種變長分塊算法，它應用數(shù)據(jù)指紋將文件分割成長度大小不等的分塊。CDC算法對文件內容變化不敏感，插入或刪除數(shù)據(jù)只會影響到較少的數(shù)據(jù)塊，其余數(shù)據(jù)塊則不受影響。該算法也有缺陷，數(shù)據(jù)塊大小的確定比較困難。

滑動塊(Sliding Block)算法結合了定長切分和CDC切分的優(yōu)點，數(shù)據(jù)塊大小固定。它對定長數(shù)據(jù)塊先計算弱校驗值，如果匹配則再計算MD5強校驗值，兩者都匹配則認為是一個數(shù)據(jù)塊邊界。該數(shù)據(jù)塊前面的數(shù)據(jù)碎片也是不定長的數(shù)據(jù)塊。如果滑動窗口移過一個塊大小的距離仍無法匹配，則認定其為一個數(shù)據(jù)塊邊界?；瑒訅K算法對插入和刪除問題的處理非常高效，并且能夠檢測到比CDC更多的冗余數(shù)據(jù)，但它容易產生數(shù)據(jù)碎片。

1.3 哈希查找和存儲算法

1.3.1 MD5算法

MD5算法即消息摘要算法第5版，由MIT計算機科學實驗室和RSA數(shù)碼保安公司聯(lián)合開發(fā)，經(jīng)MD2、MD3和MD4延伸而來[3]。它將文件的任意一段內容通過一系列算法壓縮成一段128 bit的信息摘要(哈希值)。其本質即為一種哈希函數(shù)，具有單向性、抗弱碰撞性和抗強碰撞性等特點。

在MD5算法操作中，先對元數(shù)據(jù)信息進行填充，使得其字節(jié)長度對512求余結果為448；接著填充64 bit數(shù)據(jù)段長度信息，湊齊為512的整數(shù)倍；然后用4個固定的鏈接變量作為參數(shù)對MD緩沖器進行初始化；最后用4種不同的非線性函數(shù)進行輪換計算，結果輸出4個32 bit即128 bit的哈希值[4-5]。算法過程如圖1所示。

圖1 MD5算法過程

1.3.2 Bloom Filter算法

Bloom Filter由Howard Bloom在1970年提出。它利用位數(shù)組很簡潔地表示一個集合，并能通過一組哈希映射函數(shù)判斷一個元素是否屬于這個集合。該算法具有很好的空間效率和時間效率，但是卻有一定的誤識別率(假陽性誤判)，并且刪除操作比較困難。

該算法主要包括數(shù)據(jù)元素的查找和插入兩部分。在查找操作中，首先將目標信息存儲到一個集合S中，接著設計多個相互獨立的哈希函數(shù)及適度大小的哈希表，并設其初始值全為0。在集合S中任取一個元素，經(jīng)哈希函數(shù)分別映射到哈希表中。如果所對應哈希表位置的值都為1，則說明該元素可能已經(jīng)存在，但也有誤判的可能。若有任意其中一個位置不為1，則說明該元素必不存在。同樣插入操作經(jīng)哈希函數(shù)計算并映射后，把相應位置的值都置為1。

2 方案設計及實現(xiàn)

2.1 應用場景

圖2所示為常見的一種應用虛擬磁帶庫進行數(shù)據(jù)備份的場景。各個客戶端所產生的數(shù)據(jù)通過網(wǎng)絡傳送到服務器端，在服務器中備份軟件的操作下，將數(shù)據(jù)備份到虛擬磁帶庫所模擬成磁帶格式的磁盤陣列中，該磁盤陣列由相應的RAID組構成，從而進行容災保護。該數(shù)據(jù)可以實時導入、導出到相應的物理磁帶庫中。同樣，數(shù)據(jù)流的逆向即可實現(xiàn)數(shù)據(jù)恢復作業(yè)。在虛擬磁帶庫系統(tǒng)中可以對所備份的數(shù)據(jù)進行重新掃描和重復數(shù)據(jù)刪除，并存儲壓縮后的數(shù)據(jù)，選擇是否刪除原有數(shù)據(jù)，進而節(jié)省大量的磁盤空間。

2.2 系統(tǒng)結構設計

帶有重復數(shù)據(jù)刪除功能的虛擬磁帶庫系統(tǒng)結構設計如圖3所示。上層為包含有支持 NFS/CIFS、OST及VTL等文件協(xié)議的文件協(xié)議讀取層，該層將存儲子系統(tǒng)進行網(wǎng)絡化，實現(xiàn)存儲內容的高速共享訪問。下一層為文件管理層，該層主要實現(xiàn)對數(shù)據(jù)存放文件及命名空間的管理和設置。文件管理層下面為重復數(shù)據(jù)刪除模塊，主要對搜尋到的數(shù)據(jù)文件進行分塊處理、哈希計算和查找并歸類存儲等操作。下一層為磁盤管理模塊，主要負責對磁盤陣列數(shù)據(jù)元數(shù)據(jù)和哈希值的分類存放和獲取，以及磁盤訪問順序的優(yōu)化處理等。

2.3 重復數(shù)據(jù)刪除功能詳細設計

為實現(xiàn)文件中重復數(shù)據(jù)的刪除功能，本文進行了如圖4所示的詳細設計。首先該模塊對虛擬磁帶庫中需處理的磁帶文件進行查找和獲取，然后計算出相應的哈希值，先用Bloom Filter算法進行快速計算和查找，如果位數(shù)組A中已存在相關的文件，則再次進行MD5算法計算和查找，如果位數(shù)組A中的確存在該文件，則只存儲該文件相關哈希值，接著進行下個文件的處理。如果在Bloom Filter算法的位數(shù)組A中不存在該數(shù)據(jù)的信息，則進行添加和更新，接著完成對該文件哈希值的存儲，然后對該文件進行數(shù)據(jù)塊級的處理。由于在Bloom Filter中可能出現(xiàn)誤判，故而當MD5再次校驗不存在時，同樣也會進入數(shù)據(jù)塊級處理中。

本文應用可以根據(jù)需要選擇定長、CDC、滑動塊任意一種切分方式來進行數(shù)據(jù)塊劃分。接著對所切分的數(shù)據(jù)塊進行如同文件級別的Bloom Filter和MD5雙重驗證。首先對數(shù)據(jù)塊進行Bloom Filter計算，當結果不匹配位數(shù)組B中相關位時，則表明該數(shù)據(jù)塊必不存在，對位數(shù)組中相關位進行插入和更新，并分別存儲該數(shù)據(jù)塊和相關的哈希值；如果該數(shù)據(jù)塊匹配該位數(shù)組B時，則再次進行MD5計算和校驗。如果仍然匹配，則說明該數(shù)據(jù)塊重復，只存儲該數(shù)據(jù)塊的哈希值；如果出現(xiàn)不匹配情況，則說明前面計算出現(xiàn)誤判，分別存儲該數(shù)據(jù)塊和相應的哈希值。

數(shù)據(jù)塊及相應哈希值存儲及檢索如圖5所示。當文件A進入計算時，會生成相應哈希值并指向對應數(shù)據(jù)塊。當首次查找數(shù)據(jù)塊N不存在時，則先存入數(shù)據(jù)塊，然后再把數(shù)據(jù)塊N的索引指向該數(shù)據(jù)塊所在位置，當再次查找時，僅存儲對應哈希值。文件A檢索完畢后同樣對文件B進行相關操作。而當A’經(jīng)計算與文件A內容相同時，則文件A’的索引會指向文件A的索引，當文件A’數(shù)據(jù)恢復時，通過指引直接檢索調用文件A中的索引值，從而進一步加快效率，節(jié)省存儲空間。

2.4 關鍵參數(shù)分析

2.4.1 Bloom Filter誤判率

假設在Bloom Filter算法中，有k個相互獨立的Hash函數(shù)，待處理的元素數(shù)為n，位數(shù)組位數(shù)為m，此時需滿足kn＜m。當所有元素都被k個Hash函數(shù)映射到位數(shù)組中，可以求得誤判率f為：

容易看出，當位數(shù)組m增加時，誤判率會下降。經(jīng)計算可得當 k＝(ln2)時，誤判率取得最小值，即：

當誤判率為 e時，若 f≤e成立，則需

m≥n×log2(1/e)

表1 k值和m/n值對誤判率的影響

若使 f≤0.01，則需 m≥9.567n，此時取 k＝7[6]。 表1中所示數(shù)據(jù)可獲得不同k值和m/n下對應的誤判率的大小以及m/n固定時取得最小誤判率的最佳k值。

假設本文處理的數(shù)據(jù)為16 TB，平均分塊大小為8 KB，則數(shù)據(jù)塊的數(shù)量大概為 2×109個，位數(shù)組B占用內存空間大概為：93 567×2×109÷8≈2.4 GB。這對于虛擬磁帶庫系統(tǒng)是完全可以實現(xiàn)的。

2.4.2 重刪率

重復數(shù)據(jù)刪除算法的效果可用重刪率DDR(Data De-duplication Ratio)來表示。即為元數(shù)據(jù)在重復數(shù)據(jù)刪除之前的字節(jié)數(shù)與處理之后的字節(jié)數(shù)之比：

重刪率同樣依賴于數(shù)據(jù)集自身的特征、數(shù)據(jù)劃分策略以及平均數(shù)據(jù)分塊大小等因素。故而有專家對上述公式進行了修正：

由上式可以看出，修正后的重刪率在平均分塊大小較小時與元數(shù)據(jù)大小成正比，而當平均分塊大小較大時，與元數(shù)據(jù)大小成反比。因此設定合適的數(shù)據(jù)分塊策略和分塊大小界限很關鍵。

3 實驗結果和分析

本文在以下實驗環(huán)境進行了測試：CPU為Intel core 2雙核處理器，2 GB內存，磁盤空間為 200 GB；Win7系統(tǒng)下VMware虛擬運行Red Hat 5 Linux系統(tǒng)；虛擬磁帶庫系統(tǒng)應用軟件選用開源軟件MHVTL0.18。實驗根據(jù)以上設定的規(guī)格分別對不同的數(shù)據(jù)進行備份，然后進行重刪處理，其結果如表2所示。

表2 測試結果分析

實驗中采用分塊大小為4 KB，共對5組大小及內容不同的文件進行了數(shù)據(jù)的重復刪除處理。由表2可知，文件1中TXT文件和文件3中PDF文件存在相當數(shù)量的重復塊；而照片、音頻和視頻等文件存在較少重復數(shù)據(jù)塊。由于測試環(huán)境限制，本次測試的子文件都不相同，且數(shù)據(jù)量小，所以重刪率較低，甚至出現(xiàn)小于1的情況。不過數(shù)據(jù)經(jīng)還原處理后，與原始數(shù)據(jù)相比完全相同，安全性能有保障，當出現(xiàn)大量重復文件時，效果更好。

本文主要介紹了一種重復數(shù)據(jù)刪除算法在虛擬磁帶庫系統(tǒng)中的應用方法。該應用采用后處理式的數(shù)據(jù)分塊哈希計算方法來進行數(shù)據(jù)的重復刪除。數(shù)據(jù)分塊可選擇使用任一種常用的3種分塊方法，數(shù)據(jù)查找和存儲采用Bloom Filter和MD5算法雙重計算，經(jīng)過設置參數(shù)有效地降低了Bloom Filter的誤判率和MD5算法的碰撞率。有效提高了存儲的時間效率和空間效率，并獲得良好的重刪率，同時完成了數(shù)據(jù)的壓縮和加密雙重功能。

[1]付印芳，肖儂，劉芳.重復數(shù)據(jù)刪除關鍵技術研究進展[J].計算機研究與發(fā)展，2012，49(1)：12-20.

[2]敖莉，舒繼武，李明強.重復數(shù)據(jù)刪除技術[J].軟件學報，2010，21(5)：916-929.

[3]RIVEST R.The MD5 message digest algorithm[M].RFC 1321，1992.

[4]陳少暉，翟曉寧，閻娜，等.MD5算法破譯過程解析[J].計算機工程與應用，2010，46(19)：109-112.

[5]張裔智，趙毅，湯小斌.MD5算法研究[J].計算機科學，2008，35(7)：295-297.

[6]HOROWITZ E，SAHNI S，MEHTA D.Fundamentals of data structures in C++[M].Computer Science Press，1995.