布隆過濾器：理論、工程權衡與 Go 語言實現

作者 ｜ Gabor Koos

譯者 ｜ 張衛濱

引 言

在我們的一條推薦流水線中，有一個簡單的需求，那就是不能向用戶展示他們已經瀏覽過的文章。在流量峰值時，Feed 服務每秒處理約 18000 個請求，每個請求需要評估約 120 個候選內容。這意味著每秒需要執行約 216 萬次檢查。然而，該工作負載分布極不均勻，大約 97%-98% 的檢查結果都是用戶未瀏覽。

我們最初的設計是對每個候選內容執行精確查詢（緩存 + 后端存儲）。該方案功能上可行，但是在大量查詢結果都是否定結果的項目中效率較低。每次未命中仍然會產生網絡與存儲開銷，導致 I/O 上升。在流量高峰期，這表現為 p95 延遲升高（從約 85ms 升至 140ms）、后端讀取請求激增，以及基礎設施成本持續上漲。

為了解決該問題，我們在精確查詢路徑前引入了布隆過濾器（Bloom filter）。過濾器在內存中能夠直接排除確定不存在的項目，只將可能存在的項目提交給高開銷的驗證流程。這一改動讓我們避免了對確定不存在的項目執行無效操作，同時降低了延遲與后端負載。通過提前過濾確定的未命中項，我們可以將資源集中在真正需要驗證的場景上。

本文將完整講解該實現方案，涵蓋了架構問題、布隆過濾器的原理、Go 語言集成、帶數學計算的參數調優（m 和 k），以及在生產環境約束下落地該方案的實踐經驗。

原始方案：對每個
候選內容執行精確查詢

如前文所述，在引入布隆過濾器前，我們的推薦服務采用基礎的“精確查詢優先（exact-first）”架構：

• 在候選內容生成階段，生成經過一個有序的候選文章 ID 的列表

• 在歷史檢查階段，逐個校驗候選內容是否在用戶的已瀏覽集合中

• 歷史檢查采用緩存優先的邏輯，未命中時查詢后端存儲

• 僅通過校驗的未瀏覽候選內容會進入最終排序與響應組裝

從準確性角度來看，這個方案十分理想：去重邏輯確定性強，易于理解。但從系統角度來看，該階段處于服務關鍵路徑上，每個候選內容都要執行一次遠程成員檢查。

為何僅靠精確
查詢無法滿足需求

業務負載本身的特點導致該方案從設計上就存在高開銷的問題。約 97%-98% 的檢查結果為未瀏覽，意味著絕大多數查詢僅用于返回“未瀏覽”這樣一個結果并繼續流程。換言之，我們主要為否定結果承擔存儲與網絡的開銷。

在流量峰值下，有三個問題尤為突出：

• 延遲放大：單次請求包含大量候選檢查，p95 響應延遲從約 85ms 提升至 140ms。

• 讀取放大：后端與緩存讀取量隨單個請求的候選檢查數（“候選扇出”）而增長，而非僅隨請求數增長。

• 成本壓力：基礎設施成本隨流量上漲，因為精確查詢占據了核心服務路徑。

此時我們需要一種新的設計，在保證關鍵場景準確性的前提下，在以否定結果為主的路徑中，移除絕大多數不必要的高開銷查詢。

解決方案：布隆過濾器

優化方案是在執行高開銷的歷史查詢前，引入布隆過濾器進行內存級快速檢查（“成員網關”）。簡單來說，布隆過濾器（Bloom filter） 是一種緊湊的概率型數據結構，專門用于成員檢查。它使用位數組（bit array）存儲信息，并為每個鍵應用多個哈希函數。查詢僅會有兩種結果：

• 絕對不存在（結果 100% 正確）

• 可能存在（這個結果可能會存在誤判）

它永遠不會產生假陰性的結果，非常適合快速排除確實未瀏覽的內容。

引入布隆過濾器后，請求流程調整為：

1. 生成候選文章的 ID 列表

2. 使用 (user_id, article_id) 組合鍵查詢布隆過濾器

3. 如果過濾器返回絕對不存在，直接判定為未瀏覽，保留在排序流水線中

4. 如果過濾器返回可能存在，繼續執行精確的歷史校驗

