布隆過濾器研究綜述

華文鏑，高原，呂萌，謝平*

布隆過濾器研究綜述

華文鏑1，2，3，4，高原1，2，3，4，呂萌1，2，3，4，謝平1，2，3，4*

（1.青海師范大學 計算機學院，西寧 810016； 2.青海省物聯網重點實驗室，西寧 810008； 3.省部共建藏語智能信息處理及應用國家重點實驗室，西寧 810008； 4.高原科學與可持續發展研究院，西寧 810016）（*通信作者電子郵箱xieping@qhnu.edu.cn）

布隆過濾器（BF）是一種基于哈希策略的二進制向量數據結構，憑借分攤哈希碰撞的思想、存在單向誤判性的特點以及極小常數查詢時間復雜度，常用于表示集合元素并作為進行集合元素查詢操作的“加速器”。作為計算機工程中解決集合元素查詢問題最好的數學工具，BF在網絡工程、存儲系統、數據庫、文件系統、分布式系統等領域得到了廣泛的應用和發展。近幾年來，為了適用于各種硬件環境和應用場景，BF出現了大量基于改變結構、優化算法等思想的變種方案。隨著大數據時代的發展，對BF自身特點和操作邏輯進行改進已經成為現有集合元素查詢研究的一個重要方向。

布隆過濾器；集合元素查詢；近似成員查詢結構；哈希策略；誤判率

0 引言

集合元素查詢，即查詢一個元素是否屬于某集合，是軟件開發中一種非常常見的查詢操作［1］。為了避免遍歷整個集合、提高查詢速度，常見的處理方法是把集合中所有元素的指紋（fingerprint）保存在一個哈希表中，查詢時通過哈希映射來判斷元素是否屬于集合。但由于維護哈希表時不僅要存儲元素的指紋，還要保存處理哈希碰撞而引入的其他結構（如使用鏈地址法需要存儲額外若干個指針變量），所以使用哈希表的空間效率較低。當集合數據量較大時，哈希表無法保存在內存中，這就導致查詢時需頻繁往返于內存和二級存儲之間，使得系統執行查詢操作的消耗巨大。而在一些使用場景中，對于集合元素查詢可以容忍一定的錯誤，這個特點促使產生了近似成員查詢（Approximate Membership Query， AMQ）結構來估計性地回答這種交互式查詢（interactive query）問題［2］，布隆過濾器（Bloom Filter， BF）就是其中一個典型的代表。

BF使用一個位向量和若干個哈希映射函數，通過對元素指紋的哈希映射bit位置1來間接存儲元素，并且不再處理映射過程中發生的哈希碰撞，從而使其能夠保存在內存甚至cache中，同時解決了集合元素查詢的查詢時間和空間開銷問題。但BF并不完美，還存在以下問題：

1）BF的位向量大小固定，無法改變，使用時只能對其中存儲的元素個數進行預估計；并且一切相關性能參數都針對預估計的位向量，這使得在運行前期，BF對空間的利用并不高效；而且一旦元素個數超出預期就會導致性能大幅下降，甚至出現無法繼續使用的情況。

2）雖然BF的空間開銷小于哈希表，但一旦存儲集合過大或應用場景對查詢的準確性有較高要求時，對應的BF就無法完全存在于內存而需遷移至二級存儲中，這會大大影響BF的查詢效率，無法完全發揮出BF的最高性能。

3）BF本身就是一種犧牲查詢準確率來換取空間效率的數據結構，因此在設計BF時需要在空間效率和查詢準確率之間進行權衡，而這二者都是影響應用場景的重要因素，對此BF往往無法得到一個完美的解決方案。

4）由于BF使用哈希映射對集合元素進行間接存儲表示，所以無法從其中獲得查詢元素的完整信息；而且有限大小的位向量使哈希映射必然存在碰撞，向量中的一位可能被映射多次，所以BF無法刪除已經存儲的元素。這樣的特點在一定程度上限制了BF的應用場景。

經過研究和發展，目前出現了大量針對上述問題的優化方案和一些BF綜述文章［3-4］。本文從了解每個方案的特點、梳理方案之間的關系、明確優化方案的適用場景等角度出發，對現有主流的優化方案進行綜述。

1 標準布隆過濾器

1.1 結構組成和基本操作

標準BF的基本操作分為元素查找和元素插入。需要說明的是，在一些方案中除了插入操作外還有過濾器的構建操作，但只有那些不支持在運行途中進行元素插入，只能在集合完全靜止的場景中使用元素插入的優化方案才需要區分插入和構建操作，而標準BF可以在系統運行途中進行插入操作，所以對BF的構建可以分為若干個元素的插入操作。為了突出少數優化方案的上述特點和簡化標準BF的操作，本文只考慮查找和插入兩種操作。

圖1 標準BF結構

1.2 結構參數和性能表現

本文中BF及其改進的結構參數分為過濾器位向量大小、集合中的元素個數和哈希函數個數；性能指標包括：

1）元素查詢性能：在過濾器中執行集合元素查詢等查詢操作的時間復雜度。

2）元素插入性能：元素插入到過濾器中的時間復雜度。

3）空間開銷：過濾器中所有用于存儲集合元素結構的大小總和，通常等于。

4）查詢誤判率（False Positive Rate， FPR）：過濾器對于集合元素查詢等查詢操作做出錯誤判斷的數量占總判斷數量的比率。

進而得到誤判率的公式為

所以當位向量中一個位置為0和1的概率相同時，BF的誤判率最低，此時哈希函數的個數是ln2倍位向量大小與集合元素個數的比值。

1.3 應用場景

由于BF使用哈希映射對元素進行存儲表示，所以在使用時無需考慮存儲元素的種類和大小，這也使得BF能夠適用于大量的應用場景，成為計算機工程中解決“元素是否屬于集合”問題最好的數學工具。1970年，BF被Bloom提出時用于斷字程序（hypenation program），通過在BF中維護一個字典并使用一些簡單的規則來實現［1］。在此之后，UNIX拼寫檢查［6-7］和不安全密碼檢測［8］中也出現了BF的身影。同時BF也被廣泛應用于保存差異文件（Differential File）內容［9-10］和冰山查詢（Iceberg Query）［11］等數據庫領域，用于提升數據庫查找和數據恢復的性能。進入21世紀，隨著網絡技術的發展和響應要求的提高，BF開始大量應用于網絡應用［12］中并且取得了巨大的成功，如幫助重疊網絡（Overlap Network）與點對點網絡之間的協作［13-14］、對包中的組播轉發信息進行編碼［15］、在資源路由中使用概率算法來定位資源［16］、加速和簡化路由協議來優化數據包路由［17］以及通過在路由器等網絡設備中創建數據摘要（data summary）來對其進行評估和管理［18-19］等方面。

數據中心和存儲系統也經常使用BF來檢索內部數據和刪除重復數據［20］，如圖2中利用BF來減少檢索數據時對二級存儲的訪問。近些年來，一些非計算機工程的應用場景，如生物信息學中對于基因序列的分析［21］也開始使用BF對相關的操作進行優化。

圖2 BF在存儲系統的查詢操作中的應用

2 拆分向量的布隆過濾器

BF最常見的優化思路是優化位向量，本章主要對使用拆分位向量的幾種優化方案進行介紹。位向量的常見拆分方式分為分塊和分層。由于哈希函數映射是隨機的，在最壞的情況下，兩個相鄰哈希映射的位置距離等于過濾器位向量的大小。如果小于系統cache的大小就沒有問題，但對于較大的數據集就需要大于cache的過濾器。隨著過濾器的增大，cache的命中率會下降，cache中保存的BF就會頻繁地換入換出，使操作成本逐漸增加［22］。雖然無法針對cache進行編程，但通過對過濾器進行拆分，使每次操作最多進行一次cache與內存之間的換入換出，依然可以優化BF的操作性能。

2.1 對向量分塊

2.1.1 數據和規則的平等性

標準BF為了適用更多的應用場景，沒有考慮數據和規則的平等性問題，而實際應用中，數據失效代價的不平等、數據熱度的不平等和哈希映射之間的不平等都會影響過濾器的性能，而這些正是優化的入手點。本節將介紹以上述平等性問題為優化思想的三種優化方案。

