基于雙布魯姆過濾器的數據排重技術

席曄文，楊金民

湖南大學 信息科學與工程學院，長沙 410082

基于雙布魯姆過濾器的數據排重技術

席曄文，楊金民

湖南大學 信息科學與工程學院，長沙 410082

1 引言

隨著計算機技術的飛速發展，數字信息量呈爆炸式的增長，占用的儲存空間越來越多。有研究指出，一般系統中數據有60%是冗余的，這個數據還會隨著系統運行時間的推移而繼續增長。由此，重復數據刪除技術[1]得到了大量的關注：它使系統數據的存儲空間暴增問題得以緩解，對系統中已存在的資源進行最大化利用；在網絡數據傳輸前將重復數據查找出來，減少對網絡帶寬的占用。

如何簡潔地表示海量的數據信息，如何快速地在海量數據中快速查找重復數據，是排重技術應用于大規模數據管理的關鍵。

現在流行的排重技術有Message Digest Algorithm MD5（MD5碼）[2]排重法，MD5碼是對任意長度的明文輸入，通過函數計算，得出的只屬于該輸入的獨一無二的指紋值，所以可以通過比對MD5碼來驗證2個文件是否相同。它的具體算法流程如下：將系統中所有文件計算MD5碼存儲到集合中并建立索引，稱為集合S。當更新文件時，計算傳入文件MD5碼并在集合S中查找，若發現集合中存在相同的MD5碼，說明該傳入文件是重復文件，刪除該文件，就達到了數據排重的目的。在效率方面，其查找過程就是將傳入文件MD5碼與全集S的MD5碼元素按集合索引一條條比對，時間復雜度為O(n)，若傳入文件全為新文件，則每次查找都要將集合從頭查到尾，所以該算法的查找時間并不盡人意，沒有對MD5碼進行任何處理直接進行查找，對其利用率還處于原始階段。而通過使用布魯姆過濾器技術來處理MD5碼可以幫助減少查找重復數據的耗時。

2 相關技術

標準布魯姆過濾器（Bloom Filter）[3-5]是一種高效、快速、精簡的信息表示查找技術，其應用相當廣泛，如P2P節點協作交互[6-7]和文件操作[8]等。Bloom Filter原理是將數據集合里的所有元素通過多個相互獨立的哈希函數映射到位串向量上，Bloom Filter所需存儲空間與元素自身大小和集合規模無關，使用一個共有m位的V向量來表示n個元素的集合，則每個元素平均只需要m n比特位，所以使用Bloom Filter表示數據可以極大地節約存儲空間。

布魯姆過濾器的具體原理如圖1：數據集合s= {x1，x2，…，xn}共n個元素分別代入到k個相互獨立的哈希函數，計算地址并映射到長度為m位的位串向量V向量中，所以一個布魯姆過濾器由k個相互獨立的哈希函數 {h1，h2，…，hk-1，hk}（它們值域為 {0，1，…，m}）和一個位串向量（它的向量初始值全為0）組成。

圖1 布魯姆過濾器結構示意圖

對向量進行插入元素操作時，當一個向量地址多次被置為1，只有第一次會起作用，后面幾次將沒有任何效果。在圖2中，X1和 X2都映射到了同1個向量地址（從左邊數第五位）。這也是Bloom Filter出現假陽性誤判[9]（false positive）的原因。

圖2 插入元素

查詢 y是否屬于數據集合，將 y代入k個哈希函數，如果所有hi(y)的位置不全為1(1≤i≤k)，那么就判定y不是集合中的元素，否則說明 y可能是集合中的元素。每查詢一個元素只需比對向量相應地址是否為1，這就是使用Bloom Filter排重遠快于MD5碼排重的原因。圖3中 y1不是集合中的元素，y2或者屬于這個集合；或者剛好是一個假陽性誤判（把不屬于這個集合的元素誤判屬于這個集合），這是因為查詢元素的地址可能是由其他元素置1的。