這一設計正好命中了上一節的核心痛點：以否定結果為主的路徑。由于大多數候選內容都是未瀏覽，所以

絕大部分檢查都可以在內存中完成，無需遠程 I/O。

為什么概率型方法適合該負載

這里介紹的方法具備幾個很有價值的特性：

• 否定結果占比極高：在約 97%-98% 為否定結果的分布場景中，快速拒絕否定結果的收益非常高

• 在需要的地方保持嚴格的正確性：正向結果仍然可以通過精確存儲進行校驗

• 內存占用可預測：布隆過濾器可以緊湊地表示大規模的成員集

• 可調節的權衡：正如后文所示，我們可通過 m(位數組大小) 和 k(哈希函數個數) 控制誤報率

在接下來的章節中，我們將介紹布隆過濾器如何運行、如何在 Go 中實現它，以及如何用數學方法為該推薦系統的場景完成參數調優。

布隆過濾器實踐

在我們的推薦工作負載中，布隆過濾器的目標是快速識別大概率未瀏覽的候選項，避免不必要的高開銷歷史查詢。由于大多數候選檢查都是否定的結果，過濾器可以從服務路徑中移除大量可避免的存儲和網絡開銷。

核心機制

布隆過濾器會為元素集合編碼其成員的信息。它的核心組件簡單而高效：

• 大小為 m 的位數組：每個位置存儲 0 或 1，表示該位是否被一個或多個元素置位。

• k 個哈希函數：每個元素都會被映射到位數組中的 k 個位置上。這些哈希函數應盡可能獨立，并將元素均勻分布到數組上。選擇高質量的哈希函數對于減少沖突、控制誤報率至關重要，因此是重要的工程決策。我們會在實現部分討論實際哈希函數的選型。

布隆過濾器并不存儲元素本身，而只在位數組上編碼“是否出現過”的信息。

插入操作

要把元素 E 加入布隆過濾器：

1. 對 E 應用 k 個哈希函數：h1(E), h2(E),…,hk(E) 均會生成一個數字化的哈希值。

2. 通過對 m 取模把哈希值映射到位數組中：indexi=hi(E) mod m 這樣會得到位數組中的 k 個位置 (由于沖突，某些位置可能相同)。

3. 把這些位置上的位設置為 1：bit_array[index_i]=1

多個元素可能會設置位數組中想通的位值。位值只會被置位，不會被清零，這也是標準布隆表達式不支持刪除的原因。

成員查詢

當判斷一個元素是否存在時：:

1. 先為該元素計算相同的 k 個哈希值。

2. 再檢查位數組中對應位置的位值。

如果任意一個位值為 0，那么該元素就一定不在集合中，因為如果它被插入過，該位必然會被置為 1。

如果所有的位值都為 1，該元素就“可能在集合中”。這也是可能產生誤報的地方：不同元素可能映射到同一組位置，導致即使查詢元素從未加入過，對應的位值也可能均已經被置位。

圖 1 布隆過濾器的插入與成員校驗

在上圖中，我們把 3 個元素 (element1、element2 和 element3) 通過 2 個哈希函數 (h1 和 h2) 插入到布隆過濾器中。每個元素會在位數組中設置兩個位值。當我們查詢 element4 時，發現它對應的位值沒有全部被置位，因此可以確定它不存在。(注意，圖中存在哈希沖突：例如 element1 和 element3 都設置了 index 6 上的位值，這也是可能造成誤報的原因所在。)

關鍵特性

布隆過濾器具備以下關鍵特性：

• 無假陰性：判定為“不存在”的結果始終正確。

• 可能出現誤報：元素即使從未加入，也可能看起來是“存在的”。

• 確定性：同一個元素總會映射到同一組位值上。

• 內存和速度效率高：位數組與簡單哈希計算支持快速插入和查詢。

• 僅存儲成員信息：無法反查原始元素。

• 不支持刪除：位值一旦置位，無法在不影響其他元素的前提下清零。這是標準布隆過濾器的基礎限制；雖然存在支持刪除的變體 (比如，計數布隆過濾器)，但會引入額外復雜性與內存開銷。

