Redis系列1：深刻理解高性能Redis的本質(zhì)
Redis系列2：數(shù)據(jù)持久化提高可用性
Redis系列3：高可用之主從架構(gòu)
Redis系列4：高可用之Sentinel(哨兵模式）
Redis系列5：深入分析Cluster 集群模式
追求性能極致：Redis6.0的多線(xiàn)程模型
追求性能極致：客戶(hù)端緩存帶來(lái)的革命
Redis系列8：Bitmap實(shí)現(xiàn)億萬(wàn)級(jí)數(shù)據(jù)計(jì)算
Redis系列9：Geo 類(lèi)型賦能億級(jí)地圖位置計(jì)算
Redis系列10：HyperLogLog實(shí)現(xiàn)海量數(shù)據(jù)基數(shù)統(tǒng)計(jì)
Redis系列11：內(nèi)存淘汰策略
Redis系列12：Redis 的事務(wù)機(jī)制
Redis系列13：分布式鎖實(shí)現(xiàn)
Redis系列14：使用List實(shí)現(xiàn)消息隊(duì)列
Redis系列15：使用Stream實(shí)現(xiàn)消息隊(duì)列

1 Bloom Filter 介紹

布隆過(guò)濾器（Bloom Filter）是 Redis 4.0 版本提供的新功能，我們一般將它當(dāng)做插件加載到 Redis 服務(wù)器中，給 Redis 提供強(qiáng)大的去重功能。
它是一種概率性數(shù)據(jù)結(jié)構(gòu)，可用于判斷一個(gè)元素是否存在于一個(gè)集合中。相比較之 Set 集合的去重功能，布隆過(guò)濾器空間上能節(jié)省 90% +，不足之處是去重率大約在 99% 左右，那就是有 1% 左右的誤判率，這種誤差是由布隆過(guò)濾器的自身結(jié)構(gòu)決定的。

• 優(yōu)點(diǎn)：空間效率和查詢(xún)時(shí)間都比一般的算法要好的多
• 缺點(diǎn)：有一定的誤識(shí)別率和刪除困難

2 原理分析

布隆過(guò)濾器（Bloom Filter）是一個(gè)高空間利用率的概率性數(shù)據(jù)結(jié)構(gòu)，由二進(jìn)制向量（即位數(shù)組）和一系列隨機(jī)映射函數(shù)（即哈希函數(shù)）兩部分組成。
通過(guò)使用exists()來(lái)判斷某個(gè)元素是否存在于自身結(jié)構(gòu)中。當(dāng)布隆過(guò)濾器判定某個(gè)值存在時(shí)，其實(shí)這個(gè)值只是有可能存在；當(dāng)它說(shuō)某個(gè)值不存在時(shí)，那這個(gè)值肯定不存在，這個(gè)誤判概率大約在 1% 左右。
原理拆解如下：

• 在一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)的基礎(chǔ)上，將元素哈希成不同的位置，每個(gè)位置對(duì)應(yīng)二進(jìn)制向量中的一個(gè)比特位。
• 當(dāng)加入一個(gè)元素時(shí)，采用 n 個(gè)相互獨(dú)立的 Hash 函數(shù)計(jì)算key，然后將元素 Hash 映射的 n 個(gè)位置全部設(shè)置為 1。
• 檢測(cè) key 是否存在，仍然用 Hash 函數(shù)計(jì)算出這 n 個(gè)位置，如果元素key 存在于集合中，則對(duì)應(yīng)的位置為1，否則為0。
• 如果n個(gè)位置均為1的話(huà)，可以確定元素key可能存在于集合中；如果有一個(gè)為0，那么元素的key一定不存在于集合中，下面會(huì)詳細(xì)分析這句話(huà)。
• 這種判斷機(jī)制會(huì)存在誤判的可能，但它以較小的空間代價(jià)和極簡(jiǎn)的時(shí)間復(fù)雜度來(lái)近似解決集合交、并、差等操作。

2.1 添加元素步驟

當(dāng)使用布隆過(guò)濾器添加 key 時(shí)，會(huì)使用不同的 hash 函數(shù)對(duì) key 存儲(chǔ)的元素值進(jìn)行哈希計(jì)算，從而會(huì)得到多個(gè)哈希值。根據(jù)哈希值計(jì)算出一個(gè)整數(shù)索引值，將該索引值與位數(shù)組長(zhǎng)度做取余運(yùn)算，最終得到一個(gè)位數(shù)組位置，并將該位置的值變?yōu)?1。每個(gè) hash 函數(shù)都會(huì)計(jì)算出一個(gè)不同的位置，然后把數(shù)組中與之對(duì)應(yīng)的位置變?yōu)?1。這邊可能出現(xiàn)元素碰撞的情況，比如位置3，a元素和b元素的hash計(jì)算位置一致，所以出現(xiàn)了碰撞。

