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

    進入21世紀以來，在科技飛速發展的同時，數據信息的產生也在急劇增長。據悉，企業的數據量平均年度增長率為50%左右，部分數據的冗余率卻在60%以上。這使得備份時需消耗大量的時間和空間去存儲重復的數據，資源浪費十分嚴重。為了實時存儲大量有效的信息，針對物理磁帶庫存儲容量小和效率低等不足，人們引進了虛擬磁帶庫技術，將高速磁盤陣列仿真成磁帶格式，節省了磁帶機上帶、定位、退帶等機械動作時間，同時無需擔心機械手故障、磁頭耗損或磁帶受潮等問題。節省成本的同時提高了備份和恢復速度，實現了實時有效地存儲海量數據信息。
    盡管虛擬磁帶庫在應對數據存儲時發揮了巨大作用，但是仍不能滿足市場需求。如何對存儲在虛擬磁帶庫系統中的數據進行重新壓縮從而更有效地利用存儲空間，便成為了如今研究的熱門課題。而重復數據刪除技術作為目前企業熱捧的技術之一，在數據壓縮處理和存儲領域具有很大的應用空間。本文提出了重復數據刪除算法在虛擬磁帶庫系統中的一種應用方案。
1 相關概念和算法介紹
1.1 重復數據刪除算法
    重復數據刪除算法又名智能壓縮算法，是一種通過消除冗余重復數據減少存儲需求的方法。
    重復數據刪除算法有多種分類方法。按照重復內容識別方法分類可分為三種：基于內容散列識別、基于內容識別和基于Hyper-factor識別；而基于消除冗余執行次序的分類則可以分為在線式消冗和后處理式消冗兩種；基于去重粒度分類可分為文件級、數據塊級和字節級消冗三種[1]。本文在虛擬磁帶庫系統的應用主要采用基于散列識別方法的數據塊級后處理式消冗方案。
1.2 數據分塊算法
    基于數據塊級的分塊算法主要有定長切分、CDC切分和滑動塊切分三種[2]。
    定長分塊算法(Fixed-Size Partition)主要采用預先分配好的塊對文件進行切分，并計算弱校驗值和MD5強校驗值。該算法的優點是簡單、性能高，但它對數據插入和刪除非常敏感，處理十分低效，不能根據內容變化作調整和優化。
    CDC(Content-Defined Chunking)算法是一種變長分塊算法，它應用數據指紋將文件分割成長度大小不等的分塊。CDC算法對文件內容變化不敏感，插入或刪除數據只會影響到較少的數據塊，其余數據塊則不受影響。該算法也有缺陷，數據塊大小的確定比較困難。
    滑動塊(Sliding Block)算法結合了定長切分和CDC切分的優點，數據塊大小固定。它對定長數據塊先計算弱校驗值，如果匹配則再計算MD5強校驗值，兩者都匹配則認為是一個數據塊邊界。該數據塊前面的數據碎片也是不定長的數據塊。如果滑動窗口移過一個塊大小的距離仍無法匹配，則認定其為一個數據塊邊界。滑動塊算法對插入和刪除問題的處理非常高效，并且能夠檢測到比CDC更多的冗余數據，但它容易產生數據碎片。
1.3 哈希查找和存儲算法
1.3.1 MD5算法
    MD5算法即消息摘要算法第5版，由MIT計算機科學實驗室和RSA數碼保安公司聯合開發，經MD2、MD3和MD4延伸而來[3]。它將文件的任意一段內容通過一系列算法壓縮成一段128 bit的信息摘要(哈希值)。其本質即為一種哈希函數，具有單向性、抗弱碰撞性和抗強碰撞性等特點。
    在MD5算法操作中，先對元數據信息進行填充，使得其字節長度對512求余結果為448；接著填充64 bit數據段長度信息，湊齊為512的整數倍；然后用4個固定的鏈接變量作為參數對MD緩沖器進行初始化；最后用4種不同的非線性函數進行輪換計算，結果輸出4個32 bit即128 bit的哈希值[4-5]。算法過程如圖1所示。