在一些實際應用中，查詢操作并非僅在過濾器中完成，如鍵值（Key-Value， KV）存儲系統的查詢操作，不僅需要在過濾器中判斷鍵（Key）是否存在，對于存在的Key還需要尋找二級存儲中保存的對應值（Value），如果查詢發生誤判，進入二級存儲中尋找的操作將會是無效的，這個過程中的查詢代價稱為失效代價。失效代價甚至有可能大于在過濾器中查詢所有集合元素的總開銷，這就導致理論公式分析無法完美地體現在實際應用中。文獻［23］中提出的分檔式BF就以集合元素的不同失效代價為依據將集合劃分成若干子集，為每個子集的過濾器分配不同個數的哈希函數，在元素插入和查找操作不變且不影響非誤判的查詢性能的前提下，失效代價高的數據子集對應的哈希函數相對較多，查詢誤判率也就較低；而相反情況的哈希函數相對較少，誤判率也就較高。總結下來分檔式BF能夠在總體上降低查詢代價達40%，應用在Web緩存和網絡監控系統中會有非常好的效果。而對于每個子集具體的哈希函數個數，可以通過類目標函數梯度遺傳算法［24］得到，具體細節由于篇幅有限，不再贅述。

文獻［25］中提出的彈性BF則與分檔式BF一樣，同樣關注使用BF的讀取代價問題。彈性BF被設計用于LevelDB［26］、RocksDB［27］和PebblesDB［28］等KV數據庫中，能夠在保持寫和范圍查詢性能不變的情況下，提升讀取性能。在基于日志結構合并樹（Log-Structured Merge-tree， LSM-tree）［29］的KV存儲系統中通常存在一個矛盾，為了保證BF的查詢誤判率盡可能小，就要在內存中給BF分配更多的空間。當過濾器的體積過大而無法存在于內存時，就要將其保存在二級存儲中。這樣雖然實現了降低誤判率的目標，但會帶來“讀放大”的問題，影響讀取性能。而對于上述存儲結構，一般認為LSM-tree中低層的數據會比高層的數據訪問更加頻繁，Monkey［30］也正是基于此給低層對應的BF每個元素分配更大的映射空間，但在實際應用中部分高層的數據要比低層的數據更加頻繁地被訪問；并且同一個SSTable中數據的熱度也可能存在很大的差距，這也反映出Monkey對于每一層中所有過濾器使用相同配置的缺點。

如圖3所示，彈性BF將一個SSTable中的數據區（data block）分解成若干分段（segment），針對每個分段分配一個過濾器組（filter group），而一個過濾器組中又包含若干個相互獨立的小型過濾器，稱為過濾器單元（filter unit）。雖然對每個分段創建的過濾器單元個數是一樣的，但在系統運行時，系統會根據分段的熱度把若干個對應的過濾器單元加載到內存中用于查詢操作，而沒有加載到內存的部分，則只在數據插入數據庫時將數據映射其中，執行查詢操作時并不查詢它們，這樣就間接地實現了“根據數據的不同熱度分配不同大小過濾器”的目標，使其在不增大使用空間的情況下，降低了數據整體的查詢誤判率。彈性BF使用式（7）對數據熱度進行度量：

圖3 彈性BF的結構組成

Fig. 3 Structure composition of elastic BF

2.1.2 基于固態硬盤的優化方案

BF的設計初衷是讓其完全駐留在內存中，但如果系統的數據量過大并需要較低的誤判率，且內存空間受限，就不得不把過濾器保存在二級存儲介質中。由于磁盤的特征，將過濾器移植其中只會降低其平均運行性能，而不會出現太大的問題。隨著固態硬盤（Solid State Disk， SSD）應用的普及，越來越多的二級存儲介質選擇使用SSD。SSD對頁（page）讀寫和對塊（block）擦除等特點使得把過濾器簡單地移植到SSD中會造成大量的額外I/O，從而嚴重影響性能表現，因此出現了許多“分塊+緩沖”的優化方案來適配SSD。

圖4 緩沖BF結構

緩沖BF對于插入請求進行緩沖，讓大量請求連續對一個SSD頁進行操作，總體上減少了SSD的訪問次數。但對查詢操作也進行緩沖，雖然這不會增加過濾器的查詢誤判率，但會導致響應時間的增加。

文獻［33］中的布隆Flash同樣按照頁的大小對BF進行分塊，但在內存中只保存一個緩沖區且只記錄元素的插入請求。查詢和插入同樣先確定對應的子過濾器，查詢操作直接執行，而插入操作是以“頁號，偏移量”（page_id， offset）且按前者進行分組的形式保存在緩沖區中，當緩沖區數據達到設定閾值時再把其中的數據插入到對應的子過濾器中，一個分組的所有操作全部在一次寫操作中完成。執行插入的分組順序分為兩種：

1）最“臟”分組優先原則：優先執行插入請求數量最多的子過濾器，這種“貪心法”能夠最小化SSD寫操作的總數，但沒有考慮按任意頁的順序進行寫入可能導致的性能下降。

2）順序執行原則：按照緩沖區分組中頁的邏輯順序進行插入操作，這種原則的優缺點與前者相反。

布隆Flash解決了緩沖BF查詢響應時間過大等問題，且同樣使用分塊思想，相比標準BF，在SSD中有更高效的查詢和插入性能。但布隆Flash的查詢誤判率為

當且僅當每個子過濾器的誤判率相等時，等號成立。雖然實驗表明子過濾器中最多元素個數和最少元素個數的比值為1.1，但仍然可以說明布隆Flash的查詢誤判率要略高于標準BF。

上述兩種針對SSD的BF優化方案都無法動態改變過濾器的大小，而文獻［34］中的鏈式BF把SSD中的子過濾器使用鏈表結構相連，在內存中維護一個標準BF而不再是一個緩沖區，處理插入操作時，仍然像標準BF那樣對內存中的過濾器進行操作，而當內存中過濾器保存的元素數量達到上限時，將該過濾器轉移鏈接到SSD中的子過濾器鏈表中，然后在內存中重新構建一個標準BF，繼續保存插入的元素。而當查詢元素時，先查找位于內存中的過濾器，如果認定“元素屬于集合”，則返回該結果；但如果得到的結果是“元素不屬于集合”，則在SSD鏈表結構的每一個子過濾器中繼續查找該元素，直到找到該元素或所有子過濾器中都不存在該元素，再返回相應結果。從查詢和插入策略中可以看出，鏈式BF省略了緩沖請求信息的步驟，使得插入操作與標準BF一樣高效，但其查找性能會大幅下降，雖然鏈式BF能夠通過動態增加子過濾器讓每個子過濾器的查詢誤判率低于某個設定的閾值，但在最壞的情況下，查詢一個元素需要鏈式地遍歷查找每一個子過濾器，并且查找過程中的查詢誤判率也是線性疊加的，因此鏈式BF更適合“多插入，少查詢”的應用場景。

擴展型BF和快速BF也借助了拆分過濾器的思想，但它們本身還具備其他重要的改進，將分別在2.3節和2.4節中進行詳細介紹。

2.2 對向量分層

2.2.1 基于SSD的優化方案

對于SSD作為二級存儲介質的系統，雖然2.1節中介紹的對過濾器分塊的方法可以很好地解決因SSD自身特點而帶來的問題，但這些改進方案都存在同樣的問題：由于緩沖區和過濾器之間大小尺寸的差距，這些改進方案在進行插入操作時，仍然會產生較多的頁寫入和塊刪除操作。文獻［35］中提出的森林結構BF是一種應用于“重復數據刪除”的優化方案，能解決上述的問題。重復數據刪除的特點是查詢操作和插入操作不再獨立，如果查詢數據不在集合中，則需要將該數據插入集合。對于集合中數據量的變化，森林結構BF可以動態地調節自身過濾器的大小，如果內存空間大小足以容納表示集合中所有數據的過濾器，則系統直接在內存中維護一個標準BF；但如果集合數據量超出了內存的承受能力，則與其他SSD的優化方案一樣，如圖5，森林結構BF也將過濾器整體按頁大小劃分成子過濾器，而為了解決上述其他優化方案的共性問題，該方案把存儲在一個數據塊中的若干子過濾器認為是一個子過濾器塊，并以其為非根節點構造樹形結構。此時內存中的過濾器也寫入SSD中作為樹形結構的根節點，而空閑出的內存空間則當作緩沖區使用，這一點也與2.1節中幾種優化方案一致。