圖3 查詢元素

因為假陽性的存在，Bloom Filter不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下，Bloom Filter通過極少的錯誤換取了存儲空間節省與耗時的極大縮短。因此，布魯姆過濾器是允許存在一定誤判的前提下，在查詢準確率與存儲代價、算法耗時之間的折中。

3 雙布魯姆過濾器排重算法

3.1 算法設計思想

由于MD5碼排重算法對MD5碼沒有進行任何處理，直接使用MD5碼進行重復查詢，導致算法查找耗時過長的缺點。使用布魯姆過濾器技術將文件MD5碼映射到一個位串向量上，查找時只需進行位與操作即可判斷查詢元素是否已存在，這極大地減少了查詢元素的耗時。

但是使用布魯姆過濾器，若只按文件為單位計算MD5碼值排重，很可能一個大文件中已經包含了另一個小文件中的全部內容，但由于這兩個文件大小都不相同，它們的MD5碼也是不同的，小文件作為重復數據得不到排重，這說明文件級單布魯姆過濾器排重粒度太大，無法滿足高精度的數據排重要求。

如果將文件分割成等大小的數據塊，對所有數據塊的MD5碼集合以布魯姆過濾器向量形式表示進行排重。這種數據塊級單布魯姆過濾器排重雖然進入文件內部進行數據排重，但文件的大量分塊，大大增加了重復元素查找的工作量，耗時也數倍增長。

在保證高精度排重的前提下，提高排重速度，減少算法耗時，就是新算法設計的中心思想。數據塊級單布魯姆過濾器排重算法固然完成了高精度的排重，但在算法的排重過程中，有很多完全相同的文件被分割成了大量的數據塊后再一一排重，若在數據級排重前先進行一次文件級MD5碼排重，將所有相同文件先排重掉，就可以為數據塊級排重減少相當大的工作量，從而提高算法效率。

3.2 算法設計

新算法使用雙布魯姆過濾器對文件進行2級排重。第一級采用文件級的重復數據刪除策略，計算文件MD5碼值，在預先映射好的文件級布魯姆過濾器向量上查詢，發現重復值則刪除文件；第二級采用數據塊級的重復數據刪除策略[10-11]，通過預先設定好的數據塊大小將第一級排重過濾后的文件分塊，計算數據塊MD5碼，通過映射到數據塊級布魯姆過濾器向量上比對，對數據塊排重。

該算法不同于數據塊級單布魯姆過濾器一開始就對文件進行分割掃描，而是先進行以文件為單位的重復數據查找，通過第一次排重對文件集合進行過濾，減少第2級過濾器需要排重的文件數，再進行數據塊級掃描排重，以提高數據排重的細粒度。在重復文件率高的場合，可以既達到數據級排重的效果，又有趨近于文件級排重的速度。

新算法的具體流程如下：

（1）將原有文件按文件級和數據塊級分別計算MD5碼值，并映射為相應的布魯姆過濾器向量BF1，BF2。

（2）計算新傳入文件的MD5碼，在第一級布魯姆過濾器中查詢該MD5碼值。

（3）若有該MD5碼，說明該文件為重復文件，刪除文件，結束算法。

（4）若無該MD5碼，將該MD5映射到第一級布魯姆過濾器向量中。

（5）將該文件按設定的數據塊大小分割，并計算數據塊的MD5碼值。

（6）在第二級布魯姆過濾器中查詢數據塊MD5碼值。

（7）若有該MD5碼，說明該數據塊為重復，刪除數據塊，結束算法。

（8）若無該MD5碼，說明是新數據塊，存儲，將該MD5更新到第二級布魯姆過濾器向量中。

圖4 算法流程圖

3.3 算法誤判率分析

