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

布隆過濾器研究綜述

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

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

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

布隆過濾器；集合元素查詢；近似成員查詢結(jié)構(gòu)；哈希策略；誤判率

0 引言

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

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

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

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

3）BF本身就是一種犧牲查詢準(zhǔn)確率來換取空間效率的數(shù)據(jù)結(jié)構(gòu)，因此在設(shè)計(jì)BF時(shí)需要在空間效率和查詢準(zhǔn)確率之間進(jìn)行權(quán)衡，而這二者都是影響應(yīng)用場(chǎng)景的重要因素，對(duì)此BF往往無法得到一個(gè)完美的解決方案。

4）由于BF使用哈希映射對(duì)集合元素進(jìn)行間接存儲(chǔ)表示，所以無法從其中獲得查詢?cè)氐耐暾畔?；而且有限大小的位向量使哈希映射必然存在碰撞，向量中的一位可能被映射多次，所以BF無法刪除已經(jīng)存儲(chǔ)的元素。這樣的特點(diǎn)在一定程度上限制了BF的應(yīng)用場(chǎng)景。

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

1 標(biāo)準(zhǔn)布隆過濾器

1.1 結(jié)構(gòu)組成和基本操作

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

圖1 標(biāo)準(zhǔn)BF結(jié)構(gòu)

1.2 結(jié)構(gòu)參數(shù)和性能表現(xiàn)

本文中BF及其改進(jìn)的結(jié)構(gòu)參數(shù)分為過濾器位向量大小、集合中的元素個(gè)數(shù)和哈希函數(shù)個(gè)數(shù)；性能指標(biāo)包括：

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

2）元素插入性能：元素插入到過濾器中的時(shí)間復(fù)雜度。

3）空間開銷：過濾器中所有用于存儲(chǔ)集合元素結(jié)構(gòu)的大小總和，通常等于。

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

進(jìn)而得到誤判率的公式為

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

1.3 應(yīng)用場(chǎng)景

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

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

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

2 拆分向量的布隆過濾器

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

2.1 對(duì)向量分塊

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

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

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

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

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

圖3 彈性BF的結(jié)構(gòu)組成

Fig. 3 Structure composition of elastic BF

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

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

圖4 緩沖BF結(jié)構(gòu)

緩沖BF對(duì)于插入請(qǐng)求進(jìn)行緩沖，讓大量請(qǐng)求連續(xù)對(duì)一個(gè)SSD頁進(jìn)行操作，總體上減少了SSD的訪問次數(shù)。但對(duì)查詢操作也進(jìn)行緩沖，雖然這不會(huì)增加過濾器的查詢誤判率，但會(huì)導(dǎo)致響應(yīng)時(shí)間的增加。

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

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

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

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

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

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

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

2.2 對(duì)向量分層

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

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

圖5 森林結(jié)構(gòu)BF的結(jié)構(gòu)變化

2.2.2 分支路徑的唯一性

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

1）對(duì)于不屬于集合的Key，返回了一個(gè)對(duì)應(yīng)的Value，這種誤判率與普通BF的查詢誤判本質(zhì)相同；

2）對(duì)于一個(gè)Key（無論是否屬于集合），查詢出了多個(gè)對(duì)應(yīng)的Value，無法確定哪個(gè)Value是正確的，這稱為分類錯(cuò)誤（classification failure）。

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

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

圖6 Ⅰ型過濾器結(jié)構(gòu)

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

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

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

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

3 改進(jìn)結(jié)構(gòu)的布隆過濾器

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

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

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

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

3.2 譜型布隆過濾器

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

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

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

3.3 動(dòng)態(tài)計(jì)數(shù)型過濾器

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

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

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

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

圖7 動(dòng)態(tài)計(jì)數(shù)型過濾器的結(jié)構(gòu)

3.4 擴(kuò)展型布隆過濾器

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

3.5 快速布隆過濾器

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

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

3.6 性能對(duì)比及分析

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

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

表1 幾種基于計(jì)數(shù)型BF改進(jìn)結(jié)構(gòu)方案的對(duì)比

表2 幾種基于普通BF改進(jìn)結(jié)構(gòu)方案的對(duì)比

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

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

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

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

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

4.1 “完美”哈希

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

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

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

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

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

4.2 d?left哈希

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

4.3 哈希表

圖8 商型過濾器的存儲(chǔ)單元

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

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

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

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

4.4 布谷鳥哈希

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

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

而另一個(gè)映射位置通過對(duì)式（27）的結(jié)果進(jìn)一步計(jì)算得出：

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

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

4.5 可變?cè)隽抗?/h3>

圖10 插入元素到可變?cè)隽坑?jì)數(shù)型BF中

5 其他改進(jìn)方案

5.1 結(jié)構(gòu)壓縮

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

對(duì)式（32）求導(dǎo)得：

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

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

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

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

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

5.2 值存儲(chǔ)

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

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

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

2）查詢一個(gè)存在的流時(shí)，過濾器無法找到其對(duì)應(yīng)的狀態(tài)值；

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

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

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

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

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

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

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

6 改進(jìn)方案的分析與討論

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

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

表5 布隆過濾器改進(jìn)方案對(duì)比

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

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

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

7 總結(jié)與展望

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

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

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

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

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

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

隨著大數(shù)據(jù)時(shí)代的發(fā)展，BF本身緊湊的空間使用和高效的操作，有著天然的優(yōu)勢(shì)，而且它的各部分均可優(yōu)化，還能夠針對(duì)特定應(yīng)用場(chǎng)景進(jìn)行定制化的改進(jìn)，因此未來對(duì)于高性能查詢的研究領(lǐng)域，BF仍然是一個(gè)重大課題。

[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及其應(yīng)用綜述［J］. 計(jì)算機(jī)科學(xué)， 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及其在網(wǎng)絡(luò)中的應(yīng)用綜述［J］. 計(jì)算機(jī)應(yīng)用與軟件， 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] 謝平. 存儲(chǔ)系統(tǒng)重復(fù)數(shù)據(jù)刪除技術(shù)研究綜述［J］. 計(jì)算機(jī)科學(xué)， 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] 何新貴，梁久禎. 利用目標(biāo)函數(shù)梯度的遺傳算法［J］. 軟件學(xué)報(bào)， 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。

國(guó)家自然科學(xué)基金資助項(xiàng)目（61762075）；青海省自然科學(xué)基金資助項(xiàng)目（2020?ZJ?926）。

華文鏑（1998—），男，遼寧撫順人，碩士研究生，CCF會(huì)員，主要研究方向：計(jì)算機(jī)體系結(jié)構(gòu)、大規(guī)模存儲(chǔ)系統(tǒng)、嵌入式系統(tǒng)；高原（1989—），男，山東泰安人，碩士研究生，CCF會(huì)員，主要研究方向：網(wǎng)絡(luò)存儲(chǔ)；呂萌（1998—），女，山東青島人，碩士研究生，CCF會(huì)員，主要研究方向：網(wǎng)絡(luò)存儲(chǔ)；謝平（1979—），男，四川內(nèi)江人，教授，博士，CCF會(huì)員，主要研究方向：計(jì)算機(jī)體系結(jié)構(gòu)、大規(guī)模存儲(chǔ)系統(tǒng)、嵌入式系統(tǒng)。