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

在 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 的時候官方提供了插件機制，布隆過濾器正式登場。以下網站可以下載官方提供的已經編譯好的可拓展模塊。

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

RedisModules

碼哥推薦使用 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，下載地址：https://github.com/RedisBloom/RedisBloom/releases/tag/v2.2.14

Redis 布隆

解壓編譯

解壓

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

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

module 配置

指定配置文件並啓動 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 過濾器可能是理想的）。布穀鳥過濾器在檢查操作上更快，也允許刪除。

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

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

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

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

Redission 布隆過濾器實戰

碼哥的樣例代碼基於 Spring Boot 2.1.4，代碼地址：https://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");

文末福利

送 4 本《大型網站架構實戰》給一直關注並支持碼哥的讀者。

中獎規則：在本文留言並將此文轉發到朋友圈，我從留言中隨機抽取 4 位幸運讀者，憑藉朋友圈分享記錄截圖領取。免費包郵到手！

截止：2022 年 3 月 24 20:00

大型網站系統有很多功能，一次性明確所有的功能需求並設計出一個龐大的業務架構是一件費力不討好的事情。因爲在項目前期，難免會忽視一些瑣碎功能，而隨着開發的進行，也會有很多新的想法產生，基本上不會存在完全按照最初的業務架構設計完成的軟件產品。因此，業務架構不僅要做到 “規整功能模塊，釐清產品業務邏輯”，更重要的是如何做到 “有規劃性地應對項目過程中的需求變更”。

加我微信：MageByte1024，進入專屬技術讀者羣一起成長。

參考資料

1.https://blog.csdn.net/u010066934/article/details/122026625

2.https://juejin.cn/book/6844733724618129422/section/6844733724706209806

3.https://www.cnblogs.com/heihaozi/p/12174478.html

4.https://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html

5.https://oss.redis.com/redisbloom/Bloom_Commands/

6.https://oss.redis.com/redisbloom/

7.https://redis.com/blog/rebloom-bloom-filter-datatype-redis

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

什麼是布隆過濾器

布隆過濾器原理

Redis 集成布隆過濾器

下載

解壓編譯

安裝集成

Redis 布隆過濾器實戰

添加訂單 ID 到過濾器

判斷訂單是否存在

Redission 布隆過濾器實戰

文末福利

猜你喜歡