布隆(Bloom Filter)過濾器——全面講解，建議收藏

本文已收錄于專欄

??《Redis之大廠必備技能包》??

歡迎各位關注、三連博主的文章及專欄，全套Redis學習資料，大廠必備技能！

目錄

1、什么是布隆過濾器

2、布隆過濾器的使用場景

3、布隆過濾器的原理

3.1 資料結構

3.2 空間計算

3.3 增加元素

3.4 查詢元素

3.5 修改元素

3.6 洗掉元素

4、Redis集成布隆過濾器

4.1 版本要求

4.2 安裝&編譯

4.3 Redis集成

5、Redis中布隆過濾器指令使用

5.1 bf.add

5.2 bf.madd

5.3 bf.exists

5.3 bf.mexists

6、Java本地記憶體使用布隆過濾器

6.1 引入pom依賴

6.2 撰寫測驗代碼

6.3 測驗結果

6.4 引數說明

6.5 fpp&expectedInsertions

7、Java集成Redis使用布隆過濾器

7.1 引入pom依賴

7.2 撰寫測驗代碼

7.3 測驗結果

1、什么是布隆過濾器

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

上面這句介紹比較全面的描述了什么是布隆過濾器，如果還是不太好理解的話，就可以把布隆過濾器理解為一個set集合，我們可以通過add往里面添加元素，通過contains來判斷是否包含某個元素，由于本文講述布隆過濾器時會結合Redis來講解，因此類比為Redis中的Set資料結構會比較好理解，而且Redis中的布隆過濾器使用的指令與Set集合非常類似（后續會講到），
?

學習布隆過濾器之前有必要先聊下它的優缺點，因為好的東西我們才想要嘛！
布隆過濾器的優點：

• 時間復雜度低，增加和查詢元素的時間復雜為O(N)，（N為哈希函式的個數，通常情況比較小）
• 保密性強，布隆過濾器不存盤元素本身
• 存盤空間小，如果允許存在一定的誤判，布隆過濾器是非常節省空間的（相比其他資料結構如Set集合）

布隆過濾器的缺點：

• 有點一定的誤判率，但是可以通過調整引數來降低
• 無法獲取元素本身
• 很難洗掉元素

2、布隆過濾器的使用場景

布隆過濾器可以告訴我們 “某樣東西一定不存在或者可能存在”，也就是說布隆過濾器說這個數不存在則一定不存，布隆過濾器說這個數存在可能不存在（誤判，后續會講），**利用這個判斷是否存在的特點可以做很多有趣的事情，

• 解決Redis快取穿透問題（面試重點）
• 郵件過濾，使用布隆過濾器來做郵件黑名單過濾
• 對爬蟲網址進行過濾，爬過的不再爬
• 解決新聞推薦過的不再推薦(類似抖音刷過的往下滑動不再刷到)
• HBase\RocksDB\LevelDB等資料庫內置布隆過濾器，用于判斷資料是否存在，可以減少資料庫的IO請求

3、布隆過濾器的原理

3.1 資料結構

布隆過濾器它實際上是一個很長的二進制向量和一系列隨機映射函式，以Redis中的布隆過濾器實作為例，Redis中的布隆過濾器底層是一個大型位陣列（二進制陣列）+多個無偏hash函式，
一個大型位陣列（二進制陣列）：

多個無偏hash函式：
無偏hash函式就是能把元素的hash值計算的比較均勻的hash函式，能使得計算后的元素下標比較均勻的映射到位陣列中，

如下就是一個簡單的布隆過濾器示意圖，其中k1、k2代表增加的元素，a、b、c即為無偏hash函式，最下層則為二進制陣列，

3.2 空間計算

在布隆過濾器增加元素之前，首先需要初始化布隆過濾器的空間，也就是上面說的二進制陣列，除此之外還需要計算無偏hash函式的個數，布隆過濾器提供了兩個引數，分別是預計加入元素的大小n，運行的錯誤率f，布隆過濾器中有演算法根據這兩個引數會計算出二進制陣列的大小l，以及無偏hash函式的個數k，
它們之間的關系比較簡單：

• 錯誤率越低，位陣列越長，控制元件占用較大
• 錯誤率越低，無偏hash函式越多，計算耗時較長

如下地址是一個免費的在線布隆過濾器在線計算的網址：

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

3.3 增加元素

往布隆過濾器增加元素，添加的key需要根據k個無偏hash函式計算得到多個hash值，然后對陣列長度進行取模得到陣列下標的位置，然后將對應陣列下標的位置的值置為1

