在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?orders1)?Capacity2)?(integer)?100000003)?Size4)?(integer)?77941845)?Number?of?filters6)?(integer)?17)?Number?of?items?inserted8)?(integer)?39)?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:?redissionredis:host:?127.0.0.1port:?6379ssl:?false

創建布隆過濾器

@Service
public?class?BloomFilterService?{@Autowiredprivate?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?{@Autowiredprivate?BloomFilterService?bloomFilterService;@Testpublic?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

作者?| 碼哥字節

出品?|?碼哥字節

---------------------
作者：無雙.
來源：CSDN
原文：https://blog.csdn.net/sinat_32849897/article/details/123700560
版權聲明：本文為作者原創文章，轉載請附上博文鏈接！
內容解析By：CSDN,CNBLOG博客文章一鍵轉載插件