基于BLOOM FILTER過濾算法的重復數(shù)據(jù)刪除技術的研究與改進

朱珍

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）21-4969-03

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

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

目前文件、數(shù)據(jù)塊和字節(jié)的重復數(shù)據(jù)刪除技術存在的許多不足的問題，如數(shù)據(jù)容易損壞的危險、數(shù)據(jù)完整性弱、性能較低等。該文將從改進哈希算法和優(yōu)化重復數(shù)據(jù)刪除策略兩個方面來改進重復數(shù)據(jù)刪除技術。

1 BLOOM FILTER算法

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

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

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

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

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

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

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

3） 如果k個位置上的值不全為1，則說明該指紋值一定不在指紋索引表中，此時將該新的指紋值加入到向量V中，轉5） ；

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

5） 生成新的指紋索引節(jié)點，插入到指紋索引表中，并構造下層請求下發(fā)。

3 測試與分析

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

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

1） PostMark性能測試

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

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

2） 測試結果分析

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

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

1） 壓縮比測試

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

2） 測試結果分析

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

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

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

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

4 結束語

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

參考文獻：

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

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

[3] 周敬利，余勝生.網(wǎng)絡存儲原理與技術[M].北京：清華大學出版社，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內核編程指南[M].北京：清華大學出版社，2004：86-104.

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

[7] 時成閣等.網(wǎng)絡存儲系統(tǒng)設計[M].上海：華東師范大學出版社，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.