雖然上述機制解釋了布隆過濾器是“如何工作的”，但是，單純理解其原理并不能確保能夠得到可直接用于生產環境的過濾器。如果不謹慎選擇位數組大小 (m)、哈希函數數量 (k) 和具體的哈希函數，布隆過濾器可能效率低下或產生過多的誤報。下一節我們會演示如何在 Go 中實現布隆過濾器，把機制落地成可運行的代碼，關于如何選擇和優化參數則放到了 “實踐注意事項與最佳實踐” 章節進行討論。

在 Go 中實現布隆過濾器

Go 非常適合實現布隆過濾器，因為它提供了對內存的低層控制、高效的 slice 和數組，以及快速且可預測的執行表現。這些特性讓我們更容易推導位數組、哈希計算和過濾器的整體性能，它們對于同時追求速度與內存效率的生產系統非常關鍵。

將布隆過濾器機制翻譯成 Go 代碼并不復雜。在實現上，需要使用位數組和多個哈希函數，它們對應了我們在 核心機制 小節中所描述的逐步執行的行為。在這一階段，我們先關注結構和基礎操作；參數調優會在 “實踐注意事項與最佳實踐” 章節展開。

定義布隆過濾器的結構

Go 中的布隆過濾器結構 (struct) 包含壓縮位數組、可尋址的位值總數，以及配置好的哈希函數。把哈希函數存放在struct中可以避免每次調用時的 API 誤用，也能讓使用方式更友好。與每個位值存一個布爾值相比，采用壓縮表述 (每 word 64bit) 可顯著改善內存效率和緩存行為：

}

創建新的布隆過濾器

NewBloomFilter函數用于按指定大小和哈希函數來初始化布隆過濾器：

}

為了操作壓縮位數組，我們提供了設置和讀取單個位值的輔助方法：

}

添加元素

Add方法接收一個 byte 切片 (待加入的數據)，計算配置好的哈希值，映射到位數組索引后并設置對應的位值：

}

位值只會被置位，插入邏輯與布隆過濾器核心機制完全一致。

查詢元素

Contains方法通過檢查哈希值對應的位值，判斷元素是否“可能存在于”布隆過濾器中：

}

該方法只要發現任意一個位值未置位就返回 false，因此不會產生假陰性；如果所有位值均為 1 則返回 true，表示“可能存在”(仍然有誤報的可能性)。

這個實現完整對應了前文所述的核心機制實現：多個獨立哈希、位數組更新和成員檢查。下面給出了一個可運行的示例，展示如何定義哈希函數并用樣例數據測試過濾器：

  }

在這個示例中，我們基于FNV算法定義了兩個簡單的哈希函數。這樣的函數用于演示已經足夠了，但是生產系統通常會偏好質量更高的非加密哈希 (例如，Murmur3、xxHash、MetroHash 或 HighwayHash)，并且要在真實 key 集合下驗證其分布表現。定義好兩個哈希函數后，我們創建了一個 20 bit、2 個哈希函數的布隆過濾器，加入 3 種水果，然后測試它們和另外 2 個未加入水果的是否存在。輸出會顯示哪些水果“可能存在”(可能誤報)，哪些“確定不存在”：

fig: definitely not present

布隆過濾器背后的數學原理

布隆過濾器實現起來不難，但想要“用好”它并不簡單：我們需要理解它的概率行為，才能真正發揮它的價值。這使工程師能夠預測誤報率，并在內存使用與哈希函數數量上做出有依據的選擇，以達到目標誤報率。布隆過濾器背后的數學原理對于調優參數 (m、k 和哈希函數) 至關重要，能幫助我們在內存效率與準確性之間找到平衡。

下面，我們先快速總結實踐中最常用的關鍵公式。如果需要更深入的推導與理論背景，可查看深入知識的附錄：布隆過濾器背后的數學原理 。

誤報率 (p) 大致等于:

哈希函數的最優數量 (k)：

在目標誤報率下所需的位數組大小 (m)：

結果速覽

在推薦路徑中引入布隆過濾器網關，并基于上述公式調優 m 和 K 后，我們在流量峰值窗口觀察到三個穩定的結果：

• 尾延遲（tail latency）更低：Feed 的 p95 延遲從約 140ms 降至約 96ms(大約下降了 31%)。

• 高開銷檢查更少：精確歷史查詢從每請求約 120 次降至平均約 24 次 (大約下降了 80%)。

