Redis 超級實用技巧：布隆過濾器

那麼，什麼是布隆過濾器？它有什麼特點？Redis 是怎麼支持布隆過濾器的？本文就試圖來回答這些問題，歡迎點贊、分享，謝謝！

一

什麼是布隆過濾器

布隆過濾器是一種概率型的數據結構（Probabilistic Data Structure），它佔用空間少，運行效率高，但返回的結果是概率性而不是確切性的，它可以回答：某個元素在集合中肯定不存在，或者有可能存在。

粗看起來好像有點奇怪，什麼叫有可能存在？存在就是存在，不存在就是不存在，“可能存在”，那有什麼用啊？計算機可是一門嚴謹的科學啊。

然而，在某些特定的場景下，布隆過濾器的這種特性還是非常有用的，別忘了，它還有個功能：它可以判定某個元素在集合中肯定不存在。比如：判斷一個用戶名是否已經註冊；用戶是否已經看過某條新聞或者廣告；緩存中是否存在某個 key 等等。

二

實現原理

布隆過濾器的實現原理其實非常簡單：

  1. 初始化一個固定大小的位數組，所有的數據都被置爲 0；

  2. 數據加入到集合中的時候，經過幾個 hash 函數的計算，得到相應的整數結果，然後對位數組的長度取餘，把取餘結果所對應位置的數據置爲 1；

  3. 查詢數據時，經過同樣的 hash 函數計算，如果結果中有一個爲 0，則表明肯定不存在這個數據，如果全部爲 1 則表明有可能存在這個數據。

由於 hash 函數會存在碰撞的問題，所以布隆過濾器就會有誤判的情況：判斷一個數據已經存在，但它實際不存在。（歡迎留言討論，什麼情況下會存在誤判的情況）。

我們來舉例說明，創建一個長度爲 8 的位數組：

現在添加元素 Tom，經過兩個 hash 函數計算，並把結果對數組長度 8 做取餘運算，假定得到結果 1，5，那麼布隆過濾器就把這兩個位置上的數據都置爲 1：

再添加元素 John，經過同樣的運算，結果爲 3 和 5，同樣把這兩個位置上的數據置爲 1：

可以看到，元素 Tom 和 John 都把位置 5 上的數據置爲 1，這就是哈希碰撞的問題，這也是需要多個哈希函數的原因，減少誤判。添加這兩個元素以後的情況如下：

接下來我們查詢 Eric 是不是在集合中，假定它的運算結果爲 1 和 2，因爲這兩個位置上的數據並不是全部都爲 1，所以它肯定不在集合中。但 Jack 的結果如果爲 1 和 3，這兩個位置的數據都爲 1，布隆過濾器會認爲它可能已經存在（但事實上從來沒有添加過 Jack），誤判了。

三

Redis 的支持

之前的文章提到過，Redisson 是 Redis 的 Java 客戶端，它提供了豐富的分佈式功能，包括分佈式對象、集合、分佈式鎖、分佈式服務等，同時也支持布隆過濾器，實現起來也很簡單，示例代碼如下：

// 構建一個布隆過濾器，並且指定過濾器的名稱
RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("userList");
// 初始化布隆過濾器：預計元素爲1000000L（一百萬個）,誤差率爲1%
bloomFilter.tryInit(1000000L, 0.01);
bloomFilter.add("1234567");
// 輸出true，已存在該元素
System.out.println(bloomFilter.contains("1234567"));
// false，不存在該元素
System.out.println(bloomFilter.contains("12345"));

把數據插入到集合之前（比如 MySQL 數據庫中），先把數據添加到布隆過濾器中，下次再添加數據的時候，先判斷布隆過濾器是否不存在，如果沒有該元素，則進行後續的操作，比如添加用戶、去緩存請求數據等。

四

緩存穿透

緩存穿透是指數據既不在緩存中，也不在數據庫中，如果有很多請求要獲取這些不存在的數據（比如惡意請求），就會造成數據庫的壓力陡增，如何來解決這樣的問題呢？其中比較有效的一個辦法就是使用布隆過濾器。    

從上面的圖中可以看出，使用布隆過濾器來解決緩存穿透的問題，主要是通過以下幾個步驟來完成的：

  1. 創建一個布隆過濾器，用戶新創建的數據在入庫之後，同時添加到布隆過濾器中；

  2. 用戶查詢數據時，首先去布隆過濾器裏面找，如果不存在則直接返回；

  3. 如果查詢的數據在布隆過濾器中存在，則去緩存中查詢，這個跟正常的緩存流程是一樣的。

五

總結

布隆過濾器是一種概率性的數據結構，換句話說，它不精確，表面上看可能用處不大，但在某些特定的場景中它能夠大放異彩，比如緩存穿透等。

本文介紹了布隆過濾器的背後原理，以後 Redis 對於布隆過濾器的支持，並給出了相應的 Java 示例代碼，希望對大家有所幫助。

創作不易，煩請點個在看、點個贊。

有任何問題，也歡迎留言討論。

參考文章：

https://redis.io/docs/latest/develop/data-types/probabilistic/bloom-filter/

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/-o3uIKt2f3SNdpvPxoCaFQ

猜你喜歡