經典論文解讀 — 布隆過濾器

作者：pishi，騰訊 PCG 後臺開發工程師

布隆過濾器是一種具有空間優勢的概率數據結構，用於回答一個元素是否存在於一個集合中這樣的問題，但是可能會出現誤判——即一個元素不在集合但被認爲在集合中。

相信大家對布隆過濾器（Bloom Filter，BF）都不陌生，就算沒用過也聽過。布隆過濾器是一種具有空間優勢的概率數據結構，用於回答一個元素是否存在於一個集合中這樣的問題，但是可能會出現誤判——即一個元素不在集合但被認爲在集合中。

布隆過濾器可用於避免緩存穿透、海量數據快速查詢過濾之類的場景。但是，大家真的了 BF 嗎？BF 有哪些參數？BF 支持刪除嗎？BF 的哈希函數怎麼選？還有其他類型的 BF 嗎？等等......

本文將從論文着手，從 BF 的起源開始，介紹初始的 BF，介紹 BF 的概率計算過程。接着介紹幾個 BF 的變種：包括可以支持刪除的 (Count Bloom Filter, CBF)；在 CBF 的基礎上能進一步節省空間的(dlCBF)；支持多個集合的(Spatial Bloom Filter, SBF) 和支持動態擴容的(Scalable Bloom Filter)。最後介紹一些關於 BF 的疑問，並且結合部分 Golang 組件源碼分析，將 BF 的理論帶入設計實踐。

總覽

開局一張圖，初步展示了各 BF 之間的發展關係，接下來我們一個一個具體來介紹。

本文從論文着手，從布隆過濾器的起源開始，粗略梳理了幾個有代表性的布隆過濾器的原理和應用。其中 CBF 支持計數，可以用於網絡緩存優化；dlCBF 是 CBF 的改進版，有更小的存儲空間；Spatial-BF 支持多個集合，配合同態加密使用可以用於戶隱私保護；Scalable-BF 支持自動擴容，被 Redis 作爲其布隆過濾器的內部實現。布隆過濾器中的哈希函數選擇也是有學問題的，應該選在那些分佈均勻計算速度快的，比如 Murmur3。哈希函數可以通過不同的策略，由 2 個生成無限多個。以下是對各種 BF 技術特徵的一個總結：

布隆過濾器的起源

BF 起源於 1970 年發表的一篇名爲 Space/Time Trade-offs in Hash Coding with Allowable Errors 的文章，該文章主要探討的是可容錯的哈希編碼在時空複雜度上的優勢。在不同的不可容錯的哈希編碼中，總是不可能同時佔盡時空複雜度的好處——要麼時間快 - 空間消耗大，要麼時間慢 - 空間消耗小。Bloom 提出了一個觀點，他認爲如果使用的場景可以容忍錯誤，那麼是否有一種空間消耗小且運行時間還快的算法 (數據結構) 呢？因此，他提出了兩種允許存在假陽性（false postive）的，用於測試一個給定元素是否存在於某一給定集合中的概率數據結構。通過允許容忍很小的錯誤，讓其在時空複雜度上表現良好。其中第二種結構，因其在時空上更佔優勢而被我們熟知，該結構被後人稱爲“Bloom Filter”。

BF 起源

其中對 Method2 的描述翻譯一下，就是最初 BF 的基本原理：

給定長度爲 Nbits 的哈希空間。
選取 d 個哈希函數，每個哈希函數將給定的元素映射到 [0，N-1] 的一個位置上，並將該位置爲 1。
將需要被判斷的元素也用 2 中的 d 個哈希函數算出 d 個位置 a1,a2,...,ad
如果 a1,a1,...,ad 對應的位有一個不爲 1，則該元素一定不在集合中。
如果 a1,a1,...,ad 對應的位全爲 1，則該元素可能存在於集合中。

如下圖所示，Orange 和 Lemon 兩個元素作爲集合的初始元素，經過兩個哈希函數 H1 和 H2 分別哈希到兩個位置，並將哈希到的位置元素置位 1，建立起一個 BF。當檢查元素 Kiwi 和 Onion 是否在集合中時，同樣經過哈希函數 H1 和 H2 哈希到兩個位置。Kiwi 元素哈希的位置不全爲 1，說明元素 Kiwi 一定不在集合 [Orange,Lemon] 中。而元素 Onion 哈希的兩個位置均爲 1，但我們其實知道 Onion 並不在集合 [Orange,Lemon] 中，因此出現了錯判。所以爲了實際能使用上這樣一個數據結構，我們有必要知道這個錯判概率是與哪些因素有關，從而能降低錯判概率。

