1.布隆過(guò)濾器

我們平時(shí)刷今日頭條，今日頭條會(huì)給我們推薦新的內(nèi)容，它每次推薦時(shí)要去重，去掉那些已經(jīng)看過(guò)的內(nèi)容。問(wèn)題來(lái)了，如何實(shí)現(xiàn)推送去重呢？

下意識(shí)會(huì)想到，我們?cè)跀?shù)據(jù)庫(kù)里記錄好給用戶推薦過(guò)的新聞，每次給用戶推薦前，我們先去記錄表里查一下，看是否推薦過(guò)。

存在問(wèn)題：當(dāng)數(shù)據(jù)量和并發(fā)量都很高時(shí)，數(shù)據(jù)庫(kù)扛不住

此時(shí)有小伙伴會(huì)說(shuō)，那我存redis里，存redis里當(dāng)數(shù)據(jù)量大時(shí)，會(huì)占用大量空間，也不是一個(gè)好的方案。

布隆過(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í)，那就肯定不存在。

布隆過(guò)濾器能準(zhǔn)確過(guò)濾掉那些已經(jīng)看過(guò)的內(nèi)容，那些沒(méi)有看過(guò)的新內(nèi)容，它也會(huì)過(guò)濾掉極小一部分（誤判），但是絕大多數(shù)新內(nèi)容它都能準(zhǔn)確識(shí)別。這樣就可以完全保證推薦給用戶的內(nèi)容都是無(wú)重復(fù)的。

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

2.基本使用

bf.add 添加元素，bf.exists 查詢?cè)厥欠翊嬖凇?/p>

布隆過(guò)濾器插件安裝

[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.原理

添加元素時(shí)，先把value轉(zhuǎn)化為字節(jié)（getBytes(value,”UTF-8")），通過(guò)算法對(duì)元素計(jì)算出k（14）個(gè)獨(dú)立的hash值，然后用這k個(gè)獨(dú)立的hash值與位圖長(zhǎng)度（ 201978）進(jìn)行取余，對(duì)應(yīng)位置設(shè)置1。

判斷元素是否存在，對(duì)元素計(jì)算出k個(gè)獨(dú)立的hash值，然后用這k個(gè)獨(dú)立的hash值與位圖長(zhǎng)度（201978）進(jìn)行取余，所有的位置都是1表示存在，只要有一位為0都是不存在。

使用時(shí)不要讓實(shí)際元素遠(yuǎn)大于初始化大小，當(dāng)實(shí)際元素開(kāi)始超出初始化大小時(shí)，應(yīng)該對(duì)布隆過(guò)濾器進(jìn)行重建，重新分配一個(gè) size 更大的過(guò)濾器，再將所有的歷史元素批量 add 進(jìn)去（這就要求我們?cè)谄渌拇鎯?chǔ)器中記錄所有的歷史元素）。 因?yàn)?error_rate 不會(huì)因?yàn)閿?shù)量超出就急劇增加，這就給我們重建過(guò)濾器提供了較為寬松的時(shí)間。

為什么會(huì)存在誤差？

因?yàn)檫@個(gè)位置為1，有可能是其他key設(shè)置的

建議：使用時(shí)不要讓實(shí)際元素遠(yuǎn)大于初始化大小，當(dāng)實(shí)際元素開(kāi)始超出初始化大小時(shí)，應(yīng)該對(duì)布隆過(guò)濾器進(jìn)行重建，重新分配一個(gè) size 更大的過(guò)濾器，再將所有的歷史元素批量 add 進(jìn)去（這就要求我們?cè)谄渌拇鎯?chǔ)器中記錄所有的歷史元素）。因?yàn)?error_rate 不會(huì)因?yàn)閿?shù)量超出就急劇增加，這就給我們重建過(guò)濾器提供了較為寬松的時(shí)間。

注意：位圖長(zhǎng)度越長(zhǎng)錯(cuò)誤率越低，但是需要很大的空間，一般這里都是用預(yù)計(jì)放入元素量，當(dāng)實(shí)際數(shù)量超出這個(gè)值時(shí)，誤判率會(huì)上升

錯(cuò)誤率計(jì)算器：https://krisives.github.io/bloom-calculator/

4.實(shí)戰(zhàn)

還是用最開(kāi)始我們說(shuō)的需求，實(shí)現(xiàn)新聞推送去重，假設(shè)需求需要我們保證100%的正確率，我們?cè)撊绾蝺?yōu)化呢？

我們需要設(shè)計(jì)兩層校驗(yàn)，第一層是布隆過(guò)濾器，第二層是MySQL。

public void exist(String data) {
  // 數(shù)據(jù)是否存在
  boolean existFlag = false;
  // 1.先去布隆過(guò)濾器判斷
  if(bloomFilter.exist(data)) {
    // 2.如果布隆過(guò)濾器存在，需要在MySQL中進(jìn)行二次校驗(yàn)
    if(mysqlService.exist(data)) {
      // 3.數(shù)據(jù)存在
      existFlag = true;
    }
  }
  return existFlag;
}

public void insertRecord() {
  // 1.先插入布隆過(guò)濾器
  // 2.插入到數(shù)據(jù)庫(kù)
}

有些同學(xué)說(shuō)，我的Redis版本低于4.0怎么辦？

我們可以使用redis位圖自己實(shí)現(xiàn)一個(gè)布隆過(guò)濾器

</br>

布隆過(guò)濾器使用場(chǎng)景：

• 黑名單
• 爬蟲(chóng)，爬網(wǎng)頁(yè)前先判斷url是否已經(jīng)爬過(guò)，若爬過(guò)就不再爬取
• 緩存穿透