圖5 森林結構BF的結構變化

2.2.2 分支路徑的唯一性

文獻［36］中的布隆樹是一棵叉完全樹，它的每個節點都是一個標準BF，主要解決多集合成員查詢問題。一個系統中存在多個集合，每一個集合都有其自身的過濾器，當請求查詢一個Key對應的Value時，檢查所有過濾器，如果該Key屬于其中一個集合，則返回該集合中該Key所對應的Value，這就是多集合成員查詢問題［37］。如數據包的分類與轉發，交換機和路由器都維持有轉發表，當學習一個新的表項時，轉發表會記錄新表項中的數據，把目的IP地址和流標簽的信息視作Key，而將其轉發接口（outgoing interface）視為Key對應的Value存儲在對應接口的過濾器中。這樣每一個轉發接口都對應一個過濾器，當后續數據包到達時，交換機和路由器根據包中信息查找所有過濾器，并按照查到的對應值（轉發接口）把包轉發出去。布隆樹的每一個葉節點都隱含地對應著一個值，值的取值個數就是葉節點數，因此從根節點到不同值的路徑也是不同的，每一個節點都對應著個哈希函數集合，每個集合包含若干個獨立的哈希函數，樹中相同層上每個集合的函數個數相同。而由于葉節點對應過濾器的含義是“該Key是否對應這個葉節點隱含的Value”，所以只需一個哈希函數集合。針對每一個KV，將Key按照Value的路徑選取對應的哈希函數集，映射到這個路徑經過的每一個BF節點中。查找時，從根節點開始使用每一個哈希函數集合映射檢查Key的存在，如果結果返回“真”，則根據返回“真”的對應路徑繼續尋找，直到根節點過濾器返回結果，如果返回“真”，就可以得到該Key對應的Value，即該根節點的隱含Value；如果根節點過濾器返回“假”或路徑中的非葉節點所有哈希函數集合的映射檢查結果都為“假”，則說明該Key不屬于集合。查詢中布隆樹可能出現兩種誤判的情況：

1）對于不屬于集合的Key，返回了一個對應的Value，這種誤判率與普通BF的查詢誤判本質相同；

2）對于一個Key（無論是否屬于集合），查詢出了多個對應的Value，無法確定哪個Value是正確的，這稱為分類錯誤（classification failure）。

由于過濾器自身的樹形結構，父節點中產生的誤判可能通過在其子節點的判斷中糾正過來，所以在實際應用中查詢誤判率不會增加；而且布隆樹能夠在相同的空間中比標準BF多存儲127%的數據，并將查找性能提升37.5%左右；此外，布隆樹還能通過“把路徑引入Key中來減少哈希函數個數”“對值進行‘或’運算使映射更加均勻化”和“并行訪問來縮短訪問時間”的方法對其做進一步的優化。

2.2.3 優化范圍查詢

圖6 Ⅰ型過濾器結構

其中：表示Ⅱ型過濾器的層數；FPR表示第層BF的查詢誤判率。Ⅱ型過濾器的動態策略是當系統時間達到閾值時，重新創建一個BF作為第0層，原有過濾器的層數均加1。這樣后續時間的元素就可以繼續插入了。

持久型BF成功將時間范圍查詢減低到了對數級別，并且由于應用場景的特殊性，過濾器無需支持刪除操作。而文獻［39］中的羅塞塔（Rosetta）則是在不影響普通成員資格查詢操作性能的前提下，優化了KV存儲系統的范圍查詢問題，把RocksDB中的范圍查詢性能提升了近40倍。它使用了目前該問題最先進的前綴BF［38］和SuRF［40］所使用的“前綴技術”，即存儲和查詢集合元素的前綴來優化解決范圍查詢問題。但在存儲系統的范圍查詢中，對于較小范圍查詢的結果有很大的可能為空（范圍中根本不存在元素）。當這種情況發生時，上述的兩種方法會造成大量的負載，而Rosetta可以很好地解決這個問題。一個Rosetta實例針對LSM?tree中的一個持久性系列（）為集合而創建，其樹形結構的層數與集合中元素前綴位數的最大值相同，每一層仍是一個標準BF，系統把集合中所有長度為的前綴通過哈希映射的方式插入到第層的過濾器中，就可以將Rosetta看成一個隱式的線段樹。在執行范圍查詢時，先將查詢范圍進行劃分，在樹形結構中找到能正好覆蓋它們的前綴節點（這些節點很可能不在同一層中），如查詢范圍是［12，14］，其對應的二進制為1100、1101和1110，前綴110和1110就可以正好覆蓋。然后使用標準BF的查詢操作在對應層中查詢這些前綴，如果查找的前綴節點不在最后一層，且查詢結果為“真”，則需要向隱式線段樹中其孩子節點繼續遞歸查詢，查詢途中一旦遞歸查詢結果返回“假”，則說明以該節點表示前綴的元素不存在，只有遞歸查詢一直到最后一層仍為“真”，才說明對應表示的元素屬于集合，也就可以說明在總查詢范圍中存在該元素。而如果找到的范圍覆蓋在最后一層或不在最后一層但結果為“假”，則無需繼續查詢。前者的查詢結果直接表示對應元素是否存在，而后者直接說明集合中不存在以該節點表示為前綴的元素。這樣如果查詢的范圍為空，則可以很快地在上層節點中被知曉，從而避免過大的負載。而普通的成員資格查詢直接在最后一層BF中就可完成，因為最后一層中插入的元素前綴就是元素本身。

由于一個Rosetta只針對一個持久性系列且一個系列中元素Key的取值范圍不同，所以導致存儲系統中每個Rosetta都不一樣，這就使系統可以對每個Rosetta進行“定制”，如根據數據的熱度為較熱的Rosetta分配更大的空間，以降低其查詢誤判率，或對于KV范圍較小的系列只設定單層BF等操作。并且由于LSM-tree的合并操作，一個Rosetta實例的生命周期不會太長，會因為舊數據的合并而回收并重新構造，這也反過來為Rosetta的定制提供了方便。

總結來說，將過濾器分層更多地是利用層次結構層數是節點個數對數級的特點來對原始方案進行優化，除了上述的這些優化方案，還有許多對過濾器分層的方案，如多層壓縮BF，詳細介紹見4.1節。

3 改進結構的布隆過濾器

第2章中介紹的優化方案僅僅是對過濾器進行了結構上的拆分，并沒有改變過濾器的本質，這導致這些優化方案只是改變了BF的操作邏輯，并沒有改變具體操作過濾器的步驟和方法，也就只針對特定的應用場景優化了相關的一些性能參數。本章將介紹5個改進結構的過濾器優化方案，它們從本質上改進了BF的結構，包括過濾器向量類型、過濾器擴展策略和哈希映射范圍。

3.1 計數型布隆過濾器

本文在開頭中提到，BF無法支持刪除的缺點，而在實際應用中存在大量可以使用BF對其查詢性能進行優化且同樣對刪除元素存在需求的應用場景，比如對于數據倉庫來說，維持一個數據的滑動窗口（sliding window）需要一種支持刪除操作的BF來優化其性能。流數據（streaming data）中通常只使用當前一小時或一天的數據，如果采用支持刪除操作的BF，其性能表現將進一步提高［39］。

雖然計數型BF能夠對元素計數，但是其向量中的每一個計數器都存在相同的上限，如果集合中相同的元素過多或哈希碰撞頻繁就會導致計數器溢出，從而影響查詢操作，導致把本屬于集合的元素判斷成不屬于，這就破壞了BF的“單向誤判性”。而如果分配向量每一位的位數過多，就會導致空間上的浪費，根據壇子模型（urn model）和對實際應用情況的統計，4 bit是一個適用于大多數使用場景的選擇。計數型BF簡單地更改了向量的類型就在不降低過濾器操作性能的基礎上增加了刪除操作，并且由于如負載平衡、緩存、路由和差異化服務等眾多應用領域和場景對刪除元素的操作存在需求，計數型BF取得了重大的成功，Facebook的分布式存儲系統Cassandra［42］、Chrome瀏覽器［43］以及谷歌公司的數據庫系統BigTable［44］等產品中都有計數型BF的身影，它甚至成為了標準BF的替代品和BF改進基礎，大量的改進方案都在計數型BF基礎上進行。