一個簡單 BF 示例

從上面的例子中我們可以看出，一個布隆過濾器應該起碼有以下參數：

哈希空間大小，記爲 m。以上示例中 m = 20 bits；
元素集合大小，記爲 n。以上示例中 n = 2；
哈希函數個數，記爲 k。以上示例中 k = 2；
因爲 BF 是 Allowable Errors 的，可能會出現一個元素原本不在集合中，但是被錯判爲存在於集合中，這個錯判的概率叫 false postive，記爲ε。

Bloom 雖然提出了這樣一個概率數據結構，但是並未給出這些參數之間的關係和證明。下面我們給出 BF 的概率證明，同時寫出各個參數之間的關係表達式。

BF 是概率結構

以下爲條件獨立情況下的 BF 計算過程，並不複雜，稍微懂一點概率論的應該都能看懂。假設某 BF 的哈希空間大小爲 m，使用的哈希函數爲 k 個。能得出：

一次哈希，某一位沒有被置位 1 的概率爲：

k 次哈希後，某一位依然沒有被置爲 1 的概率爲：

使用 1/e 的等價提換：

帶入得：

那麼，在插入 n 個元素後，某一位依然是 0 的概率就爲：

因此，取反，在插入 n 個元素後，某一位是 1 的概率就爲：

最終，某一元素沒在集合中，但是被誤判在集合中的概率爲：

對於實際應用，我們的目標應該是使錯判率 ε 最小，即需要使函數：

取到最小值。求最小值的過程略，直接上結論：當 k = (ln2)(m/n) 時，錯判率最小，因爲 k 需要取整數，所以即當 k = [(ln2)(m/n)] 時，布隆過濾器有最好的效果。以下是 k 取最優值時，各個參數之間的關係：

以上只是條件獨立下的概率證明，非條件獨立下的概率證明在 2005 年由 Mitzenmacher 和 Upfal 給出，過程稍顯複雜，但是結論是一致的。感興趣的可以參考：Probability and Computing

在 k 取最優值 ln2*(m/n) 時，隨着 n 增長，不同 m 情況下錯判率的變化關係。

有了這些參數之間的關係表達式，就能方便的讓我們選取最合適的參數。比如現有一場景，我們有 1000w 個黑產賬號，需要以不高於 0.001% 錯誤的的情況下識別出來，那麼我們選取多少個哈希函數最合適以及需要耗費多少空間 (即哈希空間 m 是大多)？

答案：我們需要 k=17 個哈希函數以及 m=239626460 (28.57MiB)。

具體計算帶入公式即可。下面是一個網站，能幫忙我們快速計算各個參數：Bloom filter calculator

BF 各參數計算

計數 BF

普通的 BF 其實並不支持刪除元素，因爲多個元素可能哈希到一個布隆過濾器的同一個位置，如果直接刪除該位置的元素，則會影響其他元素的判斷。因此，在 2000 年，在 Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol 這篇文章中，Li Fan 等人使用帶計數器的布隆過濾器，彌補了布隆過濾器不支持刪除的缺點，並將 CBF 引入提出新的 ICP（Internet Cache Protocol）以達到降低 Web 緩存代理帶寬、cpu 時間、消息數量的同時還提高命中率的效果。

CBF 起源

Count Bloom Filter 原理：

給定長度爲 N*Mbits 的哈希空間。M 是用來存計數的位大小，文中取 4，即最大計數爲 15。因爲此時會溢出的概率已經足夠小。
插入：選取 d 個哈希函數，每個哈希函數將給定的元素映射到 [0，N-1] 的一個位置上，並將該位對應的值 + 1。如果值大於 15，則取 15。
刪除：選取 d 個哈希函數，每個哈希函數將給定的元素映射到 [0，N-1] 的一個位置上，並將該位對應的值 - 1。如果值小於 0，則取 0。
判斷存在：和經典布隆過濾器相同。

