Google用1%內(nèi)存過(guò)濾99%請(qǐng)求

每秒216萬(wàn)次查詢(xún)，怎么做到不重復(fù)推薦？這是InfoQ一篇技術(shù)長(zhǎng)文里的真實(shí)數(shù)字——某推薦系統(tǒng)峰值時(shí)要處理18000請(qǐng)求/秒，每個(gè)請(qǐng)求檢查120條候選內(nèi)容是否被用戶(hù)看過(guò)。傳統(tǒng)數(shù)據(jù)庫(kù)扛不住，Redis集群也肉疼，工程師最后掏出了一個(gè)1970年誕生的老古董。

答案叫布隆過(guò)濾器（Bloom Filter）。一個(gè)用1%內(nèi)存換取99%過(guò)濾效率的概率型數(shù)據(jù)結(jié)構(gòu)。

這東西的原理說(shuō)起來(lái)像賭場(chǎng)抽老千：你問(wèn)"這個(gè)用戶(hù)看過(guò)這篇文章嗎"，它要么說(shuō)"肯定沒(méi)看過(guò)"，要么說(shuō)"可能看過(guò)"。從不說(shuō)謊說(shuō)"肯定看過(guò)"，但偶爾會(huì)誤判。代價(jià)是極低的內(nèi)存占用——存100萬(wàn)個(gè)元素只要約1.14MB，而Redis需要幾十倍空間。

布隆過(guò)濾器的數(shù)學(xué)基礎(chǔ)很樸素。它用一個(gè)長(zhǎng)度為m的二進(jìn)制位數(shù)組，配合k個(gè)獨(dú)立哈希函數(shù)。插入元素時(shí)，k個(gè)哈希函數(shù)算出k個(gè)位置，全部置為1。查詢(xún)時(shí)，檢查這k個(gè)位是否都為1：但凡有一個(gè)為0，元素絕對(duì)不存在；全為1則"可能存在"。

誤判率（假陽(yáng)性率）的公式是 (1 - e^(-kn/m))^k。工程師真正要算的是：給定預(yù)期元素?cái)?shù)量n和可接受的誤判率p，該選多大的m、多少個(gè)k？推導(dǎo)結(jié)果是 m = -n·ln(p)/(ln2)^2，k = m/n·ln2。

以實(shí)際場(chǎng)景為例：預(yù)期100萬(wàn)元素，誤判率1%，需要約143.8萬(wàn)位（約1.72MB），哈希函數(shù)7個(gè)。誤判率壓到0.1%，內(nèi)存漲到2.58MB，哈希函數(shù)10個(gè)。這是典型的工程權(quán)衡——精度換空間，或空間換精度。

Go語(yǔ)言實(shí)現(xiàn)布隆過(guò)濾器相當(dāng)直白。位數(shù)組用 []uint64，哈希函數(shù)選MurmurHash3或xxHash這類(lèi)高性能非加密哈希。核心操作是位運(yùn)算：定位到具體uint64，再算位偏移。

代碼結(jié)構(gòu)通常三層：底層是位集（BitSet）的讀寫(xiě)封裝，中間是哈希策略接口，上層是BloomFilter結(jié)構(gòu)體暴露Add和Contains方法。Go的內(nèi)存布局和指針運(yùn)算讓這種位級(jí)操作很可控，沒(méi)有C的指針噩夢(mèng)，也沒(méi)有Java的裝箱開(kāi)銷(xiāo)。

但布隆過(guò)濾器有個(gè)致命缺陷：不能刪除。位被多個(gè)元素共享，貿(mào)然清零會(huì)誤傷。計(jì)數(shù)布隆過(guò)濾器（Counting Bloom Filter）用4位或8位計(jì)數(shù)器代替單比特，支持刪除，內(nèi)存也相應(yīng)膨脹4-8倍。還有布谷鳥(niǎo)過(guò)濾器（Cuckoo Filter），用另一種哈希方案實(shí)現(xiàn)可刪除，但實(shí)現(xiàn)復(fù)雜度和內(nèi)存效率各有取舍。

工程落地時(shí)，布隆過(guò)濾器常作為"預(yù)過(guò)濾器"存在。查詢(xún)先過(guò)布隆，不存在直接返回，存在再走數(shù)據(jù)庫(kù)或緩存驗(yàn)證。這樣把昂貴的存儲(chǔ)查詢(xún)砍掉大部分，只剩少量誤判需要二次確認(rèn)。文章里的推薦系統(tǒng)正是這個(gè)套路：先過(guò)濾掉用戶(hù)已讀內(nèi)容，再對(duì)剩余候選做精排。