3.2 譜型布隆過濾器

計數型BF把位向量擴展成了計數器向量從而支持了元素刪除操作，但是從計數器中的映射次數還可以挖掘出更多的信息。在一些數據流應用中，需要查詢的不是一個元素是否屬于集合，而是查詢該元素在集中的個數。文獻［45］中提出的譜型（spectral）布隆過濾器是一種基于計數型BF的改進方案，通過對計數器中數據進行分析，使其支持查詢元素個數的操作。也正是如此，該過濾器能夠過濾出某個范圍（spectrum）中重復出現的元素，因而得名譜型布隆過濾器（譜型BF）。

除了支持元素個數的查詢，譜型BF還利用索引機制使計數器能夠動態伸縮，更加高效地利用空間。譜型BF中所有計數器需要的最少位數為

除此之外，譜型BF對元素個數查詢還有兩個算法上的優化：

3.3 動態計數型過濾器

如圖7，CBFV的每一項都是一個普通的計數型BF的計數器，大小固定為

其中：為起始狀態下集合中的元素總數，為起始狀態下集合中不同元素的個數。所以

OFV的每一項是一個動態變化且同時變化的計數器，顧名思義用來處理前者對應計數器的溢出，所以映射次數的最大值決定了溢出計數器向量的大小：

元素插入或刪除時，先修改CBFV中哈希映射位置對應的計數器，如果計數器之前已經達到最大值或最小值，則會發生上溢或下溢現象，這時先調節CBFV中對應的溢出計數器，再向OFV中的對應計數器進行加1或減1操作即可。如果OFV的對應計數器之前同樣達到了最大值或最小值，就先對OFV中的每一個計數器擴展一位（如果刪除后，所有計數器的最高位都為0，就縮小一位），再修改這個對應的計數器。這種計數器向量的擴展和縮小稱為重建，其開銷很大，必須創建一個新OFV，然后把舊OFV的值拷貝到新OFV中，最后釋放舊OFV的空間。所以不像插入元素時必須重建，刪除操作可以不立即重建，而是等待一定時間或達到一定閾值后再重建，這樣既減少了刪除操作重建的次數，同時也能避免一些插入時的重建請求。

圖7 動態計數型過濾器的結構

3.4 擴展型布隆過濾器

當執行查詢操作時，擴展型BF先從最新創建的過濾器開始查找，查找方法與標準BF相同，如果找到元素則返回“元素屬于集合”，否則到次新創建的過濾器中繼續查找，直到找到該元素并返回“真”，如果查找0仍沒找到該元素，則返回“元素不屬于集合”。而對于插入操作，首先判斷此前最新創建的過濾器其存儲能力是否已經達到了上限，如果已經達到上限，則按照規則創建一個新的過濾器，并按照與標準BF相同的方式把元素插入到該過濾器中；但如果該擴展型BF并沒有達到存儲上限，則直接把元素插入到最新創建的過濾器中即可。

3.5 快速布隆過濾器

現代高端路由器和防火墻主要在硬件上實現它們對于每個數據包的操作，這使其能夠在幾個時鐘周期內轉發每個數據包。為了適應如此高的吞吐量，許多涉及數據包處理的網絡功能也必須在硬件中實現，而在內存中的BF無法實現這樣巨大的吞吐量。文獻［49］中的快速BF就是一種優化不同BF訪問性能的改進方案。

標準BF的哈希映射是全局的，哈希映射每個元素需要訪問內存中的次數不同。機器字是處理器和內存之間的傳送單位，快速BF的核心思想是限制一個元素的哈希映射范圍為若干個機器字長，使處理器對一個元素的查詢更快速地進行。普通BF要映射一個元素，通常需要的數據大小為

3.6 性能對比及分析

以上5種改進方案都針對過濾器的結構本身進行了改進。譜型BF和動態計數型過濾器都是在計數型BF基礎上進行了改進，二者都消除了計數器溢出的問題。計數型BF由于僅把比特位變成計數器，所以只在空間使用上是普通BF的計數器位數倍，其他性能沒有改變。而譜型BF和動態計數型過濾器為了動態改變計數器位數進一步增加了空間的使用，在計數器數值普遍不大的情況下，動態計數型過濾器由于不用維護復雜的索引結構，使用空間比譜型BF要少。如果將計數器數值逐漸增大，譜型BF在空間占用上的優勢就會越來越明顯。在查詢性能上，二者都有所下降，動態計數型過濾器比計數型過濾器在查詢時多訪問一次內存，而譜型BF在普通查詢時最多要進行5次內存的訪問。在重構方面，由于譜型BF的重構僅僅針對一個計數器，而動態計數型過濾器是針對所有計數器，所以譜型BF的重構頻率更高，插入和刪除元素的性能也就更差；但譜型BF支持了元素個數的查詢操作，并使用改進的算法使其誤判率比普通查詢的誤判率還小。

不同于以上兩種方案，擴展型BF和快速BF是針對普通BF的改進方案。前者犧牲查詢性能為原來的對數倍而適用于集合元素動態變化的場景，并保持元素插入性能不變；而后者通過限制元素的映射范圍提高了查詢操作的性能，但在其應用場景中數據集必須是靜態的，在一開始就要構建好整個過濾器，并且不能在系統的運行過程中插入元素。擴展型BF和快速BF對于擴展性和限制哈希映射區域的優化在本文前面介紹的幾種優化方案中已有所提及，但之前的方案都不是將此作為優化的重點，只是為了優化其他方面而被動地進行擴展和限制映射，所以采用了最簡單方便的方法。而3.4節和3.5節中的兩個過濾器均采用了動態變化的擴展方案和映射策略，主動對擴展性和映射性能進行優化。另外，這二者的改進思想很容易移植到計數型BF上，從而使其支持元素刪除操作，應用到更多的領域中。

表1 幾種基于計數型BF改進結構方案的對比

表2 幾種基于普通BF改進結構方案的對比

4 優化哈希策略的布隆過濾器

哈希函數作為BF的重要組成部分，使集合元素以存儲空間效率極高的方式存儲在過濾器中，并且哈希函數還可以統一集合元素的數據類型和長度，無論是長短字符串還是大小數值，通過哈希函數計算都可以變成類型大小相同的數據，從而便于查詢和管理。在BF中，哈希函數的輸出值通常有兩種用途：

1）用作地址：在位向量表中存儲一個元素，使用哈希函數生成若干個存儲的隨機地址。

2）用作元素的指紋：當BF存儲的集合元素之間數據類型不一致時，通常先對元素進行一次哈希運算得到該元素的指紋，然后對該元素的指紋再利用上述的第一種用途保存在過濾器中。這既保證了BF存儲數據類型的多樣性，也實現了存儲一致性。

但是沒有哈希函數是完全隨機的，只要映射范圍是有限的，就一定會存在碰撞的可能。并且一個普通哈希函數的輸出服從泊松（Poisson）分布，而BF中的個哈希函數之間相互獨立，所以依然服從泊松分布［41］。在實際應用中哈希映射的位向量位置是不均勻的，這會使碰撞率變得更大，進而增加誤判率，所以就出現了一些針對降低碰撞率和均勻分布的BF改進方案。

4.1 “完美”哈希

文獻［50］中提出的Bloomier過濾器使用了一種“完美”哈希（perfect hash）策略，在普通哈希映射之后對映射結果進行統計和調整，讓集合中每一個元素的映射位置結果不同，從而實現無碰撞的元素存儲。另外，標準BF的查詢操作僅僅回答了“元素是否屬于集合”，而Bloomier過濾器能存儲一個較小值域下的函數值，也就是KV中的Value，可以通過Key快速地找到對應的Value。所以從某種意義上來說，Bloomier過濾器不僅僅是一個過濾器，還是一個存儲結構。但由于需要在計算哈希映射之后對映射結果進行統計和調整，Bloomier過濾器僅適用于靜態集合，過濾器一旦建立結束就不能再向其中插入或刪除元素。

Bloomier過濾器構建操作就是利用“完美”哈希策略插入所有集合元素的過程。它使用貪心思想來對元素映射：分析每個元素所有可能的映射位置，每次找出具有不與任何其他元素存在映射碰撞的元素，并把其獨一無二的映射位置作為其插入位置，記錄完所有元素的插入位置后，按倒序把值插入到過濾器中。但問題在于元素查詢時無法確定哪一個映射位置為該元素的插入位置，所以Bloomier過濾器在元素插入時對值、所有可能映射位置的過濾器值和一個用于降低查詢誤判率的額外哈希值進行“異或”操作后進行存儲，