這裏可以看到，CBF 和普通 BF 的區別，僅僅是將原來的只能記 0/1 的一位，拓展爲了多位。如果遇到哈希衝突，則把該位的值 + 1，刪除時則將該位 - 1。

如下圖所示步驟 (a) 所示，向 CBF 插入元素的過程中，不是將該位置爲 1，而是直接 + 1。這樣當刪除時，比如刪除 x1，只是將它原來所在位由 [1,2,4] 變爲[0,1,3]，而不會影響其他元素是否存在於集合的判斷。

讓我們來看一個使用 CBF 優化傳統緩存共享的使用場景：

背景：傳統的網絡緩存服務器，通常會根據過期時間，緩存一批最近訪問過的地址的網頁信息。這時如果用戶再次請求相同地址，即可從本地緩存中將網頁信息取出返回給用戶，無需經過真正的網絡路由到外部真實的資源服務器。然而當用戶請求的地址沒有被 proxy 緩存時，該 proxy 會向網絡中的其他 proxy 發送請求。如果其他 proxy 有網頁信息，則會把信息返回給用戶；如果其他 proxy 也沒有網頁信息，則會通過互聯網將請求發送至目標服務器。

傳統的 ICP 架構中，由於緩存的頁面信息信息量巨大，所以都是緩存在本地磁盤中。

傳統基於 ICP 的緩存共享：

傳統基於 ICP 的緩存共享的請求時序

從這個場景中我們可以發現，當緩存 miss 時，需要向其他所有 Proxy 發送請求，從而優先獲取其他 proxy 緩存的內容，減少外部網絡訪問。一個很容易想到的優化策略就是，如果一個 Proxy 要是知道其他 Proxy 都緩存了哪些鏈接，就可以直接向目標 Proxy 發起請求而不用向每一個 Proxy 都發起請求。那麼問題就轉化爲了，一個 Proxy 如何才能存儲其他 Proxy 的緩存鏈接信息？如果全量存儲，勢必非常耗費空間。因爲一個 URL 少則十幾個字節，多則幾百個字節，而且數量也非常多。這些信息要是存內存的話又太耗費資源，存磁盤的話訪問速度又太慢。

針對以上問題，BF 就排上了用場。因爲在錯判率 1% 時，一個元素無論多大隻需要低於 10bits 存儲，能有效降低存儲空間，從而可以放到內存中。但是普通的 BF 又無法支持刪除，我們這個場景緩存會淘汰，因此會存在元素刪除的情況。這時，CBF 就派上了用處，既耗費非常少的空間，又支持刪除。使用 CBF 後，讓我們看下如何優化該場景。

使用 CBF 後，每個 Proxy 維護一個自己的 CBF，存儲於內存中，記錄各自的緩存集合信息。各個 Proxy 向其他 Proxy 同步自己的 CBF，這樣每個 Proxy 都能得到其他 Proxy 緩存的信息。同步時機可以定時同步或者設置一個緩存更新的閾值，當緩存更新超過該閾值時，向其他 Proxy 同步自己的 CBF。

使用 CBF 改進的緩存共享使用 CBF 改進的緩存共享請求時序

使用 CBF 改進後，可以從時序圖中看到，一次請求的平均通訊次數大幅減少，根據論文結論：使用 CBF 優化過的 ICP，能降低 Web 緩存代理帶寬、cpu 時間、消息數量、並且還能還提高緩存命中率。經過這樣優化後的 ICP 協議叫做 Summary Cache。

d-left 計數 BF

思科聯合哈佛大學和斯坦福大學於 2006 年提出，傳統的 CBF 因爲大部分時候值都爲 0，非常浪費空間。因此在 An Improved Construction for Counting Bloom Filters 一文中，他們基於 d-left hashing，構建了名爲 d-left Count Bloom Filter(dlCBF) 的空間利用率更高的布隆過濾器。與此同時，還提供了更小的錯判率。

dlCBF 起源

d-left Count Bloom Filter 原理：

