摘  要： 為了使VTL(虛擬磁帶庫)系統(tǒng)能更有效地利用磁盤空間,，存儲更多的數(shù)據(jù)信息,，介紹了一種帶有重復數(shù)據(jù)刪除算法的虛擬磁帶庫應用方法。該方法從性能和效率等多方面考慮,，首先把磁帶按文件級去重,，再將文件切分成塊，通過Bloom Filter和MD5算法雙重計算,，經(jīng)查找和存儲實現(xiàn)數(shù)據(jù)塊級的重復刪除,。實驗測試證明，該方案穩(wěn)定地實現(xiàn)了數(shù)據(jù)的去重及加密功能,，能有效節(jié)省虛擬磁帶庫的存儲空間,。
關鍵詞： 虛擬磁帶庫；重復數(shù)據(jù)刪除,；Bloom filter,；MD5

    進入21世紀以來，在科技飛速發(fā)展的同時,，數(shù)據(jù)信息的產(chǎn)生也在急劇增長,。據(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ù)刪除算法有多種分類方法。按照重復內(nèi)容識別方法分類可分為三種：基于內(nèi)容散列識別,、基于內(nèi)容識別和基于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ù)內(nèi)容變化作調(diào)整和優(yōu)化,。
    CDC(Content-Defined Chunking)算法是一種變長分塊算法，它應用數(shù)據(jù)指紋將文件分割成長度大小不等的分塊,。CDC算法對文件內(nèi)容變化不敏感,，插入或刪除數(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ù)，但它容易產(chǎn)生數(shù)據(jù)碎片,。
1.3 哈希查找和存儲算法
1.3.1 MD5算法
    MD5算法即消息摘要算法第5版,，由MIT計算機科學實驗室和RSA數(shù)碼保安公司聯(lián)合開發(fā)，經(jīng)MD2,、MD3和MD4延伸而來[3],。它將文件的任意一段內(nèi)容通過一系列算法壓縮成一段128 bit的信息摘要(哈希值)。其本質(zhì)即為一種哈希函數(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.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ù)備份的場景,。各個客戶端所產(chǎn)生的數(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)存儲內(nèi)容的高速共享訪問,。下一層為文件管理層,，該層主要實現(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內(nèi)容相同時,，則文件A’的索引會指向文件A的索引，當文件A’數(shù)據(jù)恢復時,，通過指引直接檢索調(diào)用文件A中的索引值,，從而進一步加快效率，節(jié)省存儲空間,。

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

    實驗中采用分塊大小為4 KB，共對5組大小及內(nèi)容不同的文件進行了數(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.