但如果執行的是元素成員資格查詢，還需判斷反向異或結果是否包含于值函數的值域，如果“包含于”則說明元素屬于集合，否則不屬于集合。Bloomier過濾器雖然使元素的映射位置不再有碰撞產生，但由于Key與Value之間的映射仍有可能存在碰撞（不屬于集合的Key也能映射出合法的Value），所以查詢操作依然存在誤判率。

雖然不支持插入和刪除操作，但Bloomier過濾器通過建立兩個過濾器可以允許修改（update）元素的值。二者中的一個過濾器用于存儲另一個過濾器中Key對應Value的存儲位置：

由于Bloomier過濾器直接對值進行存儲，所以過濾器不是位向量，而是一個存儲值的空間，并且其可以直接獲取到Key對應的Value，所以對比標準BF的空間使用也就沒有什么意義。因為它存儲元素的特性，Bloomier過濾器特別適合作為存儲系統中的緩存，讓其存在于內存中并存儲一些系統中的熱數據，在查詢它們時無需進入二級存儲介質中，直接在內存即可完成，這樣能大大縮短了查找時間，但缺點是在刪除其中數據時或每隔一段時間需要對過濾器進行一次重構。

4.2 d?left哈希

對于靜態集合來說，“完美”哈希策略無疑是一個不錯的選擇，可以實現本質上的最佳性能。但一旦集合變為動態，即涉及插入和刪除操作，如果仍然使用“完美”哈希策略，就需要對過濾器進行頻繁的重構，反而降低了性能。?left哈希是一種遵循“Always-Go-Left”原則［51］而映射均勻的哈希策略，提升了過濾器的空間使用效率。其根本思想是將哈希表平均分為個子表，對于每一個插入元素使用哈希函數提供其在每一個子表中的相關映射位置（這些位置是相互獨立的），選擇存儲元素個數最少的子表進行插入，如果多個子表都是最少元素則存儲在其中最左側的子表中，從而實現元素的均勻插入。

4.3 哈希表

圖8 商型過濾器的存儲單元

元素插入與查詢操作相似，需要說明的是，找到元素所在系列后，商型過濾器按照元素余的大小順序進行存儲，當插入位置已存在元素則按照“插入排序”的規則，把已存在元素及其之后的元素向后移動，再插入元素并調整相關的信息位。不難理解商型過濾器同樣支持刪除操作，與插入操作相反，元素刪除后，將其后面的元素向前移動并調整相關的信息位即可。

商型過濾器僅僅比標準BF的使用空間大20%，但支持刪除操作，這遠遠優于計數型BF，但大量移動元素和修改信息位的操作使元素插入和刪除的性能不如計數型BF；并且由于元素是按照大小順序存儲的，所以商型過濾器可以在不需要進行元素重哈希（re-hash）的情況下通過類似于“合并排序”的操作對兩個過濾器進行合并，也就間接地使商型過濾器能夠動態調節其大小。這種便于合并且自身有序的特點使商型過濾器特別適合用在基于LSM-tree的KV存儲系統中，優化存儲系統中元素查詢的效率。

表3 三個信息位所有可能情況的含義

商型過濾器還產生了兩種針對SSD優化的變種：緩存型商過濾器和瀑布過濾器。與2.1.2節中對于SSD優化的方案類似，緩存型商過濾器分別在內存和SSD中各創建了一個商型過濾器，當緩存型商過濾器中的元素達到系統設定查詢誤判率下個數的上限時，將其中的元素依次插入到SSD商型過濾器中，再從緩存型商過濾器中刪除它們；而瀑布過濾器則是像瀑布一樣，當內存商型過濾器“滿”時，將其與SSD商型過濾器合并保存在SSD中，而內存中則再重新創建一個商型過濾器。這兩個變種都在不影響查詢誤判率的情況下，對SSD的特殊結構特點更加友好。

4.4 布谷鳥哈希

圖9 Cuckoo哈希的元素插入操作

文獻［57］中的布谷鳥過濾器（Cuckoo Filter， CF）則是一種基于布谷鳥哈希的過濾器，它在空間使用、操作性能和實現難易方面都由于大部分的BF改進方案。CF的每一個位置都允許存儲固定數量的元素，并且與?left計數型BF一樣存儲元素的指紋。但由于使用哈希函數計算元素指紋是一個單向操作，所以無法針對過濾器中的某一指紋計算其對應元素的兩個映射位置。CF對此采用的方法是部分關鍵Cuckoo哈希（partial-key Cuckoo hashing）［58］，對于每個指紋僅使用一個哈希函數計算一個映射位置：

而另一個映射位置通過對式（27）的結果進一步計算得出：

以上三種優化方案，除了都針對哈希策略進行了優化外，還改變了過濾器的存儲內容。表4是它們之間存儲內容及各項性能指標的對比情況，這些修改方案的過濾器不再存儲bit位或是過濾器位置被映射的次數，而是存儲插入到該位置元素的指紋（?left哈希計數型BF存儲的是元素指紋和計數器），目的是統一插入元素的數據格式使其適用更多的應用場景。

表4 三種優化方案的對比

4.5 可變增量哈希

圖10 插入元素到可變增量計數型BF中

5 其他改進方案

5.1 結構壓縮

對于分布式系統來說，BF常需要作為信息在系統網絡中進行傳輸，其中處理聯接（join）是一個重要的應用。布隆聯接（Bloomjoin）是一種基于BF應用聯接問題的策略［62］，設需要通過屬性來連接關系和，BF是指把.存儲在一個BF中然后傳輸給關系，再針對這個BF過濾出集合中不關于該聯接的部分，并把剩余部分當作結果傳回關系來完成聯接請求。這樣大幅減少了分布式系統中各節點之間通信所傳輸的信息量。而如果能減少系統中節點之間的交互次數和交互過程中的信息量就可以大幅改善整個系統的運行性能，結構壓縮的BF對于這種應用場景無疑是友好的。

對式（32）求導得：

圖11 普通BF和壓縮型BF的誤判率變化

BF的壓縮不僅體現在過濾器大小上，對于計數型BF來說，可以對計數器中的數據進行壓縮降低溢出的可能性，或在設計上減少計數器的位數，從而減少計數器的空間使用。文獻［63］中的哈夫曼編碼（Huffman Coding）計數型BF就是對過濾器中內容進行哈夫曼編碼的一種優化方案，由于哈夫曼編碼能夠將集合中元素的編碼數據量降到最低，所以相較于計數型BF節省了近50%的內存空間。觀察結果表明，如圖12，當對計數型BF的計數器數值編碼時，一個數值的哈夫曼編碼長度等于該數值加1，即

這樣的優化方案看似把計數型BF的空間壓縮到了最小，但方案中的松弛位和查詢表則是從側面增大了過濾器的使用空間。多層壓縮BF［63］在哈夫曼編碼計數型BF的基礎上使用了多層結構解決了上述的問題。2.2節中介紹的幾種對過濾器分層方案雖然把一維的過濾器擴展成了二維結構，但每一層中過濾器依然是一維的；而多層壓縮BF把計數器中的數值進行跨層存儲，即從最底層開始向上每一層都存儲計數器數值中的一位，并且由于存儲的是哈夫曼編碼，是二進制數，所以每層中保存的只是標準過濾器。當需要計數器具體數值時可以通過一定的規則來獲取每層中計數器的對應數據。

除了上述兩種結構壓縮方案之外，譜型BF在作為數據進行傳輸時，也可以使用以利亞加瑪碼（Elias Gamma Code）對其進行壓縮以減少傳輸數據的大小［45］。

圖12 根據計數器值構建的哈夫曼樹

5.2 值存儲

在一些使用場景中，存儲元素的取值范圍很小，這就使得可以在BF中直接存儲元素的值。4.1節中的Bloomier過濾器就是一種直接將值保存在過濾器中的改進方案，2.2節中的布隆樹則是讓其樹形結構的葉子節點個數與值的種類個數相同，從而間接地用葉子節點來表示元素的值。文獻［64］中提出的狀態BF顧名思義是針對狀態應用場景的BF，這里的狀態是指網絡中的并發狀態機（Concurrent State Machine），將狀態BF用作近似并發狀態機（Approximate Concurrent State Machine），即近似估計網絡中大量數據流的狀態，從而用于視頻流量控制（video congestion control）和入侵檢測（intrusion detection）等方面。

