上一節(jié)我們學(xué)會(huì)了使用 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行估數(shù)梗摇，它非常有價(jià)值违柏，可以解決多精確度不高的統(tǒng)計(jì)需求。

但是如果我們想知道某一個(gè)值是不是已經(jīng)在 HyperLogLog 結(jié)構(gòu)里面了亮蛔，它就無(wú)能為力了宠互，它只提供了 pfadd 和 pfcount 方法畏线，沒(méi)有提供 pfcontains 這種方法。

講個(gè)使用場(chǎng)景良价，比如我們?cè)谑褂眯侣効蛻?hù)端看新聞時(shí)寝殴，它會(huì)給我們不停地推薦新的內(nèi)容蒿叠，它每次推薦時(shí)要去重，去掉那些已經(jīng)看過(guò)的內(nèi)容蚣常。問(wèn)題來(lái)了市咽，新聞客戶(hù)端推薦系統(tǒng)如何實(shí)現(xiàn)推送去重？

你會(huì)想到服務(wù)器記錄了用戶(hù)看過(guò)的所有歷史記錄抵蚊，當(dāng)推薦系統(tǒng)推薦新聞時(shí)會(huì)從每個(gè)用戶(hù)的歷史記錄里進(jìn)行篩選施绎，過(guò)濾掉那些已經(jīng)存在的記錄。問(wèn)題是當(dāng)用戶(hù)量很大贞绳，每個(gè)用戶(hù)看過(guò)的新聞?dòng)趾芏嗟那闆r下谷醉，這種方式，推薦系統(tǒng)的去重工作在性能上跟的上么冈闭？

實(shí)際上，如果歷史記錄存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)里，去重就需要頻繁地對(duì)數(shù)據(jù)庫(kù)進(jìn)行 exists 查詢(xún)窘俺，當(dāng)系統(tǒng)并發(fā)量很高時(shí)是掰，數(shù)據(jù)庫(kù)是很難扛住壓力的。

你可能又想到了緩存耍休，但是如此多的歷史記錄全部緩存起來(lái)刃永，那得浪費(fèi)多大存儲(chǔ)空間啊羊精？而且這個(gè)存儲(chǔ)空間是隨著時(shí)間線性增長(zhǎng)斯够，你撐得住一個(gè)月，你能撐得住幾年么园匹？但是不緩存的話雳刺，性能又跟不上，這該怎么辦裸违？

這時(shí)掖桦，布隆過(guò)濾器 (Bloom Filter) 閃亮登場(chǎng)了，它就是專(zhuān)門(mén)用來(lái)解決這種去重問(wèn)題的供汛。它在起到去重的同時(shí)枪汪，在空間上還能節(jié)省 90% 以上，只是稍微有那么點(diǎn)不精確怔昨，也就是有一定的誤判概率雀久。

布隆過(guò)濾器是什么 ？

布隆過(guò)濾器可以理解為一個(gè)不怎么精確的 set 結(jié)構(gòu)趁舀，當(dāng)你使用它的 contains 方法判斷某個(gè)對(duì)象是否存在時(shí)赖捌，它可能會(huì)誤判。但是布隆過(guò)濾器也不是特別不精確矮烹，只要參數(shù)設(shè)置的合理越庇，它的精確度可以控制的相對(duì)足夠精確罩锐，只會(huì)有小小的誤判概率。

當(dāng)布隆過(guò)濾器說(shuō)某個(gè)值存在時(shí)卤唉，這個(gè)值可能不存在涩惑；當(dāng)它說(shuō)不存在時(shí)，那就肯定不存在桑驱。打個(gè)比方竭恬，當(dāng)它說(shuō)不認(rèn)識(shí)你時(shí)，肯定就不認(rèn)識(shí)熬的；當(dāng)它說(shuō)見(jiàn)過(guò)你時(shí)痊硕，可能根本就沒(méi)見(jiàn)過(guò)面，不過(guò)因?yàn)槟愕哪樃J(rèn)識(shí)的人中某臉比較相似 (某些熟臉的系數(shù)組合)悦析，所以誤判以前見(jiàn)過(guò)你寿桨。

