源?/碼哥字節(jié)?? ? ? ??文/?

碼哥，布隆過(guò)濾器還能在哪些場(chǎng)景使用呀？

比如我們使用「碼哥跳動(dòng)」開(kāi)發(fā)的「明日頭條」APP 看新聞，如何做到每次推薦給該用戶的內(nèi)容不會(huì)重復(fù)，過(guò)濾已經(jīng)看過(guò)的內(nèi)容呢？

你會(huì)說(shuō)我們只要記錄了每個(gè)用戶看過(guò)的歷史記錄，每次推薦的時(shí)候去查詢數(shù)據(jù)庫(kù)過(guò)濾存在的數(shù)據(jù)實(shí)現(xiàn)去重。

實(shí)際上，如果歷史記錄存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)里，去重就需要頻繁地對(duì)數(shù)據(jù)庫(kù)進(jìn)行 exists 查詢，當(dāng)系統(tǒng)并發(fā)量很高時(shí)，數(shù)據(jù)庫(kù)是很難扛住壓力的。

碼哥，我可以使用緩存啊，把歷史數(shù)據(jù)存在 Redis 中。

萬(wàn)萬(wàn)不可，這么多的歷史記錄那要浪費(fèi)多大的內(nèi)存空間，所以這個(gè)時(shí)候我們就能使用布隆過(guò)濾器去解決這種去重問(wèn)題。又快又省內(nèi)存，互聯(lián)網(wǎng)開(kāi)發(fā)必備殺招！

當(dāng)你遇到數(shù)據(jù)量大，又需要去重的時(shí)候就可以考慮布隆過(guò)濾器，如下場(chǎng)景：

解決?Redis 緩存穿透問(wèn)題（面試重點(diǎn)）；
郵件過(guò)濾，使用布隆過(guò)濾器實(shí)現(xiàn)郵件黑名單過(guò)濾；
爬蟲(chóng)爬過(guò)的網(wǎng)站過(guò)濾，爬過(guò)的網(wǎng)站不再爬??；
推薦過(guò)的新聞不再推薦；

什么是布隆過(guò)濾器

布隆過(guò)濾器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出，它是一種 space efficient 的概率型數(shù)據(jù)結(jié)構(gòu)，用于判斷一個(gè)元素是否在集合中。

當(dāng)布隆過(guò)濾器說(shuō)，某個(gè)數(shù)據(jù)存在時(shí)，這個(gè)數(shù)據(jù)可能不存在；當(dāng)布隆過(guò)濾器說(shuō)，某個(gè)數(shù)據(jù)不存在時(shí)，那么這個(gè)數(shù)據(jù)一定不存在。

哈希表也能用于判斷元素是否在集合中，但是布隆過(guò)濾器只需要哈希表的 1/8 或 1/4 的空間復(fù)雜度就能完成同樣的問(wèn)題。

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

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

布隆過(guò)濾器原理

BloomFilter 的算法是，首先分配一塊內(nèi)存空間做 bit 數(shù)組，數(shù)組的 bit 位初始值全部設(shè)為 0。

加入元素時(shí)，采用 k 個(gè)相互獨(dú)立的 Hash 函數(shù)計(jì)算，然后將元素 Hash 映射的 K 個(gè)位置全部設(shè)置為 1。

檢測(cè) key 是否存在，仍然用這 k 個(gè) Hash 函數(shù)計(jì)算出 k 個(gè)位置，如果位置全部為 1，則表明 key 存在，否則不存在。

如下圖所示：

哈希函數(shù)會(huì)出現(xiàn)碰撞，所以布隆過(guò)濾器會(huì)存在誤判。

這里的誤判率是指，BloomFilter 判斷某個(gè) key 存在，但它實(shí)際不存在的概率，因?yàn)樗娴氖?key 的 Hash 值，而非 key 的值。

所以有概率存在這樣的 key，它們內(nèi)容不同，但多次 Hash 后的 Hash 值都相同。

對(duì)于 BloomFilter 判斷不存在的 key ，則是 100% 不存在的，反證法，如果這個(gè) key 存在，那它每次 Hash 后對(duì)應(yīng)的 Hash 值位置肯定是 1，而不會(huì)是 0。布隆過(guò)濾器判斷存在不一定真的存在。

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

刪除意味著需要將對(duì)應(yīng)的 k 個(gè) bits 位置設(shè)置為 0，其中有可能是其他元素對(duì)應(yīng)的位。

因此 remove 會(huì)引入 false negative，這是絕對(duì)不被允許的。