將原本的一個哈希表 (對應 CBF 的比特數組) 劃分爲 d 個子哈希表；每個子哈希表包含若干 bucket；每個 bucket 包含若干個 cell；每個 cell 包含一個哈希指紋和一個 counter。
一個哈希函數的值要被分爲 d+1 段，高 d 段用作 d 個存儲位置 (bucket 位置)，d+1 段作爲哈希指紋。
插入時，在 d 個位置中選擇元素最少的一個。如果元素數量一個，優先選最左邊一個。如果 cell 的哈希指紋相同，則計數加 1。否則新加一個 cell，counter 初始化爲 1。刪除時同，優先減少計數，減到 0 時刪除。
查詢時，遍歷所有 d 個位置，只要其中一個位置的 cell 中有對應元素的哈希指紋，則判定存在。

可見，d-left 中的'd'描述的是將原來的哈希表拆分爲多少張子表，而'left'描述的是選取桶位置的原則，即有限選取桶內 cell 少的，如果 cell 一樣多，優先選擇最左的桶。通過使數據存儲的更加均勻和密集，dlCBF 才能節省更多的空間。關於 d-left hashing，可以參考 D-left hashing_風雲龍兒的博客 - CSDN 博客_d-left 哈希解決了什麼問題。

這個過程可能比較不容易理解，我結合下面的 dlCBF 示意圖給大家做個簡單說明。下圖描述了一個地址經過一個哈希函數最終落到一個 cell 中的過程。可以看到下圖中的 d=2.

地址經過哈希函數，得到一個哈希值，哈希值包括 2+1 段 (bucket1,bucket2,Remainder1=Remainder2)，忽略隨機置換過程。其中 bucket1 和 bucket2 指定元素落在 2 個哈希子表的哪個桶中，而 Remainder 當做哈希指紋。
選擇 bucket1 還是 bucket2 時，發現兩邊都沒有當前指紋，並且兩邊當前 cell 數量是一樣的都是 2。因此根據左邊優先原則，選在 bucket1。新建一個 cell，couter 初始化爲 1，指紋爲 Remainder1。

dlCBF 示例

**爲了體現 dlCBF 的優勢，考慮一個真實 dlCBF 與標準 CBF 的對比例子。**假設要表示集合有 n 個元素，構造 dlCBF 參數如下：

d-left 哈希表包含 4 個子表。
每個子表包含 n/24 個 bucket，使得 bucket 平均負載是 6 個 cell。
子表中每個 bucket 可以容納 8 個 cell，8 個就能以很高概率保證不會溢出。
cell 中每個 counter 包含 2 位，可以容納 4 個相同的哈希指紋，每個哈希指紋佔用 r 位。

因此：錯判率 = 24*(1/2)^r。其中兩個元素哈希指紋相同的概率是 (1/2)^r，d-left hashing 查找時有 4 個選擇 (4 個子表)，每個對應一個 bucket，一個 bucket 平均負載是 6，因此需要乘 24。整個 dlCBF 所需的位數 = 4*n(r+2)/3。其中 r+2 是一個 cell 大小，n 是集合元素數，一個 bucket 容納 8 個 cell，但平均負載是 6，因此乘 4/3 就得到全部位數。

現在看一個標準 CBF。假設對於 n 個元素的集合，CBF 使用 cn 個 counter，每個 counter 使用 4 位，哈希函數的個數 k 使用最優值 cln2，得到錯判率 =(2-ln2)c，總共使用 4cn 位。

如果令 c = (r+2)/3，那麼兩種方法使用的位數相同，這時我們來比較一下錯判率。我們發現在 r ≥ 7 時有：

(2-ln2)(r+2)/3 > 24*(1/2)^r

而且使用的位數越多，兩個錯判率的差距就越大。當 r = 14 時，c = 16/3，雖然兩個結構使用的位數相同，但 CBF 比 dlCBF 的錯判率大了 100 倍以上。

**現在換個角度，看看錯判率相同的情況下兩者佔用空間的情況。**假設標準的 CBF 使用 9 個 4 位的 counter（每個元素 36 位），6 個獨立的哈希函數，得到的錯判率爲 0.01327。dlCBF 使用 11 位的哈希指紋（每個元素 52/3 位），得到的錯判率爲 0.01172。我們計算一下，52/3÷36= 0.48，也就是說，dlCBF 只使用了 CBF 不到一半的空間，就得到了比 CBF 更低的錯誤率。

結論：使用相同的位數，dlCBF 錯判率更低。保持相同的錯判率，dlCBF 所佔空間只有 CBF 的一半左右。