網絡中的數據流提供流標簽和狀態字符串的KV（flow-id， state string）來記錄網絡中流狀態的變化，狀態BF類似于計數型BF和Bloomier過濾器的結合，對每個流元素仍然使用個哈希函數映射到過濾器中。過濾器的每一個存儲單元包括一個用于存儲狀態值的空間和一個計數器，這樣就可以直接修改存儲的狀態值，而不必執行“刪除舊元素后重新插入新元素”來對元素進行修改。與標準BF不同的是，狀態BF不具有單向誤判性，有多種誤判的可能：

1）查詢一個不存在的流時，過濾器返回一個有效的狀態值；

2）查詢一個存在的流時，過濾器無法找到其對應的狀態值；

3）查詢一個存在的流時，過濾器返回了一個錯誤的狀態值。

而狀態BF此外又引入了一個全新的狀態值，當映射位置出現沖突時，對應位置存儲的狀態值改為“不知道（Don’t Know， DK）”。在必要時，查詢結果返回DK，就可以減小上述三種誤判產生的不良影響。這樣對應的過濾器操作也會發生變化：

1）插入流元素時：如果映射位置的計數器值為0，則寫入該元素的狀態值，并更新計數器值為1；如果映射位置的狀態值為DK或與插入元素的狀態值相等，就讓計數器的值原地加1；而如果映射位置的狀態值不等于插入元素的狀態值，則將映射位置的狀態值改為DK，并增加計數器的值。

2）修改流元素時：先看映射位置的狀態值是否為DK，如果是，則無法修改；否則如果映射位置的計數器值為1，就直接修改其存儲狀態值，但如果計數器值超過1，則只能把映射位置的狀態值改成DK。

3）刪除流元素時：如果映射位置的計數器值為1，則將其置為0，并擦除原本保存的狀態值；否則在計數器數值減1的基礎上，把映射位置的狀態值改為DK。

4）對于流元素的查詢，需要檢查所有映射位置的狀態值：如果全部為DK，則返回DK；而如果檢查到的狀態值有和DK兩種結果，則返回；其他情況說明該流元素根本不屬于集合。

此外，狀態BF通過使用標志位和一個全局的計數器實現了“刪除過濾器中超時流元素”的功能，并且還能搭配“存儲元素指紋”和“?left哈希策略”使其適用于Blooimer過濾器無法勝任的動態場景中。

6 改進方案的分析與討論

BF自1970年提出至今，據不完全統計，已經出現了超過60種的優化和變形［65］，近幾年還有如堆棧過濾器［66］、Chucky［67］等優化方案不斷地出現。表5對本文提到的25種現有典型BF優化方案和標準BF從查詢性能、插入性能、空間使用和誤判率四個通用性能指標，以及使用場景共5個方面進行了對比分析和總結，其中：√表示對此性能優化，×表示犧牲此性能，—表示此性能沒有改變或無法比較。這些改進方案大多數是針對一個特定的應用場景提出的，所以沒有最好最壞之分；但有些改進方案如計數型BF是標準BF的通用替代品，?left哈希計數型BF和CF是計數型BF的標準替代品。所有改進方案中使用一種以上優化思想的有擴展型BF和快速BF，它們在改進過濾器結構的基礎上繼續對過濾器進行拆分；瀑布過濾器則對多個哈希表進行合并，讓商型過濾器對SSD結構更加友好。

對結構進行拆分是本文所介紹的優化思想中最簡單的一種，而不管對過濾器是分塊還是分層，都有以下兩點原因：第一，讓過濾器充分考慮或者借助數據或規則的平等性，對不同的集合元素進行“定制化”使其更加適合集合元素的某些特點，從而在整體上提高過濾器的性能；第二，拆分過濾器縮小整個過濾器的尺寸，讓其適用于新型存儲介質 SSD的結構特點，減少多余的寫入和擦除操作。

表5 布隆過濾器改進方案對比

對結構進行改進的思想一般是給BF增加功能或在原有改進的基礎上繼續進行挖掘優化。計數型BF增加了刪除元素操作，譜型BF和動態計數型過濾器讓計數型BF大小收縮，使其結構更加靈活，并且譜型BF繼續挖掘出了更多計數器的含義，進而增加了多重集中查詢元素個數的操作。擴展型和快速BF在普通擴展和減少I/O訪問方案的基礎上對結構改進，進一步優化了擴展和減少I/O的性能。

大多數對BF的改進都是著眼于如何優化過濾器，對于哈希策略的優化是優化BF的另一個方向，其實質是改進BF的操作邏輯。并且大多數的哈希策略不會針對某個特定的應用場景，一旦某個哈希策略能夠優化標準BF的性能，就能應用在絕大多數的場景中。在本文提到的哈希策略中，“完美哈希”集合完全避免了哈希碰撞，但需要對元素進行預處理并且無法支持動態的集合；?left哈希和Cuckoo哈希都是讓元素均勻映射在過濾器中，減少過濾器空間的浪費，但?left需要對刪除元素進行特定的操作，而CF雖然在查詢和刪除操作上的性能出眾，但在元素插入時容易由于哈希碰撞而轉移大量無關元素的位置，造成性能浪費；可變增量計數型BF借助特殊序列的特殊性質，讓過濾器的每個計數器在較小映射次數時不再有查詢誤判，但一旦映射次數超過特定值，查詢誤判就會重新存在，并且對計數器每次做不同增量的操作使得計數器更容易溢出。

對于結構壓縮和值存儲兩方面優化，因受具體應用場景的影響很大，所以只有少量的改進方案。作為一個經典的優化方案，壓縮BF使用現有的壓縮技術對過濾器進行壓縮，優化了比較棘手的不同系統間的通信問題，并從理論上證明了這種結構上的壓縮不僅可以減少空間的使用，還能降低過濾器的查詢誤判率。多層壓縮BF使用哈夫曼編碼和分層思想既減少了計數器值的數據量也從理論上消除了計數器的溢出問題。Bloomier過濾器、布隆樹和狀態BF直接或間接地在過濾器中對某些元素值進行存儲，使它們在各自的應用領域中可以直接使用過濾器查詢到元素值，無需再執行其他請求操作。

7 總結與展望

隨著數據規模的不斷擴大，越來越多的應用場景在執行查詢請求時需要設計海量的數據，且場景對于這些請求的性能要求也越來越高，空間緊湊，存在少量查詢誤判但效率極高的數據結構BF是解決元素成員資格查詢的一個常見工具。本文結合不同的應用場景介紹了目前比較主流的幾種BF優化方案，并從BF各個性能指標的角度進行了對比和分析，可為以后BF可能的研究方向提供參考。

經過不斷的改良和優化，BF的優化方案在“位向量的空間靈活性”“增加空間利用率”“減少查詢誤判率”和“對元素刪除操作的支持”等方面已經有了很大的提高，但由于使用場景繁多、新型存儲介質的廣泛應用等問題，進一步優化已有的方案使其適用全新場景和新型存儲介質將成為一個熱點問題。BF未來可能的研究方向展望如下：

1）將刪除和查詢操作分離。目前討論過濾器的刪除操作都是以“元素一定屬于集合”為前提的，當過濾器刪除本不屬于集合但會產生查詢誤判的元素時，過濾器會錯誤地從過濾器中刪除該元素，等后續查詢到該元素時，查詢結果會破壞BF的單向誤判性，所以過濾器對請求刪除元素是否存在于集合的判斷必須是完全正確的。

2）哈希策略的優化是BF的一個非常重要的部分，其映射是否均勻關系到位向量的空間適用效率，在有限空間中的碰撞是BF查詢誤判率的直接原因。雖然在有限的空間中哈希策略一定存在碰撞的情況，但是對其的進一步探索是未來的一個重要方向。

3）針對二級存儲中BF的優化思想單一。當內存大小不足以容納整個BF而需將其轉移到二級存儲中時，目前的優化方案都是對過濾器進行分塊或分層來減少整體上I/O的次數從而達到優化效果，還沒有太多從其他優化思想出發的優化方案。