Redis 集成布隆過(guò)濾器

Redis 4.0 的時(shí)候官方提供了插件機(jī)制，布隆過(guò)濾器正式登場(chǎng)。以下網(wǎng)站可以下載官方提供的已經(jīng)編譯好的可拓展模塊。

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

碼哥推薦使用 Redis 版本 6.x，最低 4.x 來(lái)集成布隆過(guò)濾器。如下指令查看版本，碼哥安裝的版本是 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

編譯成功，會(huì)看到?redisbloom.so?文件。

安裝集成

需要修改 redis.conf 文件，新增?loadmodule配置，并重啟 Redis。

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

如果是集群，則每個(gè)實(shí)例的配置文件都需要加入配置。

指定配置文件并啟動(dòng) Redis：

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

加載成功的頁(yè)面如下：

客戶端連接 Redis 測(cè)試。

BF.ADD?--添加一個(gè)元素到布隆過(guò)濾器
BF.EXISTS?--判斷元素是否在布隆過(guò)濾器
BF.MADD?--添加多個(gè)元素到布隆過(guò)濾器
BF.MEXISTS?--判斷多個(gè)元素是否在布隆過(guò)濾器

Redis 布隆過(guò)濾器實(shí)戰(zhàn)

我們來(lái)用布隆過(guò)濾器來(lái)解決緩存穿透問(wèn)題，緩存穿透：意味著有特殊請(qǐng)求在查詢一個(gè)不存在的數(shù)據(jù)，即數(shù)據(jù)不存在 Redis 也不存在于數(shù)據(jù)庫(kù)。

當(dāng)用戶購(gòu)買商品創(chuàng)建訂單的時(shí)候，我們往 mq 發(fā)送消息，把訂單 ID 添加到布隆過(guò)濾器。

在添加到布隆過(guò)濾器之前，我們通過(guò)BF.RESERVE命令手動(dòng)創(chuàng)建一個(gè)名字為?orders?error_rate = 0.1 ，初始容量為 10000000 的布隆過(guò)濾器：

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

key：filter 的名字；
error_rate：期望的錯(cuò)誤率，默認(rèn) 0.1，值越低，需要的空間越大；
capacity：初始容量，默認(rèn) 100，當(dāng)實(shí)際元素的數(shù)量超過(guò)這個(gè)初始化容量時(shí)，誤判率上升。
EXPANSION：可選參數(shù)，當(dāng)添加到布隆過(guò)濾器中的數(shù)據(jù)達(dá)到初始容量后，布隆過(guò)濾器會(huì)自動(dòng)創(chuàng)建一個(gè)子過(guò)濾器，子過(guò)濾器的大小是上一個(gè)過(guò)濾器大小乘以 expansion；expansion 的默認(rèn)值是 2，也就是說(shuō)布隆過(guò)濾器擴(kuò)容默認(rèn)是 2 倍擴(kuò)容；
NONSCALING：可選參數(shù)，設(shè)置此項(xiàng)后，當(dāng)添加到布隆過(guò)濾器中的數(shù)據(jù)達(dá)到初始容量后，不會(huì)擴(kuò)容過(guò)濾器，并且會(huì)拋出異常（(error) ERR non scaling filter is full）說(shuō)明：BloomFilter 的擴(kuò)容是通過(guò)增加 BloomFilter 的層數(shù)來(lái)完成的。每增加一層，在查詢的時(shí)候就可能會(huì)遍歷多層 BloomFilter 來(lái)完成，每一層的容量都是上一層的兩倍（默認(rèn)）。

如果不使用BF.RESERVE命令創(chuàng)建，而是使用 Redis 自動(dòng)創(chuàng)建的布隆過(guò)濾器，默認(rèn)的?error_rate?是?0.01，capacity是 100。

布隆過(guò)濾器的 error_rate 越小，需要的存儲(chǔ)空間就越大，對(duì)于不需要過(guò)于精確的場(chǎng)景，error_rate 設(shè)置稍大一點(diǎn)也可以。

布隆過(guò)濾器的 capacity 設(shè)置的過(guò)大，會(huì)浪費(fèi)存儲(chǔ)空間，設(shè)置的過(guò)小，就會(huì)影響準(zhǔn)確率，所以在使用之前一定要盡可能地精確估計(jì)好元素?cái)?shù)量，還需要加上一定的冗余空間以避免實(shí)際元素可能會(huì)意外高出設(shè)置值很多。

添加訂單 ID 到過(guò)濾器

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

