從一個(gè)場(chǎng)景說(shuō)起

在刷抖音有刷到過重復(fù)內(nèi)容嗎，這么多的推薦內(nèi)容要推薦給這么多的用戶赚哗，它是怎么保證每個(gè)用戶在看推薦內(nèi)容時(shí)蟋字，保證不會(huì)出現(xiàn)之前已經(jīng)看過的推薦視頻呢？也就是說(shuō)嗅钻，抖音是如何實(shí)現(xiàn) 推送去重 的呢皂冰。

傳統(tǒng)實(shí)現(xiàn)上，可能是服務(wù)器記錄了每個(gè)用戶看過的所有歷史記錄养篓，當(dāng)推薦系統(tǒng)推薦短視頻時(shí)會(huì)從每個(gè)用戶的歷史記錄里進(jìn)行 篩選秃流，過濾掉那些已經(jīng)存在的記錄。問題是當(dāng)用戶量很大柳弄，每個(gè)用戶看過的短視頻又很多的情況下舶胀，這種方式，推薦系統(tǒng)的去重工作 在性能上是跟不上的。

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

如果使用緩存放典，但是這么多用戶這么多的歷史記錄，如果全部緩存起來(lái)基茵，那得需要浪費(fèi)多大的空間奋构，并且這個(gè)存儲(chǔ)空間會(huì)隨著時(shí)間呈線性增長(zhǎng)，撐不了多久耿导，不緩存性能又跟不上声怔。

布隆過濾器(Bloom Filter) 就是這樣一種專門用來(lái)解決去重問題的高級(jí)數(shù)據(jù)結(jié)構(gòu)，類似于bit數(shù)組舱呻，有那么一點(diǎn)不精確醋火，也存在一定的誤判概率，但它能在解決去重的同時(shí)箱吕，在 空間上能節(jié)省 90% 以上芥驳，也是非常值得的。

簡(jiǎn)介

布隆過濾器（Bloom Filter實(shí)際上 是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù) 茬高，實(shí)際上你也可以把它 簡(jiǎn)單理解 為一個(gè)不怎么精確的 set 結(jié)構(gòu)兆旬，當(dāng)你使用它的 contains 方法判斷某個(gè)對(duì)象是否存在時(shí)，它可能會(huì)誤判怎栽。但是布隆過濾器也不是特別不精確丽猬，只要參數(shù)設(shè)置的合理，它的精確度可以控制的相對(duì)足夠精確熏瞄，只會(huì)有小小的誤判概率脚祟。

當(dāng)布隆過濾器說(shuō)某個(gè)值存在時(shí)，這個(gè)值可能不存在强饮；當(dāng)它說(shuō)不存在時(shí)由桌，那么一定不存在。

原理

當(dāng)一個(gè)元素被加入集合時(shí)邮丰，通過N個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的N個(gè)點(diǎn)行您，把它們置為1。檢索時(shí)剪廉，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個(gè)0娃循，則被檢元素一定不在；如果都是1斗蒋，則被檢元素很可能在淮野。這就是布隆過濾器的基本思想捧书。

Bloom Filter跟單哈希函數(shù)Bit-Map不同之處在于：Bloom Filter使用了N個(gè)哈希函數(shù)，每個(gè)字符串跟N個(gè)bit對(duì)應(yīng)骤星。從而降低了沖突的概率。

image.png

簡(jiǎn)單的說(shuō)一下就是我們先把我們數(shù)據(jù)庫(kù)的數(shù)據(jù)都加載到我們的過濾器中爆哑，比如數(shù)據(jù)庫(kù)的id現(xiàn)在有：1洞难、2、3
那就用id：1 為例子他在上圖中經(jīng)過三次hash之后揭朝，把三次原本值0的地方改為1
下次我進(jìn)來(lái)查詢?nèi)绻鹖d也是1 那我就把1拿去三次hash 發(fā)現(xiàn)跟上面的三個(gè)位置完全一樣队贱，那就能證明過濾器中有1的，反之如果不一樣就說(shuō)明不存在了潭袱。

缺點(diǎn)

bloom filter之所以能做到在時(shí)間和空間上的效率比較高柱嫌，是因?yàn)闋奚伺袛嗟臏?zhǔn)確率、刪除的便利性

