文章目錄

• Pre
• 布隆能解決哪些問題？
• BloomFilter實現(xiàn)原理
• 構(gòu)建布隆過濾器
• 構(gòu)建布隆的誤差率
• 實際誤差率推算
• 布隆過濾器 (JVM級別)
• 布隆過濾器 (分布式)
• Bloom Filter的缺點

---

Pre

我們在 Redis進階-Redis緩存優(yōu)化中 講到了 緩存穿透 的解決防范： 比緩存空值更好的一種解決方式 布隆過濾器 ，這里我們詳細講解下。

---

布隆能解決哪些問題？

舉個例子 ： 有50億個電話號碼，現(xiàn)在給你10萬個電話號碼，如何快速準確的判斷出這些號碼是否存在？

方案A： DB ？ ----> 50億的電話號碼，這查詢效率 ？
方案B: 內(nèi)存 ？ —> 就按1個電話號碼8個字節(jié) ， 50億*8字節(jié)= 40G 內(nèi)存…
方案C： hyperloglog? ----> 準確率有點低

類似的問題還有很多，比如

• 垃圾郵件過濾
• 文字處理軟件（比如word）錯誤單詞檢測
• 網(wǎng)絡(luò)爬蟲重復URL檢測
• hbase 行過濾
• …

---

BloomFilter實現(xiàn)原理

1970年由伯頓.布隆提出 ，用很小的空間解決上述的問題

一個很長的二進制向量（你就理解為它底層的數(shù)據(jù)結(jié)構(gòu)是一個超級巨大的數(shù)組，只存0和1） ， 加上 若干個 hash函數(shù)

有 k個 hash函數(shù)， 進行k次運算，把每次hash運算的結(jié)果設(shè)置到對應的位上，獲取的時候 再把這些hash函數(shù)重新算一遍，如果有一個不是1 ，則布隆過濾器認為這個數(shù)不存在，只有全部都是1 才存在。

存 和 取 的計算方法一定要一樣，否則就歇菜了。。。。

---

構(gòu)建布隆過濾器

參數(shù)： m個二進制向量， n個預備數(shù)據(jù)，k個哈希函數(shù)

構(gòu)建布隆過濾器： n個預備數(shù)據(jù)走一遍上面過程

判斷元素存在與否：將這個數(shù)據(jù)，重走一遍構(gòu)建的過程（進行k次hash運算），如果都是1，則表示存在，反之不存在。

---

構(gòu)建布隆的誤差率

首先聲明，使用布隆過濾器一定要接受誤差 ，有存在可能的誤差。肯定存在誤差，即恰好都命中了

舉個例子，有兩個值經(jīng)過k次hash運算，計算的值都為1，這個時候其實你的底層數(shù)組中只有一個值，而布隆告訴你另外一個值也存在

參數(shù)： m個二進制向量， n個預備數(shù)據(jù)，k個哈希函數(shù)

直觀因素： m/n 的比率， hash函數(shù)的個數(shù)

假設(shè)你的用于存儲映射關(guān)系的二進制向量m 設(shè)置的很小 ，比如1000 （以Guava為例，設(shè)置1000并不是說只能存儲1000個，Guava底層有大量的數(shù)據(jù)計算，結(jié)合你設(shè)置的誤差率，計算出一個超級大的數(shù)組長度）， 你的 n (數(shù)據(jù)量) 又超級多，比如100個億，有3個hash函數(shù)用來計算。

這個時候我有一條數(shù)據(jù)“artisan ”,

經(jīng)過第一個hash函數(shù)運算 存儲到了底層數(shù)組中的第5個元素的位置
經(jīng)過第二個hash函數(shù)運算 存儲到了底層數(shù)組中的第100個元素的位置
經(jīng)過第三個hash函數(shù)運算 存儲到了底層數(shù)組中的第1024個元素的位置

這個時候 你要判斷 artisan存在與否，只需要重新運算這個3個hash函數(shù)，只要 第5 100 1024元素位置對應的值都是1 ，那么就認為它存在。 只要有一個為0 ，就不存在。