使用?BF.ADD向名稱為?orders?的布隆過(guò)濾器添加 10086 這個(gè)元素。

如果是多個(gè)元素同時(shí)添加，則使用?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?判斷一個(gè)元素是否存在于BloomFilter，返回值 = 1 表示存在。

如果需要批量檢查多個(gè)元素是否存在于布隆過(guò)濾器則使用?BF.MEXISTS，返回值是一個(gè)數(shù)組：

1：存在；
0：不存在。

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

總體說(shuō)，我們通過(guò)BF.RESERVE、BF.ADD、BF.EXISTS三個(gè)指令就能實(shí)現(xiàn)避免緩存穿透問(wèn)題。

碼哥，如何查看創(chuàng)建的布隆過(guò)濾器信息呢？

用?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：預(yù)設(shè)容量；
Size：實(shí)際占用情況，但如何計(jì)算待進(jìn)一步確認(rèn)；
Number of filters：過(guò)濾器層數(shù)；
Number of items inserted：已經(jīng)實(shí)際插入的元素?cái)?shù)量；
Expansion rate：子過(guò)濾器擴(kuò)容系數(shù)（默認(rèn) 2）；

碼哥，如何刪除布隆過(guò)濾器呢？

目前布隆過(guò)濾器不支持刪除，布谷過(guò)濾器Cuckoo Filter是支持刪除的。

Bloom 過(guò)濾器在插入項(xiàng)目時(shí)通常表現(xiàn)出更好的性能和可伸縮性（因此，如果您經(jīng)常向數(shù)據(jù)集添加項(xiàng)目，那么 Bloom 過(guò)濾器可能是理想的）。布谷鳥(niǎo)過(guò)濾器在檢查操作上更快，也允許刪除。

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

碼哥，我想知道你是如何掌握這么多技術(shù)呢？

其實(shí)我也是翻閱官方文檔并做一些簡(jiǎn)單加工而已，這篇的文章內(nèi)容實(shí)戰(zhàn)就是基于 Redis 官方文檔上面的例子：https://oss.redis.com/redisbloom/。

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

Redission 布隆過(guò)濾器實(shí)戰(zhàn)

碼哥的樣例代碼基于 Spring Boot 2.1.4，代碼地址：https://github.com/MageByte-Zero/springboot-parent-pom。

添加 Redission 依賴：

<dependency>
??<groupId>org.redissongroupId>
??<artifactId>redisson-spring-boot-starterartifactId>
??<version>3.16.7version>
dependency>

使用 Spring boot 默認(rèn)的 Redis 配置方式配置 Redission：

spring:
??application:
????name:?redission

??redis:
????host:?127.0.0.1
????port:?6379
????ssl:?false

創(chuàng)建布隆過(guò)濾器

@Service
public?class?BloomFilterService?{

????@Autowired
????private?RedissonClient?redissonClient;

????/**
?????*?創(chuàng)建布隆過(guò)濾器
?????*?@param?filterName?過(guò)濾器名稱
?????*?@param?expectedInsertions?預(yù)測(cè)插入數(shù)量
?????*?@param?falseProbability?誤判率
?????*?@param?
?????*?@return
?????*/
????public??RBloomFilter?create(String?filterName,?long?expectedInsertions,?double?falseProbability)?{
????????RBloomFilter?bloomFilter?=?redissonClient.getBloomFilter(filterName);
????????bloomFilter.tryInit(expectedInsertions,?falseProbability);
????????return?bloomFilter;
????}

}

單元測(cè)試

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

????@Autowired
????private?BloomFilterService?bloomFilterService;

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

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

????????//?統(tǒng)計(jì)誤判次數(shù)
????????int?count?=?0;
????????for?(long?i?=?expectedInsertions;?i?2;?i++)?{
????????????if?(bloomFilter.contains(i))?{
????????????????count++;
????????????}
????????}
????????log.info("誤判次數(shù)?=?{}.",?count);
????????bloomFilter.delete();
????}
}

注意事項(xiàng)：如果是 Redis Cluster 集群，則需要?RClusteredBloomFilter bloomFilter = redisson.getClusteredBloomFilter("sample");

end

頂級(jí)程序員：topcoding

做最好的程序員社區(qū)：Java后端開(kāi)發(fā)、Python、大數(shù)據(jù)、AI

一鍵三連「分享」、「點(diǎn)贊」和「在看」

硬核 | Redis 布隆（Bloom Filter）過(guò)濾器原理與實(shí)戰(zhàn)