硬核 | Redis 布隆（Bloom Filter）過濾器原理與實戰

• 2022 年 4 月 11 日
• 筆記
• JAVA, Redis, 後端

在Redis 快取擊穿（失效）、快取穿透、快取雪崩怎麼解決？中我們說到可以使用布隆過濾器避免「快取穿透」。

碼哥，布隆過濾器還能在哪些場景使用呀？

比如我們使用「碼哥跳動」開發的「明日頭條」APP 看新聞，如何做到每次推薦給該用戶的內容不會重複，過濾已經看過的內容呢？

你會說我們只要記錄了每個用戶看過的歷史記錄，每次推薦的時候去查詢資料庫過濾存在的數據實現去重。

實際上，如果歷史記錄存儲在關係資料庫里，去重就需要頻繁地對資料庫進行 exists 查詢，當系統並發量很高時，資料庫是很難扛住壓力的。

碼哥，我可以使用快取啊，把歷史數據存在 Redis 中。

萬萬不可，這麼多的歷史記錄那要浪費多大的記憶體空間，所以這個時候我們就能使用布隆過濾器去解決這種去重問題。又快又省記憶體，互聯網開發必備殺招！

當你遇到數據量大，又需要去重的時候就可以考慮布隆過濾器，如下場景：

• 解決 Redis 快取穿透問題（面試重點）；
• 郵件過濾，使用布隆過濾器實現郵件黑名單過濾；
• 爬蟲爬過的網站過濾，爬過的網站不再爬取；
• 推薦過的新聞不再推薦；

什麼是布隆過濾器

布隆過濾器 (Bloom Filter)是由 Burton Howard Bloom 於 1970 年提出，它是一種 space efficient 的概率型數據結構，用於判斷一個元素是否在集合中。

當布隆過濾器說，某個數據存在時，這個數據可能不存在；當布隆過濾器說，某個數據不存在時，那麼這個數據一定不存在。

哈希表也能用於判斷元素是否在集合中，但是布隆過濾器只需要哈希表的 1/8 或 1/4 的空間複雜度就能完成同樣的問題。

布隆過濾器可以插入元素，但不可以刪除已有元素。

其中的元素越多，false positive rate(誤報率)越大，但是 false negative (漏報)是不可能的。

布隆過濾器原理

BloomFilter 的演算法是，首先分配一塊記憶體空間做 bit 數組，數組的 bit 位初始值全部設為 0。

加入元素時，採用 k 個相互獨立的 Hash 函數計算，然後將元素 Hash 映射的 K 個位置全部設置為 1。

檢測 key 是否存在，仍然用這 k 個 Hash 函數計算出 k 個位置，如果位置全部為 1，則表明 key 存在，否則不存在。

如下圖所示：

哈希函數會出現碰撞，所以布隆過濾器會存在誤判。

這裡的誤判率是指，BloomFilter 判斷某個 key 存在，但它實際不存在的概率，因為它存的是 key 的 Hash 值，而非 key 的值。

所以有概率存在這樣的 key，它們內容不同，但多次 Hash 後的 Hash 值都相同。

對於 BloomFilter 判斷不存在的 key ，則是 100% 不存在的，反證法，如果這個 key 存在，那它每次 Hash 後對應的 Hash 值位置肯定是 1，而不會是 0。布隆過濾器判斷存在不一定真的存在。

碼哥，為什麼不允許刪除元素呢？

刪除意味著需要將對應的 k 個 bits 位置設置為 0，其中有可能是其他元素對應的位。

因此 remove 會引入 false negative，這是絕對不被允許的。

Redis 集成布隆過濾器

Redis 4.0 的時候官方提供了插件機制，布隆過濾器正式登場。以下網站可以下載官方提供的已經編譯好的可拓展模組。

//redis.com/redis-enterprise-software/download-center/modules/

碼哥推薦使用 Redis 版本 6.x，最低 4.x 來集成布隆過濾器。如下指令查看版本，碼哥安裝的版本是 6.2.6。

redis-server -v
Redis server v=6.2.6 sha=00000000:0 malloc=libc bits=64 build=b5524b65e12bbef5

下載

