「Redis」布隆過濾器「BloomFilter」

不積跬步，無以至千里；不積小流，無以成江海。

使用場景

本篇還是從一場景入手，比如我們在使用頭條看新聞時，它會給我們不停地推薦新的內容，每次推薦時都會去掉那些已經看過的內容。 有沒有想過 <strong>推送去重 是怎麼實現的？

容易想到的方案：

方案一：

瀏覽記錄存在 <strong>關係型 數據庫裡，去重時對數據庫進行 <strong>exists 查詢，但當系統 <strong>併發 量很高時，數據庫扛的住嗎？

方案二

使用set來實現這個功能。但如果數據量較大，使用set會非常消耗內存，日積月累能撐多久？還有上節提到的 BitMap 來提高性能。但 BitMap 仍然比較消耗內存，尤其是在數據比較稀疏的情況下，使用BitMap並不划算。

有了上節基礎，更易於理解本節。

實際上，對於“<strong>去重”問題，業界有另外一個更優秀的數據結構來解決這類問題，那就是—— <strong>布隆過濾器(BloomFilter)。它在起到去重的同時，還能節省 90% 以上的空間，只是稍微有那麼點不精確，也就是有一定的 <strong>誤判概率。

對於上面這種情況 某篇新聞 看過與否 真的那麼重要嗎

Bloom Filter 是什麼

布隆過濾器是Burton Howard Bloom在1970年提出來的，一種空間效率極高的 <strong>概率型算法 和 <strong>數據結構，主要用來判斷一個元素 <strong>是否在集合中存在。

因為他是一個概率型的算法，所以會存在 <strong>一定的誤差，當布隆過濾器說某個值存在時，這個值 <strong>可能 不存在；當它說不存在時，那就 <strong>肯定 不存在。

因此，Bloom Filter不適合那些“<strong>零錯誤”的應用場合。而在能容忍 <strong>低錯誤率 的應用場合下，Bloom Filter通過極少的錯誤換取了存儲空間的極大節省。

但是布隆過濾器也不是特別不精確，只要參數設置的合理，它的精確度可以控制的相對足夠精確，只會有小小的誤判概率。

布隆過濾器原理

布隆過濾器與 BitMap 類似，底層也是一個 <strong>位數組。1表示有，0表示無。但布隆過濾器比BitMap需要更少的內存，它是怎麼辦到的呢？答案是 <strong>多個hash。

每個布隆過濾器對應到 Redis 的數據結構裡面就是一個大型的 <strong>位數組 和幾個不一樣的無偏 <strong>hash 函數。所謂無偏就是能夠把元素的 hash 值算得比較均勻。

我們知道hash算法，是把一個數從較大範圍的值，映射到較小範圍值。比如我們有一個10位的數組，使用某個hash算法 對應 其數組上的表示：

hash('a') = 3

hash('b') = 5

0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0

這樣，我們使用這個hash算法就能快速的判斷一個字符串是不是存在一個集合裡面了。但眾所周知，hash算法是有可能發生 <strong>hash碰撞。比如可能有兩個不同的字符串映射到同一個數：

hash(“a”) = 3;

hash(“aof”) = 3;

這種情況下，就不能準確得判斷出某個字符串是不是存在於集合之中。

對於這種情況的處理方案是使用 多個 不同的 hash算法。比如：

h1(“a”) = 3, h2(“a”) = 5, h3(“a”) = 7;

h1(“aof”) = 5, h2(“aof”) = 6, h3(“aof”) = 7;

向布隆過濾器中 添加 key 時，會使用 <strong>多個 hash 函數對 key 進行 hash 算得一個整數 <strong>索引值,再把位數組的這幾個位置都置為 1 就完成了 add 操作。

向布隆過濾器 查找 key 是否存在時，跟 add 一樣，也會把 hash 的幾個位置都算出來，看看位數組中這幾個位置是否都為 1，只要有一個位為 0，那麼說明布隆過濾器中這個 key 不存在。

如果<strong>都是 1，這並不能說明這個 key 就一定存在，只是<strong>極有可能存在，因為這些位被置為 1 可能是因為其它的 key 存在所致。所以布隆過濾器 <strong>不能刪除，因為一旦刪除（即將相應的位置為0），就很大可能會影響其他元素。

如果這個位數組比較稀疏，判斷正確的概率就會很大，如果這個位數組比較擁擠，判斷正確的概率就會降低。

Redis 布隆過濾器

Redis的布隆過濾器不是原生自帶的，而是要通過module加載進去。Redis在<strong>4.0版本

Redis 布隆過濾器有二個基本指令：

<strong>bf.add 添加元素 <strong>bf.exists 查詢元素是否存在

它的用法和 set 集合的 sadd 和 sismember 差不多bf.add 只能一次添加一個元素，如果想要一次添加多個，就需要用到 <strong>bf.madd 指令。同樣如果需要一次查詢多個元素是否存在，就需要用到 <strong>bf.mexists 指令。

上面使用的布隆過濾器只是默認參數的布隆過濾器，它在我們第一次add的時候自動創建。Redis還提供了自定義參數的布隆過濾器，需要在add之前使用 <strong>bf.reserve 指令顯式創建。如果對應的key已經存在，bf.reserve會報錯(error) ERR item exists

bf.reserve 過濾器名 error_rate initial_size

bf.reserve strs 0.01 100

參數含義

• 第一個值是過濾器的名字。
• 第二個值為 error_rate 的值：允許布隆過濾器的錯誤率，這個值越低過濾器的位數組的大小越大，佔用空間也就越大。
• 第三個值為 initial_size 的值：布隆過濾器可以儲存的元素個數，當實際存儲的元素個數超過這個值之後，過濾器的準確率會下降。

布隆過濾器的 initial_size 估計的 <strong>過大，會<strong>浪費存儲空間

布隆過濾器的 error_rate 越小，需要的存儲空間就越大，對於不需要過於精確的場合，error_rate設置稍大一點也無傷大雅。

使用時不要讓實際元素遠大於初始化大小，當實際元素開始超出初始化大小時，應該對布隆過濾器進行 重建，重新分配一個 size 更大的過濾器，再將所有的歷史元素批量 add 進去 (這就要求我們在其它的存儲器中記錄所有的歷史元素)。因為 error_rate 不會因為數量超出就急劇增加，這就給我們重建過濾器提供了較為寬鬆的時間。

空間佔用

布隆過濾器的空間佔用 有一個計算公式，這裡略過，這裡直接用網上專門的計算器

「 https://krisives.github.io/bloom-calculator/ 」

第一個是預計元素的數量

第二個是錯誤率

公式根據這兩個輸入得到兩個輸出

第一個輸出是 hash 函數的最佳數量

第二個輸出是位數組的長度，也就是需要的存儲空間大小 (bit)

其他適用場景

在爬蟲系統中，我們需要對 URL 進行去重，已經爬過的網頁就可以不用爬了

QQ 郵箱的垃圾郵件判別

經典的緩存穿透問題

點關注 不迷路

以上就是這篇的全部內容，能看到這裡的都是 人才。

如果你從本篇內容有收穫，求 點贊，求 關注

如果本文有任何錯誤，請批評指教，不勝感激 ！

閱讀更多 不住隔壁的王老師 的文章

關鍵字: 算法 數據結構 布隆