• 通過k個無偏hash函式計算得到k個hash值
• 依次取模陣列長度，得到陣列索引
• 將計算得到的陣列索引下標位置資料修改為1

例如，key = Liziba，無偏hash函式的個數k=3，分別為hash1、hash2、hash3，三個hash函式計算后得到三個陣列下標值，并將其值修改為1.
如圖所示：

3.4 查詢元素

布隆過濾器最大的用處就在于判斷某樣東西一定不存在或者可能存在，而這個就是查詢元素的結果，其查詢元素的程序如下：

• 通過k個無偏hash函式計算得到k個hash值
• 依次取模陣列長度，得到陣列索引
• 判斷索引處的值是否全部為1，如果全部為1則存在（這種存在可能是誤判），如果存在一個0則必定不存在

關于誤判，其實非常好理解，hash函式在怎么好，也無法完全避免hash沖突，也就是說可能會存在多個元素計算的hash值是相同的，那么它們取模陣列長度后的到的陣列索引也是相同的，這就是誤判的原因，例如李子捌和李子柒的hash值取模后得到的陣列索引都是1，但其實這里只有李子捌，如果此時判斷李子柒在不在這里，誤判就出現啦！因此布隆過濾器最大的缺點誤判只要知道其判斷元素是否存在的原理就很容易明白了！

3.5 修改元素

無
?

3.6 洗掉元素

布隆過濾器對元素的洗掉不太支持，目前有一些變形的特定布隆過濾器支持元素的洗掉！關于為什么對洗掉不太支持，其實也非常好理解，hash沖突必然存在，洗掉肯定是很苦難的！
?

4、Redis集成布隆過濾器

4.1 版本要求

• 推薦版本6.x，最低4.x版本，可以通過如下命令查看版本：

redis-server -v

• 插件安裝，網上大部分推薦v1.1.1，文章寫的時候v2.2.6已經是release版本了，用戶自己選擇，地址全在下面(2.2.6官網介紹說是1.0版本的維護版本，如果不想使用新的功能，無需升級！)

v1.1.1

https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz

v2.2.6

https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

4.2 安裝&編譯

以下安裝全部在指定目錄下完成，可以選擇一個合適的統一目錄進行軟體安裝和管理，

4.2.1 下載插件壓縮包

wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

4.2.2 解壓

tar -zxvf v2.2.6.tar.gz

4.2.3 編譯插件

cd RedisBloom-2.2.6/
make

編譯成功后看到redisbloom.so檔案即可
?

4.3 Redis集成

4.3.1 Redis組態檔修改

• 在redis.conf組態檔中加入如RedisBloom的redisbloom.so檔案的地址
• 如果是集群則每個組態檔中都需要加入redisbloom.so檔案的地址
• 添加完成后需要重啟redis

loadmodule /usr/local/soft/RedisBloom-2.2.6/redisbloom.so

redis.conf組態檔中預置了loadmodule的配置項，我們可以直接在這里修改，后續修改會更加方便，

保存退出后一定要記得重啟Redis！
保存退出后一定要記得重啟Redis！
保存退出后一定要記得重啟Redis！

4.3.2 測驗是否成功

Redis集成布隆過濾器的主要指令如下：

• bf.add 添加一個元素
• bf.exists 判斷一個元素是否存在
• bf.madd 添加多個元素
• bf.mexists 判斷多個元素是否存在

連接客戶端進行測驗，如果指令有效則證明集成成功

如果出現如下情況(error) ERR unknown command ，可以通過如下方法檢查：

• SHUTDOWN Redis實體，再重啟實體，再次測驗
• 檢查組態檔是否配置redisbloom.so檔案地址正確
• 檢查Redis的版本是否過低

5、Redis中布隆過濾器指令使用

5.1 bf.add

bf.add表示添加單個元素，添加成功回傳1

127.0.0.1:6379> bf.add name liziba
(integer) 1

5.2 bf.madd

bf.madd表示添加多個元素

127.0.0.1:6379> bf.madd name liziqi lizijiu lizishi
1) (integer) 1
2) (integer) 1
3) (integer) 1

5.3 bf.exists

bf.exists表示判斷元素是否存在，存在則回傳1，不存在回傳0

127.0.0.1:6379> bf.mexists name liziba
1) (integer) 1

5.3 bf.mexists

