主頁 > 知識庫 > Redis實現(xiàn)布隆過濾器的方法及原理

Redis實現(xiàn)布隆過濾器的方法及原理

熱門標(biāo)簽:地圖標(biāo)注工廠入駐 四川穩(wěn)定外呼系統(tǒng)軟件 b2b外呼系統(tǒng) 高碑店市地圖標(biāo)注app 400電話辦理的口碑 南京手機(jī)外呼系統(tǒng)廠家 臺灣電銷 一個地圖標(biāo)注多少錢 廊坊外呼系統(tǒng)在哪買

布隆過濾器(Bloom Filter)是1970年由布隆提出的。它實際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多,缺點是有一定的誤識別率和刪除困難。

本文將介紹布隆過濾器的原理以及Redis如何實現(xiàn)布隆過濾器。

應(yīng)用場景

1、50億個電話號碼,現(xiàn)有10萬個電話號碼,如何判斷這10萬個是否已經(jīng)存在在50億個之中?(可能方案:數(shù)據(jù)庫,set, hyperloglog)
2、新聞客戶端看新聞時,它會不斷推薦新的內(nèi)容,每次推薦時都要去重,那么如何實現(xiàn)推送去重?
3、爬蟲URL去重?
4、NoSQL數(shù)據(jù)庫領(lǐng)域降低數(shù)據(jù)庫的IO請求數(shù)量?
5、郵箱系統(tǒng)的垃圾郵件過濾?

布隆過濾器(Bloom Filter)就是專門來解決這種問題的,它起到去重的同時,在空間上還能節(jié)省90%以上,只是存在一定的誤判概率。

認(rèn)識布隆過濾器

布隆過濾器是一種類似set的數(shù)據(jù)結(jié)構(gòu),只是不太準(zhǔn)確,當(dāng)用bf.exists判斷元素是否存在時返回結(jié)果存在但真實不一定存在;當(dāng)返回不存在時肯定是不存在,所以判斷去重時有一定的誤判概率。
當(dāng)然,誤判只會發(fā)生在過濾器沒有添加過的元素,對于添加過的元素不會發(fā)生誤判。
特點:高效地插入和查詢,占用空間少,返回的結(jié)果是不確定性的。

布隆過濾器原理

每個布隆過濾器對應(yīng)到Redis的數(shù)據(jù)結(jié)構(gòu)中就是一個大型的位數(shù)組和幾個不同的無偏hash函數(shù),無偏表示分布均勻。

添加key時,使用多個hash函數(shù)對key進(jìn)行hash運(yùn)算得到一個整數(shù)索引值,對位數(shù)組長度進(jìn)行取模運(yùn)算得到一個位置,每個hash函數(shù)都會得到一個不同的位置,將這幾個位置都置1就完成了add操作。

查詢同理,只要有一位是0就表示這個key不存在,但如果都是1,則不一定存在對應(yīng)的key。

空間占用估計

布隆過濾器的空間占用有一個簡單的計算公式,但推導(dǎo)比較繁瑣。布隆過濾器有兩個參數(shù),預(yù)計元素數(shù)量n,錯誤率f,公式得到兩個輸出,位數(shù)組長度L(即存儲空間大小bit),hash函數(shù)的最佳數(shù)量k。

k = 0.7*(1/n)
f = 0.6185^(L/n)

1、位數(shù)組相對長度越長,錯誤率越低;
2、位數(shù)組相對長度越長,需要的hash函數(shù)越多;
3、當(dāng)一個元素平均需要一個字節(jié)(8bit)的指紋空間時(L/n=8),錯誤率大約為2%。

實際元素超出時,誤判率會怎樣變化?

f = (1-0.5^t)^k  # t為實際元素與預(yù)計元素的倍數(shù)
1、當(dāng)錯誤率為10%時,倍數(shù)比為2時,錯誤率接近40%;
2、當(dāng)錯誤率為1%,倍數(shù)比為2時,錯誤率15%;
3、當(dāng)錯誤率為0.1%,倍數(shù)為2時,錯誤率5%

Redis實現(xiàn)簡單Bloom Filter

要想使用redis提供的布隆過濾器,必須添加redis 4.0版本以上的插件才行,具體參照網(wǎng)上安裝步驟。

布隆過濾器有兩個基本指令,bf.add添加元素,bf.exists查詢元素是否存在,bf.madd一次添加多個元素,bf.mexists一次查詢多個元素。

> 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

布隆過濾器在第一次add的時候自動創(chuàng)建基于默認(rèn)參數(shù)的過濾器,Redis還提供了自定義參數(shù)的布隆過濾器。

在add之前使用bf.reserve指令顯式創(chuàng)建,其有3個參數(shù),key,error_rate, initial_size,錯誤率越低,需要的空間越大,error_rate表示預(yù)計錯誤率,initial_size參數(shù)表示預(yù)計放入的元素數(shù)量,當(dāng)實際數(shù)量超過這個值時,誤判率會上升,所以需要提前設(shè)置一個較大的數(shù)值來避免超出。

默認(rèn)的error_rate是0.01,initial_size是100。

利用布隆過濾器減少磁盤 IO 或者網(wǎng)絡(luò)請求,因為一旦一個值必定不存在的話,我們可以不用進(jìn)行后續(xù)昂貴的查詢請求。

總結(jié)

以上所述是小編給大家介紹的Redis實現(xiàn)布隆過濾器的方法及原理,希望對大家有所幫助,如果大家有任何疑問歡迎給我留言,小編會及時回復(fù)大家的!

您可能感興趣的文章:
  • Redis使用元素刪除的布隆過濾器來解決緩存穿透問題
  • 布隆過濾器(bloom filter)及php和redis實現(xiàn)布隆過濾器的方法
  • Redis 中的布隆過濾器的實現(xiàn)
  • Redis BloomFilter實例講解

標(biāo)簽:定州 南寧 畢節(jié) 泰州 伊春 拉薩 河源 甘南

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《Redis實現(xiàn)布隆過濾器的方法及原理》,本文關(guān)鍵詞  Redis,實現(xiàn),布隆,過濾器,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《Redis實現(xiàn)布隆過濾器的方法及原理》相關(guān)的同類信息!
  • 本頁收集關(guān)于Redis實現(xiàn)布隆過濾器的方法及原理的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章