亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

 更新時(shí)間:2018年10月18日 11:33:14   作者:JayChen  
這篇文章主要介紹了Redis 中的布隆過濾器的實(shí)現(xiàn),詳細(xì)的介紹了什么是布隆過濾器以及如何實(shí)現(xiàn),非常具有實(shí)用價(jià)值,需要的朋友可以參考下

什么是『布隆過濾器』

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

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

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

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

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

  • 使用 K 個(gè)哈希函數(shù)對元素值進(jìn)行 K 次計(jì)算,得到 K 個(gè)哈希值。
  • 根據(jù)得到的哈希值,在位數(shù)組中把對應(yīng)下標(biāo)的值置為 1。

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

  • 對值進(jìn)行三次哈希計(jì)算,得到三個(gè)值 n1, n2, n3。
  • 把位數(shù)組中三個(gè)元素 arr[n1], arr[n2], arr[3] 置為 1。

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

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

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

  • 布隆過濾器說某個(gè)元素在,可能會(huì)被誤判。
  • 布隆過濾器說某個(gè)元素不在,那么一定不在。

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

Redis 中的布隆過濾器

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

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

redis 布隆過濾器主要就兩個(gè)命令:

  • bf.add 添加元素到布隆過濾器中:bf.add urls https://jaychen.cc
  • bf.exists 判斷某個(gè)元素是否在過濾器中:bf.exists urls https://jaychen.cc。

上面說過布隆過濾器存在誤判的情況,在 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 urls 0.01 100

三個(gè)參數(shù)的含義:

  • 第一個(gè)值是過濾器的名字。
  • 第二個(gè)值為 error_rate 的值。
  • 第三個(gè)值為 initial_size 的值。

使用這個(gè)命令要注意一點(diǎn):執(zhí)行這個(gè)命令之前過濾器的名字應(yīng)該不存在,如果執(zhí)行之前就存在會(huì)報(bào)錯(cuò):(error) ERR item exists

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • Redis數(shù)據(jù)庫的安裝配置方法

    Redis數(shù)據(jù)庫的安裝配置方法

    redis 是一個(gè)高性能的key-value數(shù)據(jù)庫。 redis的出現(xiàn),很大程度補(bǔ)償了memcached這類keyvalue存儲(chǔ)的不足,在部 分場合可以對關(guān)系數(shù)據(jù)庫起到很好的補(bǔ)充作用。它提供了Python,Ruby,Erlang,PHP客戶端,使用很方便
    2014-06-06
  • redis中如何做到內(nèi)存優(yōu)化

    redis中如何做到內(nèi)存優(yōu)化

    為了提高數(shù)據(jù)處理效率和降低存儲(chǔ)成本,優(yōu)化數(shù)據(jù)結(jié)構(gòu)和采用高效的存儲(chǔ)策略至關(guān)重要,使用最小存儲(chǔ)形式、整數(shù)編碼、Redis的HyperLogLog等方法可以有效減少內(nèi)存占用,Redis6引入的對象壓縮、設(shè)置合理的過期時(shí)間、數(shù)據(jù)分片
    2024-09-09
  • CentOS系統(tǒng)安裝Redis及Redis的PHP擴(kuò)展詳解

    CentOS系統(tǒng)安裝Redis及Redis的PHP擴(kuò)展詳解

    這篇文章主要介紹了CentOS系統(tǒng)下安裝Redis數(shù)據(jù)的教程,以及詳解了Redis數(shù)據(jù)庫的PHP擴(kuò)展,文中介紹的很詳細(xì),相信對大家的理解和學(xué)習(xí)具有一定的參考借鑒價(jià)值,有需要的朋友們可以參考借鑒,下面來一起看看吧。
    2016-12-12
  • Redis主從/哨兵機(jī)制原理分析

    Redis主從/哨兵機(jī)制原理分析

    本文介紹了Redis的主從復(fù)制和哨兵機(jī)制,主從復(fù)制實(shí)現(xiàn)了數(shù)據(jù)的熱備份和負(fù)載均衡,而哨兵機(jī)制可以監(jiān)控Redis集群,實(shí)現(xiàn)自動(dòng)故障轉(zhuǎn)移,哨兵機(jī)制通過監(jiān)控、下線、選舉和故障轉(zhuǎn)移等步驟,確保Redis集群的高可用性
    2025-01-01
  • Redis 內(nèi)存淘汰策略深度解析(最新推薦)

    Redis 內(nèi)存淘汰策略深度解析(最新推薦)

    本文詳細(xì)探討了Redis的內(nèi)存淘汰策略、實(shí)現(xiàn)原理、適用場景及最佳實(shí)踐,介紹了八種內(nèi)存淘汰策略,包括noeviction、LRU、LFU、TTL、Random等,并分析了它們的應(yīng)用場景,同時(shí),文章還介紹了Redis內(nèi)存淘汰的底層實(shí)現(xiàn),包括LRU/LFU的近似算法和淘汰流程,感興趣的朋友一起看看吧
    2025-03-03
  • AOP?Redis自定義注解實(shí)現(xiàn)細(xì)粒度接口IP訪問限制

    AOP?Redis自定義注解實(shí)現(xiàn)細(xì)粒度接口IP訪問限制

    這篇文章主要為大家介紹了AOP?Redis自定義注解實(shí)現(xiàn)細(xì)粒度接口IP訪問限制,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-10-10
  • python中使用redis用法詳解

    python中使用redis用法詳解

    Redis擁有豐富的數(shù)據(jù)結(jié)構(gòu),擁有事務(wù)功能,保證命令的原子性。由于是內(nèi)存數(shù)據(jù)庫,讀寫非常高速,可達(dá)10w/s的評(píng)率,所以一般應(yīng)用于數(shù)據(jù)變化快、實(shí)時(shí)通訊、緩存等。這篇文章給大家講解一下Python如何使用Redis,并進(jìn)行相關(guān)的實(shí)戰(zhàn)操作。
    2022-12-12
  • redis使用zset實(shí)現(xiàn)延時(shí)隊(duì)列的示例代碼

    redis使用zset實(shí)現(xiàn)延時(shí)隊(duì)列的示例代碼

    本文主要介紹了redis使用zset實(shí)現(xiàn)延時(shí)隊(duì)列的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • redis間歇性斷連解決方式

    redis間歇性斷連解決方式

    本文主要介紹了在使用lettuce4.2.2.Final版本作為Redis客戶端時(shí)遇到的間歇性斷連問題,具有一定的參考價(jià)值,感興趣的可以了解一下
    2025-03-03
  • Redis持久化解讀

    Redis持久化解讀

    Redis是一種內(nèi)存級(jí)數(shù)據(jù)庫,提供高速讀寫性能,但數(shù)據(jù)易失,它支持三種持久化方式:RDB(快照持久化)、AOF(追加文件持久化)和混合持久化,RDB通過快照將數(shù)據(jù)保存到磁盤,AOF記錄所有寫操作命令,混合持久化結(jié)合兩者優(yōu)點(diǎn)
    2025-01-01

最新評(píng)論