：緩存穿透、URL去重及Redis集成)
先拋一個問題高并發(fā)接口有人用一批不存在的ID瘋狂刷請求每次都繞過緩存直接打數(shù)據(jù)庫連接池瞬間被榨干或者你負責的爬蟲系統(tǒng)每天要抓幾百萬URL用Redis的Set去重內(nèi)存看著往下掉。我當時遇到這兩類需求第一反應(yīng)都是找一種能省內(nèi)存、判斷又夠快的數(shù)據(jù)結(jié)構(gòu)。布隆過濾器就是這么個小家伙它用極小的內(nèi)存告訴你“這個值一定不存在”對于“可能存在”只敢說大概率。這篇內(nèi)容我會把布隆過濾器的原理、手寫實現(xiàn)、Redis集成方式以及兩個真實場景的落地案例完整捋一遍最后聊聊參數(shù)和排坑。不管你是后端開發(fā)、數(shù)據(jù)工程師還是架構(gòu)師只要碰到大量去重或者緩存穿透這篇應(yīng)該能給你一個可以直接開干的方案。1. 布隆過濾器到底解決了什么問題1.1 先從緩存穿透說起緩存穿透這個詞后端同學(xué)應(yīng)該不陌生。正常情況下請求先查Redis緩存命中了就返回沒命中再查數(shù)據(jù)庫查完回填緩存。但有一類請求特別陰險它查的數(shù)據(jù)壓根就不存在。比如攻擊者構(gòu)造一批隨機用戶ID這些ID在系統(tǒng)里沒有任何記錄。緩存里沒有數(shù)據(jù)庫里也沒有于是每次請求都得實打?qū)嵈虻綌?shù)據(jù)庫。數(shù)據(jù)庫要做的是一次全表或者聚簇索引查找查完發(fā)現(xiàn)沒有然后什么也不返回。這種“查一次空一次”的流量如果被放大再大的數(shù)據(jù)庫集群也扛不住。布隆過濾器在這里的作用就是一道低成本的前置關(guān)卡。系統(tǒng)把所有合法ID先寫入布隆過濾器請求進來先問它這個ID存在嗎如果回答“不存在”那太好了直接返回數(shù)據(jù)不存在連緩存都不用查更不用去碰數(shù)據(jù)庫。只有當它回答“可能存在”時才繼續(xù)往下走緩存和數(shù)據(jù)庫的鏈路。由于布隆過濾器能保證“不存在”這個結(jié)論是百分百正確的所以合法ID永遠不會被誤殺被攔下來的都是非法流量。1.2 內(nèi)存量級和延遲的博弈除了防穿透布隆過濾器最常見的用途是海量數(shù)據(jù)去重。舉個具體例子假設(shè)你的爬蟲系統(tǒng)要記錄1000萬條已經(jīng)抓過的URL。用HashSet存每個URL按50字節(jié)算光內(nèi)存就要500MB左右這還只是對象開銷比較理想的情況下。如果URL更長一些或者Java里加上了指針對齊1GB都很正常。更麻煩的是這1000萬條數(shù)據(jù)放入Redis的Set里網(wǎng)絡(luò)開銷、序列化開銷都會讓事情變復(fù)雜。布隆過濾器的內(nèi)存占用則是另一個量級。按誤判率1%來算1000萬條URL大約只要1200萬比特換算下來只有大概1.4MB。就算是誤判率壓到0.1%也才不到18MB。這就是它的核心價值用可控的誤判換幾十甚至幾百倍的內(nèi)存節(jié)省。而且布隆過濾器的查詢只涉及幾次位運算不像HashSet那樣可能存在拉鏈遍歷所以平均延遲也極其穩(wěn)定。1.3 那個“寧漏勿錯”的性質(zhì)我剛接觸布隆過濾器時最困惑的是“誤判”到底怎么理解。后來發(fā)現(xiàn)一句話就能說清楚布隆過濾器只能說“不在”不能說“一定在”。它給出的“在”是概率性的可能把不在集合里的元素誤判成存在這叫假陽性但它永遠不會把真正存在判斷成不存在也就是不會發(fā)生假陰性。這個特性決定了它能用在哪些地方。防緩存穿透場景里假陽性只會讓少數(shù)非法請求繼續(xù)下探到數(shù)據(jù)庫影響有限而假陰性則會直接擋住合法數(shù)據(jù)那是不可接受的。布隆過濾器正好沒有假陰性所以適合做這種“寧可錯殺不寧可不殺也不能漏殺”的場景。等到后面講爬蟲去重你會發(fā)現(xiàn)假陽性可能導(dǎo)致“漏抓”這是它的另一面需要業(yè)務(wù)上單獨兜底。2. 核心原理位數(shù)組和哈希函數(shù)的組合2.1 底料就是個巨型位數(shù)組不用把布隆過濾器想得太玄乎它的底層就是一個很長的位數(shù)組每個位置只能存0或1。一開始所有位都置成0。往里添加元素的時候把這個元素喂給若干個哈希函數(shù)得到若干個位置把這些位置上的0改成1。查詢的時候也一樣算出位置檢查這些位置上是否全部為1。這里的關(guān)鍵點在于“若干個哈希函數(shù)”。哈希函數(shù)的作用是把任意長度的輸入映射到一個固定范圍內(nèi)的整數(shù)也就是位數(shù)組的下標。布隆過濾器要求這些哈希函數(shù)彼此獨立、分布均勻這樣元素被映射到的每個位置都盡量沒有關(guān)聯(lián)能最大程度降低不同元素之間的位重疊概率。2.2 添加和查詢的完整動作看一個具體例子。初始化一個長度為16的位數(shù)組初始狀態(tài)是16個0?，F(xiàn)在要添加字符串a(chǎn)pple我們用了3個哈希函數(shù)分別算出下標1、5、9那么就把這三個位置全部置為1。再添加banana哈希算出的下標是2、5、13把2和13置為15本來就是1保持不變。查詢apple時重新計算1、5、9三個位置全是1于是布隆過濾器回答“可能存在”。查詢cherry時算出下標3、7、11位置3是0立刻就能斷定cherry不在集合里。這就是它的工作原理。值得留意的是為什么不能根據(jù)位置全為1就斷定一定存在因為不同的元素經(jīng)過不同的哈希函數(shù)可能映射到同一個位置。比如某個元素grape的三個哈希值恰好是1、5、9但它從來沒有被添加過布隆過濾器也會認為它存在這就是假陽性。位數(shù)組越短、元素越多這種碰撞概率越大。2.3 誤判率怎么算出來誤判率并不是拍腦袋定出來的。假設(shè)位數(shù)組長度為m元素數(shù)量是n哈希函數(shù)個數(shù)是k。添加完n個元素后任意一個位還是0的概率約等于(1 - 1/m)^(k*n)。查詢一個不存在元素時要能得到“可能存在”需要它對應(yīng)的k個位置全部是1所以誤判率大約為(1 - (1 - 1/m)^(k*n))^k。工程上一般用兩個公式反過來推算參數(shù)。已知預(yù)估元素數(shù)量n和能接受的誤判率p位數(shù)組長度m - (n * ln p) / (ln 2)^2哈希函數(shù)個數(shù)k (m / n) * ln 2舉個例子想要容納1億個元素誤判率控制在0.1%計算得m大約是14.3億比特約179MBk大概是7。也就是說分配179MB內(nèi)存用7個哈希函數(shù)就能支撐1億元素的去重需求。2.4 為什么刪除操作這么棘手布隆過濾器最大的痛點是“不能刪除”。原因很直觀一個位可能同時被多個元素標記為1刪除某個元素時如果把它對應(yīng)的幾個位清零可能把其他元素標記過的位也清了導(dǎo)致其他元素被誤判為不存在。有人會想到計數(shù)布隆過濾器也就是把每個位從0/1換成計數(shù)器刪除時對應(yīng)位置計數(shù)減一減到0才置空。這個思路可行但代價是內(nèi)存占用成倍增加而且計數(shù)溢出需要額外處理。實際生產(chǎn)里我更推薦用“定期重建”或者“按時間分片”的思路來解決數(shù)據(jù)淘汰問題后面排坑部分會細說。3. 手寫一個布隆過濾器并驗證3.1 動手前的思路理論講得再多不如手擼一把。我實現(xiàn)了一個純Python版本的布隆過濾器不依賴第三方位數(shù)組庫只用了標準庫的hashlib和math。整體思路很簡單用一個bytearray當位數(shù)組哈希函數(shù)從md5的摘要里拆出兩個獨立值再用雙哈希方式生成k個可復(fù)現(xiàn)的下標。這樣做的好處是單文件、零依賴用來學(xué)習原理或者做小規(guī)模驗證非常方便。生產(chǎn)環(huán)境建議直接用Redis或者RedisBloom模塊畢竟純Python的位運算性能一般但邏輯是完全一致的。3.2 核心代碼實現(xiàn)import hashlib import math class BloomFilter: def __init__(self, expected_items, error_rate): self.expected_items int(expected_items) self.error_rate error_rate # 計算位數(shù)組長度和哈希函數(shù)個數(shù) self.bit_array_size self._calculate_bit_array_size() self.hash_count self._calculate_hash_count() # 用bytearray存位, 每個字節(jié)8個位 self.bit_array bytearray(self.bit_array_size // 8 1) def _calculate_bit_array_size(self): return int(- (self.expected_items * math.log(self.error_rate)) / (math.log(2) ** 2)) def _calculate_hash_count(self): return int((self.bit_array_size / self.expected_items) * math.log(2)) def _hashes(self, item): # 用md5摘要拆出兩個64位整數(shù)作為獨立哈希的基礎(chǔ) digest hashlib.md5(item.encode(utf-8)).hexdigest() h1 int(digest[:16], 16) h2 int(digest[16:32], 16) if h2 0: h2 1 # 雙哈希生成第i個哈希位置 return [(h1 i * h2) % self.bit_array_size for i in range(self.hash_count)] def _get_bit(self, offset): byte_index offset // 8 bit_offset offset % 8 return (self.bit_array[byte_index] bit_offset) 1 def _set_bit(self, offset): byte_index offset // 8 bit_offset offset % 8 self.bit_array[byte_index] | (1 bit_offset) def add(self, item): for position in self._hashes(item): self._set_bit(position) def contains(self, item): for position in self._hashes(item): if self._get_bit(position) 0: return False return True這段代碼里_hashes用了雙哈希公式(h1 i * h2) % m。h1和h2由md5的摘要拆開得到可以認為相互獨立。生產(chǎn)級實現(xiàn)通常會直接用MurmurHash3或者別的非加密哈希但用md5做示例足夠好用了。3.3 實測一下誤判率代碼寫完就得跑數(shù)據(jù)驗證。我做了個小實驗往過濾器里添加1萬個元素然后用另外1萬個不存在的元素做檢測統(tǒng)計被誤判為存在的比例。def test_error_rate(): bf BloomFilter(expected_items10000, error_rate0.001) # 添加1萬個元素 for i in range(10000): bf.add(fitem-{i}) # 檢查1萬個不存在的元素 false_positive 0 for i in range(10000, 20000): if bf.contains(fitem-{i}): false_positive 1 print(f實際誤判率: {false_positive / 10000:.4%}) test_error_rate()我自己跑了幾次誤判率基本都在0.08%到0.12%之間浮動和理論值接近。說明這套參數(shù)計算和哈希邏輯是靠譜的。如果你把error_rate改成0.0001位數(shù)組長度會變大實測誤判率也會隨之下降。3.4 用Redis bitmap做分布式版本單機版好理解但實際系統(tǒng)通常是多實例部署。共享一份布隆過濾器最省事的辦法就是直接用Redis的bitmap。Redis天然支持SETBIT和GETBIT一個鍵就是完整位數(shù)組所有服務(wù)實例共用。import redis import hashlib import math class RedisBloomFilter: def __init__(self, client, key, expected_items, error_rate): self.client client self.key key self.expected_items expected_items self.error_rate error_rate self.bit_array_size int(- (expected_items * math.log(error_rate)) / (math.log(2) ** 2)) self.hash_count int((self.bit_array_size / expected_items) * math.log(2)) def _hashes(self, item): digest hashlib.md5(item.encode(utf-8)).hexdigest() h1 int(digest[:16], 16) h2 int(digest[16:32], 16) if h2 0: h2 1 return [(h1 i * h2) % self.bit_array_size for i in range(self.hash_count)] def add(self, item): for pos in self._hashes(item): self.client.setbit(self.key, pos, 1) def contains(self, item): for pos in self._hashes(item): if self.client.getbit(self.key, pos) 0: return False return True這段代碼里bit_array_size直接作為Redis bitmap的偏移量上限取決于Redis單個字符串鍵的最大長度默認512MB足夠支持幾十億位的位數(shù)組。如果使用Redis的RedisBloom模塊還有BF.RESERVE和BF.ADD這些命令底層都差不多不需要重復(fù)造輪子。4. 兩個能直接落地的實戰(zhàn)案例4.1 案例一高并發(fā)接口防緩存穿透我參與過的一個商品詳情系統(tǒng)商品ID是大整數(shù)總量接近億級。當時接口偶然會被惡意流量打穿每次幾百個不存在的商品ID請求直接把數(shù)據(jù)庫的讀負載拉滿。當時的解決方案就是布隆過濾器。流程設(shè)計不復(fù)雜。系統(tǒng)啟動時先從商品表把所有商品ID掃一遍寫入一個Redis布隆過濾器大概消耗幾十MB內(nèi)存。之后請求路徑變成請求帶商品ID進來。先用布隆過濾器判斷ID是否存在。如果不存在直接返回“商品不存在”。如果可能存在繼續(xù)查Redis緩存。緩存未命中再查數(shù)據(jù)庫回填緩存并返回結(jié)果。新商品上架時需要注意同步問題。我的做法是先寫入數(shù)據(jù)庫成功再調(diào)用add方法把新ID加入布隆過濾器。這里存在一個極窄的時間窗口商品已經(jīng)寫庫但過濾器還沒更新此時查詢這個新ID會被判定為不存在。這樣的情況很少見而且只會返回一次“不存在”客戶端重試后就能正常。如果你對這個時間窗口容忍不了可以改成先更新布隆過濾器再落庫代價是數(shù)據(jù)庫寫失敗時過濾器里會殘留一個假ID影響也不大。加了這層過濾之后非法流量的請求基本都止步于第一步數(shù)據(jù)庫的無效查詢比例下降了99%以上。對于合法數(shù)據(jù)里的熱點和冷門數(shù)據(jù)原本的緩存邏輯沒有任何改動這就是布隆過濾器的魅力侵入性低收益明確。4.2 案例二爬蟲URL去重告別內(nèi)存爆炸另一個典型的場景是爬蟲。當年我們有個定向抓取任務(wù)每天要處理幾十萬條新URL累計的去重集合很快到了一個分鐘級就要查重幾十萬次的狀態(tài)。早期用Redis的Set存已抓URL跑了兩個星期內(nèi)存就吃掉了好幾個GB而且成員數(shù)量越大判斷耗時也在增加。后來把去重結(jié)構(gòu)換成了布隆過濾器。URL先做一次歸一化只保留規(guī)范格式然后按10億條URL、0.01%誤判率初始化過濾器。抓取前先contains一下如果返回False就抓抓完立刻add。內(nèi)存占用從幾個GB降到了幾百MB查詢耗時更是穩(wěn)定。但這里有個必須正視的問題假陽性會導(dǎo)致部分未抓取URL被當成“已抓過”而漏抓。對于嚴謹?shù)呐老x業(yè)務(wù)漏抓的代價可能比較大。我的做法是對重要URL不做布隆過濾器的唯一性裁決而是用一個極小的白名單Set輔助。具體邏輯是先查白名單Set再查布隆過濾器兩者只要有任何一個判定為“不存在”就去抓取。這個白名單Set只保存那些絕對不允許漏掉的URL比如種子頁、首頁、高價值頁面。這樣布隆過濾器承擔絕大部分去重壓力白名單補足確定性兩者搭配很順手。5. 參數(shù)調(diào)優(yōu)和排坑指南5.1 容量和誤判率估算先別拍腦袋很多人在初始化布隆過濾器時直接用“大概”乘以“隨便”來定參數(shù)結(jié)果上線后誤判率高得離譜。正確做法是先結(jié)合業(yè)務(wù)實際情況估算元素總量n和可接受誤判率p再用公式算出位數(shù)組長度m和哈希函數(shù)個數(shù)k。這里我列出幾個常用配置的參考值預(yù)估元素數(shù)量 n誤判率 p位數(shù)組長度 m占用內(nèi)存哈希函數(shù) k1千萬1%約9580萬比特約11.4MB71千萬0.1%約1.43億比特約17.1MB101億0.1%約14.3億比特約170MB710億0.01%約191.7億比特約2.2GB13可以看出來誤判率要求越嚴格內(nèi)存開銷越大。實際項目里我一般選0.1%作為默認值既能把假陽性控制在很低水平又不會讓內(nèi)存暴漲。如果業(yè)務(wù)場景對漏抓零容忍那么0.01%甚至0.001%也是可以考慮的先估算再定參數(shù)。5.2 誤判率高了怎么調(diào)如果運行一段時間后發(fā)現(xiàn)誤判率明顯高于設(shè)定值排查順序通常是這幾步第一檢查實際元素數(shù)量是不是遠超預(yù)估。布隆過濾器的誤判率會隨著插入元素數(shù)量增加而上升而且是指數(shù)級惡化。如果業(yè)務(wù)增長速度超出預(yù)期就需要擴容。第二檢查哈希函數(shù)個數(shù)k是否合理。k太小位被置1的概率變大k太大位數(shù)組很快就會被全部置1。這兩個極端都會讓誤判率升高。第三檢查位數(shù)組是否因為Redis持久化或者進程重啟導(dǎo)致部分位被重置。這個問題比較隱蔽如果Redis沒有開啟持久化重啟后位數(shù)組會重新歸零那么所有已添加元素都會被判斷為不存在這不是誤判率問題而是數(shù)據(jù)丟失問題。解決思路要么開啟AOF或RDB持久化要么在啟動時從數(shù)據(jù)源重建過濾器。5.3 過濾器不能刪業(yè)務(wù)上怎么兜底正如前面說的標準布隆過濾器不支持刪除。業(yè)務(wù)上如果有元素需要過期淘汰比如URL在一段時間后不再需要去重怎么辦我最常用的方案是“時間分片”。以天為單位生成獨立的布隆過濾器鍵比如url_filter_20250601、url_filter_20250602。查詢時先查當天的過濾器再查昨天的最多查最近N天寫入時只寫當天。這樣歷史數(shù)據(jù)自然過期只需要定期刪除若干天前的鍵就實現(xiàn)了偽刪除。另外一個方案是“定期重建 雙緩沖”。凌晨初始化一個新的布隆過濾器把源數(shù)據(jù)重新灌入然后切換查詢?nèi)肟谂f的過濾器延遲刪除。這個方案適合源數(shù)據(jù)量可控的場景而且能順便調(diào)整參數(shù)。雙緩沖期間要保證寫入只能落到新過濾器否則數(shù)據(jù)會丟。5.4 容易被忽略的幾個坑布隆過濾器用久了有幾個坑值得單獨提出來。第一個坑是哈希函數(shù)的選擇。直接用各個語言自帶的hashCode或者hash()是危險的因為不同進程、不同版本的哈希種子可能不同而且分布質(zhì)量參差不齊?？绶?wù)實例時如果A實例和B實例用不同的哈希函數(shù)同一個元素會生成不同的位位置過濾器的判斷就會錯亂。必須保證所有實例使用完全相同且穩(wěn)定的哈希函數(shù)組合。第二個坑是位數(shù)組偏移量和Redis的字符串編碼。當Redis的字符串長度比較小時內(nèi)部編碼可能是embstr或raw不影響SETBIT和GETBIT但如果你自己拼接位數(shù)組要注意大小端和偏移轉(zhuǎn)換否則數(shù)據(jù)全會錯位。第三個坑是高并發(fā)寫入時的Redis性能。如果每添加一個元素就要執(zhí)行多次SETBIT在超高QPS下會產(chǎn)生很多次RTT。一個優(yōu)化思路是使用Lua腳本把多次位操作合并成一次原子腳本或者使用RedisBloom模塊的BF.ADD、BF.MADD命令。第四個坑是布隆過濾器誤判的“放大器”作用。在防穿透場景里假陽性意味著仍有少量非法請求會穿透到數(shù)據(jù)庫。如果攻擊流量特別大即使1%的假陽性也可能對應(yīng)大量請求。如果觀測到數(shù)據(jù)庫仍然偶爾被打就要把誤判率和非法請求總量相加評估必要時再加一層參數(shù)校驗。我在實際使用中還有一個習慣無論參數(shù)算得多準都會在系統(tǒng)里保留一個布隆過濾器位數(shù)組快照的監(jiān)控指標比如當前元素數(shù)量、位數(shù)組置1的比例。當置1比例超過一定閾值就自動告警提醒我該評估擴容了。這種數(shù)據(jù)驅(qū)動的方式比我最初靠感覺維護過濾器可靠得多。布隆過濾器是個非常成熟的數(shù)據(jù)結(jié)構(gòu)但它的“概率性”決定了我們不能只關(guān)注它省了多少內(nèi)存更要關(guān)注它每個參數(shù)背后對應(yīng)的業(yè)務(wù)風險。只要你把容量估算、哈希一致性和數(shù)據(jù)重建這些細節(jié)處理好它在生產(chǎn)環(huán)境里是真的又省又穩(wěn)。 布隆過濾器原理與實戰(zhàn)：緩存穿透、URL去重及Redis集成
先拋一個問題高并發(fā)接口有人用一批不存在的ID瘋狂刷請求每次都繞過緩存直接打數(shù)據(jù)庫連接池瞬間被榨干或者你負責的爬蟲系統(tǒng)每天要抓幾百萬URL用Redis的Set去重內(nèi)存看著往下掉。我當時遇到這兩類需求第一反應(yīng)都是找一種能省內(nèi)存、判斷又夠快的數(shù)據(jù)結(jié)構(gòu)。布隆過濾器就是這么個小家伙它用極小的內(nèi)存告訴你“這個值一定不存在”對于“可能存在”只敢說大概率。這篇內(nèi)容我會把布隆過濾器的原理、手寫實現(xiàn)、Redis集成方式以及兩個真實場景的落地案例完整捋一遍最后聊聊參數(shù)和排坑。不管你是后端開發(fā)、數(shù)據(jù)工程師還是架構(gòu)師只要碰到大量去重或者緩存穿透這篇應(yīng)該能給你一個可以直接開干的方案。1. 布隆過濾器到底解決了什么問題1.1 先從緩存穿透說起緩存穿透這個詞后端同學(xué)應(yīng)該不陌生。正常情況下請求先查Redis緩存命中了就返回沒命中再查數(shù)據(jù)庫查完回填緩存。但有一類請求特別陰險它查的數(shù)據(jù)壓根就不存在。比如攻擊者構(gòu)造一批隨機用戶ID這些ID在系統(tǒng)里沒有任何記錄。緩存里沒有數(shù)據(jù)庫里也沒有于是每次請求都得實打?qū)嵈虻綌?shù)據(jù)庫。數(shù)據(jù)庫要做的是一次全表或者聚簇索引查找查完發(fā)現(xiàn)沒有然后什么也不返回。這種“查一次空一次”的流量如果被放大再大的數(shù)據(jù)庫集群也扛不住。布隆過濾器在這里的作用就是一道低成本的前置關(guān)卡。系統(tǒng)把所有合法ID先寫入布隆過濾器請求進來先問它這個ID存在嗎如果回答“不存在”那太好了直接返回數(shù)據(jù)不存在連緩存都不用查更不用去碰數(shù)據(jù)庫。只有當它回答“可能存在”時才繼續(xù)往下走緩存和數(shù)據(jù)庫的鏈路。由于布隆過濾器能保證“不存在”這個結(jié)論是百分百正確的所以合法ID永遠不會被誤殺被攔下來的都是非法流量。1.2 內(nèi)存量級和延遲的博弈除了防穿透布隆過濾器最常見的用途是海量數(shù)據(jù)去重。舉個具體例子假設(shè)你的爬蟲系統(tǒng)要記錄1000萬條已經(jīng)抓過的URL。用HashSet存每個URL按50字節(jié)算光內(nèi)存就要500MB左右這還只是對象開銷比較理想的情況下。如果URL更長一些或者Java里加上了指針對齊1GB都很正常。更麻煩的是這1000萬條數(shù)據(jù)放入Redis的Set里網(wǎng)絡(luò)開銷、序列化開銷都會讓事情變復(fù)雜。布隆過濾器的內(nèi)存占用則是另一個量級。按誤判率1%來算1000萬條URL大約只要1200萬比特換算下來只有大概1.4MB。就算是誤判率壓到0.1%也才不到18MB。這就是它的核心價值用可控的誤判換幾十甚至幾百倍的內(nèi)存節(jié)省。而且布隆過濾器的查詢只涉及幾次位運算不像HashSet那樣可能存在拉鏈遍歷所以平均延遲也極其穩(wěn)定。1.3 那個“寧漏勿錯”的性質(zhì)我剛接觸布隆過濾器時最困惑的是“誤判”到底怎么理解。后來發(fā)現(xiàn)一句話就能說清楚布隆過濾器只能說“不在”不能說“一定在”。它給出的“在”是概率性的可能把不在集合里的元素誤判成存在這叫假陽性但它永遠不會把真正存在判斷成不存在也就是不會發(fā)生假陰性。這個特性決定了它能用在哪些地方。防緩存穿透場景里假陽性只會讓少數(shù)非法請求繼續(xù)下探到數(shù)據(jù)庫影響有限而假陰性則會直接擋住合法數(shù)據(jù)那是不可接受的。布隆過濾器正好沒有假陰性所以適合做這種“寧可錯殺不寧可不殺也不能漏殺”的場景。等到后面講爬蟲去重你會發(fā)現(xiàn)假陽性可能導(dǎo)致“漏抓”這是它的另一面需要業(yè)務(wù)上單獨兜底。2. 核心原理位數(shù)組和哈希函數(shù)的組合2.1 底料就是個巨型位數(shù)組不用把布隆過濾器想得太玄乎它的底層就是一個很長的位數(shù)組每個位置只能存0或1。一開始所有位都置成0。往里添加元素的時候把這個元素喂給若干個哈希函數(shù)得到若干個位置把這些位置上的0改成1。查詢的時候也一樣算出位置檢查這些位置上是否全部為1。這里的關(guān)鍵點在于“若干個哈希函數(shù)”。哈希函數(shù)的作用是把任意長度的輸入映射到一個固定范圍內(nèi)的整數(shù)也就是位數(shù)組的下標。布隆過濾器要求這些哈希函數(shù)彼此獨立、分布均勻這樣元素被映射到的每個位置都盡量沒有關(guān)聯(lián)能最大程度降低不同元素之間的位重疊概率。2.2 添加和查詢的完整動作看一個具體例子。初始化一個長度為16的位數(shù)組初始狀態(tài)是16個0?，F(xiàn)在要添加字符串a(chǎn)pple我們用了3個哈希函數(shù)分別算出下標1、5、9那么就把這三個位置全部置為1。再添加banana哈希算出的下標是2、5、13把2和13置為15本來就是1保持不變。查詢apple時重新計算1、5、9三個位置全是1于是布隆過濾器回答“可能存在”。查詢cherry時算出下標3、7、11位置3是0立刻就能斷定cherry不在集合里。這就是它的工作原理。值得留意的是為什么不能根據(jù)位置全為1就斷定一定存在因為不同的元素經(jīng)過不同的哈希函數(shù)可能映射到同一個位置。比如某個元素grape的三個哈希值恰好是1、5、9但它從來沒有被添加過布隆過濾器也會認為它存在這就是假陽性。位數(shù)組越短、元素越多這種碰撞概率越大。2.3 誤判率怎么算出來誤判率并不是拍腦袋定出來的。假設(shè)位數(shù)組長度為m元素數(shù)量是n哈希函數(shù)個數(shù)是k。添加完n個元素后任意一個位還是0的概率約等于(1 - 1/m)^(k*n)。查詢一個不存在元素時要能得到“可能存在”需要它對應(yīng)的k個位置全部是1所以誤判率大約為(1 - (1 - 1/m)^(k*n))^k。工程上一般用兩個公式反過來推算參數(shù)。已知預(yù)估元素數(shù)量n和能接受的誤判率p位數(shù)組長度m - (n * ln p) / (ln 2)^2哈希函數(shù)個數(shù)k (m / n) * ln 2舉個例子想要容納1億個元素誤判率控制在0.1%計算得m大約是14.3億比特約179MBk大概是7。也就是說分配179MB內(nèi)存用7個哈希函數(shù)就能支撐1億元素的去重需求。2.4 為什么刪除操作這么棘手布隆過濾器最大的痛點是“不能刪除”。原因很直觀一個位可能同時被多個元素標記為1刪除某個元素時如果把它對應(yīng)的幾個位清零可能把其他元素標記過的位也清了導(dǎo)致其他元素被誤判為不存在。有人會想到計數(shù)布隆過濾器也就是把每個位從0/1換成計數(shù)器刪除時對應(yīng)位置計數(shù)減一減到0才置空。這個思路可行但代價是內(nèi)存占用成倍增加而且計數(shù)溢出需要額外處理。實際生產(chǎn)里我更推薦用“定期重建”或者“按時間分片”的思路來解決數(shù)據(jù)淘汰問題后面排坑部分會細說。3. 手寫一個布隆過濾器并驗證3.1 動手前的思路理論講得再多不如手擼一把。我實現(xiàn)了一個純Python版本的布隆過濾器不依賴第三方位數(shù)組庫只用了標準庫的hashlib和math。整體思路很簡單用一個bytearray當位數(shù)組哈希函數(shù)從md5的摘要里拆出兩個獨立值再用雙哈希方式生成k個可復(fù)現(xiàn)的下標。這樣做的好處是單文件、零依賴用來學(xué)習原理或者做小規(guī)模驗證非常方便。生產(chǎn)環(huán)境建議直接用Redis或者RedisBloom模塊畢竟純Python的位運算性能一般但邏輯是完全一致的。3.2 核心代碼實現(xiàn)import hashlib import math class BloomFilter: def __init__(self, expected_items, error_rate): self.expected_items int(expected_items) self.error_rate error_rate # 計算位數(shù)組長度和哈希函數(shù)個數(shù) self.bit_array_size self._calculate_bit_array_size() self.hash_count self._calculate_hash_count() # 用bytearray存位, 每個字節(jié)8個位 self.bit_array bytearray(self.bit_array_size // 8 1) def _calculate_bit_array_size(self): return int(- (self.expected_items * math.log(self.error_rate)) / (math.log(2) ** 2)) def _calculate_hash_count(self): return int((self.bit_array_size / self.expected_items) * math.log(2)) def _hashes(self, item): # 用md5摘要拆出兩個64位整數(shù)作為獨立哈希的基礎(chǔ) digest hashlib.md5(item.encode(utf-8)).hexdigest() h1 int(digest[:16], 16) h2 int(digest[16:32], 16) if h2 0: h2 1 # 雙哈希生成第i個哈希位置 return [(h1 i * h2) % self.bit_array_size for i in range(self.hash_count)] def _get_bit(self, offset): byte_index offset // 8 bit_offset offset % 8 return (self.bit_array[byte_index] bit_offset) 1 def _set_bit(self, offset): byte_index offset // 8 bit_offset offset % 8 self.bit_array[byte_index] | (1 bit_offset) def add(self, item): for position in self._hashes(item): self._set_bit(position) def contains(self, item): for position in self._hashes(item): if self._get_bit(position) 0: return False return True這段代碼里_hashes用了雙哈希公式(h1 i * h2) % m。h1和h2由md5的摘要拆開得到可以認為相互獨立。生產(chǎn)級實現(xiàn)通常會直接用MurmurHash3或者別的非加密哈希但用md5做示例足夠好用了。3.3 實測一下誤判率代碼寫完就得跑數(shù)據(jù)驗證。我做了個小實驗往過濾器里添加1萬個元素然后用另外1萬個不存在的元素做檢測統(tǒng)計被誤判為存在的比例。def test_error_rate(): bf BloomFilter(expected_items10000, error_rate0.001) # 添加1萬個元素 for i in range(10000): bf.add(fitem-{i}) # 檢查1萬個不存在的元素 false_positive 0 for i in range(10000, 20000): if bf.contains(fitem-{i}): false_positive 1 print(f實際誤判率: {false_positive / 10000:.4%}) test_error_rate()我自己跑了幾次誤判率基本都在0.08%到0.12%之間浮動和理論值接近。說明這套參數(shù)計算和哈希邏輯是靠譜的。如果你把error_rate改成0.0001位數(shù)組長度會變大實測誤判率也會隨之下降。3.4 用Redis bitmap做分布式版本單機版好理解但實際系統(tǒng)通常是多實例部署。共享一份布隆過濾器最省事的辦法就是直接用Redis的bitmap。Redis天然支持SETBIT和GETBIT一個鍵就是完整位數(shù)組所有服務(wù)實例共用。import redis import hashlib import math class RedisBloomFilter: def __init__(self, client, key, expected_items, error_rate): self.client client self.key key self.expected_items expected_items self.error_rate error_rate self.bit_array_size int(- (expected_items * math.log(error_rate)) / (math.log(2) ** 2)) self.hash_count int((self.bit_array_size / expected_items) * math.log(2)) def _hashes(self, item): digest hashlib.md5(item.encode(utf-8)).hexdigest() h1 int(digest[:16], 16) h2 int(digest[16:32], 16) if h2 0: h2 1 return [(h1 i * h2) % self.bit_array_size for i in range(self.hash_count)] def add(self, item): for pos in self._hashes(item): self.client.setbit(self.key, pos, 1) def contains(self, item): for pos in self._hashes(item): if self.client.getbit(self.key, pos) 0: return False return True這段代碼里bit_array_size直接作為Redis bitmap的偏移量上限取決于Redis單個字符串鍵的最大長度默認512MB足夠支持幾十億位的位數(shù)組。如果使用Redis的RedisBloom模塊還有BF.RESERVE和BF.ADD這些命令底層都差不多不需要重復(fù)造輪子。4. 兩個能直接落地的實戰(zhàn)案例4.1 案例一高并發(fā)接口防緩存穿透我參與過的一個商品詳情系統(tǒng)商品ID是大整數(shù)總量接近億級。當時接口偶然會被惡意流量打穿每次幾百個不存在的商品ID請求直接把數(shù)據(jù)庫的讀負載拉滿。當時的解決方案就是布隆過濾器。流程設(shè)計不復(fù)雜。系統(tǒng)啟動時先從商品表把所有商品ID掃一遍寫入一個Redis布隆過濾器大概消耗幾十MB內(nèi)存。之后請求路徑變成請求帶商品ID進來。先用布隆過濾器判斷ID是否存在。如果不存在直接返回“商品不存在”。如果可能存在繼續(xù)查Redis緩存。緩存未命中再查數(shù)據(jù)庫回填緩存并返回結(jié)果。新商品上架時需要注意同步問題。我的做法是先寫入數(shù)據(jù)庫成功再調(diào)用add方法把新ID加入布隆過濾器。這里存在一個極窄的時間窗口商品已經(jīng)寫庫但過濾器還沒更新此時查詢這個新ID會被判定為不存在。這樣的情況很少見而且只會返回一次“不存在”客戶端重試后就能正常。如果你對這個時間窗口容忍不了可以改成先更新布隆過濾器再落庫代價是數(shù)據(jù)庫寫失敗時過濾器里會殘留一個假ID影響也不大。加了這層過濾之后非法流量的請求基本都止步于第一步數(shù)據(jù)庫的無效查詢比例下降了99%以上。對于合法數(shù)據(jù)里的熱點和冷門數(shù)據(jù)原本的緩存邏輯沒有任何改動這就是布隆過濾器的魅力侵入性低收益明確。4.2 案例二爬蟲URL去重告別內(nèi)存爆炸另一個典型的場景是爬蟲。當年我們有個定向抓取任務(wù)每天要處理幾十萬條新URL累計的去重集合很快到了一個分鐘級就要查重幾十萬次的狀態(tài)。早期用Redis的Set存已抓URL跑了兩個星期內(nèi)存就吃掉了好幾個GB而且成員數(shù)量越大判斷耗時也在增加。后來把去重結(jié)構(gòu)換成了布隆過濾器。URL先做一次歸一化只保留規(guī)范格式然后按10億條URL、0.01%誤判率初始化過濾器。抓取前先contains一下如果返回False就抓抓完立刻add。內(nèi)存占用從幾個GB降到了幾百MB查詢耗時更是穩(wěn)定。但這里有個必須正視的問題假陽性會導(dǎo)致部分未抓取URL被當成“已抓過”而漏抓。對于嚴謹?shù)呐老x業(yè)務(wù)漏抓的代價可能比較大。我的做法是對重要URL不做布隆過濾器的唯一性裁決而是用一個極小的白名單Set輔助。具體邏輯是先查白名單Set再查布隆過濾器兩者只要有任何一個判定為“不存在”就去抓取。這個白名單Set只保存那些絕對不允許漏掉的URL比如種子頁、首頁、高價值頁面。這樣布隆過濾器承擔絕大部分去重壓力白名單補足確定性兩者搭配很順手。5. 參數(shù)調(diào)優(yōu)和排坑指南5.1 容量和誤判率估算先別拍腦袋很多人在初始化布隆過濾器時直接用“大概”乘以“隨便”來定參數(shù)結(jié)果上線后誤判率高得離譜。正確做法是先結(jié)合業(yè)務(wù)實際情況估算元素總量n和可接受誤判率p再用公式算出位數(shù)組長度m和哈希函數(shù)個數(shù)k。這里我列出幾個常用配置的參考值預(yù)估元素數(shù)量 n誤判率 p位數(shù)組長度 m占用內(nèi)存哈希函數(shù) k1千萬1%約9580萬比特約11.4MB71千萬0.1%約1.43億比特約17.1MB101億0.1%約14.3億比特約170MB710億0.01%約191.7億比特約2.2GB13可以看出來誤判率要求越嚴格內(nèi)存開銷越大。實際項目里我一般選0.1%作為默認值既能把假陽性控制在很低水平又不會讓內(nèi)存暴漲。如果業(yè)務(wù)場景對漏抓零容忍那么0.01%甚至0.001%也是可以考慮的先估算再定參數(shù)。5.2 誤判率高了怎么調(diào)如果運行一段時間后發(fā)現(xiàn)誤判率明顯高于設(shè)定值排查順序通常是這幾步第一檢查實際元素數(shù)量是不是遠超預(yù)估。布隆過濾器的誤判率會隨著插入元素數(shù)量增加而上升而且是指數(shù)級惡化。如果業(yè)務(wù)增長速度超出預(yù)期就需要擴容。第二檢查哈希函數(shù)個數(shù)k是否合理。k太小位被置1的概率變大k太大位數(shù)組很快就會被全部置1。這兩個極端都會讓誤判率升高。第三檢查位數(shù)組是否因為Redis持久化或者進程重啟導(dǎo)致部分位被重置。這個問題比較隱蔽如果Redis沒有開啟持久化重啟后位數(shù)組會重新歸零那么所有已添加元素都會被判斷為不存在這不是誤判率問題而是數(shù)據(jù)丟失問題。解決思路要么開啟AOF或RDB持久化要么在啟動時從數(shù)據(jù)源重建過濾器。5.3 過濾器不能刪業(yè)務(wù)上怎么兜底正如前面說的標準布隆過濾器不支持刪除。業(yè)務(wù)上如果有元素需要過期淘汰比如URL在一段時間后不再需要去重怎么辦我最常用的方案是“時間分片”。以天為單位生成獨立的布隆過濾器鍵比如url_filter_20250601、url_filter_20250602。查詢時先查當天的過濾器再查昨天的最多查最近N天寫入時只寫當天。這樣歷史數(shù)據(jù)自然過期只需要定期刪除若干天前的鍵就實現(xiàn)了偽刪除。另外一個方案是“定期重建 雙緩沖”。凌晨初始化一個新的布隆過濾器把源數(shù)據(jù)重新灌入然后切換查詢?nèi)肟谂f的過濾器延遲刪除。這個方案適合源數(shù)據(jù)量可控的場景而且能順便調(diào)整參數(shù)。雙緩沖期間要保證寫入只能落到新過濾器否則數(shù)據(jù)會丟。5.4 容易被忽略的幾個坑布隆過濾器用久了有幾個坑值得單獨提出來。第一個坑是哈希函數(shù)的選擇。直接用各個語言自帶的hashCode或者hash()是危險的因為不同進程、不同版本的哈希種子可能不同而且分布質(zhì)量參差不齊?？绶?wù)實例時如果A實例和B實例用不同的哈希函數(shù)同一個元素會生成不同的位位置過濾器的判斷就會錯亂。必須保證所有實例使用完全相同且穩(wěn)定的哈希函數(shù)組合。第二個坑是位數(shù)組偏移量和Redis的字符串編碼。當Redis的字符串長度比較小時內(nèi)部編碼可能是embstr或raw不影響SETBIT和GETBIT但如果你自己拼接位數(shù)組要注意大小端和偏移轉(zhuǎn)換否則數(shù)據(jù)全會錯位。第三個坑是高并發(fā)寫入時的Redis性能。如果每添加一個元素就要執(zhí)行多次SETBIT在超高QPS下會產(chǎn)生很多次RTT。一個優(yōu)化思路是使用Lua腳本把多次位操作合并成一次原子腳本或者使用RedisBloom模塊的BF.ADD、BF.MADD命令。第四個坑是布隆過濾器誤判的“放大器”作用。在防穿透場景里假陽性意味著仍有少量非法請求會穿透到數(shù)據(jù)庫。如果攻擊流量特別大即使1%的假陽性也可能對應(yīng)大量請求。如果觀測到數(shù)據(jù)庫仍然偶爾被打就要把誤判率和非法請求總量相加評估必要時再加一層參數(shù)校驗。我在實際使用中還有一個習慣無論參數(shù)算得多準都會在系統(tǒng)里保留一個布隆過濾器位數(shù)組快照的監(jiān)控指標比如當前元素數(shù)量、位數(shù)組置1的比例。當置1比例超過一定閾值就自動告警提醒我該評估擴容了。這種數(shù)據(jù)驅(qū)動的方式比我最初靠感覺維護過濾器可靠得多。布隆過濾器是個非常成熟的數(shù)據(jù)結(jié)構(gòu)但它的“概率性”決定了我們不能只關(guān)注它省了多少內(nèi)存更要關(guān)注它每個參數(shù)背后對應(yīng)的業(yè)務(wù)風險。只要你把容量估算、哈希一致性和數(shù)據(jù)重建這些細節(jié)處理好它在生產(chǎn)環(huán)境里是真的又省又穩(wěn)。