什么是『布隆過濾器』

布隆過濾器是一個神奇的數(shù)據(jù)結構，可以用來判斷一個元素是否在一個集合中。很常用的一個功能是用來去重。在爬蟲中常見的一個需求：目標網(wǎng)站 URL 千千萬，怎么判斷某個 URL 爬蟲是否寵幸過？簡單點可以爬蟲每采集過一個 URL，就把這個 URL 存入數(shù)據(jù)庫中，每次一個新的 URL 過來就到數(shù)據(jù)庫查詢下是否訪問過。

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

但是隨著爬蟲爬過的 URL 越來越多，每次請求前都要訪問數(shù)據(jù)庫一次，并且對于這種字符串的 SQL 查詢效率并不高。除了數(shù)據(jù)庫之外，使用 Redis 的 set 結構也可以滿足這個需求，并且性能優(yōu)于數(shù)據(jù)庫。但是 Redis 也存在一個問題：耗費過多的內存。這個時候布隆過濾器就很橫的出場了：這個問題讓我來。

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

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

• 使用 K 個哈希函數(shù)對元素值進行 K 次計算，得到 K 個哈希值。
• 根據(jù)得到的哈希值，在位數(shù)組中把對應下標的值置為 1。

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

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

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

看不懂文字看下面的靈魂畫手的圖解釋??????

image.png

看了上面的說明，必然會提出一個問題：當插入的元素原來越多，位數(shù)組中被置為 1 的位置就越多，當一個不在布隆過濾器中的元素，經過哈希計算之后，得到的值在位數(shù)組中查詢，有可能這些位置也都被置為 1。這樣一個不存在布隆過濾器中的也有可能被誤判成在布隆過濾器中。但是如果布隆過濾器判斷說一個元素不在布隆過濾器中，那么這個值就一定不在布隆過濾器中。簡單來說：

• 布隆過濾器說某個元素在，可能會被誤判。
• 布隆過濾器說某個元素不在，那么一定不在。

這個布隆過濾器的缺陷放到上面爬蟲的需求中，可能存在某些沒有訪問過的 URL 可能會被誤判為訪問過，但是如果是訪問過的 URL 一定不會被誤判為沒訪問過。

Redis 中的布隆過濾器

redis 在 4.0 的版本中加入了 module 功能，布隆過濾器可以通過 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通過加載 module 來使用 redis 中的布隆過濾器。但是這不是最簡單的方式，使用 docker 可以直接在 redis 中體驗布隆過濾器。

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

redis 布隆過濾器主要命令：

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

注意：

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

BF.RESERVE

• 語法
  BF.RESERVE <key> <error_rate> <capacity>

• 時間復雜度：O(1)

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

• 參數(shù)及選項說明

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

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

• 注意
  使用這個命令要注意一點：執(zhí)行這個命令之前過濾器的名字應該不存在，如果執(zhí)行之前就存在會報錯：

BF.ADD

• 語法： BF.ADD <key> <item>

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

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

• 參數(shù)及選項說明

  1. key TairBloom的key，用于指定作為命令調用對象的TairBloom。
  2. item 需要添加到TairBloom的元素。

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

BF.MADD

• 語法：BF.MADD <key> <item> [item...]

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

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

• 參數(shù)及選項說明

  1. key TairBloom的key，用于指定作為命令調用對象的TairBloom。
  2. item 需要添加到TairBloom的元素，可設置多個。

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

BF.EXISTS

• 語法： BF.EXISTS <key> <item>

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

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

• 參數(shù)及選項說明

  1. key TairBloom的key，用于指定作為命令調用對象的TairBloom。
  2. item 需要查詢的元素。

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

BF.MEXISTS

• 語法：BF.MEXISTS <key> <item> [item...]

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

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

• 參數(shù)及選項說明

  1. key TairBloom的key，用于指定作為命令調用對象的TairBloom。
  2. item 需要查詢的元素，可設置多個。

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

BF.INSERT

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

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

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

• 參數(shù)及選項說明

  1. key TairBloom的key，用于指定作為命令調用對象的TairBloom。

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

  3. 當實際添加的元素個數(shù)超過該值時，TairBloom將進行自動的擴容，該過程會導致性能有所下降，下降的程度是隨著元素個數(shù)的指數(shù)級增長而線性下降的，這是因為TairBloom的擴容是通過增加Bloom Filter的層數(shù)來完成的。每增加一層，在查詢的時候就可能會遍歷多層Bloom Filter來完成，每一層的容量都是上一層的兩倍。因此，如果對性能非常的敏感，需要在使用前充分評估要添加到TairBloom的元素個數(shù)，避免發(fā)生擴容操作。

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

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

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

BF.DEBUG

• 語法：BF.DEBUG <key>

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

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

• 參數(shù)及選項說明

  1. key TairBloom的key，用于指定作為命令調用對象的TairBloom。

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

內存占用測試結果

image.png

版本要求:

• redis 在 4.0 以及以上版本

轉載地址 : https://help.aliyun.com/document_detail/145972.html?spm=5176.11065259.1996646101.searchclickresult.4f0e72c25d0D88#section-9lv-mn2-z93