4）SSD存儲設備雖然性能好，但價格高昂，短時間內無法完全替代傳統存儲設備，因此混合存儲系統仍是目前的主流方案，但對于混合存儲系統中BF的相關優化方案還很少。

隨著大數據時代的發展，BF本身緊湊的空間使用和高效的操作，有著天然的優勢，而且它的各部分均可優化，還能夠針對特定應用場景進行定制化的改進，因此未來對于高性能查詢的研究領域，BF仍然是一個重大課題。

[1] BLOOM B H. Space/time trade-offs in hash coding with allowable errors［J］. Communications of the ACM， 1970， 13（7）： 422-426.

[2] CARTER L， FLOYD R W， GILL J， et al. Exact and approximate membership testers［C］// Proceedings of the 10th Annual ACM Symposium on Theory of Computing. New York： ACM， 1978：59-65.

[3] 肖明忠，代亞非. Bloom Filter及其應用綜述［J］. 計算機科學， 2004， 31（4）：180-183.（XIAO M Z， DAI Y F. A survey on Bloom filters and its applications［J］. Computer Science， 2004， 31（4）： 180-183.）

[4] 劉元珍. Bloom Filter及其在網絡中的應用綜述［J］. 計算機應用與軟件， 2013， 30（9）：219-220， 249.（LIU Y Z. Survey on Bloom filter and its applications in networks［J］. Computer Applications and Software， 2013， 30（9）： 219-220， 249.）

[5] PENG Y Q， GUO J W， LI F F， et al. Persistent Bloom filter： membership testing for the entire history［C］// Proceedings of the 2018 International Conference on Management of Data. New York： ACM， 2018：1037-1052.

[6] MCLLROY M. Development of a spelling list［J］. IEEE Transactions on Communications， 1982， 30（1）： 91-99.

[7] MULLIN J K， MARGOLIASH D J. A tale of three spelling checkers［J］. Software： Practice and Experience， 1990， 20（6）： 625-630.

[8] SPAFFORD E H. OPUS： preventing weak password choices［J］. Computers and Security， 1992， 11（3）： 273-278.

[9] SEVERANCE D G， LOHMAN G M. Differential files： their application to the maintenance of large databases［J］. ACM Transactions on Database Systems， 1976， 1（3）： 256-267.

[10] GREMILLION L L. Designing a Bloom filter for differential file access［J］. Communications of the ACM， 1982， 25（9）： 600-604.

[11] FANG M， SHIVAKUMAR N， GARCIA-MOLINA H， et al. Computing iceberg queries efficiently［C］// Proceedings of the 24th International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann Publishers Inc.， 1998： 299-310.

[12] BRODER A Z， MITZENMACHER M. Network applications of bloom filters： a survey［J］. Internet Mathematics， 2004， 1（4）： 485-509.

[13] STOICA I， MORRIS R， KARGER D， et al. Chord： a scalable peer-to-peer lookup service for internet applications［C］// Proceedings of the 2001 ACM SIGCOMM Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 2001：149-160.

[14] RATNASAMY S， FRANCIS P， HANDLEY M， et al. A scalable content-addressable network［C］// Proceedings of the 2001 ACM SIGCOMM Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 2001：161-172.

[15] JOKELA P， ZAHEMSZKY A， ROTHENBERG C E， et al. LIPSIN： line speed publish/subscribe inter-networking［C］// Proceedings of the 2009 ACM SIGCOMM Conference on Data Communication. New York： ACM， 2009：195-206.

[16] RHEA S C， KUBIATOWICZ J. Probabilistic location and routing［C］// Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway： IEEE， 2002：1248-1257.

[17] WHITAKER A， WETHERALL D. Forwarding without loops in Icarus［C］// Proceedings of the 2002 IEEE Conference on Open Architectures and Network Programming. Piscataway： IEEE， 2002：63-75.

[18] FENG W C， SHIN K G， KANDLUR D D， et al. The BLUE active queue management algorithms［J］. IEEE/ACM Transactions on Networking， 2002， 10（4）： 513-528.

[19] ESTAN C， VARGHESE G. New directions in traffic measurement and accounting［C］// Proceedings of the 2002 ACM SIGCOMM Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 2002：323-336.

[20] 謝平. 存儲系統重復數據刪除技術研究綜述［J］. 計算機科學， 2014， 41（1）：22-30， 42.（XIE P. Survey on data deduplication techniques for storage systems［J］. Computer Science， 2014， 41（1）： 22-30， 42.）

[21] MALDE K， O'SULLIVAN B. Using Bloom filters for large scale gene sequence analysis in Haskell［C］// Proceedings of the 2009 International Symposium on Practical Aspects of Declarative Languages， LNPSE 5418. Berlin： Springer， 2009：183-194.

[22] CANIM M， MIHAILA G A， BHATTACHARJEE B， et al. Buffered bloom filters on solid state storage［C/OL］// Proceedings of the 2010 International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures@Very Large Data Bases Conference. ［2021-05-23］.https：//vldb.org/archives/workshop/2010/proceedings/files/vldb_2010_workshop/ADMS_2010/adms10-canim.pdf.

[23] XIE K， MIN Y H， ZHANG D F， et al. Basket Bloom filters for membership queries［C］// Proceedings of the 2005 IEEE Region 10 Conference. Piscataway： IEEE， 2005：1-6.

[24] 何新貴，梁久禎. 利用目標函數梯度的遺傳算法［J］. 軟件學報， 2001， 12（7）：981-986.（HE X G， LIANG J Z. Genetic algorithms using gradients of object functions［J］. Journal of Software， 2001， 12（7）： 981-986.）

[25] LI Y K， TIAN C J， GUO F， et al. ElasticBF： elastic bloom filter with hotness awareness for boosting read performance in large key-value stores［C］// Proceedings of the 2019 USENIX Annual Technical Conference. Berkeley： USENIX Association， 2019：739-752.

[26] Google. LevelDB［DB/OL］. ［2021-02-24］.https：//github.com/google/leveldb.

[27] Meta Open Source. RocksDB［DB/OL］. ［2021-05-06］.http：//rocksdb.org/.

[28] RAJU P， KADEKODI R， CHIDAMBARAM V， et al. PebblesDB： building key-value stores using fragmented log-structured merge trees［C］// Proceedings of the 26th Symposium on Operating Systems Principles. New York： ACM， 2017：497-514.

[29] O’NEIL P E， CHENG E， GAWLICK D， et al. The Log-Structured Merge-tree （LSM-tree）［J］. Acta Informatica， 1996， 33（4）： 351-385.

[30] DAYAN N， ATHANASSOULIS M， IDREOS S. Monkey： optimal navigable key-value store［C］// Proceedings of the 2017 ACM International Conference on Management of Data. New York： ACM， 2017：79-94.

[31] ZHOU Y Y， PHILBIN J F， LI K. The multi-queue replacement algorithm for second level buffer caches［C］// Proceedings of the 2001 USENIX Annual Technical Conference. Berkeley： USENIX Association， 2001：91-104.

[32] CHEN Y P， SCHMIDT B， MASSKELL D L. A reconfigurable Bloom filter architecture for BLASTN［C］// Proceedings of the 2009 Architektur von Rechensystemen. Berlin： Springer， 2009：40-49.

[33] DEBNATH B， SENGUPTA S， LI J， et al. BloomFlash： Bloom filter on flash-based storage［C］// Proceedings of the 31st International Conference on Distributed Computing Systems. Piscataway： IEEE， 2011：635-644.

[34] GUO D K， WU J， CHEN H H， et al. Theory and network applications of dynamic Bloom filters［C］// Proceedings of the 25th IEEE International Conference on Computer Communications. Piscataway： IEEE， 2006：1-12.

[35] LU G L， DEBNATH B K， DU D H C. A forest-structured Bloom filter with flash memory［C］// Proceedings of the IEEE 27th Symposium on Mass Storage Systems and Technologies. Piscataway： IEEE， 2011：1-6.

[36] YOON M K， SON J， SHIN S H. Bloom tree： a search tree based on Bloom filters for multiple-set membership testing［C］// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway： IEEE， 2014：1429-1437.

[37] HAO F， KODIALAM M， LAKSHAM T V， et al. Fast dynamic multiple-set membership testing using combinatorial Bloom filters［J］. IEEE/ACM Transactions on Networking， 2012， 20（1）： 295-304.