（1）假陰性誤判率 f-：該算法基于標準布魯姆過濾器實現，將數據MD5碼映射到對應的BF向量上，向量對應位不全為1則判定該數據不屬于集合，數據屬于集合則向量對應位全為1，所以算法出現假陰性誤判率（將屬于集合的數據判斷為不屬于集合）為0%，這說明算法不會將重復文件判斷為新文件，對信息進行重復儲存。

（2）假陽性誤判率 f+：設第一級布魯姆過濾器BF1假陽性誤判率為 f1，第二級布魯姆過濾器BF2假陽性誤判率為 f2，2級布魯姆過濾器采用的都是參數相同的標準布魯姆過濾器，它的假陽性誤判率為 fbf，所以2層布魯姆過濾器單獨的假陽性誤判率都為：

（3）設有查詢文件集合S，它與原始文件的重復率為r，在第二級排重中，BF2的文件集合S′是第一次排重中減去重復文件和第一級假陽性誤判文件剩下判為不重復的文件，這其中沒有誤判文件（布魯姆過濾器不存在假陰性誤判）：

設該算法誤判率為 f，為假陰性誤判文件加上假陽性誤判文件與全集合文件的大小之比。假陰性誤判率為0，則

從式（4）可知該算法誤判率只與選擇的布魯姆過濾器假陽性誤判率和查詢文件集合的重復文件率有關。在選定布魯姆過濾器參數后，理論上該算法對數據冗余越多的系統排重誤判率越低。

3.4 算法時間空間復雜度分析

3.4.1 算法時間復雜度

在初次運行該算法時，需要把原系統中所有文件分別映射為文件級和數據塊級布魯姆過濾器向量，設T1為將原計算機里的文件映射到第一級布魯姆過濾器向量BF1的時間；T2為將原計算機里的文件按分割塊大小映射到第二級布魯姆過濾器向量BF2的時間，使用標準布魯姆過濾器插入一個元素，需要進行k次哈希運算，所以一個元素插入操作的時間復雜度為O(k)。這2個耗時只在初次運行時出現，不計入一般排重時間開銷，設本算法的耗時為T：

（1）Tmd5為算法對查詢集合文件和第一次過濾后不重復文件分割的數據塊計算MD5碼的時間。

（2）T3為文件MD5碼代入 BF1中查詢的時間，T4為數據塊MD5碼代入BF2中查詢的時間。當查詢元素是否在集合中時，只需進行k次哈希計算。這也是使用布魯姆過濾器查詢優于MD5碼直接索引查詢的地方，它使得快速匹配成為可能，因為布魯姆過濾器的查詢操作是在位向量上進行，按位與操作。

（3）S的文件個數不會改變，而S和S′之間的關系由式（2）可知，當新算法在面對重復率相當大的數據集的時候，留給BF2排重的文件數也大幅減少，所以在實際應用中設定好布魯姆過濾器誤判率 fbf后，算法耗時將隨著查詢集合的重復率的增大而減少。

3.4.2 算法空間復雜度

作為一種精簡的信息表示方案，對于n個元素的集合，只需要m位向量V，其空間復雜度為O(m)。同時在分布式系統的文件排重中，排重算法將BF1和BF2傳送到待傳輸機器上，比傳輸占用空間更大的MD5值集合，也可以幫助節省網絡帶寬。

4 實驗分析與結果

在實際測試中，使用的操作系統為Windows XP，機器的配置如表1。

表1 實驗配置

實驗具體為：在一個目錄中存放有8 000個待傳輸文件的集合B，將集合B傳輸到另一個目錄A下。改變集合B中的文件使之與目錄A中的文件有不同的重復文件率r，文件分割塊設定為0.5 MB。分別使用MD5排重、文件級單布魯姆過濾器排重、數據塊級單布魯姆過濾器排重、雙層布魯姆過濾器排重新算法將集合B傳輸到目錄A下。圖5～圖7、表2從各方面比較了4種不同算法的性能：（1）數據集重復文件率與數據排重率關系（r-p見圖5）。（2）數據集重復文件率與算法耗時關系（r-t見圖6）。（3）數據集重復文件率與實驗重復文件誤判率關系（r-f見圖7）。（4）4種排重算法的理論誤判率與實際誤判率（見表2）。

