redis bloom

什么是『布隆過(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ù)查詢下是否訪問(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 查詢效率并不高。除了數(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à)手的圖解釋??????


image.png

看了上面的說(shuō)明，必然會(huì)提出一個(gè)問(wèn)題：當(dāng)插入的元素原來(lái)越多，位數(shù)組中被置為 1 的位置就越多，當(dāng)一個(gè)不在布隆過(guò)濾器中的元素，經(jīng)過(guò)哈希計(jì)算之后，得到的值在位數(shù)組中查詢，有可能這些位置也都被置為 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ò)濾器主要命令：

  • BF.RESERVE <key> <error_rate> <capacity> 創(chuàng)建一個(gè)大小為capacity，錯(cuò)誤率為error_rate的空的TairBloom。
  • BF.ADD <key> <item> 在key指定的TairBloom中添加一個(gè)元素item。bf.add urls test1url。
  • BF.MADD <key> <item> [item...] 在key指定的TairBloom中一次性添加多個(gè)元素。
  • BF.EXISTS <key> <item> 檢查一個(gè)元素是否存在于key指定的TairBloom中。bf.exists urls test1url。
  • BF.MEXISTS <key> <item> [item...] 同時(shí)檢查多個(gè)元素是否存在于key指定的TairBloom中。
  • BF.DEBUG <key> 可以查看key指定的TairBloom內(nèi)部信息，如當(dāng)前層數(shù)和每一層的元素個(gè)數(shù)、錯(cuò)誤率等。
  • DEL <key> [key ...] 使用原生Redis的DEL命令可以刪除一條或多條TairBloom數(shù)據(jù)。
  • BF.INSERT <key> [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS <item...> 在key指定的TairBloom中一次性添加多個(gè)元素，添加時(shí)可以指定大小和錯(cuò)誤率，且可以控制在TairBloom不存在的時(shí)候是否自動(dòng)創(chuàng)建。

注意：

已加入TairBloom數(shù)據(jù)中的元素?zé)o法單獨(dú)刪除，您可以使用DEL命令刪除整條TairBloom數(shù)據(jù)。

BF.RESERVE

  • 語(yǔ)法
    BF.RESERVE <key> <error_rate> <capacity>

  • 時(shí)間復(fù)雜度：O(1)

  • 命令描述：創(chuàng)建一個(gè)大小為capacity，錯(cuò)誤率為error_rate的空的TairBloom。

  • 參數(shù)及選項(xiàng)說(shuō)明

    1. key : TairBloom的key，用于指定作為命令調(diào)用對(duì)象的TairBloom。
    2. error_rate : 期望的錯(cuò)誤率（False Positive Rate），該值必須介于0和1之間。該值越小，TairBloom的內(nèi)存占用量越大，CPU使用率越高。
    3. capacity : TairBloom的初始容量，即期望添加到TairBloom中的元素的個(gè)數(shù)。
      當(dāng)實(shí)際添加的元素個(gè)數(shù)超過(guò)該值時(shí)，TairBloom將進(jìn)行自動(dòng)的擴(kuò)容，該過(guò)程會(huì)導(dǎo)致性能有所下降，下降的程度是隨著元素個(gè)數(shù)的指數(shù)級(jí)增長(zhǎng)而線性下降的，這是因?yàn)門(mén)airBloom的擴(kuò)容是通過(guò)增加Bloom Filter的層數(shù)來(lái)完成的。每增加一層，在查詢的時(shí)候就可能會(huì)遍歷多層Bloom Filter來(lái)完成，每一層的容量都是上一層的兩倍。因此，如果對(duì)性能非常的敏感，需要在使用前充分評(píng)估要添加到TairBloom的元素個(gè)數(shù)，避免發(fā)生擴(kuò)容操作。

  • 返回值
    成功：OK。
    其它情況返回相應(yīng)的異常信息。

  • 注意
    使用這個(gè)命令要注意一點(diǎn)：執(zhí)行這個(gè)命令之前過(guò)濾器的名字應(yīng)該不存在，如果執(zhí)行之前就存在會(huì)報(bào)錯(cuò)：

BF.ADD

  • 語(yǔ)法： BF.ADD <key> <item>

  • 時(shí)間復(fù)雜度： O(log N) ，其中N是TairBloom的層數(shù)。

  • 命令描述： 在key指定的TairBloom中添加一個(gè)元素。

  • 參數(shù)及選項(xiàng)說(shuō)明

    1. key TairBloom的key，用于指定作為命令調(diào)用對(duì)象的TairBloom。
    2. item 需要添加到TairBloom的元素。

  • 返回值
    元素一定不存在：1。
    元素可能已經(jīng)存在：0。
    其它情況返回相應(yīng)的異常信息。

BF.MADD

  • 語(yǔ)法：BF.MADD <key> <item> [item...]

  • 時(shí)間復(fù)雜度： O(log N) ，其中N是TairBloom的層數(shù)。

  • 命令描述： 在key指定的TairBloom中添加多個(gè)元素。

  • 參數(shù)及選項(xiàng)說(shuō)明

    1. key TairBloom的key，用于指定作為命令調(diào)用對(duì)象的TairBloom。
    2. item 需要添加到TairBloom的元素，可設(shè)置多個(gè)。

  • 返回值
    成功：返回一個(gè)數(shù)組，數(shù)組的每一個(gè)元素可能為1或0，當(dāng)item一定不存在時(shí)數(shù)組元素值為1，當(dāng)item可能已經(jīng)存在時(shí)數(shù)組元素值為0。
    其它情況返回相應(yīng)的異常信息。

