朱珍

摘要：隨著企業(yè)數(shù)據(jù)信息量的不斷地增加，海量數(shù)據(jù)信息的存儲(chǔ)和不斷備份給企業(yè)的存儲(chǔ)空間帶來(lái)了巨大的存儲(chǔ)壓力。該文深入研究重復(fù)數(shù)據(jù)刪除技術(shù)，并針對(duì)目前重復(fù)數(shù)據(jù)刪除技術(shù)中存在的數(shù)據(jù)丟失及性能低等問(wèn)題以及BLOOM FILTER算法流程和重復(fù)數(shù)據(jù)刪除策略的分析和研究，提出了一種重復(fù)數(shù)據(jù)刪除技術(shù)優(yōu)化模型。測(cè)試分析表明，該優(yōu)化模型實(shí)現(xiàn)了高效和安全的重復(fù)數(shù)據(jù)刪除功能，節(jié)省了企業(yè)內(nèi)部存儲(chǔ)空問(wèn)的存儲(chǔ)成本開(kāi)銷(xiāo)。

關(guān)鍵詞：重復(fù)數(shù)據(jù)刪除技術(shù)；BLOOM FILTER算法；哈希沖突；存儲(chǔ)空間

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）21-4969-03

隨著信息化時(shí)代的推進(jìn)，各企事業(yè)單位的信息數(shù)據(jù)量不斷增長(zhǎng)，存儲(chǔ)管理員不斷努力地處理日益激增的數(shù)據(jù)，然而存儲(chǔ)這些數(shù)據(jù)對(duì)企業(yè)而言并不是最佳的解決方案，大量的文件將會(huì)加重企業(yè)數(shù)據(jù)備份以及災(zāi)難恢復(fù)系統(tǒng)的負(fù)擔(dān)。企業(yè)與其尋求更多的存儲(chǔ)數(shù)據(jù)的不同方式，如數(shù)據(jù)刪除技術(shù)，以存儲(chǔ)更少的數(shù)據(jù)。

重復(fù)數(shù)據(jù)刪除技術(shù)大致分為兩個(gè)方向，一方面是數(shù)據(jù)備份領(lǐng)域，另一方面是基礎(chǔ)存儲(chǔ)領(lǐng)域。重復(fù)數(shù)據(jù)刪除技術(shù)通過(guò)識(shí)別和消除數(shù)據(jù)環(huán)境中的冗余數(shù)據(jù)，從而大大減少需要保護(hù)的數(shù)據(jù)量，確保同樣的數(shù)據(jù)信息只被保存一次，這樣不僅顯著提高現(xiàn)有磁盤(pán)存儲(chǔ)空間的有效容量，從而使保護(hù)數(shù)據(jù)所需的物理磁盤(pán)數(shù)量更少，還有助于企業(yè)對(duì)數(shù)據(jù)的維護(hù)管理。這便可以幫助企業(yè)減輕硬件投資和后期維護(hù)所帶來(lái)的經(jīng)濟(jì)壓力。

目前文件、數(shù)據(jù)塊和字節(jié)的重復(fù)數(shù)據(jù)刪除技術(shù)存在的許多不足的問(wèn)題，如數(shù)據(jù)容易損壞的危險(xiǎn)、數(shù)據(jù)完整性弱、性能較低等。該文將從改進(jìn)哈希算法和優(yōu)化重復(fù)數(shù)據(jù)刪除策略?xún)蓚€(gè)方面來(lái)改進(jìn)重復(fù)數(shù)據(jù)刪除技術(shù)。

1 BLOOM FILTER算法

Bloom Filter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。Bloom Filter的這種高效是有一定代價(jià)的：在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會(huì)把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合（false positive）。因此，Bloom Filter不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，Bloom Filter通過(guò)極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。

Bloom過(guò)濾器對(duì)集合采用一個(gè)位串表示，并支持元素的哈希查找。其算法結(jié)構(gòu)的實(shí)質(zhì)是將集合中的元素通過(guò)k 個(gè)哈希函數(shù)映射到位串向量中。近年來(lái)Bloom Filter算法在實(shí)際中的應(yīng)用越來(lái)越廣泛，關(guān)于這種算法的相關(guān)研究工作也備受關(guān)注。標(biāo)準(zhǔn)的Bloom Filter算法的工作原理如下：如圖1所示，數(shù)據(jù)集合S={s1，s2，…，sn}共有n 個(gè)元素通過(guò)k 個(gè)哈希函數(shù)h1，h2，…，hk 映射到長(zhǎng)度為m 的位串向量V 中。通常， Bloom過(guò)濾器表示的匯總信息就是向量V。每一個(gè)哈希函數(shù)相互獨(dú)立且函數(shù)的取值范圍為{0，1，2，…，m?1}。初始狀態(tài)下，向量中的每個(gè)位都為0，對(duì)任意一個(gè)元素，第i個(gè)哈希函數(shù)映射的位置h（i）就會(huì)被置為1。注意，如果一個(gè)位置多次被置為1，那么只有第一次會(huì)起作用，后面幾次將沒(méi)有任何效果。

