Redis中布隆過濾器的實現(xiàn)

redis 中布隆過濾器的實現(xiàn)？相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

創(chuàng)新互聯(lián)公司服務項目包括安吉網(wǎng)站建設、安吉網(wǎng)站制作、安吉網(wǎng)頁制作以及安吉網(wǎng)絡營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，安吉網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務的客戶以成都為中心已經(jīng)輻射到安吉省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

什么是『布隆過濾器』

布隆過濾器是一個神奇的數(shù)據(jù)結(jié)構(gòu)，可以用來判斷一個元素是否在一個集合中。很常用的一個功能是用來去重。在爬蟲中常見的一個需求：目標網(wǎng)站 URL 千千萬，怎么判斷某個 URL 爬蟲是否寵幸過？簡單點可以爬蟲每采集過一個 URL，就把這個 URL 存入數(shù)據(jù)庫中，每次一個新的 URL 過來就到數(shù)據(jù)庫查詢下是否訪問過。

select id from table where url = 'https://jaychen.cc'

但是隨著爬蟲爬過的 URL 越來越多，每次請求前都要訪問數(shù)據(jù)庫一次，并且對于這種字符串的 SQL 查詢效率并不高。除了數(shù)據(jù)庫之外，使用 Redis 的 set 結(jié)構(gòu)也可以滿足這個需求，并且性能優(yōu)于數(shù)據(jù)庫。但是 Redis 也存在一個問題：耗費過多的內(nèi)存。這個時候布隆過濾器就很橫的出場了：這個問題讓我來。

相比于數(shù)據(jù)庫和 Redis，使用布隆過濾器可以很好的避免性能和內(nèi)存占用的問題。

布隆過濾器本質(zhì)是一個位數(shù)組，位數(shù)組就是數(shù)組的每個元素都只占用 1 bit 。每個元素只能是 0 或者 1。這樣申請一個 10000 個元素的位數(shù)組只占用 10000 / 8 = 1250 B 的空間。布隆過濾器除了一個位數(shù)組，還有 K 個哈希函數(shù)。當一個元素加入布隆過濾器中的時候，會進行如下操作：

• 使用 K 個哈希函數(shù)對元素值進行 K 次計算，得到 K 個哈希值。

• 根據(jù)得到的哈希值，在位數(shù)組中把對應下標的值置為 1。

舉個?，假設布隆過濾器有 3 個哈希函數(shù)：f1, f2, f3 和一個位數(shù)組 arr?，F(xiàn)在要把 https://jaychen.cc 插入布隆過濾器中：

• 對值進行三次哈希計算，得到三個值 n1, n2, n3。

• 把位數(shù)組中三個元素 arr[n1], arr[n2], arr[3] 置為 1。

當要判斷一個值是否在布隆過濾器中，對元素再次進行哈希計算，得到值之后判斷位數(shù)組中的每個元素是否都為 1，如果值都為 1，那么說明這個值在布隆過濾器中，如果存在一個值不為 1，說明該元素不在布隆過濾器中。

看不懂文字看下面的靈魂畫手的圖解釋???

看了上面的說明，必然會提出一個問題：當插入的元素原來越多，位數(shù)組中被置為 1 的位置就越多，當一個不在布隆過濾器中的元素，經(jīng)過哈希計算之后，得到的值在位數(shù)組中查詢，有可能這些位置也都被置為 1。這樣一個不存在布隆過濾器中的也有可能被誤判成在布隆過濾器中。但是如果布隆過濾器判斷說一個元素不在布隆過濾器中，那么這個值就一定不在布隆過濾器中。簡單來說：

• 布隆過濾器說某個元素在，可能會被誤判。

• 布隆過濾器說某個元素不在，那么一定不在。

這個布隆過濾器的缺陷放到上面爬蟲的需求中，可能存在某些沒有訪問過的 URL 可能會被誤判為訪問過，但是如果是訪問過的 URL 一定不會被誤判為沒訪問過。

Redis 中的布隆過濾器

redis 在 4.0 的版本中加入了 module 功能，布隆過濾器可以通過 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通過加載 module 來使用 redis 中的布隆過濾器。但是這不是最簡單的方式，使用 docker 可以直接在 redis 中體驗布隆過濾器。

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

redis 布隆過濾器主要就兩個命令：

• bf.add 添加元素到布隆過濾器中：bf.add urls https://jaychen.cc。

• bf.exists 判斷某個元素是否在過濾器中：bf.exists urls https://jaychen.cc。

上面說過布隆過濾器存在誤判的情況，在 redis 中有兩個值決定布隆過濾器的準確率：

• error_rate ：允許布隆過濾器的錯誤率，這個值越低過濾器的位數(shù)組的大小越大，占用空間也就越大。

• initial_size ：布隆過濾器可以儲存的元素個數(shù)，當實際存儲的元素個數(shù)超過這個值之后，過濾器的準確率會下降。

redis 中有一個命令可以來設置這兩個值：

bf.reserve urls 0.01 100

三個參數(shù)的含義：

• 第一個值是過濾器的名字。

• 第二個值為 error_rate 的值。

• 第三個值為 initial_size 的值。

使用這個命令要注意一點：執(zhí)行這個命令之前過濾器的名字應該不存在，如果執(zhí)行之前就存在會報錯：(error) ERR item exists

看完上述內(nèi)容，你們掌握Redis 中布隆過濾器的實現(xiàn)的方法了嗎？如果還想學到更多技能或想了解更多相關內(nèi)容，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

當前題目：Redis中布隆過濾器的實現(xiàn)
路徑分享：http://bm7419.com/article14/jcegge.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站設計、、ChatGPT、網(wǎng)站收錄、網(wǎng)站維護

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)