從一個場景說起
在刷抖音有刷到過重復(fù)內(nèi)容嗎，這么多的推薦內(nèi)容要推薦給這么多的用戶，它是怎么保證每個用戶在看推薦內(nèi)容時，保證不會出現(xiàn)之前已經(jīng)看過的推薦視頻呢？也就是說，抖音是如何實現(xiàn) 推送去重 的呢。
傳統(tǒng)實現(xiàn)上，可能是服務(wù)器記錄了每個用戶看過的所有歷史記錄，當推薦系統(tǒng)推薦短視頻時會從每個用戶的歷史記錄里進行 篩選，過濾掉那些已經(jīng)存在的記錄。問題是當用戶量很大，每個用戶看過的短視頻又很多的情況下，這種方式，推薦系統(tǒng)的去重工作 在性能上是跟不上的。
如果歷史記錄存儲在關(guān)系數(shù)據(jù)庫里，去重就需要頻繁地對數(shù)據(jù)庫進行 exists 查詢，當系統(tǒng)并發(fā)量很高時，數(shù)據(jù)庫是很難抗住壓力的。
如果使用緩存，但是這么多用戶這么多的歷史記錄，如果全部緩存起來，那得需要浪費多大的空間，并且這個存儲空間會隨著時間呈線性增長，撐不了多久，不緩存性能又跟不上。
布隆過濾器(Bloom Filter) 就是這樣一種專門用來解決去重問題的高級數(shù)據(jù)結(jié)構(gòu)，類似于bit數(shù)組，有那么一點不精確，也存在一定的誤判概率，但它能在解決去重的同時，在 空間上能節(jié)省 90% 以上，也是非常值得的。
簡介
布隆過濾器（Bloom Filter實際上 是一個很長的二進制向量和一系列隨機映射函數(shù) ，實際上你也可以把它 簡單理解 為一個不怎么精確的 set 結(jié)構(gòu)，當你使用它的 contains 方法判斷某個對象是否存在時，它可能會誤判。但是布隆過濾器也不是特別不精確，只要參數(shù)設(shè)置的合理，它的精確度可以控制的相對足夠精確，只會有小小的誤判概率。
當布隆過濾器說某個值存在時，這個值可能不存在；當它說不存在時，那么一定不存在。
原理
當一個元素被加入集合時，通過N個散列函數(shù)將這個元素映射成一個位數(shù)組中的N個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。
Bloom Filter跟單哈希函數(shù)Bit-Map不同之處在于：Bloom Filter使用了N個哈希函數(shù)，每個字符串跟N個bit對應(yīng)。從而降低了沖突的概率。
簡單的說一下就是我們先把我們數(shù)據(jù)庫的數(shù)據(jù)都加載到我們的過濾器中，比如數(shù)據(jù)庫的id現(xiàn)在有：1、2、3
那就用id：1 為例子他在上圖中經(jīng)過三次hash之后，把三次原本值0的地方改為1
下次我進來查詢?nèi)绻鹖d也是1 那我就把1拿去三次hash 發(fā)現(xiàn)跟上面的三個位置完全一樣，那就能證明過濾器中有1的，反之如果不一樣就說明不存在了。
缺點
bloom filter之所以能做到在時間和空間上的效率比較高，是因為犧牲了判斷的準確率、刪除的便利性
存在誤判，可能要查到的元素并沒有在容器中，但是hash之后得到的n個位置上值都是1。如果bloom filter中存儲的是黑名單，那么可以通過建立一個白名單來存儲可能會誤判的元素。
刪除困難。一個放入容器的元素映射到bit數(shù)組的n個位置上是1，刪除的時候不能簡單的直接置為0，可能會影響其他元素的判斷。
應(yīng)用場景
解決緩存穿透：我們經(jīng)常會把一些熱點數(shù)據(jù)放在 Redis 中當作緩存，例如產(chǎn)品詳情。通常一個請求過來之后我們會先查詢緩存，而不用直接讀取數(shù)據(jù)庫，這是提升性能最簡單也是最普遍的做法，但是 如果一直請求一個不存在的緩存，那么此時一定不存在緩存，那就會有大量請求直接打到數(shù)據(jù)庫 上，造成 緩存穿透，布隆過濾器也可以用來解決此類問題。
大數(shù)據(jù)判斷是否存在：這就可以實現(xiàn)出上述的去重功能，如果你的服務(wù)器內(nèi)存足夠大的話，那么使用 HashMap 可能是一個不錯的解決方案，理論上時間復(fù)雜度可以達到 O(1)的級別，但是當數(shù)據(jù)量起來之后，還是只能考慮布隆過濾器。場景有例如爬蟲過濾已抓到的url就不再抓，可用bloom filter過濾；前面說的存儲用戶看過的視頻記錄； 垃圾郵件過濾等。
垃圾郵件過濾。如果用哈希表，每存儲一億個 email地址，就需要 1.6GB的內(nèi)存（用哈希表實現(xiàn)的具體辦法是將每一個 email地址對應(yīng)成一個八字節(jié)的信息指紋，然后將這些信息指紋存入哈希表，由于哈希表的存儲效率一般只有 50%，因此一個 email地址需要占用十六個字節(jié)。一億個地址大約要 1.6GB，即十六億字節(jié)的內(nèi)存）。因此存貯幾十億個郵件地址可能需要上百 GB的內(nèi)存。而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解決同樣的問題。
Redis中使用
Redis 官方 提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場。布隆過濾器作為一個插件加載到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。
實驗
布隆過濾器有兩個基本指令，bf.add 添加元素，bf.exists 查詢元素是否存在，它的用法和 set 集合的 sadd 和 sismember 差不多。注意 bf.add 只能一次添加一個元素，如果想要一次添加多個，就需要用到 bf.madd 指令。同樣如果需要一次查詢多個元素是否存在，就需要用到 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--
