Bloom Filter研究進展*

嚴華云,關佶紅

(1.湖州師范學院信息與工程學院 湖州 313000；2.同濟大學電子與信息工程學院 上海 201804)

1 引言

在計算機應用領域，信息的表示和查詢是核心問題，這兩個問題常常是相關的。其中，表示意味著根據一定的規(guī)則組織信息，查詢則意味著判斷一個給定屬性值的元素是否屬于某一集合。

Bloom filter[1]是一種節(jié)省空間、高效率的數據表示和查詢結構。它利用位數組很簡潔地表示一個集合，并能以很高的概率判斷一個元素是否屬于這個集合。因此，這種數據結構適合應用在能容忍低錯誤率的場合。

Burton H.Bloom于1970年提出Bloom filter用以解決某（些）元素是否為集合中元素的判斷問題。它突破了傳統(tǒng)哈希函數的映射和存儲元素的方式，通過一定的錯誤率換取了空間的節(jié)省和查詢的高效。在20世紀70年代，其應用價值并沒有體現出來。80年代，隨著PC應用的推廣，Bloom filter的應用開始推廣，如高效地解決拼寫檢查問題[2]，解決多處理器計算機中數據庫的連接問題[3]。網絡時代的到來使得Bloom filter具有越來越多的應用，如應用到分布式數據庫中進行查詢[4,5]，應用到網絡中取代ICP以進行高速緩存查詢[6]，應用到P2P中進行高效的聯合查詢[7,8]等。肖明忠、Broder、謝鯤等分別于2003年、2004年、2007年寫了Bloom filter的綜述性文獻[9～11]。近幾年，Bloom filter及其應用又取得了新的進展，本文對Bloom filter在通信領域的研究進行歸納和展望，并介紹了Bloom filter的典型應用。

2 標準的Bloom filter

標準Bloom filter的工作原理如圖1所示。為了表達S={x1,x2,…,xn}這樣一個有n個元素的集合，Bloom filter使用k個相互獨立的哈希函數（hash function），它們分別將集合中的每個元素映射到位數組BFV的k個位中（BFV共有m位）。對任意一個元素x，第i個哈希函數映射的位置 hi(x)就會被置為 1（1≤i≤k），如果一個位置已經為 1，那么隨后映射到該位置時其值將不變。

當查詢元素zi時，用Bloom filter中的k個哈希函數映射到BFV中，如果每一個哈希函數映射到的位都為1，則認為zi屬于S，否則 zi不屬于S。

與經典的哈希函數相比，Bloom filter最大的優(yōu)勢是它的空間效率。另外，由于Bloom filter不用處理碰撞，無論集合中元素有多少，也無論多少集合元素已經加入到了位向量中，Bloom filter在增加或查找集合元素時所用的時間都為哈希函數的計算時間。由于Bloom filter對集合中的元素進行了編碼，因此想從Bloom filter的位向量中恢復集合元素并不容易，如果不想讓別人直接看到集合元素，這樣的編碼處理相當于一種加密，從而有利于保護隱私。

Bloom filter的這些優(yōu)點是有一定代價的：在判斷某一個元素zi是否屬于集合S時，有可能會把不屬于S中的元素誤認為屬于S，這種情況稱為“假陽性”的“錯誤率”（false positive），這個錯誤率可以通過概率的方法計算出來。因此，Bloom filter不適合那些“零錯誤”的應用場合。

在標準的Bloom filter中，對于使用k個哈希函數，向m位長的Bloom filter中裝入n個元素后，位向量中某一位仍然為0的概率p為：

則錯誤率fp為：

在式(2)中，令g=-(m/n)ln(p)ln(1-p)，根據對稱性法則可知，當p=1/2，g取到最小值，則fp取到最小值。

錯誤率fp最小的條件為：

由此可見，標準Bloom filter中參數m、n的比值是已知的，為了保證錯誤率最小，則要求k=(m/n)ln2，此時BFV中某一位為零的概率為1/2(即p=1/2)。將式(3)代入式(2)有：

由式(3)和式(4)可知，當m和n的比值越大則要求哈希函數的個數k越大，并且其錯誤率越小。

3 Bloom filter結構的各種經典變體