套在上面的使用場(chǎng)景中，布隆過(guò)濾器能準(zhǔn)確過(guò)濾掉那些已經(jīng)看過(guò)的內(nèi)容强戴，那些沒(méi)有看過(guò)的新內(nèi)容亭螟，它也會(huì)過(guò)濾掉極小一部分 (誤判)，但是絕大多數(shù)新內(nèi)容它都能準(zhǔn)確識(shí)別骑歹。這樣就可以完全保證推薦給用戶(hù)的內(nèi)容都是無(wú)重復(fù)的预烙。

布隆過(guò)濾器基本使用

布隆過(guò)濾器有二個(gè)基本指令，bf.add 添加元素道媚，bf.exists 查詢(xún)?cè)厥欠翊嬖诒獾В挠梅ê?set 集合的 sadd 和 sismember 差不多。注意 bf.add 只能一次添加一個(gè)元素最域，如果想要一次添加多個(gè)谴分，就需要用到 bf.madd 指令。同樣如果需要一次查詢(xún)多個(gè)元素是否存在镀脂，就需要用到bf.mexists 指令牺蹄。

使用的布隆過(guò)濾器只是默認(rèn)參數(shù)的布隆過(guò)濾器，它在我們第一次 add 的時(shí)候自動(dòng)創(chuàng)建薄翅。Redis 其實(shí)還提供了自定義參數(shù)的布隆過(guò)濾器沙兰，需要我們?cè)?add 之前使用 bf.reserve指令顯式創(chuàng)建。如果對(duì)應(yīng)的 key 已經(jīng)存在翘魄，bf.reserve 會(huì)報(bào)錯(cuò)鼎天。bf.reserve 有三個(gè)參數(shù)，分別是 key, error_rate 和 initial_size暑竟。錯(cuò)誤率越低斋射，需要的空間越大。initial_size 參數(shù)表示預(yù)計(jì)放入的元素?cái)?shù)量，當(dāng)實(shí)際數(shù)量超出這個(gè)數(shù)值時(shí)绩鸣，誤判率會(huì)上升怀大。

所以需要提前設(shè)置一個(gè)較大的數(shù)值避免超出導(dǎo)致誤判率升高。如果不使用 bf.reserve呀闻，默認(rèn)的 error_rate 是 0.01，默認(rèn)的 initial_size 是 100潜慎。

注意事項(xiàng)

布隆過(guò)濾器的 initial_size 估計(jì)的過(guò)大捡多，會(huì)浪費(fèi)存儲(chǔ)空間，估計(jì)的過(guò)小铐炫，就會(huì)影響準(zhǔn)確率垒手，用戶(hù)在使用之前一定要盡可能地精確估計(jì)好元素?cái)?shù)量，還需要加上一定的冗余空間以避免實(shí)際元素可能會(huì)意外高出估計(jì)值很多倒信。

布隆過(guò)濾器的 error_rate 越小科贬，需要的存儲(chǔ)空間就越大，對(duì)于不需要過(guò)于精確的場(chǎng)合鳖悠，error_rate 設(shè)置稍大一點(diǎn)也無(wú)傷大雅榜掌。比如在新聞去重上而言，誤判率高一點(diǎn)只會(huì)讓小部分文章不能讓合適的人看到乘综，文章的整體閱讀量不會(huì)因?yàn)檫@點(diǎn)誤判率就帶來(lái)巨大的改變憎账。

布隆過(guò)濾器基本使用

布隆過(guò)濾器有二個(gè)基本指令，bf.add 添加元素卡辰，bf.exists 查詢(xún)?cè)厥欠翊嬖诎澹挠梅ê?set 集合的 sadd 和 sismember 差不多。注意 bf.add 只能一次添加一個(gè)元素九妈，如果想要一次添加多個(gè)反砌，就需要用到 bf.madd 指令。同樣如果需要一次查詢(xún)多個(gè)元素是否存在萌朱，就需要用到 bf.mexists 指令宴树。