1.3.2 Bloom Filter算法
    Bloom Filter由Howard Bloom在1970年提出。它利用位數組很簡潔地表示一個集合，并能通過一組哈希映射函數判斷一個元素是否屬于這個集合。該算法具有很好的空間效率和時間效率，但是卻有一定的誤識別率(假陽性誤判)，并且刪除操作比較困難。
    該算法主要包括數據元素的查找和插入兩部分。在查找操作中，首先將目標信息存儲到一個集合S中，接著設計多個相互獨立的哈希函數及適度大小的哈希表，并設其初始值全為0。在集合S中任取一個元素，經哈希函數分別映射到哈希表中。如果所對應哈希表位置的值都為1，則說明該元素可能已經存在，但也有誤判的可能。若有任意其中一個位置不為1，則說明該元素必不存在。同樣插入操作經哈希函數計算并映射后，把相應位置的值都置為1。
2 方案設計及實現
2.1 應用場景
    圖2所示為常見的一種應用虛擬磁帶庫進行數據備份的場景。各個客戶端所產生的數據通過網絡傳送到服務器端，在服務器中備份軟件的操作下，將數據備份到虛擬磁帶庫所模擬成磁帶格式的磁盤陣列中，該磁盤陣列由相應的RAID組構成，從而進行容災保護。該數據可以實時導入、導出到相應的物理磁帶庫中。同樣，數據流的逆向即可實現數據恢復作業。在虛擬磁帶庫系統中可以對所備份的數據進行重新掃描和重復數據刪除，并存儲壓縮后的數據，選擇是否刪除原有數據，進而節省大量的磁盤空間。

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

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

    本文應用可以根據需要選擇定長、CDC、滑動塊任意一種切分方式來進行數據塊劃分。接著對所切分的數據塊進行如同文件級別的Bloom Filter和MD5雙重驗證。首先對數據塊進行Bloom Filter計算，當結果不匹配位數組B中相關位時，則表明該數據塊必不存在，對位數組中相關位進行插入和更新，并分別存儲該數據塊和相關的哈希值；如果該數據塊匹配該位數組B時，則再次進行MD5計算和校驗。如果仍然匹配，則說明該數據塊重復，只存儲該數據塊的哈希值；如果出現不匹配情況，則說明前面計算出現誤判，分別存儲該數據塊和相應的哈希值。
    數據塊及相應哈希值存儲及檢索如圖5所示。當文件A進入計算時，會生成相應哈希值并指向對應數據塊。當首次查找數據塊N不存在時，則先存入數據塊，然后再把數據塊N的索引指向該數據塊所在位置，當再次查找時，僅存儲對應哈希值。文件A檢索完畢后同樣對文件B進行相關操作。而當A’經計算與文件A內容相同時，則文件A’的索引會指向文件A的索引，當文件A’數據恢復時，通過指引直接檢索調用文件A中的索引值，從而進一步加快效率，節省存儲空間。

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

    實驗中采用分塊大小為4 KB，共對5組大小及內容不同的文件進行了數據的重復刪除處理。由表2可知，文件1中TXT文件和文件3中PDF文件存在相當數量的重復塊；而照片、音頻和視頻等文件存在較少重復數據塊。由于測試環境限制，本次測試的子文件都不相同，且數據量小，所以重刪率較低，甚至出現小于1的情況。不過數據經還原處理后，與原始數據相比完全相同，安全性能有保障，當出現大量重復文件時，效果更好。
    本文主要介紹了一種重復數據刪除算法在虛擬磁帶庫系統中的應用方法。該應用采用后處理式的數據分塊哈希計算方法來進行數據的重復刪除。數據分塊可選擇使用任一種常用的3種分塊方法，數據查找和存儲采用Bloom Filter和MD5算法雙重計算，經過設置參數有效地降低了Bloom Filter的誤判率和MD5算法的碰撞率。有效提高了存儲的時間效率和空間效率，并獲得良好的重刪率，同時完成了數據的壓縮和加密雙重功能。
參考文獻
[1] 付印芳，肖儂，劉芳.重復數據刪除關鍵技術研究進展[J].計算機研究與發展，2012，49(1)：12-20.
[2] 敖莉，舒繼武，李明強.重復數據刪除技術[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.