在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/

碼哥推薦使用 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

解壓編譯

解壓

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

大家有興趣可可以看下：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");

參考資料

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