圖5 集合重復文件率與數據排重率的關系

（1）圖5發現，對同一數據集，采用相同參數的布魯姆過濾器，雙層排重新算法在4種排重算法里的排重效果是最好的，對4個數據集的排重率分別達到61.62%、66.07%、70.12%、72.83%，其他3種算法里只有數據級單布魯姆過濾器排重率與之接近。

圖6 集合重復文件率與算法耗時關系

圖7 集合重復文件率與算法誤判率關系

（2）圖6得出，同排重率相近的數據塊級單布魯姆過濾器相比，雙布魯姆過濾器排重算法最少減少了43%耗時，其他3種算法耗時與文件重復率參數無關，算法時間基本保持不變，而雙布魯姆過濾器排重算法隨著r的提高耗時繼續保持下降，當重復率達到60%時，新算法比數據塊單布魯姆過濾器減少了68%耗時，這是因為新算法在1級排重中已經將重復文件進行了排重，減少了2級排重的工作量，所以新算法對于重復率高的數據集有著良好的耗時表現，隨著重復率的提升，耗時逐漸向文件級單布魯姆過濾器排重算法靠近。

（3）圖7得出，實驗中MD5碼排重算法保持0誤判率；布魯姆排重算法使用的標準布魯姆過濾器的參數取值分別為n=8 000；m=131 072；k=4，2種單層布魯姆過濾器排重算法誤判率基本保持不變，稍有上下浮動，說明重復文件比例對單層布魯姆過濾器排重算法誤判率沒有影響；而雙層布魯姆過濾器排重算法同理論分析的一樣，隨著實驗數據集重復文件比例的增加，誤判率呈減少趨勢，向單層布魯姆過濾器排重算法誤判率靠攏。

表2 4種算法排重誤判率

（4）表2得出，當布魯姆排重算法使用的標準布魯姆過濾器的參數取值分別為n=8 000；m=131 072；k=8時，使用雙布魯姆過濾器排重算法，平均每10 000個文件出現7個誤刪除，相比單層布魯姆過濾器平均每10 000個文件出現5個誤刪除差別不大，對于絕大多數排重系統，該算法是穩定可靠的。并且隨著排重系統中冗余數據的增多，新算法不管是耗時還是誤判率都會有更好的表現。

5 結束語

雙布魯姆過濾器排重算法的文件級和數據塊級的雙重排重結構是算法的優勢所在。通過文件級排重減少了第2級排重的工作量，減少了算法耗時，通過數據塊級的排重獲得了數據塊級的排重細粒度。實驗表明，雙布魯姆過濾器排重算法在保持低假陽性誤判率的前提下，對4個數據集的排重率分別達到61.62%、66.07%、70.12%、72.83%，雖然數據塊級單布魯姆過濾器排重率與新算法接近，但是耗時上新算法比之提高了43%、55%、62%、68%。隨著數據集重復率的繼續增加，新算法將呈現出越來越好的排重判斷率，所需的時間也將隨之減少。

本算法還有可進一步提高的空間，如采用改進型布魯姆過濾器[12-13]滿足集合動態增長問題，使用CDC檢測技術[14]、滑動塊分割技術[15]根據文件自身內容的特征和變化對文件進行分割。

[1]敖莉，舒繼武，李明強.重復數據刪除技術[J].軟件學報，2010，21（5）：916-929.

[2]廖海生，趙躍龍.基于MD5算法的重復數據刪除技術的研究與改進[J].計算機測量與控制，2010，18（3）：635-638.

[3]謝鯤，文吉剛，張大方，等.布魯姆過濾器查詢算法[J].軟件學報，2009，20（1）：96-108.