自從Bloom filter在通信領域得到廣泛應用后，研究人員在不同的應用背景下對Bloom filter進行了一些改進，下面對Bloom filter的一些典型變體進行介紹。

3.1 可刪除元素的Bloom filter

由于在Bloom filter中不可以刪除元素，參考文獻[6]在對網頁進行緩存時(集合中元素不重合)，為了更新并淘汰過時的網頁，設計了一種稱為Couting Bloom filter（計數型CBF）的變體，其具體辦法為：將圖1中向量BFV的每一位擴展成幾位（詳細如圖2所示的CBFV，文中稱擴展成的這幾位為一個計數器 (counter)）。

經擴展后，當某一個元素要插入集合S時，分別用k個哈希函數映射到CBFV的k位計數器，將這些計數器增加1；當某一個元素要從集合S刪除時，分別用k個哈希函數映射到CBFV上的k個計數器，并將這些計數器減少1個。通過擴展BFV的位成為CBFV計數器后的CBF，就能夠處理元素刪除的操作。對于網頁緩存這類不重復元素問題，當CBF中計數器用4位時，經過相應推導，出現溢出的概率為：

式(5)表示的是計數器中最大值大于等于16出現的概率，其中m是CBFV的長度。即使某一位計數器出現溢出，也不會導致馬上出現錯誤，而是刪除元素直到該位計數器為零后才會出現所謂的 “假陰性”的 “錯誤率”(false negative)，即把屬于該集合的元素誤認為不屬于該集合的錯誤，因此出現“假陰性”的“錯誤率”的概率為式(5)的2倍。因此，將CBF的計數器設計成4位是合理的。

針對CBF可能溢出的問題，有一種解決方法叫做d-Left Counting Bloom filter(dlCBF)[12]。

dlCBF通過引入一種叫做d-Left hash的更均衡的哈希函數來降低CBF向量中counter的位數。在添加一個key時，先對其作一次hash，得到d個存儲位置和一個fingerprint，然后判斷d個位置中的負載情況，并在負載最輕的幾個位置中選擇最左邊的插入。如果選擇的位置已經存儲了相同的fingerprint，就把那個cell的counter加1。在刪除一個key時，同樣地作一次hash，然后在d個存儲位置查找相應的fingerprint，如果找到就將這個cell置空或者將相應的counter減1。

在集合中刪除元素時可能會出現：不同的兩個元素的hash值（fingerprint）相同，從而刪除元素時不好判斷將哪一個counter減1。為了解決這個問題，該文引入隨機置換避免了位置重合，從而使問題得以解決。

為了節(jié)省CBF的存儲空間，提出了MultiLayer compressed counting bloom filter[13],該 Bloom filter也支持集合中刪除元素的操作。

3.2 可統(tǒng)計元素頻次的Bloom filter

當應用中需要統(tǒng)計元素出現的頻次(即重復元素問題)時，由于CBF的計數器采用固定長度的位數，會產生溢出(overflow)的問題。為了解決這種溢出，相關文獻提出了兩種方法：一種是參考文獻[14]提出的Spectral Bloom filter（SBF），由于SBF中要建立索引，查詢起來比較費時；為進一步解決SBF訪問速度的問題，參考文獻[15]提出了另一種數據結構Dynamic count filter(DCF)。對于動態(tài)計數型的Bloom filter，下面選擇DCF進行介紹。

DCF的數據結構如圖2所示，它由兩部分組成，一部分是前面提到的CBFV向量，其位長度x由集合中數據元素的總個數M和集合中不同元素的總個數n的比值取2為底的對數確定；另一部分是為了處理CBFV溢出而設計的OFV向量，其位數y值是動態(tài)變化的（DCF的動態(tài)體現在這里），其值由集合中元素出現的最高頻次所決定。DCF中計數器的值Value是由OFV和CBFV中相同下標位的二進制數連接而成。當需要查詢某元素在DCF的出現頻次時，就用DCF的k個哈希函數映射到DCF數據結構上，其中的最小值(value)就被認為是其頻次(最小值不是頻次的情況是k個位置同時出現了碰撞，這個概率和誤判率的概率相同)。

3.3 可處理動態(tài)數據集的Bloom filter

