建站
咨詢
售后
建站咨詢
新聞中心
創(chuàng)新互聯(lián)長(zhǎng)期為上1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為寧河企業(yè)提供專(zhuān)業(yè)的網(wǎng)站制作、網(wǎng)站設(shè)計(jì)，寧河網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。
相比于 Set 集合的去重功能而言，布隆過(guò)濾器在空間上能節(jié)省 90% 以上，但是它的不足之處是去重率大約在 99% 左右，也就是說(shuō)有 1% 左右的誤判率，這種誤差是由布隆過(guò)濾器的自身結(jié)構(gòu)決定的。俗話說(shuō)“魚(yú)與熊掌不可兼得”，如果想要節(jié)省空間，就需要犧牲 1% 的誤判率，而且這種誤判率，在處理海量數(shù)據(jù)時(shí)，幾乎可以忽略。
應(yīng)用場(chǎng)景
布隆過(guò)濾器是 Redis 的高級(jí)功能，雖然這種結(jié)構(gòu)的去重率并不完全精確，但和其他結(jié)構(gòu)一樣都有特定的應(yīng)用場(chǎng)景，比如當(dāng)處理海量數(shù)據(jù)時(shí)，就可以使用布隆過(guò)濾器實(shí)現(xiàn)去重。
下面舉兩個(gè)簡(jiǎn)單的例子：
1) 示例：
百度爬蟲(chóng)系統(tǒng)每天會(huì)面臨海量的 URL 數(shù)據(jù)，我們希望它每次只爬取最新的頁(yè)面，而對(duì)于沒(méi)有更新過(guò)的頁(yè)面則不爬取，因策爬蟲(chóng)系統(tǒng)必須對(duì)已經(jīng)抓取過(guò)的 URL 去重，否則會(huì)嚴(yán)重影響執(zhí)行效率。但是如果使用一個(gè) set（集合）去裝載這些 URL 地址，那么將造成資源空間的嚴(yán)重浪費(fèi)。
2) 示例：
垃圾郵件過(guò)濾功能也采用了布隆過(guò)濾器。雖然在過(guò)濾的過(guò)程中，布隆過(guò)濾器會(huì)存在一定的誤判，但比較于犧牲寶貴的性能和空間來(lái)說(shuō)，這一點(diǎn)誤判是微不足道的。
工作原理
布隆過(guò)濾器（Bloom Filter）是一個(gè)高空間利用率的概率性數(shù)據(jù)結(jié)構(gòu)，由二進(jìn)制向量（即位數(shù)組）和一系列隨機(jī)映射函數(shù)（即哈希函數(shù)）兩部分組成。
布隆過(guò)濾器使用
exists()來(lái)判斷某個(gè)元素是否存在于自身結(jié)構(gòu)中。當(dāng)布隆過(guò)濾器判定某個(gè)值存在時(shí)，其實(shí)這個(gè)值只是有可能存在；當(dāng)它說(shuō)某個(gè)值不存在時(shí)，那這個(gè)值肯定不存在，這個(gè)誤判概率大約在 1% 左右。
1) 工作流程-添加元素
布隆過(guò)濾器主要由位數(shù)組和一系列 hash 函數(shù)構(gòu)成，其中位數(shù)組的初始狀態(tài)都為 0。
下面對(duì)布隆過(guò)濾器工作流程做簡(jiǎn)單描述，如下圖所示：
圖1：布隆過(guò)濾器原理
當(dāng)使用布隆過(guò)濾器添加 key 時(shí)，會(huì)使用不同的 hash 函數(shù)對(duì) key 存儲(chǔ)的元素值進(jìn)行哈希計(jì)算，從而會(huì)得到多個(gè)哈希值。根據(jù)哈希值計(jì)算出一個(gè)整數(shù)索引值，將該索引值與位數(shù)組長(zhǎng)度做取余運(yùn)算，最終得到一個(gè)位數(shù)組位置，并將該位置的值變?yōu)?1。每個(gè) hash 函數(shù)都會(huì)計(jì)算出一個(gè)不同的位置，然后把數(shù)組中與之對(duì)應(yīng)的位置變?yōu)?1。通過(guò)上述過(guò)程就完成了元素添加(add)操作。
2) 工作流程-判定元素是否存在
當(dāng)我們需要判斷一個(gè)元素是否存時(shí)，其流程如下：首先對(duì)給定元素再次執(zhí)行哈希計(jì)算，得到與添加元素時(shí)相同的位數(shù)組位置，判斷所得位置是否都為 1，如果其中有一個(gè)為 0，那么說(shuō)明元素不存在，若都為 1，則說(shuō)明元素有可能存在。
3) 為什么是可能“存在”
您可能會(huì)問(wèn)，為什么是有可能存在？其實(shí)原因很簡(jiǎn)單，那些被置為 1 的位置也可能是由于其他元素的操作而改變的。比如，元素1 和 元素2，這兩個(gè)元素同時(shí)將一個(gè)位置變?yōu)榱?1（圖1所示）。在這種情況下，我們就不能判定“元素 1”一定存在，這是布隆過(guò)濾器存在誤判的根本原因。
安裝與使用
在 Redis 4.0 版本之后，布隆過(guò)濾器才作為插件被正式使用。布隆過(guò)濾器需要單獨(dú)安裝，下面介紹安裝 RedisBloom 的幾種方法：
1) docker安裝
docker 安裝布隆過(guò)濾器是最簡(jiǎn)單、快捷的一種方式：
docker pull redislabs/rebloom:latest docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest docker exec -it redis-redisbloom bash redis-cli #測(cè)試是否安裝成功 127.0.0.1:6379> bf.add www.biancheng.net hello
2) 直接編譯安裝
如果您對(duì) docker 不熟悉，也可以采用直接編譯的方式來(lái)安裝。
下載地址： https://github.com/RedisBloom/RedisBloom 解壓文件： unzip RedisBloom-master.zip 進(jìn)入目錄： cd RedisBloom-master 執(zhí)行編譯命令，生成redisbloom.so 文件： make 拷貝至指定目錄： cp redisbloom.so /usr/local/redis/bin/redisbloom.so 在redis配置文件里加入以下配置： loadmodule /usr/local/redis/bin/redisbloom.so 配置完成后重啟redis服務(wù)： sudo /etc/init.d/redis-server restart #測(cè)試是否安裝成功 127.0.0.1:6379> bf.add www.biancheng.net hello
常用命令匯總
| 命令 | 說(shuō)明 |
|---|---|
| bf.add | 只能添加元素到布隆過(guò)濾器。 |
| bf.exists | 判斷某個(gè)元素是否在于布隆過(guò)濾器中。 |
| bf.madd | 同時(shí)添加多個(gè)元素到布隆過(guò)濾器。 |
| bf.mexists | 同時(shí)判斷多個(gè)元素是否存在于布隆過(guò)濾器中。 |
| bf.reserve | 以自定義的方式設(shè)置布隆過(guò)濾器參數(shù)值，共有 3 個(gè)參數(shù)分別是 key、error_rate(錯(cuò)誤率)、initial_size(初始大小)。 |
1) 命令應(yīng)用
127.0.0.1:6379> bf.add spider:url www.biancheng.net (integer) 1 127.0.0.1:6379> bf.exists spider:url www.biancheng.net (integer) 1 127.0.0.1:6379> bf.madd spider:url www.taobao.com www.123qq.com 1) (integer) 1 2) (integer) 1 127.0.0.1:6379> bf.mexists spider:url www.jd.com www.taobao.com 1) (integer) 0 2) (integer) 1
Python使用布隆過(guò)濾器
下面使用 Python 測(cè)試布隆過(guò)濾器的誤判率，代碼如下所示：
import redis
size=10000
r = redis.Redis()
count = 0
for i in range(size):
#添加元素，key為userid，值為user0...user9999
r.execute_command("bf.add", "userid", "user%d" % i)
#判斷元素是否存在，此處切記 i+1
res = r.execute_command("bf.exists", "userid", "user%d" % (i + 1))
if res == 1:
print(i)
count += 1
#求誤判率，round()中的5表示保留的小數(shù)點(diǎn)位數(shù)
print("size: {} ,error rate:{}%".format(size, round(count / size * 100, 5)))
執(zhí)行三次測(cè)試，size 從小到大。輸出結(jié)果如下：
size: 1000 , error rate: 1.0% size: 10000 , error rate: 1.25% size: 100000 , error rate: 1.305%
通過(guò)上述結(jié)果可以看出布隆過(guò)濾器的錯(cuò)誤率為 1% 多點(diǎn)，當(dāng) size 越來(lái)越大時(shí)，布隆過(guò)濾器的錯(cuò)誤率就會(huì)升高，那么有沒(méi)有辦法降低錯(cuò)誤率呢？這就用到了布隆過(guò)濾器提供的
bf.reserve方法。如果不使用該方法設(shè)置參數(shù)，那么布隆過(guò)濾器將按照默認(rèn)參數(shù)進(jìn)行設(shè)置，如下所示：
key #指定存儲(chǔ)元素的鍵，若已經(jīng)存在,則bf.reserve會(huì)報(bào)錯(cuò) error_rate=0.01 #表示錯(cuò)誤率 initial_size=100 #表示預(yù)計(jì)放入布隆過(guò)濾器中的元素?cái)?shù)量
當(dāng)放入過(guò)濾器中的元素?cái)?shù)量超過(guò)了 initial_size 值時(shí)，錯(cuò)誤率 error_rate 就會(huì)升高。因此就需要設(shè)置一個(gè)較大 initial_size 值，避免因數(shù)量超出導(dǎo)致的錯(cuò)誤率上升。
解決錯(cuò)誤率過(guò)高的問(wèn)題
錯(cuò)誤率越低，所需要的空間也會(huì)越大，因此就需要我們盡可能精確的估算元素?cái)?shù)量，避免空間的浪費(fèi)。我們也要根據(jù)具體的業(yè)務(wù)來(lái)確定錯(cuò)誤率的許可范圍，對(duì)于不需要太精確的業(yè)務(wù)場(chǎng)景，錯(cuò)誤率稍微設(shè)置大一點(diǎn)也可以。
注意：如果要使用自定義的布隆過(guò)濾器需要在 add 操作之前，使用 bf.reserve 命令顯式地創(chuàng)建 key，格式如下：
client.execute_command("bf.reserve", "keyname", 0.001, 50000)
布隆過(guò)濾器相比于平時(shí)常用的的列表、散列、集合等數(shù)據(jù)結(jié)構(gòu)，其占用空間更少、效率更高，但缺點(diǎn)就是返回的結(jié)果具有概率性，并不是很準(zhǔn)確。在理論情況下，添加的元素越多，誤報(bào)的可能性就越大。再者，存放于布隆過(guò)濾器中的元素不容易被刪除，因?yàn)榭赡艹霈F(xiàn)會(huì)誤刪其他元素情況。
分享名稱：Redis布隆過(guò)濾器（原理+圖解）
文章網(wǎng)址：http://fisionsoft.com.cn/article/djighsg.html