假設(shè)我還有另外一條數(shù)據(jù) xxxx , 經(jīng)過三次hash計算，如果他正好也落在第5 100 1024個元素位置，那布隆告訴你了 xxx存在，實際上呢？ 實際上 第5 100 1024是artisan這個值計算出來的，而不是xxx ,這就造成了數(shù)據(jù)的不準確，你要接受這誤差可能性。

---

m/n 與誤差率成反比， k與誤差率成反比

m/n 與誤差率成反比： m個二進制向量， n個預備數(shù)據(jù) ， 你用來存儲二進制的數(shù)組m越大，你實際需要存儲的數(shù)據(jù) n越小，那么m/n 是不是就越大？ 那誤差率就相應的越低了。

k與誤差率成反比 ： 這個也好理解，假設(shè)你只有1個哈希函數(shù)，是不是你重復的概率就高很多？ 所以說 k越大，誤差率越低。

---

實際誤差率推算

參數(shù)： m個二進制向量， n個預備數(shù)據(jù)，k個哈希函數(shù)

• 1） 1個元素，1個hash函數(shù)， 任何一個bit為1的概率為 1/m , 為0的概率為 1- 1/m

• 2） k個函數(shù)，為0的概率為 （1-1/m）的k次方， n個元素，依然為0的概率為 （1-1/m）的nk次方

• 3） 被設(shè)置為1的概率為 1 - （1-1/m）的nk次方

• 4） 新元素全中的概率為

常用的hash函數(shù)取值下的錯誤率：

---

布隆過濾器 (JVM級別)

可以先了解下BitMap Algorithms_算法專項_Bitmap原理及應用