[38] DHARMAPURIKAR S， KRISHNAMURTHY P， TAYLOR D E. Longest prefix matching using Bloom filters［J］. IEEE/ACM Transactions on Networking， 2006， 14（2）： 397-409.

[39] LUO S Q， CHATTERJEE S， KETSETSIDIS R， et al. Rosetta： a robust space-time optimized range filter for key-value stores［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2020：2071-2086.

[40] ZHANG H C， LIM H， LEIS V， et al. SuRF： practical range query filtering with fast succinct tries［C］// Proceedings of the 2018 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2018：323-336.

[41] FAN L， CAO P， ALMEIDA J， et al. Summary cache： a scalable wide-area web cache sharing protocol［C］// Proceedings of the 1998 ACM SIGCOMM Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 1998：254-265.

[42] LAKSHMAN A， MALIK P. Cassandra： a decentralized structured storage system［J］. ACM SIGOPS Operating Systems Review， 2010， 44（2）： 35-40.

[43] The Chromium Projects. Google Chrome safe browsing［EB/OL］. ［2021-05-09］.http：//src.chromium.org/viewvc/chrome/trunk/src/chrome/browser/safe_browsing/.

[44] CHANG F， DEAN J， GHEMAWAT S， et al. Bigtable： a distributed storage system for structured data［C］// Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation. Berkeley： USENIX Association， 2006：205-218.

[45] COHEN S， MATIAS Y. Spectral Bloom filters［C］// Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2003：241-252.

[46] AGUILAR-SABORIT J， TRANCOSO P， MUNTES-MULERO V， et al. Dynamic count filters［J］. ACM SIGMOD Record， 2006， 35（1）： 26-32.

[47] XIE K， MIN Y H， ZHANG D F， et al. A scalable Bloom filter for membership queries［C］// Proceedings of the 2007 Global Telecommunications Conference. Piscataway： IEEE， 2007：543-547.

[48] CARTER J L， WEGMAN M N. Universal classes of hash functions［J］. Journal of Computer and System Sciences， 1979， 18（2）： 143-154.

[49] QIAO Y， LI T， CHEN S G. Fast Bloom filters and their generalization［J］. IEEE Transactions on Parallel and Distributed Systems， 2014， 25（1）： 93-103.

[50] CHAZELLE B， KILIAN J， RUBINFELD R， et al. The Bloomier filter： an efficient data structure for static support lookup tables［C］// Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia， PA： SIAM， 2004：30-39.

[51] VOCKING B. How asymmetry helps load balancing［C］// Proceedings of the 40th Annual Symposium on Foundations of Computer Science. Piscataway： IEEE， 1999：131-141.

[52] BONOMI F， MITZENMACHER M， PANIGRAHY R， et al. An improved construction for counting Bloom filters［C］// Proceedings of the 2006 European Symposium on Algorithms， LNTCS 4168. Berlin： Springer， 2006：684-695.

[53] BENDER M A， FARACH -COLTON M， JOHNSON R， et al. Don’t thrash： how to cache your hash on flash［J］. Proceedings of the VLDB Endowment， 2012， 5（11）： 1627-1637.

[54] CLERRY J G. Compact hash tables using bidirectional linear probing［J］. IEEE Transactions on Computers， 1984， C-33（9）： 828-834.

[55] Wikipedia. Quotient filter［EB/OL］. ［2021-06-13］.https：//en.wikipedia.org/wiki/Quotient_filter.

[56] PAGH R， RODLER F F. Cuckoo hashing［J］. Journal of Algorithms， 2004， 51（2）： 122-144.

[57] FAN B， ANDERSEN D G， KAMINSKY M， et al. Cuckoo filter： practically better than bloom［C］// Proceedings of the 10th ACM International Conference on emerging Networking Experiments and Technologies. New York： ACM， 2014：75-88.

[58] FAN B， ANDERSEN D G， KAMINSKY M. MemC3： compact and concurrent memcache with dumber caching and smarter hashing［C］// Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation. Berkeley： USENIX Association， 2013：371-384.

[59] ROTTENSTREICH O， KANIZO Y， KESLASSY I. The variable-increment counting Bloom filter［C］// Proceedings of the 2012 IEEE Conference on Computer Communications. Piscataway： IEEE， 2012：1880-1888.

[60] GRAHAM S. Bhsequences［M］// BERNDT B C， DIAMOND H G， HILDEBRAND A J. Analytic Number Theory， PM 138. Boston： Birkh?user， 1996： 431-449.

[61] PUTZE F， SANDERS P， SINGLER J. Cache-， hash- and space-efficient Bloom filters［C］// Proceedings of the 2007 nternational Workshop on Experimental and Efficient Algorithms， LNTCS 4525. Berlin： Springer， 2007：108-121.

[62] MACKERT L F， LOHMAN G M. R* optimizer validation and performance evaluation for local queries［C］// Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1986：84-95.

[63] FICARA D， DI PIETRO A， GIORDANO S， et al. Enhancing counting Bloom filters through Huffman-coded multilayer structures［J］. IEEE/ACM Transactions on Networking， 2010， 18（6）： 1977-1987.

[64] BONOMI F， MITZENMACHER M， PANIGRAHY R， et al. Beyond Bloom filters： from approximate membership checks to approximate state machines［C］// Proceedings of the 2006 ACM SIGCOMM Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 2006：315-326.

[65] Wikipedia. Bloom Filter［EB/OL］. ［2021-06-13］.https：//en.wikipedia.org/wiki/Bloom_filter.

[66] DEEDS K， HENTSCHEL B， IDREOS S. Stacked filters： learning to filter by structure［J］. Proceedings of the VLDB Endowment， 2020， 14（4）： 600-612.

[67] DAYAN N， TWITTO M. Chucky： a succinct cuckoo filter for LSM-tree［C］// Proceedings of the 2021 International Conference on Management of Data. New York： ACM， 2021：365-378.

Research on Bloom filter： a survey

HUA Wendi1，2，3，4， GAO Yuan1，2，3，4， LYU Meng1，2，3，4， XIE Ping1，2，3，4*

（1，，8100016，；2，810008，；3，810018，；4，810016，）

Bloom Filter （BF） is a binary vector data structure based on hashing strategy. With the idea of sharing hash collisions， the characteristic of one-way misjudgment and the very small time complexity of constant query， BF is often used to represent membership and as an “accelerator” for membership query operations. As the best mathematical tool to solve the membership query problem in computer engineering， BF has been widely used and developed in network engineering， storage system， database， file system， distributed system and some other fields. In the past few years， in order to adapt to various hardware environments and application scenarios， a large number of variant optimization schemes of BF based on the ideas of changing structure and optimizing algorithm appeared. With the development of big data era， it has become an important direction of membership query to improve the characteristics and operation logic of BF.

Bloom Filter (BF); membership query; Approximate Membership Query (AMQ) structure; hashing strategy; False Positive Rate (FPR)

This work is partially supported by National Natural Science Foundation of China （61762075）， Natural Science Foundation of Qinghai Province （2020-ZJ-926）.

HUA Wendi， born in 1998， M. S. candidate. His research interests include computer architecture， mass storage system， embedded system.

GAO Yuan， born in 1989， M. S. candidate. His research interests include network storage.

LYU Meng， born in 1998， M. S. candidate. Her research interests include network storage.

XIE Ping， born in 1979， Ph. D.， professor. His research interests include computer architecture， mass storage system， embedded system.

TP393

A

1001-9081（2022）06-1729-19

10.11772/j.issn.1001-9081.2021061392

2021?08?04；

2021?09?29；

2021?09?30。

國家自然科學基金資助項目（61762075）；青海省自然科學基金資助項目（2020?ZJ?926）。

華文鏑（1998—），男，遼寧撫順人，碩士研究生，CCF會員，主要研究方向：計算機體系結構、大規模存儲系統、嵌入式系統；高原（1989—），男，山東泰安人，碩士研究生，CCF會員，主要研究方向：網絡存儲；呂萌（1998—），女，山東青島人，碩士研究生，CCF會員，主要研究方向：網絡存儲；謝平（1979—），男，四川內江人，教授，博士，CCF會員，主要研究方向：計算機體系結構、大規模存儲系統、嵌入式系統。