Bloom Filter算法主要包含兩個(gè)操作：插入操作和查詢(xún)操作。元素插入操作就是將元素插入到集合，完成元素到Bloom過(guò)濾器的向量表示；元素的查詢(xún)操作就是利用Bloom判斷元素是否在集合中。Bloom過(guò)濾器在使用前必須初始化，即將V 向量的各位初始化為0。

2 重復(fù)數(shù)據(jù)刪除策略的改進(jìn)

Bloom Filter算法的代碼實(shí)現(xiàn)中提供了初始化、插入、查詢(xún)和退出四個(gè)接口，通過(guò)調(diào)用這四個(gè)接口函數(shù)就可以實(shí)現(xiàn)過(guò)濾的功能。

1） 計(jì)算請(qǐng)求數(shù)據(jù)塊的指紋值；

2） 以指紋值為輸入，通過(guò)選取的k個(gè)哈希函數(shù)計(jì)算出k個(gè)值，然后查找向量V中相應(yīng)位置的值；

3） 如果k個(gè)位置上的值不全為1，則說(shuō)明該指紋值一定不在指紋索引表中，此時(shí)將該新的指紋值加入到向量V中，轉(zhuǎn)5） ；

4） 如果k個(gè)位置上的值全為1，則說(shuō)明該指紋值可能在指紋索引表中，此時(shí)要對(duì)該指紋值進(jìn)行檢索操作。若檢索成功，則構(gòu)造下層請(qǐng)求并下發(fā)，檢索過(guò)程結(jié)束；若檢索失敗，則說(shuō)明Bloom Filter算法出現(xiàn)了誤判，接著往下執(zhí)行。

5） 生成新的指紋索引節(jié)點(diǎn)，插入到指紋索引表中，并構(gòu)造下層請(qǐng)求下發(fā)。

3 測(cè)試與分析

3.1 系統(tǒng)性能測(cè)試與比較分析

在性能測(cè)試中在，采用兩種模式來(lái)進(jìn)行對(duì)比測(cè)試，分別為標(biāo)準(zhǔn)iSCSI模式和基于iSCSI的重復(fù)數(shù)據(jù)刪除模式。采用PostMark專(zhuān)業(yè)測(cè)試工具分別對(duì)兩種模式進(jìn)行性能測(cè)試。為了記錄和表述方便，用iet代表標(biāo)準(zhǔn)的iSCSI模式，用dup代表加入重復(fù)數(shù)據(jù)刪除的模式。

1） PostMark性能測(cè)試

PostMark是由著名的NAS提供商N(yùn)etApp開(kāi)發(fā)的，用來(lái)測(cè)試其產(chǎn)品的后端存儲(chǔ)性能。主要應(yīng)用于測(cè)試需要頻繁、大量地存取小文件的環(huán)境，比如郵件系統(tǒng)或電子商務(wù)系統(tǒng)等。本測(cè)試中主要用來(lái)測(cè)試兩種不同模式下，每秒事務(wù)數(shù)、在事務(wù)處理中平均每秒創(chuàng)建和刪除的文件數(shù)以及讀和寫(xiě)的平均傳輸速度。

PostMark的參數(shù)設(shè)置中，總的事務(wù)數(shù)是一定的，通過(guò)改變讀操作發(fā)生的頻率來(lái)測(cè)試兩種模式下每秒事務(wù)數(shù)、在事務(wù)處理中平均每秒創(chuàng)建和刪除的文件數(shù)以及讀和寫(xiě)的平均傳輸速度的變化。下圖為兩種模式下在事務(wù)處理中每秒創(chuàng)建和刪除的文件數(shù)的測(cè)試結(jié)果。

2） 測(cè)試結(jié)果分析

通過(guò)PostMark的測(cè)試結(jié)果來(lái)看，iet模式的性能比dup模式的性能要好一些。這個(gè)測(cè)試結(jié)果是符合理論預(yù)期的：重復(fù)數(shù)據(jù)刪除模塊需要進(jìn)行指紋計(jì)算和指紋檢索，會(huì)增加響應(yīng)時(shí)間，造成性能上的一定損失，所以加入了重復(fù)數(shù)據(jù)刪除模塊后，系統(tǒng)的性能會(huì)有所下降。

3.2重復(fù)數(shù)據(jù)刪除壓縮比測(cè)試

1） 壓縮比測(cè)試