我們自己編譯安裝，需要從 github 下載，目前的 release 版本是 v2.2.14，下載地址：//github.com/RedisBloom/RedisBloom/releases/tag/v2.2.14

解壓編譯

解壓

tar -zxvf RedisBloom-2.2.14.tar

編譯插件

cd RedisBloom-2.2.14
make

編異成功，會看到 redisbloom.so 文件。

安裝集成

需改 redis.conf 文件，新增 loadmodule配置，並重啟 Redis。

loadmodule /opt/app/RedisBloom-2.2.14/redisbloom.so

如果是集群，則每個實例的配置文件都需要加入配置。

指定配置文件並啟動 Redis：

redis-server /opt/app/redis-6.2.6/redis.conf

載入成功的頁面如下：

客戶端連接 Redis 測試。

BF.ADD --添加一個元素到布隆過濾器
BF.EXISTS --判斷元素是否在布隆過濾器
BF.MADD --添加多個元素到布隆過濾器
BF.MEXISTS --判斷多個元素是否在布隆過濾器

Redis 布隆過濾器實戰

我們來用布隆過濾器來解決快取穿透問題，快取穿透：意味著有特殊請求在查詢一個不存在的數據，即數據不存在 Redis 也不存在於資料庫。

當用戶購買商品創建訂單的時候，我們往 mq 發送消息，把訂單 ID 添加到布隆過濾器。

在添加到布隆過濾器之前，我們通過BF.RESERVE命令手動創建一個名字為 orders error_rate = 0.1 ，初始容量為 10000000 的布隆過濾器：

# BF.RESERVE {key} {error_rate} {capacity} [EXPANSION {expansion}] [NONSCALING]
BF.RESERVE orders 0.1 10000000

• key：filter 的名字；
• error_rate：期望的錯誤率，默認 0.1，值越低，需要的空間越大；
• capacity：初始容量，默認 100，當實際元素的數量超過這個初始化容量時，誤判率上升。
• EXPANSION：可選參數，當添加到布隆過濾器中的數據達到初始容量後，布隆過濾器會自動創建一個子過濾器，子過濾器的大小是上一個過濾器大小乘以 expansion；expansion 的默認值是 2，也就是說布隆過濾器擴容默認是 2 倍擴容；
• NONSCALING：可選參數，設置此項後，當添加到布隆過濾器中的數據達到初始容量後，不會擴容過濾器，並且會拋出異常（(error) ERR non scaling filter is full）
  說明：BloomFilter 的擴容是通過增加 BloomFilter 的層數來完成的。每增加一層，在查詢的時候就可能會遍歷多層 BloomFilter 來完成，每一層的容量都是上一層的兩倍（默認）。

如果不使用BF.RESERVE命令創建，而是使用 Redis 自動創建的布隆過濾器，默認的 error_rate 是 0.01，capacity是 100。

隆過濾器的 error_rate 越小，需要的存儲空間就越大，對於不需要過於精確的場景，error_rate 設置稍大一點也可以。

布隆過濾器的 capacity 設置的過大，會浪費存儲空間，設置的過小，就會影響準確率，所以在使用之前一定要儘可能地精確估計好元素數量，還需要加上一定的冗餘空間以避免實際元素可能會意外高出設置值很多。

添加訂單 ID 到過濾器

# BF.ADD {key} {item}
BF.ADD orders 10086
(integer) 1

使用 BF.ADD向名稱為 orders 的布隆過濾器添加 10086 這個元素。

如果是多個元素同時添加，則使用 BF.MADD key {item ...}，如下：

BF.MADD orders 10087 10089
1) (integer) 1
2) (integer) 1

判斷訂單是否存在

# BF.EXISTS {key} {item}
BF.EXISTS orders 10086
(integer) 1

BF.EXISTS 判斷一個元素是否存在於BloomFilter，返回值 = 1 表示存在。

如果需要批量檢查多個元素是否存在於布隆過濾器則使用 BF.MEXISTS，返回值是一個數組：

• 1：存在；
• 0：不存在。

# BF.MEXISTS {key} {item}
BF.MEXISTS orders 100 10089
1) (integer) 0
2) (integer) 1