import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels;public class GuavaBloomFilterTest {// BloomFilter 容量 （實際上Guava通過計算后開辟的空間遠遠大于capacity）private static final int capacity = 100000;// 構(gòu)建 BloomFilterprivate static BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), capacity);// 模擬初始化數(shù)據(jù)static{for (int i = 0; i < capacity; i++) {bloomFilter.put(i);}}public static void main(String[] args) {int testData = 999;long startTime = System.nanoTime();if (bloomFilter.mightContain(testData)){System.out.println(testData + " 包含在布隆過濾器中 ");}System.out.println("消耗時間: " + (System.nanoTime() - startTime) + " 微秒");// 錯誤率判斷double errNums = 0;for (int i = capacity + 1000000; i < capacity + 2000000; i++) {if (bloomFilter.mightContain(i)) {++errNums;}}System.out.println("錯誤率: " + (errNums/1000000));} }

本地布隆過濾器的問題

• 容量受到本地容器比如tomcat 的jvm內(nèi)存的限制
• 多個應用存在多個布隆過濾器，構(gòu)建同步復雜 （類比session，就好理解了）

• 重啟應用緩存內(nèi)容需要重新構(gòu)建

---

對于惡意攻擊，向服務器請求大量不存在的數(shù)據(jù)造成的緩存穿透，還可以用布隆過濾器先做一次過濾，對于不存在的數(shù)據(jù)布隆過濾器一般都能夠過濾掉，不讓請求再往后端發(fā)送.

布隆過濾器返回某個值存在時，這個值可能不存在；當它說不存在時，那就肯定不存在。

布隆過濾器就是一個大型的位數(shù)組和幾個不一樣的無偏 hash 函數(shù)。

所謂無偏就是能夠把元素的 hash 值算得比較均勻。

向布隆過濾器中添加 key 時，會使用多個 hash 函數(shù)對 key 進行 hash 算得一個整數(shù)索引值然后對位數(shù)組長度進行取模運算得到一個位置，每個 hash 函數(shù)都會算得一個不同的位置。再把位數(shù)組的這幾個位置都置為 1 就完成了 add 操作。

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

如果都是 1，這并不能說明這個key 就一定存在，只是極有可能存在，因為這些位被置為 1 可能是因為其它的 key 存在所致.

如果這個位數(shù)組比較稀疏，這個概率就會很大，如果這個位數(shù)組比較擁擠，這個概率就會降低。

這種方法適用于數(shù)據(jù)命中不高、 數(shù)據(jù)相對固定、 實時性低（通常是數(shù)據(jù)集較大） 的應用場景， 代碼維護較為復雜， 但是緩存空間占用很少 .

---

偽代碼如下

可以用guvua包自帶的布隆過濾器，引入依賴

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>22.0</version> </dependency> import com.google.common.hash.BloomFilter;//初始化布隆過濾器 //1000：期望存入的數(shù)據(jù)個數(shù)，0.001：期望的誤差率 BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf‐8")), 1000, 0.001);//把所有數(shù)據(jù)存入布隆過濾器 void init(){for (String key: keys) {bloomFilter.put(key);} }String get(String key) {// 從布隆過濾器這一級緩存判斷下key是否存在Boolean exist = bloomFilter.mightContain(key);if(!exist){return "";}// 從緩存中獲取數(shù)據(jù)String cacheValue = cache.get(key);// 緩存為空if (StringUtils.isBlank(cacheValue)) {// 從存儲中獲取String storageValue = storage.get(key);cache.set(key, storageValue);// 如果存儲數(shù)據(jù)為空， 需要設(shè)置一個過期時間(300秒)if (storageValue == null) {cache.expire(key, 60 * 5);}return storageValue;} else {// 緩存非空return cacheValue;}}

---

布隆過濾器 (分布式)

我們分析了本地布隆過濾器的缺點 ，僅僅存在單個應用中，多個應用之間的布隆過濾器同步困難，而且一旦應用重啟，緩存丟失。

對于分布式環(huán)境，可以利用 Redis 構(gòu)建分布式布隆過濾器

使用redisson 框架

https://github.com/redisson/redisson/wiki/6.-distributed-objects#68-bloom-filter

RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample"); // initialize bloom filter with // expectedInsertions = 55000000 // falseProbability = 0.03 bloomFilter.tryInit(55000000L, 0.03);bloomFilter.add(new SomeObject("field1Value", "field2Value")); bloomFilter.add(new SomeObject("field5Value", "field8Value"));bloomFilter.contains(new SomeObject("field1Value", "field8Value")); bloomFilter.count();

redis布隆過濾器 主要解決的場景是 緩存穿透 ，導致大量的請求落到DB上，壓垮DB。

所以布隆過濾器應該在 redis緩存和 DB之間 。

布隆告訴你 ，存在的不一定存在，不存在的一定不存在。 所以 當你從DB中沒有查到值的時候，你應該把這個key更新到布隆過濾器中，下次這個key再過來的時候，直接返回不存在了，無需再次查詢DB。

偽代碼如下

public String getByKey(String key) {String value = get(key);if (StringUtils.isEmpty(value)) {logger.info("Redis 沒命中 {}", key);if (bloomFilter.mightContain(key)) {logger.info("BloomFilter 命中 {}", key);return value;} else {if (mapDB.containsKey(key)) {logger.info("更新 Key {} 到 Redis", key);String valDB = mapDB.get(key);set(key, valDB);return valDB;} else {logger.info("更新 Key {} 到 BloomFilter", key);bloomFilter.put(key);return value;}}} else {logger.info("Redis 命中 {}", key);return value;} }

---

Bloom Filter的缺點

bloom filter犧牲了判斷的準確率、刪除的便利性 ，才做到在時間和空間上的效率比較高，是因為

• 存在誤判，可能要查到的元素并沒有在容器中，但是hash之后得到的k個位置上值都是1。如果bloom filter中存儲的是黑名單，那么可以通過建立一個白名單來存儲可能會誤判的元素。

• 刪除數(shù)據(jù)。一個放入容器的元素映射到bit數(shù)組的k個位置上是1，刪除的時候不能簡單的直接置為0，可能會影響其他元素的判斷。可以考慮Counting Bloom Filter

總結(jié)

以上是生活随笔為你收集整理的Redis进阶-布隆过滤器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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