建站
咨詢
售后
建站咨詢
新聞中心
小編給大家分享一下Redis如何實(shí)現(xiàn)布隆過(guò)濾器，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。
本文將介紹布隆過(guò)濾器的原理以及Redis如何實(shí)現(xiàn)布隆過(guò)濾器。
應(yīng)用場(chǎng)景
1、50億個(gè)電話號(hào)碼，現(xiàn)有10萬(wàn)個(gè)電話號(hào)碼，如何判斷這10萬(wàn)個(gè)是否已經(jīng)存在在50億個(gè)之中？（可能方案：數(shù)據(jù)庫(kù)，set, hyperloglog）
2、新聞客戶端看新聞時(shí)，它會(huì)不斷推薦新的內(nèi)容，每次推薦時(shí)都要去重，那么如何實(shí)現(xiàn)推送去重？
3、爬蟲(chóng)URL去重？
4、NoSQL數(shù)據(jù)庫(kù)領(lǐng)域降低數(shù)據(jù)庫(kù)的IO請(qǐng)求數(shù)量？
5、郵箱系統(tǒng)的垃圾郵件過(guò)濾？
布隆過(guò)濾器（Bloom Filter）就是專(zhuān)門(mén)來(lái)解決這種問(wèn)題的，它起到去重的同時(shí)，在空間上還能節(jié)省90%以上，只是存在一定的誤判概率。
認(rèn)識(shí)布隆過(guò)濾器
布隆過(guò)濾器是一種類(lèi)似set的數(shù)據(jù)結(jié)構(gòu)，只是不太準(zhǔn)確，當(dāng)用bf.exists判斷元素是否存在時(shí)返回結(jié)果存在但真實(shí)不一定存在；當(dāng)返回不存在時(shí)肯定是不存在，所以判斷去重時(shí)有一定的誤判概率。
當(dāng)然，誤判只會(huì)發(fā)生在過(guò)濾器沒(méi)有添加過(guò)的元素，對(duì)于添加過(guò)的元素不會(huì)發(fā)生誤判。
特點(diǎn)：高效地插入和查詢，占用空間少，返回的結(jié)果是不確定性的。
布隆過(guò)濾器原理
每個(gè)布隆過(guò)濾器對(duì)應(yīng)到Redis的數(shù)據(jù)結(jié)構(gòu)中就是一個(gè)大型的位數(shù)組和幾個(gè)不同的無(wú)偏hash函數(shù)，無(wú)偏表示分布均勻。
添加key時(shí)，使用多個(gè)hash函數(shù)對(duì)key進(jìn)行hash運(yùn)算得到一個(gè)整數(shù)索引值，對(duì)位數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算得到一個(gè)位置，每個(gè)hash函數(shù)都會(huì)得到一個(gè)不同的位置，將這幾個(gè)位置都置1就完成了add操作。
查詢同理，只要有一位是0就表示這個(gè)key不存在，但如果都是1，則不一定存在對(duì)應(yīng)的key。
空間占用估計(jì)
布隆過(guò)濾器的空間占用有一個(gè)簡(jiǎn)單的計(jì)算公式，但推導(dǎo)比較繁瑣。布隆過(guò)濾器有兩個(gè)參數(shù)，預(yù)計(jì)元素?cái)?shù)量n，錯(cuò)誤率f，公式得到兩個(gè)輸出，位數(shù)組長(zhǎng)度L（即存儲(chǔ)空間大小bit），hash函數(shù)的最佳數(shù)量k。
k = 0.7*(1/n)
f = 0.6185^(L/n)
1、位數(shù)組相對(duì)長(zhǎng)度越長(zhǎng)，錯(cuò)誤率越低；
2、位數(shù)組相對(duì)長(zhǎng)度越長(zhǎng)，需要的hash函數(shù)越多；
3、當(dāng)一個(gè)元素平均需要一個(gè)字節(jié)（8bit）的指紋空間時(shí)（L/n=8)，錯(cuò)誤率大約為2%。
實(shí)際元素超出時(shí)，誤判率會(huì)怎樣變化？
f = (1-0.5^t)^k # t為實(shí)際元素與預(yù)計(jì)元素的倍數(shù)
1、當(dāng)錯(cuò)誤率為10%時(shí)，倍數(shù)比為2時(shí)，錯(cuò)誤率接近40%；
2、當(dāng)錯(cuò)誤率為1%，倍數(shù)比為2時(shí)，錯(cuò)誤率15%；
3、當(dāng)錯(cuò)誤率為0.1%，倍數(shù)為2時(shí)，錯(cuò)誤率5%
Redis實(shí)現(xiàn)簡(jiǎn)單Bloom Filter
要想使用redis提供的布隆過(guò)濾器，必須添加redis 4.0版本以上的插件才行，具體參照網(wǎng)上安裝步驟。
布隆過(guò)濾器有兩個(gè)基本指令，bf.add添加元素，bf.exists查詢?cè)厥欠翊嬖?，bf.madd一次添加多個(gè)元素，bf.mexists一次查詢多個(gè)元素。
> bf.add spiderurl www.baidu.com
> bf.exists spiderurl www.baidu.com
> bf.madd spiderurl www.sougou.com www.jd.com
> bf.mexists spiderurl www.jd.com www.taobao.com
布隆過(guò)濾器在第一次add的時(shí)候自動(dòng)創(chuàng)建基于默認(rèn)參數(shù)的過(guò)濾器，Redis還提供了自定義參數(shù)的布隆過(guò)濾器。
在add之前使用bf.reserve指令顯式創(chuàng)建，其有3個(gè)參數(shù)，key，error_rate， initial_size，錯(cuò)誤率越低，需要的空間越大，error_rate表示預(yù)計(jì)錯(cuò)誤率，initial_size參數(shù)表示預(yù)計(jì)放入的元素?cái)?shù)量，當(dāng)實(shí)際數(shù)量超過(guò)這個(gè)值時(shí)，誤判率會(huì)上升，所以需要提前設(shè)置一個(gè)較大的數(shù)值來(lái)避免超出。
默認(rèn)的error_rate是0.01，initial_size是100。
利用布隆過(guò)濾器減少磁盤(pán) IO 或者網(wǎng)絡(luò)請(qǐng)求，因?yàn)橐坏┮粋€(gè)值必定不存在的話，我們可以不用進(jìn)行后續(xù)昂貴的查詢請(qǐng)求。
以上是“Redis如何實(shí)現(xiàn)布隆過(guò)濾器”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計(jì)公司行業(yè)資訊頻道！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
名稱(chēng)欄目：Redis如何實(shí)現(xiàn)布隆過(guò)濾器-創(chuàng)新互聯(lián)
標(biāo)題URL：http://fisionsoft.com.cn/article/csjscs.html