• 后端壓力更低：歷史存儲的讀取流量下降了約 65%-70%，同時測得布隆過濾器誤報導致的過度過濾保持在約 0.5% 以內。

這些數字與具體負載有關，但模式具有普適性：當查詢以否定結果為主且代價高昂時，調優得當的布隆過濾器可以消除大量可避免的后端工作。

實踐注意事項與最佳實踐

在該機制實現完成，并掌握如何用數學選擇 k 與 m 之后，我們就可以把理論轉化為工程決策。

先從產品約束出發，而不是先看布隆過濾器的參數

對我們的推薦路徑來說，產品層面的問題不是“該使用什么值的 k 與 m？”，而是：

• 可接受多少重復推薦

• 服務層可投入多少內存

• 每個候選過濾還剩多少延遲預算

這讓我們得到了明確的調優目標：

• 把誤報控制在足夠低的水平，避免對未瀏覽內容產生可感知的過度過濾

• 同時，在否定結果占主導的路徑上減少高開銷的精確歷史查詢

這是通用的原則：先從服務 SLO 和用戶影響容忍度出發，再反推布隆過濾器的參數。

我們的場景中如何選擇 n、m 和 k

在實現中，我們將 n 建模為一個過濾器在其生命周期窗口內所代表的預期已瀏覽條目的數量 (例如，按用戶滾動窗口統計)。

隨后我們做了三項工程化的調整：

1. 對 n 要預留增長余量：按增長規模而非當前均值確定容量，避免過早飽和。

2. 為實現效率對 m 取整：為匹配壓縮[]uint64 存儲，按 word 邊界取整。

3. 為控制 CPU 成本限制 k：把計算值作為起點，再選取能讓每個請求哈希計算保持在預算內的值 (哈希本身的代價可能比較昂貴)。

在實踐中，這意味著我們會接受略高的內存來保障業務增長場景下的誤報，同時避免過大的 k 拖慢熱點路徑的延遲。

在這個具體推薦場景中，我們還做了一個重要服務決策：當誤報率處于產品容忍范圍內時，布隆過濾器為“可能存在”的結果并不總是會繼續執行精確查詢。小幅誤報意味著偶爾會漏過一條未瀏覽內容，這在我們的 Feed 質量目標下是可接受的，而跳過精確校驗會進一步減少后端成本和延遲。該做法適用于我們這個場景，但許多系統仍需要更嚴格保證。

該方式之所以可行，是因為偶發遺漏在我們的業務中是可接受的；但在很多系統里，仍然必須提供更嚴格保障的。一般來說，當誤報代價高或正確性至關重要時，布隆過濾器命中的結果必須做精確驗證；只有當產品行為能夠容忍少量過度過濾時，才可選擇性地略過。

哈希函數選擇：先正確性，再吞吐量

在本文中，哈希值按照確定性的方式來生成的，并通過對 m 取模實現映射。一個關鍵的生產經驗是，哈希策略絕非“無關輕重的細節”：

• 分布不佳會放大沖突

• 沖突會放大誤報

• 誤報會提高精確查詢透傳率

• 透傳率升高會侵蝕布隆過濾器的收益

在各類布隆過濾器部署中都存在一個通用的權衡：完全獨立的哈希族在服務系統中很少使用，因為 CPU 開銷較高。更常見做法是雙重 哈希(由兩個基礎哈希推導 k 個索引)，通常能在保持良好分布的同時降低計算成本。

我們驗證有效的做法包括：

• 跨實例保持確定且穩定的哈希行為

• 服務路徑使用快速非加密哈希以保障性能

• 在代表性 key 集下做誤報行為的實證驗證

總體建議是：把哈希質量當作“可測量的指標”，而不是默認成立的假設。

監控正確的運行指標

一個布隆過濾器看起來“邏輯正確”，但在運行時仍可能“效果堪憂”。我們跟蹤了如下指標：

• 透傳到精確歷史校驗的比例

• 有效誤報的指標 (布隆過濾器的“可能存在”結果被精確查詢判定不存在的比例)

• 對 Feed 服務各階段延遲的影響

• 每個過濾器作用域的內存占用

• 隨時間變化的飽和度漂移