127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1

布隆過(guò)濾器的原理

學(xué)會(huì)了布隆過(guò)濾器的使用，下面有必要把原理解釋一下嚷兔，不然讀者還會(huì)繼續(xù)蒙在鼓里森渐。

原理

每個(gè)布隆過(guò)濾器對(duì)應(yīng)到 Redis 的數(shù)據(jù)結(jié)構(gòu)里面就是一個(gè)大型的位數(shù)組和幾個(gè)不一樣的無(wú)偏 hash 函數(shù)。所謂無(wú)偏就是能夠把元素的 hash 值算得比較均勻冒晰。向布隆過(guò)濾器中添加 key 時(shí)同衣，會(huì)使用多個(gè) hash 函數(shù)對(duì) key 進(jìn)行 hash 算得一個(gè)整數(shù)索引值然后對(duì)位數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算得到一個(gè)位置，每個(gè) hash 函數(shù)都會(huì)算得一個(gè)不同的位置壶运。再把位數(shù)組的這幾個(gè)位置都置為 1 就完成了 add 操作耐齐。

向布隆過(guò)濾器詢(xún)問(wèn) key 是否存在時(shí)，跟 add 一樣，也會(huì)把 hash 的幾個(gè)位置都算出來(lái)埠况，看看位數(shù)組中這幾個(gè)位置是否都位 1耸携，只要有一個(gè)位為 0，那么說(shuō)明布隆過(guò)濾器中這個(gè)key 不存在辕翰。如果都是 1夺衍，這并不能說(shuō)明這個(gè) key 就一定存在，只是極有可能存在喜命，因?yàn)檫@些位被置為 1 可能是因?yàn)槠渌?key 存在所致沟沙。如果這個(gè)位數(shù)組比較稀疏，這個(gè)概率就會(huì)很大壁榕，如果這個(gè)位數(shù)組比較擁擠矛紫，這個(gè)概率就會(huì)降低。

空間占用估計(jì)

布隆過(guò)濾器的空間占用有一個(gè)簡(jiǎn)單的計(jì)算公式牌里。布隆過(guò)濾器有兩個(gè)參數(shù)颊咬，第一個(gè)是預(yù)計(jì)元素的數(shù)量 n，第二個(gè)是錯(cuò)誤率 f牡辽。公式根據(jù)這兩個(gè)輸入得到兩個(gè)輸出喳篇，第一個(gè)輸出是位數(shù)組的長(zhǎng)度 l，也就是需要的存儲(chǔ)空間大小 (bit)催享，第二個(gè)輸出是 hash 函數(shù)的最佳數(shù)量 k杭隙。hash 函數(shù)的數(shù)量也會(huì)直接影響到錯(cuò)誤率，最佳的數(shù)量會(huì)有最低的錯(cuò)誤率因妙。
k=0.7*(l/n) # 約等于
f=0.6185^(l/n) # ^ 表示次方計(jì)算痰憎，也就是 math.pow

