刷抖音的時(shí)候是否曾想過(guò)，我們刷過(guò)的視頻很難在重復(fù)刷到那么它到底是如何實(shí)現(xiàn)的呢？

如果說(shuō)我們每刷一個(gè)視頻并且把視頻id和用戶的id組合成一條數(shù)據(jù)保存到數(shù)據(jù)庫(kù)中每次推薦視頻的時(shí)候都去數(shù)據(jù)檢測(cè)是否已經(jīng)刷過(guò)了，嗯，這樣可以實(shí)現(xiàn)這個(gè)功能，但是存在多個(gè)問(wèn)題，頻繁操作數(shù)據(jù)表對(duì)數(shù)據(jù)庫(kù)造成很大的負(fù)擔(dān)，每次推薦視頻時(shí)都得保存數(shù)據(jù)，人流量一多，數(shù)據(jù)庫(kù)很快就扛不住。

那么我們可否使用緩存redis中的set來(lái)實(shí)現(xiàn)呢？當(dāng)然是可以的，redis4.0版本給我們提供了更加快捷更加節(jié)省空間的數(shù)據(jù)結(jié)構(gòu)--布隆過(guò)濾器（Bloom Filter）

布隆過(guò)濾器的簡(jiǎn)介

布隆過(guò)濾器（BloomFilter）是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)，我們也可以簡(jiǎn)單的理解為它是一個(gè)不怎么精確的set結(jié)構(gòu)。本質(zhì)上布隆過(guò)濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點(diǎn)是高效地插入和查詢，可以用來(lái)告訴你 “某樣?xùn)|西一定不存在或者可能存在”。相比于傳統(tǒng)的List、Set、Map等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點(diǎn)是其返回的結(jié)果是概率性的，但是我們不必過(guò)于擔(dān)心它不夠精確，只要參數(shù)設(shè)置合理，它的精度可以控制到足夠的精確。

適用場(chǎng)景：

• 大數(shù)據(jù)是否存在的問(wèn)題，比如上述的刷抖音去重問(wèn)題

• 解決緩存擊穿問(wèn)題，如果數(shù)據(jù)請(qǐng)求一直是一個(gè)不存在的內(nèi)容，那么它會(huì)越過(guò)緩存直接請(qǐng)求數(shù)據(jù)庫(kù)，造成緩存擊穿，布隆過(guò)濾器也可以解決此類問(wèn)題

• 解決爬蟲(chóng)爬到重復(fù)url內(nèi)容等等

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

布隆過(guò)濾器有二個(gè)基本指令，bf.add添加元素，bf.exists查詢?cè)厥欠翊嬖?#xff0c;它的用法和set集合的sadd和sismember差不多。注意bf.add只能一次添加一個(gè)元素，如果想要一次添加多個(gè)，就需要用到bf.madd指令。同樣如果需要一次查詢多個(gè)元素是否存在，就需要用到bf.mexists指令。

> bf.add user user1(integer) 1> bf.add user user2(integer) 1> bf.add user user3(integer) 1> bf.exists user user1(integer)?1>?bf.exists?user user4(integer) 0> bf.madd user user4 user5 user61) (integer) 12) (integer) 13) (integer) 1> bf.mexists user user4 user5 user6 user71) (integer) 12) (integer) 13) (integer) 14) (integer) 0

上面使用的布隆過(guò)過(guò)濾器只是默認(rèn)參數(shù)的布隆過(guò)濾器，它在我們第一次add的時(shí)候自動(dòng)創(chuàng)建。Redis也提供了可以自定義參數(shù)的布隆過(guò)濾器，只需要在add之前使用bf.reserve指令顯式創(chuàng)建就好了。如果對(duì)應(yīng)的key已經(jīng)存在，bf.reserve會(huì)報(bào)錯(cuò)。bf.reserve有三個(gè)參數(shù)，分別是key、error_rate(錯(cuò)誤率)和initial_size：
error_rate越低，需要的空間越大
initial_size表示預(yù)計(jì)放入的元素?cái)?shù)量，當(dāng)實(shí)際數(shù)量超過(guò)這個(gè)值時(shí)，誤判率就會(huì)提升，所以需要提前設(shè)置一個(gè)較大的數(shù)值避免超出導(dǎo)致誤判率升高；
如果不適用bf.reserve，默認(rèn)的error_rate是0.01，默認(rèn)的initial_size是100。

布隆過(guò)濾器的實(shí)現(xiàn)原理

add操作

每個(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操作。

exists操作

exists操作跟add一樣，也會(huì)把hash的幾個(gè)位置都算出來(lái)，看看位數(shù)組中這幾個(gè)位置是否都是1，只要有一個(gè)位為0，那么說(shuō)明布隆過(guò)濾器中這個(gè)key不存在。如果都是1，這并不能說(shuō)明這個(gè)key就一定存在，只是極有可能存在，因?yàn)檫@些位被置為1可能是因?yàn)槠渌膋ey存在所致。

如果這個(gè)位數(shù)組比較稀疏，這個(gè)概率就會(huì)很大，如果這個(gè)位數(shù)組比較擁擠，這個(gè)概率就會(huì)降低。使用時(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)閑rror_rate不會(huì)因?yàn)閿?shù)量超出就急劇增加，這就給我們重建過(guò)濾器提供了較為寬松的時(shí)間。

空間占用估算

計(jì)算公式：k=0.7*(l/n)??????????#約等于f=0.6185^(l/n) #^表示次方計(jì)算，也就是 math.pow

布隆過(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ò)誤率。

從公式中可以看出

• 1.位數(shù)組相對(duì)越長(zhǎng)(l/n)，錯(cuò)誤率f越低，這個(gè)和直觀上理解是一致的

• 位數(shù)組相對(duì)越長(zhǎng)(l/n)，hash函數(shù)需要的最佳數(shù)量也越多，影響計(jì)算效率

• 當(dāng)一個(gè)元素平均需要1個(gè)字節(jié)(8bit)的指紋空間時(shí)(l/n=8)，錯(cuò)誤率大約為 2%

錯(cuò)誤率	一個(gè)元素所需平均空間	空間數(shù)
10%	4.792個(gè)bit	5bit
1%	9.585個(gè)bit	10bit
0.1%	14.377個(gè)bit	15bit

有人會(huì)問(wèn)如果實(shí)際的元素超過(guò)了預(yù)算元素，錯(cuò)誤率會(huì)如何變化，會(huì)不會(huì)錯(cuò)誤率非常高？我們引入一個(gè)公式

f=(1-0.5^t)^k#極限近似，?k?是?hash?函數(shù)的最佳數(shù)量#t表示實(shí)際元素和預(yù)計(jì)元素的倍數(shù)

錯(cuò)誤率為 10% 時(shí)，倍數(shù)比為 2 時(shí)，錯(cuò)誤率就會(huì)升至接近 40%
錯(cuò)誤率為 1% 時(shí)，倍數(shù)比為 2 時(shí)，錯(cuò)誤率升至 15%
錯(cuò)誤率為 0.1%，倍數(shù)比為 2 時(shí)，錯(cuò)誤率升至 5%

?

?

?

一名正在搶救的coder

筆名：mangolove

CSDN地址：https://blog.csdn.net/mango_love

GitHub地址：https://github.com/mangoloveYu

?

總結(jié)

以上是生活随笔為你收集整理的Redis如何实现刷抖音不重复-布隆过滤器（Bloom Filter）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。