先說一個(gè)我真實(shí)踩過的坑。前幾年做廣告平臺(tái)的數(shù)據(jù)服務(wù)每天要接收幾千萬條設(shè)備ID的去重和狀態(tài)判斷一開始直接用 Redis Set 存儲(chǔ)內(nèi)存眼看著往上飆不到兩周就觸發(fā)容量預(yù)警。后來有同事提醒了一句“布隆過濾器可以看看”我當(dāng)時(shí)也聽說過位圖這個(gè)數(shù)據(jù)結(jié)構(gòu)心想布隆過濾器不就是位圖加幾個(gè)哈希函數(shù)能有多大區(qū)別。結(jié)果真動(dòng)手去改造、去壓測(cè)、去調(diào)參數(shù)之后才意識(shí)到這個(gè)“位圖加哈?！钡男|西背后牽扯的原理推導(dǎo)、參數(shù)權(quán)衡和工程坑比想象中多得多。這篇文章不聊虛的就認(rèn)認(rèn)真真拆一下布隆過濾器Bloom Filter和位圖Bitmap這兩個(gè)數(shù)據(jù)結(jié)構(gòu)。它們到底能解決什么問題一句話概括在數(shù)據(jù)量大、內(nèi)存吃緊、又允許一定概率誤差的場(chǎng)景下用極低的內(nèi)存代價(jià)去判斷“某個(gè)元素是否大概率出現(xiàn)過”。典型應(yīng)用包括緩存穿透防護(hù)、黑名單過濾、爬蟲 URL 去重、數(shù)據(jù)庫(kù)層的快速存在性判定。適合誰(shuí)看一是面試前想徹底搞懂布隆過濾器原理的人二是后端開發(fā)時(shí)打算真正落地這個(gè)方案的人三是被 Redis 內(nèi)存逼瘋、想找一個(gè)省內(nèi)存替代方案的人。我盡量把原理講明白把公式推導(dǎo)過程給你把可復(fù)現(xiàn)的 Java 和 Redis 實(shí)操代碼貼出來最后再把線上踩過的坑和排查思路整理成速查表。1. 位圖用比特位做標(biāo)記的高效數(shù)據(jù)結(jié)構(gòu)1.1 位圖的底層原理位圖的全稱叫 Bitmap核心思想極其樸素用一個(gè) bit位來標(biāo)記某個(gè)元素是否存在。8 個(gè) bit 組成一個(gè)字節(jié)32 個(gè) bit 組成一個(gè) int。如果我們要存儲(chǔ)“某個(gè)數(shù)字是否出現(xiàn)過”傳統(tǒng)做法是往 Set 或 Map 里塞數(shù)據(jù)一個(gè) int 占 4 字節(jié)一億個(gè) int 就是 400MB。但位圖的思路是把“數(shù)值本身”當(dāng)作數(shù)組下標(biāo)把該下標(biāo)對(duì)應(yīng)的 bit 置為 1。一億個(gè)數(shù)字只需要一億個(gè) bit換算下來約 12.5MB差距是幾十倍。你可以把位圖想象成一棟宿舍樓的電子門牌系統(tǒng)。每個(gè)房間號(hào)對(duì)應(yīng)一個(gè)開關(guān)開關(guān)只有“亮/滅”兩種狀態(tài)。你要標(biāo)記 10086 號(hào)房間有人入住就把 10086 號(hào)開關(guān)打開要查 10086 是否入住就看那個(gè)開關(guān)有沒有亮。這里的關(guān)鍵是房間號(hào)本身就是數(shù)據(jù)不需要額外存一份數(shù)據(jù)副本。所以位圖天然適合做“是否存在”這種判斷題而且是精確判斷不是概率判斷。實(shí)現(xiàn)層面Java 里最直接的位圖是java.util.BitSet它內(nèi)部用long[]存儲(chǔ)一個(gè) long 是 64 位。手動(dòng)實(shí)現(xiàn)也很簡(jiǎn)單核心就三件事找到目標(biāo) bit 在數(shù)組中的下標(biāo)用位運(yùn)算把對(duì)應(yīng)位置置 1用位運(yùn)算讀回對(duì)應(yīng)位置。位運(yùn)算無外乎|置 1、判斷和/移位。1.2 手寫一個(gè)簡(jiǎn)單位圖我不建議你把BitSet當(dāng)成黑盒用一遍就完事自己寫一次更能理解底層邏輯。下面這個(gè)實(shí)現(xiàn)只保留 set、get、clear 三個(gè)核心方法足夠覆蓋大多數(shù)使用場(chǎng)景。public class SimpleBitmap { private final long[] words; private final int bitCount; public SimpleBitmap(int bitCount) { this.bitCount bitCount; // 每個(gè) long 有 64 位需要多少個(gè) long 才能覆蓋 bitCount 個(gè)位 this.words new long[(bitCount 63) / 64]; } public void set(int index) { checkIndex(index); // index / 64 定位到哪個(gè) longindex % 64 定位到 long 里的哪個(gè)位 words[index / 64] | (1L (index % 64)); } public boolean get(int index) { checkIndex(index); return (words[index / 64] (1L (index % 64))) ! 0; } public void clear(int index) { checkIndex(index); words[index / 64] ~(1L (index % 64)); } private void checkIndex(int index) { if (index 0 || index bitCount) { throw new IndexOutOfBoundsException(index: index); } } }這段代碼有幾個(gè)細(xì)節(jié)值得注意。第一(bitCount 63) / 64是向上取整保證空間足夠多出來的位不會(huì)訪問到。第二1L (index % 64)必須用1L而不是1否則在移位超過 31 位時(shí) int 會(huì)溢出導(dǎo)致標(biāo)記錯(cuò)位。第三clear方法用的是 ~(1L ...)先取反再與原理是“把目標(biāo)位變 0其他位保持不變”這個(gè)模式在嵌入式編程、操作系統(tǒng)頁(yè)表管理里也很常見。寫完之后可以做個(gè)內(nèi)存估算練習(xí)。假設(shè)要標(biāo)記 10 億個(gè) int直接HashSetInteger大概要 4GB 以上還要算上對(duì)象頭和擴(kuò)容開銷換成位圖只需要(10^9 / 8) / 1024 / 1024 ≈ 119MB。如果把范圍縮小到 1 億就是約 12.5MB。這個(gè)差距面試官問“海量數(shù)據(jù)如何去重”時(shí)位圖就是標(biāo)準(zhǔn)答案之一。1.3 位圖的經(jīng)典應(yīng)用場(chǎng)景位圖不只是教科書概念它藏在很多基礎(chǔ)軟件里。最常見的是操作系統(tǒng)內(nèi)存管理里的頁(yè)分配器物理內(nèi)存被劃分成固定大小的頁(yè)幀內(nèi)核用一張位圖記錄每個(gè)頁(yè)幀是空閑還是已被占用分配頁(yè)時(shí)掃描位圖找空閑位釋放頁(yè)時(shí)把對(duì)應(yīng)位清 0。熱搜詞里的“頁(yè)分配器與位圖安裝”說的大體就是這個(gè)機(jī)制。這種場(chǎng)景對(duì)空間極度敏感位圖帶來的節(jié)省是實(shí)打?qū)嵉?。另一個(gè)典型場(chǎng)景是 Redis 的 Bitmap 操作。Redis 的 String 類型底層是字節(jié)數(shù)組可以用SETBIT和GETBIT按位操作相當(dāng)于一個(gè)可共享的分布式位圖。比如統(tǒng)計(jì)一整年用戶的簽到狀態(tài)一年 365 天一個(gè)用戶只占 365 個(gè) bit一萬個(gè)用戶也就 50KB 不到。用BITCOUNT還能直接算出有多少天簽到比傳統(tǒng)的關(guān)系表省太多。我自己的經(jīng)驗(yàn)是位圖適合“元素范圍可預(yù)估、分布相對(duì)緊湊”的場(chǎng)景。如果數(shù)據(jù)范圍極大且極度稀疏比如在 32 位整數(shù)空間里只存幾百個(gè)隨機(jī)數(shù)位圖反而浪費(fèi)——這時(shí)應(yīng)該用哈希表或其他索引結(jié)構(gòu)。做技術(shù)選型時(shí)不要只盯著空間優(yōu)勢(shì)數(shù)據(jù)分布特征必須一起看。2. 布隆過濾器位圖之上的概率型進(jìn)階2.1 位圖到布隆過濾器的跳躍位圖有一個(gè)天然局限它把“數(shù)值本身”當(dāng)作下標(biāo)所以只能處理整數(shù)而且要求數(shù)值范圍不能太大。當(dāng)我們要判斷“某個(gè) URL 是否已經(jīng)抓取過”“某個(gè)用戶 ID 是否在黑名單里”這類字符串場(chǎng)景時(shí)位圖直接失靈。怎么辦最簡(jiǎn)單的想法是用哈希函數(shù)把字符串映射成一個(gè)整數(shù)下標(biāo)然后去位圖里查。但哈希函數(shù)存在碰撞不同字符串可能映射到同一個(gè) bit 位光靠一個(gè) bit 無法區(qū)分它們。布隆過濾器解決這個(gè)問題的思路很直白一個(gè)哈希函數(shù)會(huì)碰撞那就用多個(gè)哈希函數(shù)把每個(gè)元素映射到多個(gè) bit 位上。比如用 3 個(gè)哈希函數(shù)算出一個(gè)字符串的 3 個(gè)下標(biāo)插入時(shí)把這 3 個(gè)位置都置 1查詢時(shí)看這 3 個(gè)位置是否都為 1只要有一個(gè)位置是 0就說明這個(gè)字符串肯定不在集合里。這里的關(guān)鍵邏輯是所有位置都是 1不代表元素一定存在但只要有任意一個(gè)位置是 0元素一定不存在。這就是布隆過濾器的“概率性”來源。這句“有 0 必不存在全 1 未必存在”是整個(gè)數(shù)據(jù)結(jié)構(gòu)最核心的結(jié)論。它決定了布隆過濾器的幾個(gè)特點(diǎn)支持“可能存在”的判斷支持“一定不存在”的判斷沒有假陰性False Negative但會(huì)有假陽(yáng)性False Positive。用大白話說就是它會(huì)漏報(bào)“不存在”嗎不會(huì)。它會(huì)誤報(bào)“存在”嗎會(huì)而且這就是“布隆過濾器誤判”這個(gè)熱搜詞的真正含義。2.2 誤判率的直觀理解很多人第一次碰到布隆過濾器誤判時(shí)會(huì)覺得不靠譜其實(shí)誤判是概率性的而且可以通過參數(shù)控制。我們來構(gòu)建一個(gè)直覺模型。假設(shè)位數(shù)組長(zhǎng)度為 m當(dāng)前已經(jīng)插入了 n 個(gè)元素每個(gè)元素使用 k 個(gè)哈希函數(shù)。哈希函數(shù)輸出范圍很大近似認(rèn)為每次映射到任意一個(gè)位置的概率均勻。那么在某一次插入時(shí)某個(gè)特定的位沒有被某個(gè)哈希函數(shù)選中的概率是1 - 1/m這個(gè)元素一共做 k 次映射所以特定一位在插入該元素后仍為 0 的概率是(1 - 1/m)^k。等 n 個(gè)元素都插入完某個(gè)位仍然為 0 的概率近似為(1 - 1/m)^(k*n)。查詢一個(gè)“從未插入過”的元素時(shí)它的 k 個(gè)哈希位置如果碰巧都已經(jīng)被其他元素置為 1就會(huì)產(chǎn)生誤判。所以誤判率大約是[1 - (1 - 1/m)^(k*n)]^k。當(dāng) m 足夠大時(shí)(1 - 1/m)^(k*n)可以近似為e^(-k*n/m)于是誤判率公式化簡(jiǎn)為(1 - e^(-k*n/m))^k。這個(gè)公式是布隆過濾器參數(shù)設(shè)計(jì)的基石。我第一次推導(dǎo)時(shí)花了很長(zhǎng)時(shí)間才理解“假陽(yáng)性率取決于位數(shù)組被填充的密度”。如果 m 相對(duì)于 n 太小位數(shù)組幾乎全被填成 1那么隨便查一個(gè)不存在的元素k 個(gè)位置大概率都命中誤判率接近 100%布隆過濾器就退化成“什么都可能存在”完全失去意義。2.3 參數(shù)推導(dǎo)與最佳實(shí)踐公式實(shí)際工程中我們不會(huì)去盲猜參數(shù)而是根據(jù)兩個(gè)輸入來反推預(yù)估元素?cái)?shù)量 n 和可接受的最大誤判率 p。需要求的是位數(shù)組長(zhǎng)度 m 和哈希函數(shù)個(gè)數(shù) k。布隆過濾器論文給出了兩個(gè)經(jīng)典公式最優(yōu)位數(shù)組長(zhǎng)度m - n * ln(p) / (ln 2)^2最優(yōu)哈希函數(shù)個(gè)數(shù)k (m / n) * ln 2從數(shù)學(xué)上當(dāng)k (m/n) * ln2時(shí)誤判率達(dá)到最小。近似計(jì)算時(shí)k ≈ 0.7 * (m / n)這個(gè)“0.7”很好記用來快速估算很有效。我舉一個(gè)具體例子。假設(shè)預(yù)估元素 n100 萬要求誤判率 p1%即 0.01。先算 mln(0.01) -4.605(ln 2)^2 0.4805所以m -1000000 * (-4.605) / 0.4805 ≈ 9583105個(gè) bit約 1.15MB。再看 kk (m/n) * ln2 9.58 * 0.693 ≈ 6.64向上取整為 7。也就是用 7 個(gè)哈希函數(shù)在 1.15MB 的位數(shù)組上處理 100 萬個(gè)元素理論誤判率不到 1%。如果把 p 改成 0.1%m 會(huì)變成約 1.72MBk 仍接近 7。這說明在誤判率要求不是極端苛刻時(shí)內(nèi)存開銷其實(shí)相當(dāng)可控。這也是為什么布隆過濾器能在大數(shù)據(jù)領(lǐng)域活下來幾 MB 就能支撐百萬級(jí)數(shù)據(jù)的存在性判斷換成哈希集合是幾十 MB 甚至上 GB。下表是幾個(gè)常用參數(shù)組合可以直接參考預(yù)估元素量 n期望誤判率 p位數(shù)組大小 m內(nèi)存占用哈希函數(shù)個(gè)數(shù) k10 萬1%約 96 萬 bit0.12 MB7100 萬1%約 958 萬 bit1.15 MB7100 萬0.1%約 1437 萬 bit1.72 MB101000 萬1%約 9583 萬 bit11.4 MB71 億0.01%約 19.2 億 bit229 MB13注意一個(gè)問題k 算出來往往不是整數(shù)實(shí)際使用要取整。取整后真實(shí)誤判率會(huì)略高于理論最優(yōu)值但只要?jiǎng)e差太遠(yuǎn)工程上都可以接受。我的建議是 k 向上取整位數(shù)組長(zhǎng)度 m 也可以適當(dāng)往大取因?yàn)槎喾峙湟稽c(diǎn)內(nèi)存能顯著壓低誤判率而少了位后重建代價(jià)更高。3. 實(shí)戰(zhàn)Java 與 Redis 完整落地布隆過濾器3.1 用 Guava 三分鐘接入布隆過濾器生產(chǎn)環(huán)境最快的落地方式是用 Google Guava 的BloomFilter類。Guava 內(nèi)部已經(jīng)實(shí)現(xiàn)好了最優(yōu)參數(shù)計(jì)算、位數(shù)組管理和哈希函數(shù)分配我們只需要告訴它預(yù)期元素量和想要的誤判率。dependency groupIdcom.google.guava/groupId artifactIdguava/artifactId version33.0.0-jre/version /dependency核心代碼如下import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; import java.nio.charset.Charset; import java.util.ArrayList; import java.util.List; import java.util.UUID; public class BloomFilterDemo { public static void main(String[] args) { int expectedInsertions 100_0000; // 預(yù)估插入 100 萬條 double fpp 0.01; // 期望誤判率 1% BloomFilterString filter BloomFilter.create( Funnels.stringFunnel(Charset.defaultCharset()), expectedInsertions, fpp); // 插入 100 萬條模擬數(shù)據(jù) ListString samples new ArrayList(); for (int i 0; i expectedInsertions; i) { String value user- UUID.randomUUID(); samples.add(value); filter.put(value); } // 全部插入完成后再判斷統(tǒng)計(jì)誤判率 int falsePositiveCount 0; for (String value : samples) { // 這里故意再插一次來判斷不對(duì)應(yīng)該換一批不存在的值 } // 正確測(cè)法用一批從未插入過的值測(cè)試 int testCount 10_0000; int hitCount 0; for (int i 0; i testCount; i) { String notExistValue fake- UUID.randomUUID(); if (filter.mightContain(notExistValue)) { hitCount; } } System.out.println(誤判率: (hitCount * 1.0 / testCount)); } }上面代碼里注釋標(biāo)出了我第一次寫時(shí)的錯(cuò)誤為了測(cè)誤判率我又把已插入的值拿去查了一遍當(dāng)然全部命中毫無意義。正確做法是用另一批從未插入過的隨機(jī)字符串去查看有多少被誤判成“存在”。實(shí)測(cè)結(jié)果通常在 1% 左右徘徊符合參數(shù)預(yù)期。Guava 的BloomFilter有一個(gè)值得注意的底層設(shè)計(jì)它內(nèi)部不是用HashMap或BitSet存數(shù)據(jù)而是用了LockFreeBitArray底層是一個(gè)AtomicLongArray。這意味著 Guava 版布隆過濾器是線程安全的多線程并發(fā)put和mightContain不需要額外加鎖這對(duì)高并發(fā)場(chǎng)景非常友好。3.2 Redis 實(shí)現(xiàn)分布式布隆過濾器Guava 的布隆過濾器是進(jìn)程內(nèi)對(duì)象如果應(yīng)用部署了多個(gè)實(shí)例每個(gè)實(shí)例的位數(shù)組是獨(dú)立的判斷結(jié)果就各自為政。比如用戶請(qǐng)求負(fù)載均衡到 A 實(shí)例A 的布隆過濾器說“不存在”但用戶數(shù)據(jù)在 B 實(shí)例里被插入過于是發(fā)生漏判。要解決這個(gè)問題要么引入外部存儲(chǔ)統(tǒng)一維護(hù)位數(shù)組要么做內(nèi)存同步。我推薦前者直接把位圖放到 Redis 里。Redis 的 String 底層是字節(jié)數(shù)組天然支持按位操作。核心命令就三個(gè)SETBIT key offset value把 key 對(duì)應(yīng)的位圖第 offset 位設(shè)為 0 或 1GETBIT key offset讀取第 offset 位BITCOUNT key統(tǒng)計(jì)位圖中有多少位是 1我們的任務(wù)是把“一個(gè)元素的 k 個(gè)哈希位置”轉(zhuǎn)換成多個(gè) offset逐個(gè)SETBIT。這里不再依賴 Guava而是自己實(shí)現(xiàn)哈希映射和位數(shù)組邏輯。import redis.clients.jedis.Jedis; import java.nio.charset.StandardCharsets; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; public class RedisBloomFilter { private static final String KEY bloom:url:filter; private static final int BIT_SIZE 10_000_000; // 1000萬位約1.2MB private static final int HASH_COUNT 7; private final Jedis jedis; public RedisBloomFilter(Jedis jedis) { this.jedis jedis; } public void add(String value) { int[] offsets hashOffsets(value); for (int offset : offsets) { jedis.setbit(KEY, offset, true); } } public boolean mightContain(String value) { int[] offsets hashOffsets(value); for (int offset : offsets) { if (!jedis.getbit(KEY, offset)) { return false; } } return true; } private int[] hashOffsets(String value) { int[] offsets new int[HASH_COUNT]; try { MessageDigest md MessageDigest.getInstance(MD5); byte[] digest md.digest(value.getBytes(StandardCharsets.UTF_8)); // 用一個(gè) 128 位的 MD5 拆成多個(gè)位置 for (int i 0; i HASH_COUNT; i) { int h ((digest[2 * i] 0xFF) 8) | (digest[2 * i 1] 0xFF); offsets[i] Math.abs(h % BIT_SIZE); } } catch (NoSuchAlgorithmException e) { throw new RuntimeException(e); } return offsets; } }這里我用了 MD5 拆位來生成多個(gè)哈希位置簡(jiǎn)單但不完美。MD5 只能算一個(gè)哈希函數(shù)把它拆成多段并不能真正生成 k 個(gè)獨(dú)立哈希只是工程上夠用。更嚴(yán)謹(jǐn)?shù)淖龇ㄊ遣捎秒p重哈?；蚴褂胢urmurhash配合不同種子生成 k 個(gè)獨(dú)立哈希。Guava 內(nèi)部實(shí)際就是基于murmur3_128拆高位和低位來生成線性獨(dú)立的哈希函數(shù)效果比 MD5 拆位好。生產(chǎn)環(huán)境中我建議用 Lua 腳本把“一個(gè)元素的 k 次 setbit”打包成原子操作避免并發(fā)時(shí)中間狀態(tài)被讀到性能也會(huì)好很多。大體的 Lua 邏輯是先用redis.call(GETBIT, ...)判斷所有位置如果都命中則直接返回 1否則逐位SETBIT最后返回 0 或 1。3.3 布隆過濾器不能刪除元素的坑與 Counting Bloom Filter布隆過濾器最大的痛點(diǎn)之一是不支持刪除元素。原因想想就明白一個(gè) bit 位可能同時(shí)被多個(gè)元素共享如果我們刪除某個(gè)元素時(shí)把它對(duì)應(yīng)的 k 個(gè) bit 清 0很可能把其他元素的位置也清了導(dǎo)致其他元素變成“有時(shí)不存在”。這是布隆過濾器的固有缺陷不是實(shí)現(xiàn) bug。面試?yán)锝?jīng)常考這個(gè)點(diǎn)標(biāo)準(zhǔn)回答是常規(guī)布隆過濾器可以 insert 和 query但不能 delete如果業(yè)務(wù)必須支持刪除就要用變種結(jié)構(gòu)比如 Counting Bloom Filter計(jì)數(shù)布隆過濾器。Counting Bloom Filter 的思路是把位數(shù)組里的每一個(gè) bit 擴(kuò)展成一個(gè)計(jì)數(shù)器插入時(shí)給 k 個(gè)位置的計(jì)數(shù)器加 1刪除時(shí)減 1查詢時(shí)看計(jì)數(shù)器是否都大于 0。計(jì)數(shù)器一般用 4 位能表示 0~15支持大約 15 次重復(fù)插入。但它的缺點(diǎn)是空間開銷比普通布隆過濾器大得多因?yàn)槊總€(gè)位置從 1 bit 變成了 4 bit需要的內(nèi)存直接翻 4 倍。工程上我會(huì)先問業(yè)務(wù)真的要支持刪除嗎如果只是偶爾需要“刪除”可以定期重建布隆過濾器成本往往低于引入 Counting Bloom Filter 的復(fù)雜度。我還見過一個(gè)更工程化的補(bǔ)償方案主布隆過濾器不刪除額外維護(hù)一個(gè)“精確刪除集合”也就是用 Redis Set 或數(shù)據(jù)庫(kù)把待刪除的元素精確記錄下來。判斷時(shí)先查布隆過濾器如果布隆過濾器說“不存在”直接返回如果說“可能存在”再去刪除集合里二次確認(rèn)。這樣布隆過濾器本身不用變也能保證刪除語(yǔ)義。缺點(diǎn)是精確集合不能太大否則內(nèi)存優(yōu)勢(shì)就沒了。4. 真實(shí)業(yè)務(wù)場(chǎng)景盤點(diǎn)緩存穿透、黑名單與爬蟲去重4.1 緩存穿透防護(hù)緩存穿透是后端高頻問題。用戶瘋狂請(qǐng)求一個(gè) redis 里不存在、數(shù)據(jù)庫(kù)里也不存在的 key請(qǐng)求每次都繞過緩存直達(dá)數(shù)據(jù)庫(kù)輕則拖慢接口重則把數(shù)據(jù)庫(kù)打掛。布隆過濾器的做法是系統(tǒng)啟動(dòng)或數(shù)據(jù)寫入時(shí)把所有合法 key 都預(yù)先把 hash 位置置 1請(qǐng)求進(jìn)來先過布隆過濾器如果它判定 key 不存在直接返回空根本不去查 Redis 和數(shù)據(jù)庫(kù)。這里要特別說清楚一個(gè)細(xì)節(jié)布隆過濾器說“可能存在”時(shí)我們才去查緩存和 DB說“不存在”時(shí)就直接擋掉。如果是緩存里有但布隆過濾器沒數(shù)據(jù)就會(huì)出現(xiàn)“本來存在卻被誤殺”的情況。所以布隆過濾器必須在數(shù)據(jù)寫入真正的存儲(chǔ)之前就一起更新順序不能反。比如新增一個(gè)用戶時(shí)先filter.put(userId)再寫數(shù)據(jù)庫(kù)或緩存這樣查詢路徑上布隆過濾器的判斷才是完整的。我之前在線上遇到過一個(gè)數(shù)據(jù)不一致的坑歷史存量數(shù)據(jù)導(dǎo)入時(shí)只寫了 Redis 緩存忘記同步布隆過濾器導(dǎo)致大量存量用戶被誤判為“不存在”接口直接返回空數(shù)據(jù)。排查半天最后是逐個(gè)對(duì)比布隆過濾器和數(shù)據(jù)庫(kù)才發(fā)現(xiàn)的。所以如果要從零引入布隆過濾器務(wù)必設(shè)計(jì)離線全量重建流程重建邏輯就是循環(huán)存量數(shù)據(jù)重新put比如在凌晨低峰期跑批處理跑完再切換讀取路徑。4.2 黑名單與敏感信息過濾黑名單場(chǎng)景很經(jīng)典。比如封禁手機(jī)號(hào)、拉黑惡意 IP、過濾垃圾郵件地址本質(zhì)上都是“某個(gè)值在不在名單里”的判斷題。布隆過濾器可以先把黑名單值全部放入查詢時(shí)快速過濾。它的誤判方向是“把白名單誤判成黑名單”也就是寧可錯(cuò)殺、不可放過。這對(duì)部分風(fēng)控業(yè)務(wù)可以接受但對(duì)用戶體驗(yàn)要求高的場(chǎng)景要斟酌。我的建議是采用兩層過濾第一層布隆過濾器粗篩命中后進(jìn)入第二層精確名單Redis Set 或數(shù)據(jù)庫(kù)索引二次確認(rèn)。這樣既享受了布隆過濾器的低內(nèi)存優(yōu)點(diǎn)又避免誤殺真實(shí)用戶。這里要額外提醒一點(diǎn)不要把過于嚴(yán)格的黑名單直接只靠布隆過濾器承載因?yàn)樗坏┱`判用戶要申訴、解封操作成本遠(yuǎn)高于那點(diǎn)內(nèi)存節(jié)省。4.3 爬蟲與 URL 去重分布式爬蟲的 URL 去重是布隆過濾器最舒服的戰(zhàn)場(chǎng)。原因在于爬蟲 URL 去重對(duì)誤判的容忍度很高誤判最多導(dǎo)致少爬幾個(gè)網(wǎng)頁(yè)不影響整體抓取質(zhì)量但 URL 數(shù)量能達(dá)到幾千萬甚至幾十億用哈希表存會(huì)撐爆內(nèi)存用數(shù)據(jù)庫(kù)查詢又太慢。布隆過濾器往中間一放內(nèi)存占用小單次判斷是 O(k) 的位運(yùn)算速度極快。這個(gè)場(chǎng)景我做過一次對(duì)比測(cè)試5000 萬 URL 放在 Guava 布隆過濾器里預(yù)期誤判率 1%內(nèi)存只占約 60MB同樣的數(shù)據(jù)放 Redis Set光 key 就占了不到一點(diǎn)value 內(nèi)存卻要 1GB 以上。差別擺在那里沒有懸念。4.4 數(shù)據(jù)庫(kù)與分庫(kù)分表場(chǎng)景分庫(kù)分表之后跨庫(kù)查詢很昂貴。布隆過濾器可以作為分片路由的輔助結(jié)構(gòu)每個(gè)分片維護(hù)一個(gè)布隆過濾器記錄本分片有哪些主鍵。查詢時(shí)先快速判斷“目標(biāo)主鍵可能在這個(gè)分片嗎”如果所有分片的布隆過濾器都判定不存在就直接返回空避免把所有分片都查一遍。這個(gè)做法在數(shù)據(jù)分布均勻、主鍵命中率低的時(shí)候收益很高。還有一個(gè)和索引相關(guān)的點(diǎn)在 LSM-Tree 結(jié)構(gòu)的存儲(chǔ)引擎里布隆過濾器被用來加速點(diǎn)查。比如 RocksDB 每個(gè) SSTable 都帶一個(gè)內(nèi)置布隆過濾器查詢時(shí)先判斷 key 是否可能在某個(gè) SSTable 里不可能就跳過該文件減少無效磁盤 IO。這就是為什么把布隆過濾器稱為“數(shù)據(jù)庫(kù)隱藏加速器”它不直接存數(shù)據(jù)卻能大幅降低存儲(chǔ)層的隨機(jī)訪問成本。5. 參數(shù)調(diào)優(yōu)、常見問題與排查實(shí)錄5.1 參數(shù)選擇時(shí)要避免的三類錯(cuò)誤參數(shù)選錯(cuò)是布隆過濾器上線后翻車的最常見原因我總結(jié)成三條。第一預(yù)估元素量 n 太樂觀。很多人設(shè)計(jì)時(shí)按當(dāng)時(shí)的數(shù)據(jù)量選 n結(jié)果半年后數(shù)據(jù)翻倍誤判率跟著飆漲。布隆過濾器不像哈希表可以自動(dòng)擴(kuò)容初始化后位數(shù)組大小就固定了只能重建。所以預(yù)估 n 時(shí)我一般會(huì)乘以 2 到 3 倍的冗余系數(shù)寧多勿少。多出來的內(nèi)存通常只有幾 MB 到幾十 MB換來的卻是長(zhǎng)時(shí)間穩(wěn)定運(yùn)行。第二期望誤判率 p 選得太小。理論上看 p 越小越好但 m 和 p 是對(duì)數(shù)關(guān)系把 p 從 1% 壓到 0.01%位數(shù)組長(zhǎng)度大約增加一倍。如果業(yè)務(wù)其實(shí)能容忍 5% 的誤判率卻非要按 0.1% 設(shè)計(jì)純粹是浪費(fèi)內(nèi)存。我自己有個(gè)經(jīng)驗(yàn)值緩存穿透場(chǎng)景一般取 1% 到 5%因?yàn)榧词拐`判也會(huì)落到緩存層成本可控爬蟲去重取 5% 都行風(fēng)控黑名單因?yàn)橛卸尉_校驗(yàn)可以取 1%。第三哈希函數(shù)選得不夠均勻。有的實(shí)現(xiàn)隨便用hashCode()取模這在數(shù)據(jù)分布不均勻時(shí)會(huì)讓位數(shù)組局部過熱誤判率遠(yuǎn)超理論值。穩(wěn)妥做法是用 MurmurHash、MD5 等公認(rèn)的散列算法并檢查哈希函數(shù)數(shù)量 k 和位數(shù)組長(zhǎng)度 m 的組合是否與公式計(jì)算一致。5.2 高頻問題排查速查表我整理了一份布隆過濾器線上排查速查表都是踩過坑后固化下來的判斷路徑?，F(xiàn)象可能原因排查與解決誤判率遠(yuǎn)超預(yù)期位數(shù)組長(zhǎng)度 m 不足或哈希函數(shù)取值相關(guān)用公式按當(dāng)前實(shí)際 n 反算理論誤判率確認(rèn)是否接近考慮重建并擴(kuò)大 m部分?jǐn)?shù)據(jù)查不到假陰性元素可能未插入或插入時(shí)位數(shù)組已滿檢查插入路徑有沒有全量執(zhí)行布隆過濾器本身不存在假陰性出現(xiàn)假陰性一定是你漏插或重建時(shí)丟數(shù)據(jù)內(nèi)存占用超預(yù)期誤用了 Counting Bloom Filter 或哈希表替代確認(rèn)底層使用的是位數(shù)組不是 Set 或 MapRedis 用MEMORY USAGE key檢查實(shí)際占用多實(shí)例結(jié)果不一致每個(gè)實(shí)例各持有一個(gè)獨(dú)立布隆過濾器改用 Redis 統(tǒng)一位數(shù)組或在應(yīng)用層做數(shù)據(jù)同步重建并發(fā)插入時(shí)查詢到中間狀態(tài)插入不是原子的多個(gè)位寫入不連貫用 Lua 腳本包裝多個(gè) setbit保證原子性刪除元素后報(bào)錯(cuò)或異常普通布隆過濾器不支持刪除改用 Counting Bloom Filter或增加精確刪除集合二次確認(rèn)redis key 太大阻塞請(qǐng)求位數(shù)組很大且單 key 頻繁讀寫考慮分段存儲(chǔ)把一個(gè)大 bitmap 拆成多個(gè) key按哈希前綴路由表格里的“假陰性”我特意強(qiáng)調(diào)一下理論上布隆過濾器不會(huì)誤判“存在”為“不存在”一旦出現(xiàn)通常不是因?yàn)椴悸∵^濾器本身而是你插入邏輯沒有覆蓋全部數(shù)據(jù)源或者位數(shù)組被重建但沒同步全部數(shù)據(jù)。我在多個(gè)項(xiàng)目里發(fā)現(xiàn)這個(gè)認(rèn)知能省很多排查時(shí)間。5.3 線上壓測(cè)與災(zāi)備的額外建議布隆過濾器上線前我習(xí)慣先做一輪“誤判率實(shí)測(cè)”準(zhǔn)備 100 萬個(gè)已插入元素和 100 萬個(gè)從未插入元素分別統(tǒng)計(jì)mightContain結(jié)果算出真實(shí)誤判率。如果實(shí)測(cè)和理論差太多多半是哈希函數(shù)質(zhì)量問題或位數(shù)組長(zhǎng)度設(shè)置錯(cuò)誤。實(shí)測(cè)腳本很簡(jiǎn)單代碼本身可以作為自動(dòng)化測(cè)試的一部分長(zhǎng)期執(zhí)行防止后續(xù)改動(dòng)導(dǎo)致回歸。災(zāi)備方面Redis 版布隆過濾器最怕的是 Redis 宕機(jī)或數(shù)據(jù)丟失。位數(shù)組一旦丟失很多元素會(huì)被誤判為不存在緩存穿透問題立即暴露。建議定期把位數(shù)組 dump 到磁盤或者干脆用 AOF 持久化。如果是 Guava 進(jìn)程內(nèi)版本應(yīng)用重啟意味著布隆過濾器清空此時(shí)最好有一個(gè)從數(shù)據(jù)庫(kù)全量重建的兜底任務(wù)在啟動(dòng)后異步執(zhí)行避免服務(wù)一開就被穿透打垮。還有一點(diǎn)個(gè)人經(jīng)驗(yàn)布隆過濾器盡量不要做成公共依賴服務(wù)后讓業(yè)務(wù)方無腦調(diào)用。它帶了“概率誤判”這個(gè)屬性業(yè)務(wù)方如果不理解會(huì)把“可能存在”當(dāng)成“一定存在”導(dǎo)致線上事故。我現(xiàn)在的做法是在 API 命名上直接暴露語(yǔ)義比如mightContain()而不是contains()再在文檔和注釋里反復(fù)強(qiáng)調(diào)這個(gè)方法的語(yǔ)義是“可能”。這個(gè)看起來是個(gè)小細(xì)節(jié)但對(duì)規(guī)避事故很有用。6. 結(jié)尾再聊幾句實(shí)在的最后分享一個(gè)我自己的體會(huì)。做技術(shù)選型時(shí)布隆過濾器看起來是個(gè)“老古董”數(shù)據(jù)結(jié)構(gòu)但它解決的問題恰恰是很多新方案繞不過去的用空間換時(shí)間的反面是用極小的空間成本支撐海量數(shù)據(jù)的存在性判斷。我踩過預(yù)估值不準(zhǔn)的坑也踩過搞錯(cuò)插入順序?qū)е戮彺娲┩傅目拥褏?shù)、業(yè)務(wù)語(yǔ)義和兜底流程想清楚之后它就是一套非常穩(wěn)的基礎(chǔ)設(shè)施。如果你現(xiàn)在正面臨內(nèi)存告急、查詢太慢或者緩存穿透的困擾建議先從“能不能接受誤判”這個(gè)問題入手。答案是可以的話布隆過濾器就有資格進(jìn)入候選答案是不可以的話那就用兩層方案讓布隆過濾器做粗篩精確集合做兜底。數(shù)據(jù)結(jié)構(gòu)的價(jià)值不在于它有多高級(jí)而在于它在合適的場(chǎng)景里能不能用最小的成本解決最扎手的問題。