1. 布隆過濾器

1.1 概念

在架構設計時有一種最常見的設計被稱為布隆過濾器，它可以有效減少緩存穿透的情況。其主旨是采用一個很長的二進制數(shù)組，通過一系列的 Hash 函數(shù)來確定該數(shù)據(jù)是否存在。

布隆過濾器本質上是一個 n 位的二進制數(shù)組。你也知道二進制只有 0 和 1 來表示，針對于當前我們的場景。這里我模擬了一個二進制數(shù)組，其每一位它的初始值都是 0。

而這個二進制數(shù)組會被存儲在 Redis 服務器中，那么這個數(shù)組該怎么用呢？

1.2 原理

使用若干次 Hash 來確定其位置。

假設有 1000 個商品編號，從 1~1000。作為布隆過濾器，在初始化的時候，實際上就是對每一個商品編號進行若干次 Hash 來確定它們的位置。

（1）1 號商品計算
比如說針對于當前的“1”編號，我們對其執(zhí)行了三次 Hash。所謂 Hash 函數(shù)就是將數(shù)據(jù)代入以后確定一個具體的位置。

Hash 1 函數(shù)：它會定位到二進制數(shù)組的第 2 位上，并將其數(shù)值從 0 改為 1；

Hash 2 函數(shù)：它定位到索引為 5 的位置，并將從 0 改為 1；

Hash 3 函數(shù)：定位到索引為 99 的位置上，將其從 0 改為 1。

（2）2 號商品計算
那 1 號商品計算完以后，該輪到 2 號商品。2 號商品經(jīng)過三次 Hash 以后，分別定位到索引為 1、3 以及 98 號位置上。
原始數(shù)據(jù)中 1 號位因為剛才已經(jīng)變成了 1，現(xiàn)在它不變；而 3 號位和 98 號位原始數(shù)據(jù)從 0 變?yōu)?1。

這里又衍生出一個 Hash 新規(guī)則：如果在 Hash 后，原始位它是 0 的話，將其從 0 變?yōu)?1；如果本身這一位就是 1 的話，則保持不變。

（3）1000 號商品計算
此時 2 號商品也處理完了，我們繼續(xù)向后 3、4、5、6、7、8 直到編號達到了最后一個 1000，當商品編號 1000 處理完后，他將索引為 3、6、98 設置為 1。

2. 布隆過濾器在電商商品中的實踐

（1）先看一個已存在的情況
比如，此時某一個用戶要查詢 858 號商品數(shù)據(jù)。都知道 858 是存在的，那么按照原始的三個 Hash 分別定位到了 1、5 和 98 號位，當每一個 Hash 位的數(shù)值都是 1 時，則代表對應的編號它是存在的。
（2）再看一個不存在的情況
例如這里要查詢 8888。8888 這個數(shù)值經(jīng)過三次 Hash 后，定位到了 3、6 和 100 這三個位置。此時索引為 100 的數(shù)值是 0，在多次 Hash 時有任何一位為 0 則代表這個數(shù)據(jù)是不存在的。

簡單總結一下：如果布隆過濾器所有 Hash 的值都是 1 的話，則代表這個數(shù)據(jù)可能存在。
注意我的表達：它是可能存在；但如果某一位的數(shù)值是 0 的話，它是一定不存在的。

布隆過濾器設計之初，它就不是一個精確的判斷，因為布隆過濾器存在誤判的情況。

（3）最后看一個誤判情況
來看一下當前的演示：比如現(xiàn)在我要查詢 8889 的情況，經(jīng)過三次 Hash 正好每一位上都是 1。盡管在數(shù)據(jù)庫中，8889 這個商品是不存在的；但在布隆過濾器中，它會被判定為存在。這就是在布隆過濾器中會出現(xiàn)的小概率的誤判情況。

3. 如何減少布隆過濾器的誤判

關于減少誤判的產生，方法有兩個：

• 第一個是增加二進制位數(shù)。在原始情況下我們設置索引位到達了 100，但是如果我們把它放大 1 萬倍，到達了 100 萬，是不是 Hash 以后的數(shù)據(jù)會變得更分散，出現(xiàn)重復的情況就會更小。

• 第二個是增加 Hash 的次數(shù)。其實每一次 Hash 處理都是在增加數(shù)據(jù)的特征，特征越多，出現(xiàn)誤判的概率就越小。

現(xiàn)在我們是做了三次 Hash，那么如果你做十次，是不是它出現(xiàn)誤判的概率就會小非常多？但是在這個過程中，代價便是 CPU 需要進行更多運算，這會讓布隆過濾器的性能有所降低。

4. 布隆過濾器在 Java 中的應用