可擴展 BF

在這篇文章中，Almeida 等人提出傳統的布隆過濾器需要先驗的確定錯判率 p（false pasitive）和集合中元素大小 n，纔能有效的確定哈希函數 k 和過濾器大小 m。然而，大部分情況下，我們並不能事先知道集合中到底會插入多少個元素，因此有必要有一種能動態根據集合中的元素計算適合的哈希函數個數和 filter 大小的機制。使用該機制的布隆過濾器就叫做 Scalable Bloom Filters。

Scalable-BF 起源

Scalable Bloom Filter 原理：

確定初始值：在確定 P0 的情況下，給定初始 filter 大小 M0 和 K0 個初始哈希函數 h0,h1,...,hk。
劃分：將大小爲 M0 的數組劃分爲長度 m=M0/K0 的 K0 個數組 m0,m1,...,mk，因此初始值 M0 必需要能被 K0 整除。
哈希規則：有 K0 個哈希函數，每個哈希函數 hi 只將值哈希到一個數組 mi（分段哈希）。
擴容：隨着元素的插入，錯判率 p 在增大，當增大到快要超過 P0 時，執行擴容。擴容規則爲，新增一個布隆過濾器。新增的過濾器 m->ms^i, k->K0+ilog2(r^-1)。此時舊的布隆過濾器變爲只讀，新的布隆過濾器可讀寫。其中 s 爲子數組增長係數，r 爲容錯係數，即 P1=P0*r。
查詢：檢驗一個成員是否存在時，和經典布隆過濾器一樣，但需要檢驗所有的（包括擴容出來的）布隆過濾器。

Scalable Bloom Filter 參數選擇：

在第 4 步擴容中，引入了兩個新的因子 s 和 r。根據論文中給出的計算公式，問題就轉化爲尋找最適合的 s 和 r。根據論文結論，當規模增長率很大的時候 s=4 比較合適，當規模增長不是很大的時候 s=2 合適。在選定 s 的基礎上，r 一般取 0.8~0.9 最爲合適。

如下圖所示，下圖是一個 s=1,r=1/2 的 Scalabel-BF 示例。下圖右半部分是一個因錯判率達到閾值而擴容出來的新的 BF。新擴容出來的 BF 可讀寫，原先的 BF 變爲只讀。根據公式 m->ms^i，帶入 s=1，i=1 得到結果 = m，可以知道新擴容出來的每一列依然保持 m 的大小。而根據公式 k->K0+ilog2(r^-1)，帶入 k0=3,r=1/2,i=1 得到結果 = 4，可知新擴容出來的哈希函數比原來多了一個。

實際上 redis 中的 BF 拓展，就是利用 Scalable Bloom Filter 的原理來實現的。

https://github.com/RedisBloom/RedisBloom

空間 BF

到目前爲止我們發現，以上所有的 BF，都只支持單個集合，即加入到 BF 中的元素都屬於同一個集合。然而，BF 還是有可能支持多個集合的。

在 Spatial Bloom Filters: Enabling Privacy in Location-Aware Applications 這篇文章中，Palmieri, Calderoni & Maio 提出了 SBF 這一數據結構來存儲空間信息，從而提供無需暴露用戶具體位置就能爲其提供位置服務的好處。然而，SBF 最大的特性，是其支持將多個有優先級的集合使用同一個數據結構來存儲。

SBF 起源

Spatial Bloom Filter 原理：

劃分：將全集按優先級從小到大分爲 s 個子集，Δ1,Δ2,...,Δs
構造：從優先級低的集合 i 開始，集合中的每個元素哈希到對應的位置，並將值置爲 i。注意：高優先級值會覆蓋低優先級值。
查詢：對於給定元素的查詢，先算哈希，找到要判斷的 d 個位置。順序判斷所有位置：
如果該位置爲 0，返回 false
如果該位置不爲 0，保存該位置的值作爲最大值，如果有更大的值則替換
返回最大值對應的集合，即該元素可能存在於該集合

論文中作者使用 SBF，主要是用於構建地理信息。結合下面兩張圖，使用空間布隆過濾器，現在我們可以描述一下地理信息建模過程。

