快捷導(dǎo)航

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

更新時(shí)間：2018年10月18日 11:33:14 作者：JayChen

這篇文章主要介紹了Redis 中的布隆過(guò)濾器的實(shí)現(xiàn)，詳細(xì)的介紹了什么是布隆過(guò)濾器以及如何實(shí)現(xiàn)，非常具有實(shí)用價(jià)值，需要的朋友可以參考下

什么是『布隆過(guò)濾器』

布隆過(guò)濾器是一個(gè)神奇的數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)判斷一個(gè)元素是否在一個(gè)集合中。很常用的一個(gè)功能是用來(lái)去重。在爬蟲(chóng)中常見(jiàn)的一個(gè)需求：目標(biāo)網(wǎng)站 URL 千千萬(wàn)，怎么判斷某個(gè) URL 爬蟲(chóng)是否寵幸過(guò)？簡(jiǎn)單點(diǎn)可以爬蟲(chóng)每采集過(guò)一個(gè) URL，就把這個(gè) URL 存入數(shù)據(jù)庫(kù)中，每次一個(gè)新的 URL 過(guò)來(lái)就到數(shù)據(jù)庫(kù)查詢(xún)下是否訪問(wèn)過(guò)。

select id from table where url = 'https://jaychen.cc'

但是隨著爬蟲(chóng)爬過(guò)的 URL 越來(lái)越多，每次請(qǐng)求前都要訪問(wèn)數(shù)據(jù)庫(kù)一次，并且對(duì)于這種字符串的 SQL 查詢(xún)效率并不高。除了數(shù)據(jù)庫(kù)之外，使用 Redis 的 set 結(jié)構(gòu)也可以滿足這個(gè)需求，并且性能優(yōu)于數(shù)據(jù)庫(kù)。但是 Redis 也存在一個(gè)問(wèn)題：耗費(fèi)過(guò)多的內(nèi)存。這個(gè)時(shí)候布隆過(guò)濾器就很橫的出場(chǎng)了：這個(gè)問(wèn)題讓我來(lái)。

相比于數(shù)據(jù)庫(kù)和 Redis，使用布隆過(guò)濾器可以很好的避免性能和內(nèi)存占用的問(wèn)題。

布隆過(guò)濾器本質(zhì)是一個(gè)位數(shù)組，位數(shù)組就是數(shù)組的每個(gè)元素都只占用 1 bit 。每個(gè)元素只能是 0 或者 1。這樣申請(qǐng)一個(gè) 10000 個(gè)元素的位數(shù)組只占用 10000 / 8 = 1250 B 的空間。布隆過(guò)濾器除了一個(gè)位數(shù)組，還有 K 個(gè)哈希函數(shù)。當(dāng)一個(gè)元素加入布隆過(guò)濾器中的時(shí)候，會(huì)進(jìn)行如下操作：

使用 K 個(gè)哈希函數(shù)對(duì)元素值進(jìn)行 K 次計(jì)算，得到 K 個(gè)哈希值。
根據(jù)得到的哈希值，在位數(shù)組中把對(duì)應(yīng)下標(biāo)的值置為 1。

舉個(gè)🌰，假設(shè)布隆過(guò)濾器有 3 個(gè)哈希函數(shù)：f1, f2, f3 和一個(gè)位數(shù)組 arr?，F(xiàn)在要把 https://jaychen.cc 插入布隆過(guò)濾器中：

對(duì)值進(jìn)行三次哈希計(jì)算，得到三個(gè)值 n1, n2, n3。
把位數(shù)組中三個(gè)元素 arr[n1], arr[n2], arr[3] 置為 1。

當(dāng)要判斷一個(gè)值是否在布隆過(guò)濾器中，對(duì)元素再次進(jìn)行哈希計(jì)算，得到值之后判斷位數(shù)組中的每個(gè)元素是否都為 1，如果值都為 1，那么說(shuō)明這個(gè)值在布隆過(guò)濾器中，如果存在一個(gè)值不為 1，說(shuō)明該元素不在布隆過(guò)濾器中。

看不懂文字看下面的靈魂畫(huà)手的圖解釋👇👇👇

看了上面的說(shuō)明，必然會(huì)提出一個(gè)問(wèn)題：當(dāng)插入的元素原來(lái)越多，位數(shù)組中被置為 1 的位置就越多，當(dāng)一個(gè)不在布隆過(guò)濾器中的元素，經(jīng)過(guò)哈希計(jì)算之后，得到的值在位數(shù)組中查詢(xún)，有可能這些位置也都被置為 1。這樣一個(gè)不存在布隆過(guò)濾器中的也有可能被誤判成在布隆過(guò)濾器中。但是如果布隆過(guò)濾器判斷說(shuō)一個(gè)元素不在布隆過(guò)濾器中，那么這個(gè)值就一定不在布隆過(guò)濾器中。簡(jiǎn)單來(lái)說(shuō)：

布隆過(guò)濾器說(shuō)某個(gè)元素在，可能會(huì)被誤判。
布隆過(guò)濾器說(shuō)某個(gè)元素不在，那么一定不在。

這個(gè)布隆過(guò)濾器的缺陷放到上面爬蟲(chóng)的需求中，可能存在某些沒(méi)有訪問(wèn)過(guò)的 URL 可能會(huì)被誤判為訪問(wèn)過(guò)，但是如果是訪問(wèn)過(guò)的 URL 一定不會(huì)被誤判為沒(méi)訪問(wèn)過(guò)。

Redis 中的布隆過(guò)濾器

redis 在 4.0 的版本中加入了 module 功能，布隆過(guò)濾器可以通過(guò) module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通過(guò)加載 module 來(lái)使用 redis 中的布隆過(guò)濾器。但是這不是最簡(jiǎn)單的方式，使用 docker 可以直接在 redis 中體驗(yàn)布隆過(guò)濾器。

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

redis 布隆過(guò)濾器主要就兩個(gè)命令：

bf.add 添加元素到布隆過(guò)濾器中：bf.add urls https://jaychen.cc。
bf.exists 判斷某個(gè)元素是否在過(guò)濾器中：bf.exists urls https://jaychen.cc。

上面說(shuō)過(guò)布隆過(guò)濾器存在誤判的情況，在 redis 中有兩個(gè)值決定布隆過(guò)濾器的準(zhǔn)確率：

error_rate ：允許布隆過(guò)濾器的錯(cuò)誤率，這個(gè)值越低過(guò)濾器的位數(shù)組的大小越大，占用空間也就越大。
initial_size ：布隆過(guò)濾器可以?xún)?chǔ)存的元素個(gè)數(shù)，當(dāng)實(shí)際存儲(chǔ)的元素個(gè)數(shù)超過(guò)這個(gè)值之后，過(guò)濾器的準(zhǔn)確率會(huì)下降。

redis 中有一個(gè)命令可以來(lái)設(shè)置這兩個(gè)值：