布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。

本文將介紹布隆過濾器的原理以及Redis如何實現布隆過濾器。

應用場景

1、50億個電話號碼，現有10萬個電話號碼，如何判斷這10萬個是否已經存在在50億個之中？（可能方案：數據庫，set, hyperloglog）
2、新聞客戶端看新聞時，它會不斷推薦新的內容，每次推薦時都要去重，那么如何實現推送去重？
3、爬蟲URL去重？
4、NoSQL數據庫領域降低數據庫的IO請求數量？
5、郵箱系統的垃圾郵件過濾？

布隆過濾器（Bloom Filter）就是專門來解決這種問題的，它起到去重的同時，在空間上還能節省90%以上，只是存在一定的誤判概率。

認識布隆過濾器

布隆過濾器是一種類似set的數據結構，只是不太準確，當用bf.exists判斷元素是否存在時返回結果存在但真實不一定存在；當返回不存在時肯定是不存在，所以判斷去重時有一定的誤判概率。
當然，誤判只會發生在過濾器沒有添加過的元素，對于添加過的元素不會發生誤判。
特點：高效地插入和查詢，占用空間少，返回的結果是不確定性的。

布隆過濾器原理

每個布隆過濾器對應到Redis的數據結構中就是一個大型的位數組和幾個不同的無偏hash函數，無偏表示分布均勻。

添加key時，使用多個hash函數對key進行hash運算得到一個整數索引值，對位數組長度進行取模運算得到一個位置，每個hash函數都會得到一個不同的位置，將這幾個位置都置1就完成了add操作。

查詢同理，只要有一位是0就表示這個key不存在，但如果都是1，則不一定存在對應的key。

空間占用估計

布隆過濾器的空間占用有一個簡單的計算公式，但推導比較繁瑣。布隆過濾器有兩個參數，預計元素數量n，錯誤率f，公式得到兩個輸出，位數組長度L（即存儲空間大小bit），hash函數的最佳數量k。

k = 0.7*(1/n)
f = 0.6185^(L/n)

1、位數組相對長度越長，錯誤率越低；
2、位數組相對長度越長，需要的hash函數越多；
3、當一個元素平均需要一個字節（8bit）的指紋空間時（L/n=8)，錯誤率大約為2%。

實際元素超出時，誤判率會怎樣變化？

f = (1-0.5^t)^k  # t為實際元素與預計元素的倍數
1、當錯誤率為10%時，倍數比為2時，錯誤率接近40%；
2、當錯誤率為1%，倍數比為2時，錯誤率15%；
3、當錯誤率為0.1%，倍數為2時，錯誤率5%

Redis實現簡單Bloom Filter

要想使用redis提供的布隆過濾器，必須添加redis 4.0版本以上的插件才行，具體參照網上安裝步驟。

布隆過濾器有兩個基本指令，bf.add添加元素，bf.exists查詢元素是否存在，bf.madd一次添加多個元素，bf.mexists一次查詢多個元素。

> bf.add spiderurl www.baidu.com
> bf.exists spiderurl www.baidu.com
> bf.madd spiderurl www.sougou.com www.jd.com
> bf.mexists spiderurl www.jd.com www.taobao.com

布隆過濾器在第一次add的時候自動創建基于默認參數的過濾器，Redis還提供了自定義參數的布隆過濾器。

在add之前使用bf.reserve指令顯式創建，其有3個參數，key，error_rate， initial_size，錯誤率越低，需要的空間越大，error_rate表示預計錯誤率，initial_size參數表示預計放入的元素數量，當實際數量超過這個值時，誤判率會上升，所以需要提前設置一個較大的數值來避免超出。

默認的error_rate是0.01，initial_size是100。

利用布隆過濾器減少磁盤 IO 或者網絡請求，因為一旦一個值必定不存在的話，我們可以不用進行后續昂貴的查詢請求。

總結

以上所述是小編給大家介紹的Redis實現布隆過濾器的方法及原理，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復大家的！