bf.mexists表示判斷多個元素是否存在，存在的回傳1，不存在的回傳0

127.0.0.1:6379> bf.mexists name liziqi lizijiu liziliu
1) (integer) 1
2) (integer) 1
3) (integer) 0

6、Java本地記憶體使用布隆過濾器

使用布隆過濾器的方式有很多，還有很多大佬自己手寫的，我這里使用的是谷歌guava包中實作的布隆過濾器，這種方式的布隆過濾器是在本地記憶體中實作，

6.1 引入pom依賴

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>29.0-jre</version>
</dependency>

6.2 撰寫測驗代碼

package com.lizba.bf;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**
 * <p>
 *        布隆過濾器測驗代碼
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/8/29 14:51
 */
public class BloomFilterTest {

    /** 預計插入的資料 */
    private static Integer expectedInsertions = 10000000;
    /** 誤判率 */
    private static Double fpp = 0.01;
    /** 布隆過濾器 */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);

    public static void main(String[] args) {
        // 插入 1千萬資料
        for (int i = 0; i < expectedInsertions; i++) {
            bloomFilter.put(i);
        }

        // 用1千萬資料測驗誤判率
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions *2; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
            }
        }
        System.out.println("一共誤判了：" + count);

    }

}

6.3 測驗結果

誤判了100075次，大概是expectedInsertions（1千萬）的0.01，這與我們設定的 fpp = 0.01非常接近，

6.4 引數說明

在guava包中的BloomFilter原始碼中，構造一個BloomFilter物件有四個引數：

• Funnel funnel：資料型別，由Funnels類指定即可
• long expectedInsertions：預期插入的值的數量
• fpp：錯誤率
• BloomFilter.Strategy：hash演算法

6.5 fpp&expectedInsertions

• 當expectedInsertions=10000000&&fpp=0.01時，位陣列的大小numBits=95850583，hash函式的個數numHashFunctions=7

• 當expectedInsertions=10000000&&fpp=0.03時，位陣列的大小numBits=72984408，hash函式的個數numHashFunctions=5

• 當expectedInsertions=100000&&fpp=0.03時，位陣列的大小numBits=729844，hash函式的個數numHashFunctions=5

綜上三次測驗可以得出如下結論：

• 當預計插入的值的數量不變時，偏差值fpp越小，位陣列越大，hash函式的個數越多
• 當偏差值不變時，預計插入的中的數量越大，位陣列越大，hash函式并沒有變化（注意這個結論只是在guava實作的布隆過濾器中的演算法符合，并不是說所有的演算法都是這個結論，我做了多次測驗，確實numHashFunctions在fpp相同時，是不變的！）

7、Java集成Redis使用布隆過濾器

Redis經常會被問道快取擊穿問題，比較優秀的解決辦法是使用布隆過濾器，也有使用空物件解決的，但是最好的辦法肯定是布隆過濾器，我們可以通過布隆過濾器來判斷元素是否存在，避免快取和資料庫都不存在的資料進行查詢訪問！在如下的代碼中只要通過bloomFilter.contains(xxx)即可，我這里演示的還是誤判率！

7.1 引入pom依賴

<dependency>
  <groupId>org.redisson</groupId>
  <artifactId>redisson-spring-boot-starter</artifactId>
  <version>3.16.0</version>
</dependency>

7.2 撰寫測驗代碼

package com.lizba.bf;

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

/**
 * <p>
 *      Java集成Redis使用布隆過濾器防止快取穿透方案
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/8/29 16:13
 */
public class RedisBloomFilterTest {

    /** 預計插入的資料 */
    private static Integer expectedInsertions = 10000;
    /** 誤判率 */
    private static Double fpp = 0.01;

    public static void main(String[] args) {
        // Redis連接配置，無密碼
        Config config = new Config();
        config.useSingleServer().setAddress("redis://192.168.211.108:6379");
        // config.useSingleServer().setPassword("123456");

        // 初始化布隆過濾器
        RedissonClient client = Redisson.create(config);
        RBloomFilter<Object> bloomFilter = client.getBloomFilter("user");
        bloomFilter.tryInit(expectedInsertions, fpp);

        // 布隆過濾器增加元素
        for (Integer i = 0; i < expectedInsertions; i++) {
            bloomFilter.add(i);
        }

        // 統計元素
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions*2; i++) {
            if (bloomFilter.contains(i)) {
                count++;
            }
        }
        System.out.println("誤判次數" + count);

    }

}

7.3 測驗結果