從公式中可以看出
1、位數(shù)組相對(duì)越長(zhǎng) (l/n)攀涵，錯(cuò)誤率 f 越低铣耘，這個(gè)和直觀上理解是一致的
2、位數(shù)組相對(duì)越長(zhǎng) (l/n)以故，hash 函數(shù)需要的最佳數(shù)量也越多蜗细，影響計(jì)算效率
3、當(dāng)一個(gè)元素平均需要 1 個(gè)字節(jié) (8bit) 的指紋空間時(shí) (l/n=8)怒详，錯(cuò)誤率大約為 2%
4炉媒、錯(cuò)誤率為 10%，一個(gè)元素需要的平均指紋空間為 4.792 個(gè) bit昆烁，大約為 5bit
5吊骤、錯(cuò)誤率為 1%，一個(gè)元素需要的平均指紋空間為 9.585 個(gè) bit静尼，大約為 10bit
6白粉、錯(cuò)誤率為 0.1%传泊，一個(gè)元素需要的平均指紋空間為 14.377 個(gè) bit，大約為 15bit
你也許會(huì)想鸭巴，如果一個(gè)元素需要占據(jù) 15 個(gè) bit眷细，那相對(duì) set 集合的空間優(yōu)勢(shì)是不是就沒(méi)有那么明顯了？這里需要明確的是鹃祖，set 中會(huì)存儲(chǔ)每個(gè)元素的內(nèi)容溪椎，而布隆過(guò)濾器僅僅存儲(chǔ)元素的指紋。元素的內(nèi)容大小就是字符串的長(zhǎng)度惯豆，它一般會(huì)有多個(gè)字節(jié)池磁，甚至是幾十個(gè)上百個(gè)字節(jié)，每個(gè)元素本身還需要一個(gè)指針被 set 集合來(lái)引用楷兽，這個(gè)指針又會(huì)占去 4 個(gè)字節(jié)或 8 個(gè)字節(jié)，取決于系統(tǒng)是 32bit 還是 64bit华临。而指紋空間只有接近 2 個(gè)字節(jié)芯杀，所以布隆過(guò)濾器的空間優(yōu)勢(shì)還是非常明顯的。

實(shí)際元素超出時(shí) 雅潭，誤判率會(huì)怎樣變化

當(dāng)實(shí)際元素超出預(yù)計(jì)元素時(shí)揭厚，錯(cuò)誤率會(huì)有多大變化，它會(huì)急劇上升么扶供，還是平緩地上升筛圆，這就需要另外一個(gè)公式，引入?yún)?shù) t 表示實(shí)際元素和預(yù)計(jì)元素的倍數(shù) t
f=(1-0.5^t)k # 極限近似椿浓，k 是 hash 函數(shù)的最佳數(shù)量
當(dāng) t 增大時(shí)太援，錯(cuò)誤率，f 也會(huì)跟著增大扳碍，分別選擇錯(cuò)誤率為 10%,1%,0.1% 的 k 值提岔，畫(huà)出它的曲線進(jìn)行直觀觀察。

布隆過(guò)濾器的其它應(yīng)用

在爬蟲(chóng)系統(tǒng)中，我們需要對(duì) URL 進(jìn)行去重星瘾，已經(jīng)爬過(guò)的網(wǎng)頁(yè)就可以不用爬了走孽。但是URL 太多了，幾千萬(wàn)幾個(gè)億琳状，如果用一個(gè)集合裝下這些 URL 地址那是非常浪費(fèi)空間的磕瓷。這時(shí)候就可以考慮使用布隆過(guò)濾器。它可以大幅降低去重存儲(chǔ)消耗念逞，只不過(guò)也會(huì)使得爬蟲(chóng)系統(tǒng)錯(cuò)過(guò)少量的頁(yè)面困食。

布隆過(guò)濾器在 NoSQL 數(shù)據(jù)庫(kù)領(lǐng)域使用非常廣泛，我們平時(shí)用到的 HBase翎承、Cassandra還有 LevelDB硕盹、RocksDB 內(nèi)部都有布隆過(guò)濾器結(jié)構(gòu)，布隆過(guò)濾器可以顯著降低數(shù)據(jù)庫(kù)的 IO請(qǐng)求數(shù)量叨咖。當(dāng)用戶(hù)來(lái)查詢(xún)某個(gè) row 時(shí)瘩例，可以先通過(guò)內(nèi)存中的布隆過(guò)濾器過(guò)濾掉大量不存在的row 請(qǐng)求，然后再去磁盤(pán)進(jìn)行查詢(xún)甸各。

郵箱系統(tǒng)的垃圾郵件過(guò)濾功能也普遍用到了布隆過(guò)濾器垛贤，因?yàn)橛昧诉@個(gè)過(guò)濾器，所以平時(shí)也會(huì)遇到某些正常的郵件被放進(jìn)了垃圾郵件目錄中趣倾，這個(gè)就是誤判所致聘惦，概率很低。