前面所介紹的Bloom filter應用有一個共同點，即事先能夠確定集合S中的元素個數m。事實上，很多應用在事先并不清楚要處理多大的數據集；或者要處理很大的一個數據集，但數據元素的加入是緩慢的。參考文獻[16]稱這種問題為增長問題，這種情況在P2P環(huán)境中經常出現。為了處理這類問題，出現了一類可以拉伸位數組 (BF)個數的Bloom filter[16～19]。下面介紹 Dynamic Bloom filter(DBF，動 態(tài)Bloom filter)。

DBF的辦法是先用一個能處理較少元素的Bloom filter來處理，當此Bloom filter達到處理元素的極限時，再生成一個和初始Bloom filter長度相同的Bloom filter，如此這般。新元素加入時映射到最新生成的Bloom filter中，查詢時在幾個子Bloom filter都同時進行查詢，只要映射到DBF中的一個子Bloom filter的k個位置的值都為1，則認為該元素為集合中的元素。

由于這種方法可以看成由多個Bloom filter向量組成的一個矩陣，由應用需要取其中一個或多個Bloom filter進行使用，因此參考文獻[16]稱之為拆分型Bloom filter。

3.4 壓縮型Bloom filter

在標準Bloom filter中，已知參數m、n的比值，為使錯誤率最小，則要求k=(m/n)ln2(具體推導見參考文獻[10])。參考文獻[20]考慮在網絡中傳播消息時要進行壓縮，這時Bloom filter不再是僅由m、n、k這3個參數決定錯誤率，應該加上z參數（表示Bloom filter的位向量被壓縮后的長度），這4個參數一起決定了錯誤率，這就是所謂的Compressed Bloom filter(壓縮型BF)。由于壓縮編碼時要服從香農編碼原理，即壓縮編碼后的最大壓縮比不小于信息熵H(P),即有最小的z=m H(P),引入z后的分析和標準的Bloom filter中的分析相同，即將z取代m代入錯誤率的表達式中。經過一定的變換分析得出：當p=1/2時，其錯誤率最大(此時的熵為1，即根本得不到壓縮,此時和標準BF中的正好相反)；當p越接近0時(k趨于無窮，此種情況不符合實際應用)和p越接近1時 (k趨于0，實際應用中1≤k≤(m/n)ln2)，其錯誤率越小，其詳細推導見參考文獻[20]。為了對壓縮型BF有更深的了解，表1列出了各個參數和錯誤率間的關系，其中z/n是固定的。

表1 壓縮型Bloom filter中各參數和錯誤率的關系

表1中第一列數據（加粗的數據）是沒有壓縮的情況，此時需要k的個數最多，且錯誤率最高。隨著壓縮比越大，則需要k的個數越少，錯誤率也更低，這說明壓縮能夠降低錯誤率。

3.5 各種典型Bloom filter的比較

表2列出了幾種經典Bloom filter的性能比較。從該表可以看出：所有的Bloom filter都具有基本的功能，即進行集合元素的表示和查詢；支持元素頻次查詢操作的Bloom filter一定支持刪除元素操作。

表2 幾種經典Bloom filter的性能比較

4 Bloom filter的應用

Bloom filter的應用包括：它表示一種壓縮數據集合,可以替代原始的數據集合,完成元素是否在集合的查詢判斷,如數據庫操作、字典查詢和文件操作[2,3,21～24]方面；Bloom filter也廣泛應用到網絡領域，包括P2P網絡[7,8,25,26]、資源路由[27]、數據幀路由標簽[28]、網絡測量管理[29～32]、網絡入侵檢測[33]、傳感器網絡數據過濾和路由[34]等；第三類是元素表示的保密性。因此，凡是有上述3類要求的，并且能容忍一定錯誤率的應用都可以將Bloom filter派上用場。Broder和Mitzenmacher在2004年的綜述論文[10]中預言：當前Bloom filter在網絡上的應用還十分有限,隨著Bloom filter被越來越多的研究人員認識和重視,它將在現代計算機網絡和一些新的學術領域得到更為廣泛的應用。確實，Bloom filter這幾年的應用研究正在而且必將繼續(xù)印證該論斷。

4.1 Bloom filter典型的分布式應用

