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