[4]謝鯤，張大方，文吉剛，等.布魯姆過濾器布爾代數探討[J].電子學報，2008，36（5）：869-874.

[5]謝鯤，閔應驊，張大方.分檔布魯姆過濾器的查詢算法[J].計算機學報，2007，30（4）：597-607.

[6]Jonathan L，Jacob M T，Laura S，et al.Self-organization in peer-to-peer systems[C]//Proc of the 10th Workshop onACM SIGOPS European Workshop.Saint-Emilion：ACM，2002：125-132.

[7]謝鯤，張大方，謝高崗，等.基于軌跡標簽的無結構P2P副本一致性維護算法[J].軟件學報，2007，18（1）：105-116.

[8]Gremillion L L.Designing a bloom filter for differential file access[J].Communications of the ACM，1982，25（9）：600-604.

[9]Mitzenmacher M.Compressed bloom filters[J].ACM Trans on Networking，2002，10（5）：604-612.

[10]付印金，肖儂，劉芳.重復數據刪除關鍵技術研究進展[J].計算機研究與發展，2012，49（1）：12-20.

[11]馬建庭，楊頻.基于重復數據刪除的多用戶文件備份系統[J].計算機工程與設計，2011，32（11）：3586-3589.

[12]AlmeidaP S，BaqueroC，Pregui?aN，et al.Scalable bloom filters[J].Information Processing Letters，2007，101：255-261.

[13]肖明忠，代亞非，李曉明.拆分型Bloom filter[J].電子學報，2004，32（2）：241-245.

[14]Bobbarjung D R，Jagannathan S，Dubnicki C.Improving duplicate elimination in storage systems[J].ACM Trans on Storage，2006，2（4）：424-448.

[15]Jain N，Dahlin M，Tewari R.Taper：tiered approach for eliminating redundancy in replicasynchronization[C]// Procofthe4th Usenix Confon Fileand Storage Technologies（FAST 2005）.Berkeley：USENIX Association，2005：281-294.

XI Yewen,YANG Jinmin

School of Information Science and Technology,Hunan University,Changsha 410082,China

Aiming at the disadvantage of file level single bloom filter duplicate data delete algorithm deletes duplicate data only at file size,block level single bloom filter duplicate data delete algorithm’s time-consuming is too much.In this paper, it uses 2 bloom filter,creates a 2 level duplicate data delete algorithm structure-file level and block level.The experimental results show that,double bloom filter duplicate data delete algorithm could delete duplicate data at block level,keep false positive error rate at a low level,time-consuming gets 43%～68%shorter compared with block level single bloom filter duplicate data delete algorithm.

duplicate data delete;query elements;bloom filter;MD5;false positive error rate

針對文件級單布魯姆過濾器排重算法只能以文件為單位進行數據排重，數據塊級單布魯姆過濾器排重算法耗時過多的缺點，采用2個布魯姆過濾器，創建文件級和數據塊級2級數據排重的算法結構。實驗結果表明，雙布魯姆過濾器排重算法可以以數據塊為單位對數據排重，在保持低假陽性誤判率的同時，相比數據塊級單布魯姆過濾器排重算法耗時縮短了43%～68%。

重復數據刪除；集合元素查詢；布魯姆過濾器；MD5；假陽性誤判率

A

TP311.13

10.3778/j.issn.1002-8331.1301-0141

XI Yewen,YANG Jinmin.Duplicate data delete technology based on double bloom filter.Computer Engineering and Applications,2014,50（23）：198-202.

國家自然科學基金（No.61272401，No.61173167）；“973”子項目（No.2012CB315801）。

席曄文（1987—），男，碩士研究生，研究方向為數據處理；楊金民（1967—），男，博士，教授，研究領域為故障恢復與系統容錯、系統可靠性、軟件工程。E-mail：402595164@qq.com

2013-01-14

2013-03-22

1002-8331（2014）23-0198-05

CNKI網絡優先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1646.008.html