c 點爲感興趣的中心位置，r 爲感興趣的範圍，離 c 越近優先級越高。以 c 爲圓心，r 爲半徑畫圓，這個圓會覆蓋很多區域。
把 c 點所在的區域距離設爲 0，計算圓覆蓋範圍區域 δ 與 c 的曼哈頓距離。
根據曼哈頓距離給區域分類（劃分優先級），劃分優先級的策略可以自定義，比如示例中 1,2 優先級相同，3,4 優先級相同。優先級劃分完後從高到低，從內到外，分出了三個區域：[Δ3,Δ2,Δ1]，對應的值分別是 [3,2,1]。

空間布隆過濾器建立算法流程：

輸入：Δ1,Δ2, ... , Δs, H(多個哈希函數);
輸出：空間布隆過濾器b#；
for i ← 1 to s do
    foreach δ∈Δi do
        foreach h∈H do
            b#[h(δ)] ← i；
        end
    end
end
return b#；

空間布隆過濾器查詢算法流程：

輸入：b#，H，δ，s;
輸出：Δi；
i = s;
foreach h∈H do
    if b#[h(δ)]=0 then
        return false;
    else
        if b#[h(δ)]<i then
            i ← b#[h(δ)];
        end
    end
end
return Δi；

參數釋義：

b#：SBF

H：哈希函數

δ：具體某一個地理小方格

Δ：同一優先級的小方格集合

s：不同優先級集合個數

作爲論文中的例子，作者利用 SBF 建模地理信息，使用同態加密保證數據的 “可用而不可見”，來完成對通訊雙方位置隱私的保護。從而構建了一種無需提供精確位置下的位置依賴服務 (location base service)。由於通訊流程比較複雜，這裏就不展開講解了。

學習 SBF 原理，我也撰寫了一篇專利一種提供位置隱私保護的附近的人一起看陪看推薦方法，大家有興趣也可以看看。裏面詳細介紹了使用 SBF + 乘法同態加密完成一個位置隱私保護的推薦流程。

如何構建一個好的 BF

說了這麼多，還是沒有回答一開始提出來的問題，BF 的哈希函數究竟要怎麼選擇？MD5 行不行？

如何選擇哈希函數

從概率計算和速度角度，哈希函數需滿足：

1）獨立、均勻分佈。

2）計算速度快。

因此：

Murmur3，FNV 系列和 Jenkins 等非密碼學哈希函數適合，其中 Murmur3 因其簡單，並且在速度和隨機分佈上有最好的權衡，實踐中多選用它作爲哈希函數。

以下是一些哈希函數測評：hash-functions-benchmarks

幾個哈希函數的基準測試：

Murmur 隨機性很好（點分佈均勻）

選擇幾個哈希函數？

當需要 10 個哈希函數的時候，我們總不可能選擇 10 個不同的哈希函數來進行操作吧，這樣也根本無法編程。哈佛大學的一篇論文計算證明，其實按照一定策略，只需要取 2 個哈希函數，即可以達到生成任意多個哈希函數的目的。論文中提出了兩種可行的策略:

Partition Schemes:

hi=h1(u) + ih2(u) mod m′

**Double Hashing Schemes:**hi=h1(u) + ih2(u) + f(i) mod m

其中 h1 和 h2 是兩個哈希函數，m 是 bloom filter 大小，m'是 m/k（要求 m 能整除 k）。

在 go 語言的 BloomFilters 實現中，利用了類似 partition schemes 的策略，通過 2 個哈希函數（第二個哈希函數實際上是將輸入值 + 1 後取哈希值實現的)，生成無數多個哈希函數。

源碼分析

在瞭解了布隆過濾器原理後，結合一份源碼，讓我們看一下一個 BF 組件的內部實現。源碼分析部分就不展開了，感興趣的可以拓展閱讀 BloomFilter-Golang 源碼分析。

寫在最後

布隆過濾器的原理部分，涉及大量的證明和推導，因此除了最原始的布隆過濾器給出了推導，其他變種的推導過程都省略了。同時因爲作者學識、精力和時間都有限，並沒有把整個布隆過濾器的發展脈絡都梳理出來，只選取了部分富有代表性的來講解。文中的內容，也是作者讀了論文後自己翻譯和總結的，可能會有稍許誤差，如各位發現其中的錯誤，還望不吝賜教，感謝大家。