分布式場(chǎng)景更有意思。Google的Bigtable用布隆過(guò)濾器減少磁盤(pán)IO，查詢(xún)前先檢查內(nèi)存中的布隆過(guò)濾器，避免訪問(wèn)根本不存在的數(shù)據(jù)塊。LevelDB、RocksDB同理，每個(gè)SSTable文件配一個(gè)布隆過(guò)濾器，讀放大顯著降低。這是存儲(chǔ)引擎的標(biāo)配優(yōu)化，但用戶(hù)通常無(wú)感知。

參數(shù)調(diào)優(yōu)是門(mén)手藝。元素?cái)?shù)量預(yù)估偏差太大，實(shí)際誤判率會(huì)偏離設(shè)計(jì)值。哈希函數(shù)太多，計(jì)算開(kāi)銷(xiāo)上升；太少，誤判率壓不住。位數(shù)組太大，內(nèi)存浪費(fèi)；太小，精度崩盤(pán)。沒(méi)有銀彈，只有針對(duì)具體 workload 的反復(fù)測(cè)試。

文章作者用Go寫(xiě)了個(gè)實(shí)現(xiàn)，核心代碼不過(guò)兩百行。測(cè)試覆蓋各種邊界：空過(guò)濾器、重復(fù)插入、誤判率統(tǒng)計(jì)。benchmark顯示單次查詢(xún)約20-50納秒，內(nèi)存訪問(wèn)是瓶頸——現(xiàn)代CPU算哈希比讀內(nèi)存快。

什么場(chǎng)景不該用布隆過(guò)濾器？需要精確答案的場(chǎng)合，比如金融交易對(duì)賬、醫(yī)療診斷系統(tǒng)。假陽(yáng)性的代價(jià)太高，寧可多花內(nèi)存用精確集合。元素?cái)?shù)量極小（幾千個(gè)）也不值得，哈希表的常數(shù)開(kāi)銷(xiāo)更低。還有需要遍歷所有元素的場(chǎng)景——布隆過(guò)濾器根本存不下原始數(shù)據(jù)。

布隆過(guò)濾器的變體很多。分層布隆過(guò)濾器處理元素動(dòng)態(tài)增長(zhǎng)，可擴(kuò)展布隆過(guò)濾器（Scalable Bloom Filter）用多個(gè)子過(guò)濾器串聯(lián)，元素增多時(shí)新建更大的過(guò)濾器，查詢(xún)時(shí)逐個(gè)檢查。這些擴(kuò)展解決原始設(shè)計(jì)的剛性，但復(fù)雜度也線(xiàn)性上升。

回到文章開(kāi)頭的推薦系統(tǒng)。216萬(wàn)次查詢(xún)/秒，如果用Redis Set，按每個(gè)元素64位估算，100萬(wàn)元素需要約8MB內(nèi)存，查詢(xún)是O(1)但網(wǎng)絡(luò)RTT致命。布隆過(guò)濾器常駐進(jìn)程內(nèi)存，查詢(xún)是幾十納秒的本地操作，差距是數(shù)量級(jí)的。

作者最后提到一個(gè)細(xì)節(jié)：他們的生產(chǎn)環(huán)境用了分層策略。熱數(shù)據(jù)用精確集合保證體驗(yàn)，冷數(shù)據(jù)用布隆過(guò)濾器省內(nèi)存。用戶(hù)最近看過(guò)的幾百篇文章絕對(duì)不準(zhǔn)重復(fù)，幾年前的舊內(nèi)容偶爾誤判也無(wú)傷大雅。工程是妥協(xié)的藝術(shù)，不是算法的炫技。

布隆過(guò)濾器的發(fā)明者Burton Bloom在1970年的論文里，大概想不到這個(gè)結(jié)構(gòu)會(huì)在50年后支撐每秒數(shù)十億次的互聯(lián)網(wǎng)請(qǐng)求。概率型數(shù)據(jù)結(jié)構(gòu)的魅力就在于此：接受微小的不確定性，換取巨大的資源效率。這不是缺陷，是設(shè)計(jì)。

文章末尾，作者留了個(gè)未解的問(wèn)題：他們的實(shí)現(xiàn)用了固定大小的位數(shù)組，生產(chǎn)環(huán)境怎么優(yōu)雅處理元素?cái)?shù)量超出預(yù)期的場(chǎng)景？擴(kuò)容意味著重建過(guò)濾器，服務(wù)怎么做到無(wú)感知？