圖3為Bloom filter在分布式系統(tǒng)中的應用例子。當客戶向服務器A提出請求時：A首先檢查本身的緩存和其他近鄰Proxy(如B)的緩存，這些緩存的目錄摘要用Bloom filter表示,如果A及其近鄰Proxy的緩存目錄摘要里有文檔信息,則向相應的近鄰Proxy請求以獲取文件,如果沒有,就直接向上級服務器發(fā)送請求。

4.2 Bloom filter的網絡資源

[35]是Bloom filter源代碼的下載地址，該源碼用Java語言實現，該源碼由Indiana大學的Liu Hongbin和Jerzak提供，它實現了兩種Bloom filter：一個是標準的Bloom filter，它用BitSet表示；另一個是支持刪除元素的Counting Bloom filter，它用一個數組表示。HashFactory(m,k)是生成BF的接口，其中需要給出兩個參數m和k（即BF的長度和哈希函數的個數），其中可供選擇的哈希函數個數k共有10個（即k不能超過10，當然自己可以根據需要擴展）。

5 總結與展望

使用Bloom filter可達到兩方面的性能：壓縮數據和高查詢效率 (時間為計算哈希函數的時間)。只要在具體應用中需要Bloom filter的任何性能，并能夠容忍較小的錯誤率，都可以引入Bloom filter。

Bloom filter雖然根據不同應用需求具有了很多變體，但是其仍有很多應用需要改進，主要有以下3方面。

（1）網絡傳輸中壓縮型Bloom filter的實現

由于Bloom filter及其變體被廣泛應用于分布式數據庫、Proxy的Cache、對等網等網絡環(huán)境中，在網絡傳輸中如何進行壓縮是一個問題。參考文獻 [20]從理論上提出了CBF，但文中沒有給出具體的實現。另外，在DCF的推理中用到了極限熵進行壓縮編碼，我們知道一般編碼是很難達到極限熵的，對特定數據集能夠達到極限熵編碼，對其他數據未必就能達到極限熵編碼，例如常見的哈夫曼編碼就是一個例子。因此，Bloom filter網絡傳輸問題的壓縮編碼算法還有待研究。

（2）Bloom filter結構在海量數據問題中的擴展

在對等網、信息檢索領域中，所涉及的數據量非常大，并且沒辦法估計數據量的大小，或者考慮到數據量是漸增和動態(tài)變化的，沒必要一開始就建立一個很大的Bloom filter，在數據量漸增和動態(tài)變化的過程中需要能夠建立一種能夠動態(tài)伸縮的Bloom filter。

（3）并行 Bloom filter的需求

在網絡Cache和一些信息安全領域用到Bloom filter時，需要Bloom filter具有快捷的速度。這種情況下，需要將Bloom filter做到硬件中，并且最好能夠提供并行計算的功能，目前Bloom filter的變體基本上都不支持并行計算的功能。Bloom filter的并行性需求有待我們去研究。

總之,自從Burton Bloom在1970年提出Bloom filter之后，Bloom filter就被廣泛用于拼寫檢查和數據庫系統(tǒng)中。隨著網絡的普及和發(fā)展，Bloom filter的研究和應用迅猛發(fā)展，新的Bloom filter變種和新的應用不斷出現。可以預見，隨著互聯網的不斷發(fā)展，Bloom filter的新變種和應用將會繼續(xù)出現。

參考文獻

1 Bloom B H.Space/time trade-offs in hash coding with allowable errors.Communications of the ACM,1970,13(7):422～426

2 Mcilroy M D.Development of a spelling list.IEEE Transactions on Communications,1982,30(1):91～99

3 Valdurez P,Gardarin G.Join and semijoin algorithms for a multiprocessor database machine.ACM Transactions on Database Systems,1984,9(1):133～161

4 MackettL F,Lohman G M.Roptimizer validation and performance evaluation for distributed queries.In:Proc of the VLDB,Kyoto,Japan,August 1986

5 Mullin J K.Optimal semijoins for distributed database systems.IEEE Transactions on Software Engineering,1990,16(5):558～560

6 Fan L,Cao P,Almeida J,et al.Summary cache:a scalable wide-area Web cache sharing protocol.ACM Transactions on Networking,2000,8(3):281～293

7 Reynolds P,Vahdat A.Efficient peer-to-peer keyword searching.In:Proc of Middleware,Riode Janeiro,Brazil,June 2003

