1.布隆過濾器
我們平時刷今日頭條村缸，今日頭條會給我們推薦新的內(nèi)容，它每次推薦時要去重武氓，去掉那些已經(jīng)看過的內(nèi)容梯皿。問題來了，如何實現(xiàn)推送去重呢县恕？
下意識會想到东羹，我們在數(shù)據(jù)庫里記錄好給用戶推薦過的新聞，每次給用戶推薦前忠烛，我們先去記錄表里查一下百姓，看是否推薦過。
存在問題：當數(shù)據(jù)量和并發(fā)量都很高時况木，數(shù)據(jù)庫扛不住
此時有小伙伴會說垒拢，那我存redis里，存redis里當數(shù)據(jù)量大時火惊，會占用大量空間求类，也不是一個好的方案。
布隆過濾器可以理解為一個不怎么精確的 set 結構屹耐，當你使用它的 contains 方法判斷某個對象是否存在時尸疆，它可能會誤判。但是布隆過濾器也不是特別不精確惶岭，只要參數(shù)設置的合理寿弱，它的精確度可以控制的相對足夠精確，只會有小小的誤判概率按灶。
當布隆過濾器說某個值存在時症革，這個值可能不存在；當它說不存在時鸯旁，那就肯定不存在噪矛。
布隆過濾器能準確過濾掉那些已經(jīng)看過的內(nèi)容，那些沒有看過的新內(nèi)容铺罢，它也會過濾掉極小一部分（誤判）艇挨，但是絕大多數(shù)新內(nèi)容它都能準確識別。這樣就可以完全保證推薦給用戶的內(nèi)容都是無重復的韭赘。
Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場缩滨。布隆過濾器作為一個插件加載到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。
2.基本使用
bf.add 添加元素脉漏，bf.exists 查詢元素是否存在蛋勺。
布隆過濾器插件安裝
[root@izuf65itgtxe1lpfpb***** redis]# git clone https://github.com/RedisBloom/RedisBloom.git
[root@izuf65itgtxe1lpfpb***** redis]# cd RedisBloom/
[root@izuf65itgtxe1lpfpb***** RedisBloom]# make
[root@izuf65itgtxe1lpfpb***** RedisBloom]# vi /usr/local/redis/redis.conf
## 增加配置
loadmodule /usr/local/redis/RedisBloom/redisbloom.so
## 重啟redis就行
127.0.0.1:6379> bf.add bloomFilterKey user1
(integer) 1
127.0.0.1:6379> bf.add bloomFilterKey user2
(integer) 1
127.0.0.1:6379> bf.exists bloomFilterKey user2
(integer) 1
127.0.0.1:6379> bf.exists bloomFilterKey user3
(integer) 0
3.原理
添加元素時，先把value轉化為字節(jié)（getBytes(value,”UTF-8")）鸠删，通過算法對元素計算出k（14）個獨立的hash值，然后用這k個獨立的hash值與位圖長度（ 201978）進行取余贼陶，對應位置設置1刃泡。
判斷元素是否存在，對元素計算出k個獨立的hash值碉怔，然后用這k個獨立的hash值與位圖長度（201978）進行取余烘贴，所有的位置都是1表示存在，只要有一位為0都是不存在撮胧。
使用時不要讓實際元素遠大于初始化大小桨踪，當實際元素開始超出初始化大小時，應該對布隆過濾器進行重建芹啥，重新分配一個 size 更大的過濾器锻离，再將所有的歷史元素批量 add 進去（這就要求我們在其它的存儲器中記錄所有的歷史元素）。 因為 error_rate 不會因為數(shù)量超出就急劇增加墓怀，這就給我們重建過濾器提供了較為寬松的時間汽纠。
為什么會存在誤差？
因為這個位置為1傀履，有可能是其他key設置的
建議：使用時不要讓實際元素遠大于初始化大小虱朵，當實際元素開始超出初始化大小時，應該對布隆過濾器進行重建钓账，重新分配一個 size 更大的過濾器碴犬，再將所有的歷史元素批量 add 進去（這就要求我們在其它的存儲器中記錄所有的歷史元素）。因為 error_rate 不會因為數(shù)量超出就急劇增加梆暮，這就給我們重建過濾器提供了較為寬松的時間服协。
注意：位圖長度越長錯誤率越低，但是需要很大的空間啦粹，一般這里都是用預計放入元素量蚯涮，當實際數(shù)量超出這個值時，誤判率會上升
錯誤率計算器：https://krisives.github.io/bloom-calculator/
4.實戰(zhàn)
還是用最開始我們說的需求卖陵，實現(xiàn)新聞推送去重遭顶，假設需求需要我們保證100%的正確率，我們該如何優(yōu)化呢泪蔫？
我們需要設計兩層校驗棒旗，第一層是布隆過濾器，第二層是MySQL。
public void exist(String data) {
// 數(shù)據(jù)是否存在
boolean existFlag = false;
// 1.先去布隆過濾器判斷
if(bloomFilter.exist(data)) {
// 2.如果布隆過濾器存在铣揉，需要在MySQL中進行二次校驗
if(mysqlService.exist(data)) {
// 3.數(shù)據(jù)存在
existFlag = true;
}
}
return existFlag;
}
public void insertRecord() {
// 1.先插入布隆過濾器
// 2.插入到數(shù)據(jù)庫
}
有些同學說饶深，我的Redis版本低于4.0怎么辦？
我們可以使用redis位圖自己實現(xiàn)一個布隆過濾器
</br>
布隆過濾器使用場景：
- 黑名單
- 爬蟲逛拱，爬網(wǎng)頁前先判斷url是否已經(jīng)爬過敌厘，若爬過就不再爬取
- 緩存穿透