2.2 判定元素是否存在步驟

如果我們要判定一個(gè)元素是否存在，需要如下步驟：

• 首先對(duì)給定元素key執(zhí)行哈希計(jì)算，這樣可以得到元素增加時(shí)的bit位數(shù)組位置
• 判斷這些位置是否都為 1，如果其中有一個(gè)為 0，那么說(shuō)明元素不存在
• 若全部位置都為 1，則說(shuō)明元素有可能存在。

為啥說(shuō)是可能存在呢，因?yàn)樯厦嬲f(shuō)過(guò)了，哈希函數(shù)出的結(jié)果會(huì)出現(xiàn)碰撞，所以布隆過(guò)濾器會(huì)存在誤判。

如上圖c，他的位置被其他元素的位置完全覆蓋，即使c沒(méi)有存儲(chǔ)，對(duì)應(yīng)位置上也被a和b的Hash函數(shù)設(shè)置為1，這時(shí)候就可能誤判為c是有存儲(chǔ)的。
有概率存在這樣的 key，它們內(nèi)容不同，但多次 Hash 后的 Hash 值都相同。

2.3 元素刪除步驟

一般不會(huì)刪除元素，我們上面說(shuō)了，因?yàn)榭赡艽嬖谂鲎睬闆r，所以也有可能存在誤刪除情況。

刪除意味著需要將對(duì)應(yīng)的 n 個(gè) bits 位置設(shè)置為 0，其中有可能是其他元素對(duì)應(yīng)的位。
比如圖中的b刪除之后，位置3的值也被設(shè)置為0，這樣a也可能會(huì)被判定為不存在。

3 使用場(chǎng)景介紹

我們?cè)谟龅綌?shù)據(jù)量大的時(shí)候，為了去重并避免大批量的重復(fù)計(jì)算，可以考慮使用 Bloom Filter 進(jìn)行過(guò)濾。
具體常用的經(jīng)典場(chǎng)景如下：

• 解決大流量下緩存穿透的問(wèn)題，參考筆者這篇《一次緩存雪崩的災(zāi)難復(fù)盤(pán)》。
• 過(guò)濾被屏蔽、拉黑、減少推薦的信息，一般你在瀏覽抖音或者百度App的時(shí)候，看到不喜歡的會(huì)設(shè)置減少推薦、屏蔽此類(lèi)信息等，都可以采用這種原理設(shè)計(jì)。
• 各種名單過(guò)濾，使用布隆過(guò)濾器實(shí)現(xiàn)第一層的白名單或者黑名單過(guò)濾，可用于各種AB場(chǎng)景。

4 安裝集成

如果是自己編譯安裝，可以從 github 下載，目前的latest 的 release 版本是 v2.4.5，下載地址如下：
https://github.com/RedisBloom/RedisBloom/releases/tag/v2.4.5

直接按照編譯的方式進(jìn)行安裝：

# 解壓文件：
tar -zxvf tar -zxvf RedisBloom-2.4.5.tar.gz
# 進(jìn)入目錄：
cd RedisBloom-2.4.5
# 執(zhí)行編譯命令，生成redisbloom.so 文件：
make
# 拷貝至指定目錄：
cp redisbloom.so /usr/local/redis/RedisBloom-2.4.5/redisbloom.so

# 需要修改 redis.conf 文件，新增 loadmodule配置，并重啟 Redis。
# 在redis配置文件里加入以下配置：
loadmodule /usr/local/redis/RedisBloom-2.4.5/redisbloom.so

# 配置完成后重啟redis服務(wù)：
redis-server /usr/local/redis/RedisBloom-2.4.5/redis.conf

# 測(cè)試是否安裝成功
127.0.0.1:6379> bf.add user brand
(integer) 1
127.0.0.1:6379> bf.exists user brand
(integer) 1

5 總結(jié)

大致說(shuō)了布隆過(guò)濾器的原理和使用場(chǎng)景，下一篇我們來(lái)看看實(shí)戰(zhàn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-481139.html

到了這里，關(guān)于Redis系列16：聊聊布隆過(guò)濾器（原理篇）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！