8 Chen H H,Jin H,Wang J L,et al.Efficient multi-keyword search over P2P web.In:Proc of the WWW,Beijing,China,April 2008

9 肖明忠,代亞非.Bloom Filter及其應用綜述.計算機科學,2004,31(4):180～183

10 Broder A,Mitzenmacher M.Network applications of bloom filters:a survey.Internet Mathematics,2005,1(4):485～509

11 謝鯤,文吉剛,張大方等.布魯姆過濾器查詢算法.軟件學報,2009,20(1):96～108

12 Bonomi F,Mitzenmacher M,Panigrahy R,et al.An improved construction for counting bloom filters.In:Lecture Notes in Computer Science,Zurich,Switzerland,September 2006

13 Ficara D,Giordano S,Procissi G.MultiLayer compressed counting bloom filters.In:Proc of the Infocom,Phoenix,AZ,USA,April 2008

14 Saar C,Yossi M.Spectral bloom filters.In:Proc of the SIGMOD,San Diego,USA,June 2003

15 Aguilar-Saborit J,Trancoso P,Muntes-Mulero V.Dynamic count filters.In:Proc of the SIGMOD,Chicago,USA,June 2006

16 肖明忠,代亞非,李曉明.拆分型Bloom Filter.電子學報,2004,32(2):241～245

17 Guo D,Wu J,Chen H,et al.Theory and network applications of dynamic bloom filters.In:Proc of the Infocom,Barcelona,Spain,April 2006

18 Almeida P S,Baquero C,Preguica N.Scalable bloom filters.Information Processing Letters,2007,101(6):255～261

19 Hao F,Kodialam M,Lakshman T V.Incremental bloom filters.In:Proc of the Infocom,Phoenix,AZ,USA,April 2008

20 Mitzenmacher M.Compressed bloom filters.ACM Transactions on Networking,2002,10(5):604～612

21 Mullin J K.Optimal semijoins for distributed database systems.IEEE Transactions on Software Engineering,1990,16(5):558～560

22 Udi M,Sun W.An algorithm for approximate membership checking with application to password security.Information Processing Letters,1994,50(4):191～197

23 Gremillion L L.Designing a bloom filter for differential file access.Communications of the ACM,1982,25(9):600～604

24 James K M.A second look at bloom filters.Communications of the ACM,1983,26(8):570～571

25 Ahmed R,Boutaba R.Plexus:a scalable peer-to-peer protocol enabling efficient subset search. ACM Transactions on Networking,2009,17(1):130～143

26 張一鳴,盧錫城,鄭倩冰等.一種面向大規(guī)模P2P系統(tǒng)的快速搜索算法.軟件學報,2008,19(6):1473～1480

27 Yu H,Mahapatra R N.A memory-efficienthashing by multi-predicate bloom filters for packet classification.In:Proc of the Infocom,Phoenix,AZ,USA,April 2008

28 Kumar A,Xu J,Wang J,Spatschek O,et al.SpaceScode bloom filter for efficient persflow traffic measurement.In:Proc of IEEE Infocom,Hongkong,March 2004

29 葉明江,崔勇,徐恪等.基于有狀態(tài)Bloom filter引擎的高速分組檢測.軟件學報,2007,18(1):117～126

30 Yu H,Mahapatra R N.A memory-efficienthashing by multipredicate bloom filters for packet classification.In:Proc of Infocom,Phoenix,AZ,USA,April 2008

31 Sarang D, Haoyu S, Jonathan T, et al. Fast packet classification using bloom filters.In:Proc of the 2006 ACM/IEEE Symp Architecture for Networking and Communications Systems,2006

32 HeeyeolY,Mahapatra R.A memory-efficienthashing by multi-predicate bloom filters for packet classification.In:Proc of the Infocom,Phoenix,AZ,USA,April 2008

33 Locasto M E,Parekh J J,Keromytis A D,et al.Towards collaborative security and P2P intrusion detection.In:Proc of SMC 2005,NY,USA,June 2005

34 Hebden P,Pearce A R.Data-centric routing using bloom filters in wireless sensor networks.In:Proc of ICISIP 2006,Bangalore,India,December 2006

35 Bloomfilter,http://wwwse.inf.tu-dresden.de/xsiena/bloom_filter