• 存在誤判屯换，可能要查到的元素并沒有在容器中编丘，但是hash之后得到的n個(gè)位置上值都是1。如果bloom filter中存儲(chǔ)的是黑名單彤悔，那么可以通過建立一個(gè)白名單來(lái)存儲(chǔ)可能會(huì)誤判的元素嘉抓。

• 刪除困難。一個(gè)放入容器的元素映射到bit數(shù)組的n個(gè)位置上是1晕窑，刪除的時(shí)候不能簡(jiǎn)單的直接置為0抑片，可能會(huì)影響其他元素的判斷。

應(yīng)用場(chǎng)景

• 解決緩存穿透：我們經(jīng)常會(huì)把一些熱點(diǎn)數(shù)據(jù)放在 Redis 中當(dāng)作緩存杨赤，例如產(chǎn)品詳情敞斋。通常一個(gè)請(qǐng)求過來(lái)之后我們會(huì)先查詢緩存，而不用直接讀取數(shù)據(jù)庫(kù)疾牲，這是提升性能最簡(jiǎn)單也是最普遍的做法植捎，但是 如果一直請(qǐng)求一個(gè)不存在的緩存，那么此時(shí)一定不存在緩存说敏，那就會(huì)有大量請(qǐng)求直接打到數(shù)據(jù)庫(kù) 上鸥跟，造成 緩存穿透，布隆過濾器也可以用來(lái)解決此類問題盔沫。

• 大數(shù)據(jù)判斷是否存在：這就可以實(shí)現(xiàn)出上述的去重功能医咨，如果你的服務(wù)器內(nèi)存足夠大的話，那么使用 HashMap 可能是一個(gè)不錯(cuò)的解決方案架诞，理論上時(shí)間復(fù)雜度可以達(dá)到 O(1)的級(jí)別拟淮，但是當(dāng)數(shù)據(jù)量起來(lái)之后，還是只能考慮布隆過濾器谴忧。場(chǎng)景有例如爬蟲過濾已抓到的url就不再抓很泊，可用bloom filter過濾角虫；前面說(shuō)的存儲(chǔ)用戶看過的視頻記錄； 垃圾郵件過濾等委造。

• 垃圾郵件過濾戳鹅。如果用哈希表，每存儲(chǔ)一億個(gè) email地址昏兆，就需要 1.6GB的內(nèi)存（用哈希表實(shí)現(xiàn)的具體辦法是將每一個(gè) email地址對(duì)應(yīng)成一個(gè)八字節(jié)的信息指紋枫虏，然后將這些信息指紋存入哈希表，由于哈希表的存儲(chǔ)效率一般只有 50%爬虱，因此一個(gè) email地址需要占用十六個(gè)字節(jié)隶债。一億個(gè)地址大約要 1.6GB，即十六億字節(jié)的內(nèi)存）跑筝。因此存貯幾十億個(gè)郵件地址可能需要上百 GB的內(nèi)存死讹。而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解決同樣的問題。

Redis中使用

Redis 官方 提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場(chǎng)曲梗。布隆過濾器作為一個(gè)插件加載到 Redis Server 中赞警，給 Redis 提供了強(qiáng)大的布隆去重功能。

實(shí)驗(yàn)

布隆過濾器有兩個(gè)基本指令稀并，bf.add 添加元素仅颇，bf.exists 查詢?cè)厥欠翊嬖冢挠梅ê?set 集合的 sadd 和 sismember 差不多碘举。注意 bf.add 只能一次添加一個(gè)元素忘瓦，如果想要一次添加多個(gè)，就需要用到 bf.madd 指令引颈。同樣如果需要一次查詢多個(gè)元素是否存在耕皮，就需要用到 bf.mexists 指令。

127.0.0.1:6379> bf.add bl user1
(integer) 1
127.0.0.1:6379> bf.add bl user2
(integer) 1
127.0.0.1:6379> bf.add bl user3
(integer) 1
127.0.0.1:6379> bf.exists bl user1
(integer) 1
127.0.0.1:6379> bf.exists bl user2
(integer) 1
127.0.0.1:6379> bf.exists bl user3
(integer) 1
127.0.0.1:6379> bf.exists bl user4
(integer) 0
127.0.0.1:6379> bf.madd bl user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists bl user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
127.0.0.1:6379> object encoding bl
"raw"
127.0.0.1:6379> type bl
MBbloom--