重復(fù)數(shù)據(jù)刪除壓縮比的測(cè)試采用的是直接拷貝文件的方式。在對(duì)重復(fù)數(shù)據(jù)刪除壓縮比的測(cè)試中我采用了兩種格式的文件：文檔文件和視頻文件。測(cè)試過(guò)程中，記錄了重復(fù)數(shù)據(jù)刪除之前文件的大小，在拷貝過(guò)程中記錄去重后的文件大小，然后計(jì)算重復(fù)數(shù)據(jù)刪除壓縮比=去重后的文件大小/去重前的文件大小。其測(cè)試結(jié)果如圖所示：

2） 測(cè)試結(jié)果分析

通過(guò)測(cè)試結(jié)果可以計(jì)算出視頻文件的壓縮比為93.6%，文檔文件的壓縮比為50.8%，顯然文檔文件的壓縮效果要比視頻文件的壓縮效果好，說(shuō)明文檔文件分塊后的重復(fù)度更高，而視頻文件由于在編碼時(shí)已經(jīng)經(jīng)過(guò)一次壓縮，所有其重復(fù)度并不高，重復(fù)數(shù)據(jù)刪除的效果并不好。所以重復(fù)數(shù)據(jù)刪除壓縮比的高低與應(yīng)用環(huán)境密切相關(guān)，一般用于備份存儲(chǔ)系統(tǒng)、歸檔系統(tǒng)、文檔存儲(chǔ)系統(tǒng)、郵件存儲(chǔ)系統(tǒng)等重復(fù)度較高的系統(tǒng)中，去重效果較好；而如果用于視頻存儲(chǔ)系統(tǒng)或者其它大文件類(lèi)型存儲(chǔ)系統(tǒng)中，則可能去重效果并不好。

3.3 檢索過(guò)濾性能優(yōu)化的效果測(cè)試

檢索過(guò)濾算法的實(shí)現(xiàn)中加入了三個(gè)用于統(tǒng)計(jì)信息的變量，分別用于統(tǒng)計(jì)檢索請(qǐng)求總個(gè)數(shù)、被過(guò)濾的檢索請(qǐng)求個(gè)數(shù)以及誤判個(gè)數(shù)，過(guò)濾率=被過(guò)濾的請(qǐng)求個(gè)數(shù)/總檢索請(qǐng)求數(shù)，誤判率=誤判個(gè)數(shù)/總檢索請(qǐng)求數(shù)。

測(cè)試的方式采用文件直接拷貝的方式，收集了一個(gè)8GB的測(cè)試文件，里面包含視頻、安裝程序、文檔等各種格式的文件。測(cè)試結(jié)果如表1所示。

4 結(jié)束語(yǔ)

基于BLOOM FILTER算法的改進(jìn)型重復(fù)數(shù)據(jù)刪除技術(shù)方法不僅能解決由于哈希沖突造成的數(shù)據(jù)丟失問(wèn)題，而且通過(guò)改進(jìn)的BLOOM FILTER算法還可以提高系統(tǒng)的運(yùn)行效率。該方法在改進(jìn)的重復(fù)數(shù)據(jù)刪除技術(shù)中融入了備份技術(shù)增強(qiáng)了的數(shù)據(jù)保護(hù)功能，是改進(jìn)的重復(fù)數(shù)據(jù)刪除技術(shù)的優(yōu)勢(shì)所在。該文提出的基于BLOOM FILTER算法的改進(jìn)型的重復(fù)數(shù)據(jù)刪除技術(shù)方法不僅可以減少存儲(chǔ)空間和節(jié)約成本，而且它的設(shè)計(jì)思想也可能運(yùn)用于主存儲(chǔ)器的管理中去，它為目前重復(fù)數(shù)據(jù)刪除技術(shù)的研究提供了一種新的研究思路。

參考文獻(xiàn)：

[1] 王樹(shù)鵬.重復(fù)數(shù)據(jù)刪除技術(shù)的發(fā)展及應(yīng)用[J].中興通訊技術(shù)，2010（10）.

[2] 蔡盛鑫.一種基于重復(fù)數(shù)據(jù)刪除的備份系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].北京：北京郵電大學(xué)，2010.

[3] 周敬利，余勝生.網(wǎng)絡(luò)存儲(chǔ)原理與技術(shù)[M].北京：清華大學(xué)出版社，2005.

[4] Ren Jin，Xie Changsheng，Li Wei.iSCSI Protocol and Its Implementation Under Linux[J].Mini2Micro Systems，2003，24（7）：1183-1186.

[5] 張瑜，楊繼萍.Linux內(nèi)核編程指南[M].北京：清華大學(xué)出版社，2004：86-104.

[6] 倪繼利.Linux內(nèi)核分析及編程[M].北京：電子工業(yè)出版社，2005：130-203.

[7] 時(shí)成閣等.網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)設(shè)計(jì)[M].上海：華東師范大學(xué)出版社，2007：49-100.

[8] Austin Clements，Irfan Ahmad，Murali Vilayannur.Decentralized deduplication in san cluster file systems[C].Proc.of the USENIX Annual Technical Conference，2009.