系列文章
布隆過濾器是什么？
布隆過濾器可以理解為一個(gè)不怎么精確的 set 結(jié)構(gòu)，當(dāng)你使用它的 contains 方法判斷某個(gè)對象是否存在時(shí)，它可能會(huì)誤判。但是布隆過濾器也不是特別不精確，只要參數(shù)設(shè)置的合理，它的精確度可以控制的相對足夠精確，只會(huì)有小小的誤判概率。
當(dāng)布隆過濾器說某個(gè)值存在時(shí)，這個(gè)值可能不存在；當(dāng)它說不存在時(shí)，那就肯定不存在。打個(gè)比方，當(dāng)它說不認(rèn)識你時(shí)，肯定就不認(rèn)識；當(dāng)它說見過你時(shí)，可能根本就沒見過面，不過因?yàn)槟愕哪樃J(rèn)識的人中某臉比較相似 (某些熟臉的系數(shù)組合)，所以誤判以前見過你。
套在上面的使用場景中，布隆過濾器能準(zhǔn)確過濾掉那些已經(jīng)看過的內(nèi)容，那些沒有看過的新內(nèi)容，它也會(huì)過濾掉極小一部分 (誤判)，但是絕大多數(shù)新內(nèi)容它都能準(zhǔn)確識別。這樣就可以完全保證推薦給用戶的內(nèi)容都是無重復(fù)的。
布隆過濾器的原理
其本質(zhì)就是一個(gè)只包含0和1的數(shù)組。具體操作當(dāng)一個(gè)元素被加入到集合里面后，該元素通過K個(gè)Hash函數(shù)運(yùn)算得到K個(gè)hash后的值，然后將K個(gè)值映射到這個(gè)位數(shù)組對應(yīng)的位置，把對應(yīng)位置的值設(shè)置為1。查詢是否存在時(shí)，我們就看對應(yīng)的映射點(diǎn)位置如果全是1，他就很可能存在（跟hash函數(shù)的個(gè)數(shù)和hash函數(shù)的設(shè)計(jì)有關(guān)），如果有一個(gè)位置是0，那這個(gè)元素就一定不存在。
Redis 中的布隆過濾器
Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場。布隆過濾器作為一個(gè)插件加載到 Redis Server 中，給 Redis 提供了強(qiáng)大的布隆去重功能。
你可以使用docker鏡像來體驗(yàn)
> docker pull redislabs/rebloom # 拉取鏡像
> docker run -p6379:6379 redislabs/rebloom # 運(yùn)行容器
> redis-cli # 連接容器中的 redis 服務(wù)
當(dāng)然你也可以自己編譯安裝
下載編譯安裝Rebloom插件
wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz
解壓 tar zxvf v1.1.1.tar.gz
cd rebloom-1.1.1
make
redis服啟動(dòng)添加對應(yīng)參數(shù)
rebloom_module="/usr/local/rebloom/rebloom.so"
daemon --user ${REDIS_USER-redis} "$exec $REDIS_CONFIG --loadmodule $rebloom_module --daemonize yes --pidfile $pidfile"
重啟redis服務(wù)
測試命令
bf.add test testValue
命令成功說明開啟成功
布隆過濾器基本使用
主要命令有
- bf.add 添加元素
- bf.exists 查詢元素是否存在
- bf.madd 一次添加多個(gè)元素
- bf.mexists 一次查詢多個(gè)元素是否存在
在 redis 中有兩個(gè)值決定布隆過濾器的準(zhǔn)確率：
- error_rate：允許布隆過濾器的錯(cuò)誤率，這個(gè)值越低過濾器的位數(shù)組的大小越大，占用空間也就越大。
- initial_size：布隆過濾器可以儲(chǔ)存的元素個(gè)數(shù)，當(dāng)實(shí)際存儲(chǔ)的元素個(gè)數(shù)超過這個(gè)值之后，過濾器的準(zhǔn)確率會(huì)下降。
redis 中有一個(gè)命令可以來設(shè)置這兩個(gè)值：
bf.reserve test 0.01 100
- 第一個(gè)值是過濾器的名字。
- 第二個(gè)值為 error_rate 的值。
- 第三個(gè)值為 initial_size 的值。
注意必須在add之前使用bf.reserve指令顯式創(chuàng)建，如果對應(yīng)的 key 已經(jīng)存在，bf.reserve會(huì)報(bào)錯(cuò)。同時(shí)設(shè)置的錯(cuò)誤率越低，需要的空間越大。如果不使用 bf.reserve，默認(rèn)的error_rate是 0.01，默認(rèn)的initial_size是 100。
應(yīng)用場景
主要是解決大規(guī)模數(shù)據(jù)下不需要精確過濾的場景，如檢查垃圾郵件地址，爬蟲URL地址去重，解決緩存穿透問題等。
延伸閱讀
布隆過濾器 (Bloom Filter) 詳解
布谷鳥過濾器
本文亦在微信公眾號【小道資訊】發(fā)布，歡迎掃碼關(guān)注！
