布隆過濾器研究綜述

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

布隆過濾器研究綜述

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

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

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

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

0 引言

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

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

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

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

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

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

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

1 標準布隆過濾器

1.1 結構組成和基本操作

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

圖1 標準BF結構

1.2 結構參數(shù)和性能表現(xiàn)

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

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

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

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

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

進而得到誤判率的公式為

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

1.3 應用場景

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

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

圖2 BF在存儲系統(tǒng)的查詢操作中的應用

2 拆分向量的布隆過濾器

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

2.1 對向量分塊

2.1.1 數(shù)據(jù)和規(guī)則的平等性

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

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

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

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

圖3 彈性BF的結構組成

Fig. 3 Structure composition of elastic BF

2.1.2 基于固態(tài)硬盤的優(yōu)化方案

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

圖4 緩沖BF結構

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

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

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

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

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

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

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

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

2.2 對向量分層

2.2.1 基于SSD的優(yōu)化方案

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

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

2.2.2 分支路徑的唯一性

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

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

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

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

2.2.3 優(yōu)化范圍查詢

圖6 Ⅰ型過濾器結構

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

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

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

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

3 改進結構的布隆過濾器

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

3.1 計數(shù)型布隆過濾器

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

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

3.2 譜型布隆過濾器

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

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

除此之外，譜型BF對元素個數(shù)查詢還有兩個算法上的優(yōu)化：

3.3 動態(tài)計數(shù)型過濾器

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

其中：為起始狀態(tài)下集合中的元素總數(shù)，為起始狀態(tài)下集合中不同元素的個數(shù)。所以

OFV的每一項是一個動態(tài)變化且同時變化的計數(shù)器，顧名思義用來處理前者對應計數(shù)器的溢出，所以映射次數(shù)的最大值決定了溢出計數(shù)器向量的大?。?/p>

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

圖7 動態(tài)計數(shù)型過濾器的結構

3.4 擴展型布隆過濾器

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

3.5 快速布隆過濾器

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

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

3.6 性能對比及分析

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

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

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

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

4 優(yōu)化哈希策略的布隆過濾器

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

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

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

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

4.1 “完美”哈希

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

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

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

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

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

4.2 d?left哈希

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

4.3 哈希表

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

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

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

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

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

4.4 布谷鳥哈希

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

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

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

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

表4 三種優(yōu)化方案的對比

4.5 可變增量哈希

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

5 其他改進方案

5.1 結構壓縮

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

對式（32）求導得：

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

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

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

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

圖12 根據(jù)計數(shù)器值構建的哈夫曼樹

5.2 值存儲

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

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

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

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

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

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

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

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

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

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

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

6 改進方案的分析與討論

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

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

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

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

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

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

7 總結與展望

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

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

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

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

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

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

隨著大數(shù)據(jù)時代的發(fā)展，BF本身緊湊的空間使用和高效的操作，有著天然的優(yōu)勢，而且它的各部分均可優(yōu)化，還能夠針對特定應用場景進行定制化的改進，因此未來對于高性能查詢的研究領域，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] 謝平. 存儲系統(tǒng)重復數(shù)據(jù)刪除技術研究綜述［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] 何新貴，梁久禎. 利用目標函數(shù)梯度的遺傳算法［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會員，主要研究方向：計算機體系結構、大規(guī)模存儲系統(tǒng)、嵌入式系統(tǒng)；高原（1989—），男，山東泰安人，碩士研究生，CCF會員，主要研究方向：網絡存儲；呂萌（1998—），女，山東青島人，碩士研究生，CCF會員，主要研究方向：網絡存儲；謝平（1979—），男，四川內江人，教授，博士，CCF會員，主要研究方向：計算機體系結構、大規(guī)模存儲系統(tǒng)、嵌入式系統(tǒng)。