在 Java 中提供了一個 Redisson 的組件，它內置了布隆過濾器，可以讓程序員非常簡單直接地去設置布隆過濾器。
上面代碼是 Redisson 的使用辦法，在前幾行代碼，用來設置 Redis 服務器的服務地址及端口號。

而后面關鍵的地方在這里，我們實例化一個布隆過濾器對象，后面的參數(shù)指代 Redis 使用哪個 key 來保存布隆過濾器數(shù)據(jù)？

下面這句話非常關鍵，作為當前的布隆過濾器，這里需要調用 tryInit 方法，它有兩個參數(shù)：

• 第一個參數(shù)是代表初始化的布隆過濾器長度，長度越大，出現(xiàn)誤判的可能性就越低。

• 而第二個 0.01 則代表誤判率最大允許為 1%，在我們以前的項目中通常也是設置為 1%。如果把這個數(shù)值設置太小，雖然會降低誤判率，但會產生更多次的 Hash 操作，會降低系統(tǒng)的性能（正是剛剛講過的），因此 1% 也是我所建議的數(shù)值。

當把布隆過濾器初始化以后，我們便可以通過 add 方法，往里邊去添加數(shù)據(jù)。所謂添加數(shù)據(jù)，就是將數(shù)據(jù)進行多次 Hash，將對應位從 0 變?yōu)?1 的過程。例如，現(xiàn)在我們把編號 1 增加進去，之后可以通過布隆過濾器的 contains 方法來判斷當前這個數(shù)據(jù)是否存在。

我們輸入 1，它輸出 true；而輸入了不存在的 8888，則輸出 false。
請注意：這兩個結果的含義是不同的。

• 如果輸出 false，則代表這個數(shù)據(jù)它是肯定不存在的；
• 但是如果輸出 true 的時候，它有 1% 的概率可能不存在，因為布隆過濾器它存在誤判的情況。

5. 布隆過濾器在項目中的應用

布隆過濾器在項目中的使用流程，其實就歸結成以下三部分：

• 第一個部分是在應用啟動時，我們去初始化布隆過濾器。例如將 1000 個、1 萬個、10 萬個商品進行初始化，完成從 0 到 1 的轉化工作。

• 之后便是當用戶發(fā)來請求時，會附加商品編號，如果布隆過濾器判斷編號存在，則直接去讀取存儲在 Redis 緩存中的數(shù)據(jù)；如果此時 Redis 緩存沒有存在對應的商品數(shù)據(jù)，則直接去讀取數(shù)據(jù)庫，并將讀取到的信息重新載入到 Redis 緩存中。這樣下一次用戶在查詢相同編號數(shù)據(jù)時，就可以直接讀取緩存了。

• 另外一種情況是，如果布隆過濾器判斷沒有包含編號，則直接返回數(shù)據(jù)不存在的消息提示，這樣便可以在 Redis 層面將請求進行攔截。

你可能會有疑惑，既然布隆過濾器存在誤判率，那出現(xiàn)了誤判該怎么辦呢？

其實在大多數(shù)情況下，我們出現(xiàn)誤判也不會對系統(tǒng)產生額外的影響。因為像剛才我們設置 1% 的誤判率，1 萬次請求才可能會出現(xiàn) 100 次誤判的情況。我們已經(jīng)將 99% 的無效請求進行了攔截，而這些漏網(wǎng)之魚也不會對我們系統(tǒng)產生任何實質影響。

6. 初始化后，對應商品被刪怎么辦

假如布隆過濾器初始化后，對應商品被刪除了，該怎么辦呢？這是一個布隆過濾器的小難點。

因為布隆過濾器某一位的二進制數(shù)據(jù)，可能被多個編號的 Hash 位進行引用。比如說，布隆過濾器中 2 號位是 1，但是它可能被 3、5、100、1000 這 4 個商品編號同時引用。這里是不允許直接對布隆過濾器某一位進行刪除的，否則數(shù)據(jù)就亂了，怎么辦呢？

這里業(yè)內有兩種常見的解決方案：

• 定時異步重建布隆過濾器。比如說我們每過 4 個小時在額外的一臺服務器上，異步去執(zhí)行一個任務調度，來重新生成布隆過濾器，替換掉已有的布隆過濾器。

• 計數(shù)布隆過濾器。在標準的布隆過濾器下，是無法得知當前某一位它是被哪些具體數(shù)據(jù)進行了引用，但是計數(shù)布隆過濾器它是在這一位上額外的附加的計數(shù)信息，表達出該位被幾個數(shù)據(jù)進行了引用。

7. 總體概覽

原文：
原文鏈接

總結

以上是生活随笔為你收集整理的Redis 预防缓存穿透“神器” — 布隆过滤器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。