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

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

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

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

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

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

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

    實(shí)驗(yàn)中采用分塊大小為4 KB，共對(duì)5組大小及內(nèi)容不同的文件進(jìn)行了數(shù)據(jù)的重復(fù)刪除處理,。由表2可知,，文件1中TXT文件和文件3中PDF文件存在相當(dāng)數(shù)量的重復(fù)塊；而照片,、音頻和視頻等文件存在較少重復(fù)數(shù)據(jù)塊,。由于測(cè)試環(huán)境限制，本次測(cè)試的子文件都不相同,，且數(shù)據(jù)量小,，所以重刪率較低，甚至出現(xiàn)小于1的情況,。不過數(shù)據(jù)經(jīng)還原處理后,，與原始數(shù)據(jù)相比完全相同，安全性能有保障,，當(dāng)出現(xiàn)大量重復(fù)文件時(shí),，效果更好。
    本文主要介紹了一種重復(fù)數(shù)據(jù)刪除算法在虛擬磁帶庫系統(tǒng)中的應(yīng)用方法,。該應(yīng)用采用后處理式的數(shù)據(jù)分塊哈希計(jì)算方法來進(jìn)行數(shù)據(jù)的重復(fù)刪除,。數(shù)據(jù)分塊可選擇使用任一種常用的3種分塊方法，數(shù)據(jù)查找和存儲(chǔ)采用Bloom Filter和MD5算法雙重計(jì)算,，經(jīng)過設(shè)置參數(shù)有效地降低了Bloom Filter的誤判率和MD5算法的碰撞率。有效提高了存儲(chǔ)的時(shí)間效率和空間效率,，并獲得良好的重刪率,，同時(shí)完成了數(shù)據(jù)的壓縮和加密雙重功能。
參考文獻(xiàn)
[1] 付印芳,，肖儂,，劉芳.重復(fù)數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2012，49(1)：12-20.
[2] 敖莉,，舒繼武,，李明強(qiáng).重復(fù)數(shù)據(jù)刪除技術(shù)[J].軟件學(xué)報(bào)，2010,，21(5)：916-929.
[3] RIVEST R.The MD5 message digest algorithm[M].RFC 1321,，1992.
[4] 陳少暉，翟曉寧,，閻娜,，等.MD5算法破譯過程解析[J].計(jì)算機(jī)工程與應(yīng)用，2010,，46(19)：109-112.
[5] 張裔智,，趙毅，湯小斌.MD5算法研究[J].計(jì)算機(jī)科學(xué),，2008,，35(7)：295-297.
[6] HOROWITZ E，SAHNI S,，MEHTA D.Fundamentals of data  structures in C++[M].Computer Science Press,，1995.