這些指標適用于幾乎所有生產布隆過濾器部署，它們能告訴你過濾器是在持續節省成本，還是已經退化成額外開銷的。

生命周期策略與
初始調優同樣重要

即便初始參數很好，只要基數增長超出假設，過濾器仍會退化。在我們的場景中，盡早定義生命周期策略非常關鍵，需要明確：

• 何時重建

• 何時輪轉

• 透傳率突增時如何恢復

這些策略放到推薦系統之外的一般場景同樣成立：如果數據是動態且持續增長的，就不能依賴“一次性配置”的過濾器。你需要明確生命周期策略，包括何時重建、何時輪轉，以及如何處理突發增長。否則，過濾器準確性和效率會隨時間持續退化。

實踐檢查清單

在高吞吐系統中上線布隆過濾器前，請先檢查：

• 從產品角度定義可接受的誤報影響

• 在估算 n 時預留增長余量

• 先計算 m 和 k，再結合延遲與內存預算調優

• 用真實 key 分布驗證哈希行為

• 埋點透傳率與飽和度指標

• 預先制定重建 / 輪轉策略

按這種方式使用時，布隆過濾器會是高投資回報比的優化手段，而不是脆弱的“微優化技巧”。

結 論

布隆過濾器解決的是我們真正的問題：在否定結果占主導的路徑上，“是否已瀏覽”檢查太多且太貴。通過把成員過濾前置到內存中，我們從 Feed 關鍵路徑中移除了大量可避免 I/O，在不顯著增加內存占用的前提下重新獲得了延遲余量。

核心經驗并不是“永遠使用布隆過濾器”，而是把它當作可調的系統組件：根據產品容忍度和流量形態設定 m 與 k，同時兼顧分布質量和吞吐來選擇哈希函數，并在價值被悄然侵蝕前監控飽和度。

在推薦過濾這類可容忍低頻誤報的場景中，布隆過濾器不只是教科書概念，它可以成為真正可用于生產的性能和成本優化杠桿。

深入知識的附錄：
布隆過濾器背后的數學原理

如果你對這些結果背后的數學細節感興趣，下面給出完整推導與解釋。

為什么會出現誤報

要理解誤報何時發生，先回顧以下事實：

• 每個元素插入時會在大小為 m 的位數組中置位 k 個位值。

• 位值不會被清零，不同元素可能設置重復的位值。

當某個查詢元素雖然從未插入，但其 k 個哈希位都恰好已被其他元素置位時，就會發生誤報。

單個位值仍為 0 的概率

如前所述，布隆過濾器行為由三個參數決定：

• m= 位數組位值的總數

• k= 哈希函數個數

• n= 已插入元素數量

插入一個元素時，每個哈希會設置一個位值。某個特定位在一次插入后仍為 0 的概率是：

插入 n 個元素、每個元素使用 k 個哈希后，某位值仍為 0 的概率為：

當 m 足夠大時，近似形式為：

該近似能得到更簡潔的誤報分析公式。

誤報的概率

如果某個查詢元素對應的 k 個位值全為 1，則形成誤報。基于前述結果可得：

• 插入元素越多→位值已被置位的概率越高→誤報率越高。

• 位數組 m 越大→沖突越少→誤報率越低。

• 哈希函數個數 k 決定了平衡點：太少→誤報高；太多→CPU 成本升高但收益有限。

如何選擇 m 和 k

這些公式可用于計算工程上可落地的參數：

• 給定期望元素數量 n 和目標誤報率 P：

• m 決定了內存占用和位數組飽和速度。

• k 決定每個元素需要執行的哈希運算次數。

• 這些公式提供的是起點，后續應結合實際哈希函數和負載進一步校正。

隨著飽和度升高 (位數組置位的比例接近 1)，誤報率也會逼近 1，這就是為什么容量規劃和生命周期策略都非常關鍵。

如果缺少這類分析，布隆過濾器要么誤報率過高，要么浪費內存 (甚至可能難以及時察覺)。理解這些數學原理，是在真實業務中正確配置布隆過濾器并有效管理權衡的基礎。

Bloom Filters: Theory, Engineering Trade?offs, and Implementation in Go（https://www.infoq.com/articles/bloom-filters-practice-go-recommender/）

聲明：本文由 InfoQ 翻譯，未經許可禁止轉載。