BF.EXISTS

  • 語(yǔ)法： BF.EXISTS <key> <item>

  • 時(shí)間復(fù)雜度：O(log N) ，其中N是TairBloom的層數(shù)。

  • 命令描述：檢查一個(gè)元素是否存在于key指定的TairBloom中。

  • 參數(shù)及選項(xiàng)說(shuō)明

    1. key TairBloom的key，用于指定作為命令調(diào)用對(duì)象的TairBloom。
    2. item 需要查詢的元素。

  • 返回值
    元素一定不存在：0。
    元素可能存在：1。
    其它情況返回相應(yīng)的異常信息。

BF.MEXISTS

  • 語(yǔ)法：BF.MEXISTS <key> <item> [item...]

  • 時(shí)間復(fù)雜度：O(log N) ，其中N是TairBloom的層數(shù)。

  • 命令描述：同時(shí)檢查多個(gè)元素是否存在于key指定的TairBloom中。

  • 參數(shù)及選項(xiàng)說(shuō)明

    1. key TairBloom的key，用于指定作為命令調(diào)用對(duì)象的TairBloom。
    2. item 需要查詢的元素，可設(shè)置多個(gè)。

  • 返回值
    成功：返回一個(gè)數(shù)組，數(shù)組的每一個(gè)元素可能為1或0，當(dāng)item一定不存在時(shí)數(shù)組元素值為0，當(dāng)item可能已經(jīng)存在時(shí)數(shù)組元素值為1。
    其它情況返回相應(yīng)的異常信息。

BF.INSERT

  • 語(yǔ)法：BF.INSERT <key> [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS <item...>

  • 時(shí)間復(fù)雜度：O(log N) ，其中N是TairBloom的層數(shù)。

  • 命令描述：在key指定的TairBloom中一次性添加多個(gè)元素，添加時(shí)可以指定大小和錯(cuò)誤率，且可以控制在TairBloom不存在的時(shí)候是否自動(dòng)創(chuàng)建。

  • 參數(shù)及選項(xiàng)說(shuō)明

    1. key TairBloom的key，用于指定作為命令調(diào)用對(duì)象的TairBloom。

    2. CAPACITY 指定TairBloom的容量，即期望添加到TairBloom中的元素的個(gè)數(shù)，當(dāng)TairBloom已經(jīng)存在時(shí)該值將被忽略。

    3. 當(dāng)實(shí)際添加的元素個(gè)數(shù)超過(guò)該值時(shí)，TairBloom將進(jìn)行自動(dòng)的擴(kuò)容，該過(guò)程會(huì)導(dǎo)致性能有所下降，下降的程度是隨著元素個(gè)數(shù)的指數(shù)級(jí)增長(zhǎng)而線性下降的，這是因?yàn)門(mén)airBloom的擴(kuò)容是通過(guò)增加Bloom Filter的層數(shù)來(lái)完成的。每增加一層，在查詢的時(shí)候就可能會(huì)遍歷多層Bloom Filter來(lái)完成，每一層的容量都是上一層的兩倍。因此，如果對(duì)性能非常的敏感，需要在使用前充分評(píng)估要添加到TairBloom的元素個(gè)數(shù)，避免發(fā)生擴(kuò)容操作。

    4. ERROR 期望的錯(cuò)誤率（False Positive Rate），當(dāng)TairBloom已經(jīng)存在時(shí)該值將被忽略。該值必須介于0和1之間。該值越小，TairBloom的內(nèi)存占用量越大，CPU使用率越高。
      NOCREATE 設(shè)置該選項(xiàng)后，當(dāng)指定的TairBloom不存在的時(shí)候不要自動(dòng)創(chuàng)建該TairBloom。該參數(shù)不能與CAPACITY和ERROR同時(shí)設(shè)置。

    5. ITEMS 需要添加到TairBloom中的所有元素。

  • 返回值：
    成功：返回一個(gè)數(shù)組，數(shù)組的每一個(gè)元素可能為1或0，當(dāng)item一定不存在時(shí)數(shù)組元素為1，當(dāng)item可能已經(jīng)存在時(shí)數(shù)組元素值為0。
    其它情況返回相應(yīng)的異常信息。

BF.DEBUG

  • 語(yǔ)法：BF.DEBUG <key>

  • 時(shí)間復(fù)雜度：O(log N) ，其中N是TairBloom的層數(shù)。

  • 命令描述：可以查看key指定的TairBloom內(nèi)部信息，如當(dāng)前層數(shù)和每一層的元素個(gè)數(shù)、錯(cuò)誤率等。

  • 參數(shù)及選項(xiàng)說(shuō)明

    1. key TairBloom的key，用于指定作為命令調(diào)用對(duì)象的TairBloom。

  • 返回值
    成功：返回一個(gè)數(shù)組，數(shù)組的每一個(gè)元素可能為1或0，當(dāng)item一定不存在時(shí)數(shù)組元素為1，當(dāng)item可能已經(jīng)存在時(shí)數(shù)組元素值為0。
    其它情況返回相應(yīng)的異常信息。

內(nèi)存占用測(cè)試結(jié)果

image.png

版本要求:

  • redis 在 4.0 以及以上版本
轉(zhuǎn)載地址 : https://help.aliyun.com/document_detail/145972.html?spm=5176.11065259.1996646101.searchclickresult.4f0e72c25d0D88#section-9lv-mn2-z93
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容