總體說，我們通過BF.RESERVE、BF.ADD、BF.EXISTS三個指令就能實現避免快取穿透問題。

碼哥，如何查看創建的布隆過濾器資訊呢？

用 BF.INFO key查看，如下：

BF.INFO orders
 1) Capacity
 2) (integer) 10000000
 3) Size
 4) (integer) 7794184
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 3
 9) Expansion rate
10) (integer) 2

返回值：

• Capacity：預設容量；
• Size：實際佔用情況，但如何計算待進一步確認；
• Number of filters：過濾器層數；
• Number of items inserted：已經實際插入的元素數量；
• Expansion rate：子過濾器擴容係數（默認 2）；

碼哥，如何刪除布隆過濾器呢？

目前布隆過濾器不支援刪除，布穀過濾器Cuckoo Filter是支援刪除的。

Bloom 過濾器在插入項目時通常表現出更好的性能和可伸縮性（因此，如果您經常向數據集添加項目，那麼 Bloom 過濾器可能是理想的）。布谷鳥過濾器在檢查操作上更快，也允許刪除。

大家有興趣可可以看下：//oss.redis.com/redisbloom/Cuckoo_Commands/)

碼哥，我想知道你是如何掌握這麼多技術呢？

其實我也是翻閱官方文檔並做一些簡單加工而已，這篇的文章內容實戰就是基於 Redis 官方文檔上面的例子：//oss.redis.com/redisbloom/。

大家遇到問題一定要耐心的從官方文檔尋找答案，培養自己的閱讀和定位問題的能力。

Redission 布隆過濾器實戰

碼哥的樣例程式碼基於 Spring Boot 2.1.4，程式碼地址：//github.com/MageByte-Zero/springboot-parent-pom。

添加 Redission 依賴：

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

使用 Spring boot 默認的 Redis 配置方式配置 Redission：

spring:
  application:
    name: redission

  redis:
    host: 127.0.0.1
    port: 6379
    ssl: false

創建布隆過濾器

@Service
public class BloomFilterService {

    @Autowired
    private RedissonClient redissonClient;

    /**
     * 創建布隆過濾器
     * @param filterName 過濾器名稱
     * @param expectedInsertions 預測插入數量
     * @param falseProbability 誤判率
     * @param <T>
     * @return
     */
    public <T> RBloomFilter<T> create(String filterName, long expectedInsertions, double falseProbability) {
        RBloomFilter<T> bloomFilter = redissonClient.getBloomFilter(filterName);
        bloomFilter.tryInit(expectedInsertions, falseProbability);
        return bloomFilter;
    }

}

單元測試

@Slf4j
@RunWith(SpringRunner.class)
@SpringBootTest(classes = RedissionApplication.class)
public class BloomFilterTest {

    @Autowired
    private BloomFilterService bloomFilterService;

    @Test
    public void testBloomFilter() {
        // 預期插入數量
        long expectedInsertions = 10000L;
        // 錯誤比率
        double falseProbability = 0.01;
        RBloomFilter<Long> bloomFilter = bloomFilterService.create("ipBlackList", expectedInsertions, falseProbability);

        // 布隆過濾器增加元素
        for (long i = 0; i < expectedInsertions; i++) {
            bloomFilter.add(i);
        }
        long elementCount = bloomFilter.count();
        log.info("elementCount = {}.", elementCount);

        // 統計誤判次數
        int count = 0;
        for (long i = expectedInsertions; i < expectedInsertions * 2; i++) {
            if (bloomFilter.contains(i)) {
                count++;
            }
        }
        log.info("誤判次數 = {}.", count);
        bloomFilter.delete();
    }
}

注意事項：如果是 Redis Cluster 集群，則需要 RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");

參考資料

1.//blog.csdn.net/u010066934/article/details/122026625
2.//juejin.cn/book/6844733724618129422/section/6844733724706209806
3.//www.cnblogs.com/heihaozi/p/12174478.html
4.//www.cnblogs.com/allensun/archive/2011/02/16/1956532.html
5.//oss.redis.com/redisbloom/Bloom_Commands/
6.//oss.redis.com/redisbloom/
7.//redis.com/blog/rebloom-bloom-filter-datatype-redis