python如何實(shí)現(xiàn)布隆過濾器及原理解析

這篇文章主要介紹python如何實(shí)現(xiàn)布隆過濾器及原理解析，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

一、布隆過濾器簡介

什么是布隆過濾器？

本質(zhì)上布隆過濾器( BloomFilter )是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點(diǎn)是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”。

相比于傳統(tǒng)的 Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點(diǎn)是其返回的結(jié)果是概率性的，而不是確切的。

布隆過濾器原理

布隆過濾器內(nèi)部維護(hù)一個(gè)bitArray(位數(shù)組)， 開始所有數(shù)據(jù)全部置 0 。當(dāng)一個(gè)元素過來時(shí)，能過多個(gè)哈希函數(shù)（hash2,hash3,hash4....）計(jì)算不同的在哈希值，并通過哈希值找到對(duì)應(yīng)的bitArray下標(biāo)處，將里面的值 0 置為 1 。 需要說明的是，布隆過濾器有一個(gè)誤判率的概念，誤判率越低，則數(shù)組越長，所占空間越大。誤判率越高則數(shù)組越小，所占的空間越小。

下面以網(wǎng)址為例來進(jìn)行說明, 例如布隆過濾器的初始情況如下圖所示：

現(xiàn)在我們需要往布隆過濾里中插入baidu這個(gè)url，經(jīng)過3個(gè)哈希函數(shù)的計(jì)算，hash值分別為1，4，7，那么我們就需要對(duì)布隆過濾器的對(duì)應(yīng)的bit位置1， 就如圖下所示：

接下來，需要繼續(xù)往布隆過濾器中添加tencent這個(gè)url，然后它計(jì)算出來的hash值分別3，4，8，繼續(xù)往對(duì)應(yīng)的bit位置1。這里就需要注意一個(gè)點(diǎn)， 上面兩個(gè)url最后計(jì)算出來的hash值都有4，這個(gè)現(xiàn)象也是布隆不能確認(rèn)某個(gè)元素一定存在的原因，最后如下圖所示：

布隆過濾器的查詢也很簡單，例如我們需要查找python，只需要計(jì)算出它的hash值， 如果該值為2，4，7，那么因?yàn)閷?duì)應(yīng)bit位上的數(shù)據(jù)有一個(gè)不為1， 那么一定可以斷言python不存在，但是如果它計(jì)算的hash值是1，3，7，那么就只能判斷出python可能存在，這個(gè)例子就可以看出來， 我們沒有存入python，但是由于其他key存儲(chǔ)的時(shí)候返回的hash值正好將python計(jì)算出來的hash值對(duì)應(yīng)的bit位占用了，這樣就不能準(zhǔn)確地判斷出python是否存在。

因此， 隨著添加的值越來越多， 被占的bit位越來越多， 這時(shí)候誤判的可能性就開始變高，如果布隆過濾器所有bit位都被置為1的話，那么所有key都有可能存在， 這時(shí)候布隆過濾器也就失去了過濾的功能。至此，選擇一個(gè)合適的過濾器長度就顯得非常重要。

從上面布隆過濾器的實(shí)現(xiàn)原理可以看出，它不支持刪除， 一旦將某個(gè)key對(duì)應(yīng)的bit位置0，可能會(huì)導(dǎo)致同樣bit位的其他key的存在性判斷錯(cuò)誤。

布隆過濾器的準(zhǔn)確性

布隆過濾器的核心思想有兩點(diǎn)：

多個(gè)hash，增大隨機(jī)性，減少hash碰撞的概率擴(kuò)大數(shù)組范圍，使hash值均勻分布，進(jìn)一步減少hash碰撞的概率。

雖然布隆過濾器已經(jīng)盡可能的減小hash碰撞的概率了，但是，并不能徹底消除，因此正如上面的小例子所舉的小例子的結(jié)果來看， 布隆過濾器只能告訴我們某樣?xùn)|西一定不存在以及它可能存在。

關(guān)于布隆過濾器的數(shù)組大小以及相應(yīng)的hash函數(shù)個(gè)數(shù)的選擇， 可以參考網(wǎng)上的其他博客或者是這個(gè)維基百科上對(duì)應(yīng)詞條上的結(jié)果: Probability of false positives .

上圖的縱坐標(biāo)p是誤判率，橫坐標(biāo)n表示插入的元素個(gè)數(shù)，m表示布隆過濾器的bit長度，當(dāng)然上圖結(jié)果成立都假設(shè)hash函數(shù)的個(gè)數(shù)k滿足條件k = (m/n)ln2(忽略k是整數(shù))。

從上面的結(jié)果來看， 選擇合適后誤判率還是比較低的。

布隆過濾器的應(yīng)用

1. 網(wǎng)頁爬蟲對(duì)URL的去重，避免爬取相同的URL地址

2. 反垃圾郵件，從數(shù)十億個(gè)垃圾郵件列表中判斷某郵箱是否垃圾郵箱（同理，垃圾短信）

3. 緩存穿透，將所有可能存在的數(shù)據(jù)緩存放到布隆過濾器中，當(dāng)黑客訪問不存在的緩存時(shí)迅速返回避免緩存及DB掛掉。

4. 黑名單過濾，

二、python中使用布隆過濾器

1. 先去這個(gè)網(wǎng)站下載bitarray這個(gè)依賴 https://www.lfd.uci.edu/~gohlke/pythonlibs/#bitarray

2. 直接安裝會(huì)報(bào)錯(cuò)error: Microsoft Visual C++ 14.0 is required. Get it with "Build Tools for Visual Studio": https://visualstudio.microsoft.com/downloads/

3. 安裝wheel文件, 防止我們主動(dòng)安裝報(bào)這樣的錯(cuò)誤pip3 install bitarray-1.1.0-cp36-cp36m-win_amd64.whl

4. pip3 install pybloom_live

使用案例：

from pybloom_live import ScalableBloomFilter, BloomFilter

# 可自動(dòng)擴(kuò)容的布隆過濾器
bloom = ScalableBloomFilter(initial_capacity=100, error_rate=0.001)

url1 = 'http://www.baidu.com'
url2 = 'http://qq.com'

bloom.add(url1)
print(url1 in bloom)
print(url2 in bloom)
Copy
# BloomFilter 是定長的
from pybloom_live import BloomFilter

url1 = 'http://www.baidu.com'
url2 = 'http://qq.com'

bf = BloomFilter(capacity=1000)
bf.add(url1)
print(url1 in bf)
print(url2 in bf)

三、redis中使用布隆過濾器

詳細(xì)的文檔可以參考官方文檔。

這個(gè)模塊不僅僅實(shí)現(xiàn)了布隆過濾器，還實(shí)現(xiàn)了 CuckooFilter（布谷鳥過濾器），以及 TopK功能。CuckooFilter是在 BloomFilter的基礎(chǔ)上主要解決了BloomFilter不能刪除的缺點(diǎn)。 下面只說明了布隆過濾器

安裝

傳統(tǒng)的redis服務(wù)器安裝 RedisBloom 插件，詳情可以參考centos中安裝redis插件bloom-filter

我這里使用docker進(jìn)行安裝，簡單快捷。

docker pull redislabs/rebloom:latest
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
docker exec -it redis-redisbloom /bin/bash

命令

命令使用非常簡單。

reserve

bf.reserve {key} {error_rate} {size}

創(chuàng)建一個(gè)空的名為key的布隆過濾器，并設(shè)置一個(gè)期望的錯(cuò)誤率和初始大小。{error_rate}過濾器的錯(cuò)誤率在0-1之間，

127.0.0.1:6379> bf.reserve black_male 0.001 1000
OK

add, madd

bf.add {key} {item}

bf.madd {key} {item} [item…]

往過濾器中添加元素。如果key不存在，過濾器會(huì)自動(dòng)創(chuàng)建。

127.0.0.1:6379> bf.add test 123
(integer) 1
127.0.0.1:6379> bf.madd urls baidu google tencent
1) (integer) 0
2) (integer) 0
3) (integer) 1
# 上面已經(jīng)存在的值再次添加會(huì)返回0， 不存在則返回1

exists, mexists

bf.exists {key} {item}

bf.mexists {key} {item} [item…]

判斷過濾器中是否存在該元素，不存在返回0，存在返回1。

127.0.0.1:6379> bf.exists test 123
(integer) 1
127.0.0.1:6379> bf.mexists urls baidu google hello
1) (integer) 1
2) (integer) 1
3) (integer) 0

四、python程序中使用redisbloom

使用redisbloom這個(gè)模塊來操作redis的布隆過濾器插件

pip3 install redisbloom

使用方法，參考官方給出的例子即可。https://github.com/RedisBloom/redisbloom-py

# 自己的簡單使用
from redisbloom.client import Client

# 因?yàn)槲沂褂玫氖翘摂M機(jī)中docker的redis, 填寫虛擬機(jī)的ip地址和暴露的端口
rb = Client(host='192.168.12.78', port=6379)
rb.bfAdd('urls', 'baidu')
rb.bfAdd('urls', 'google')
print(rb.bfExists('urls', 'baidu')) # out: 1
print(rb.bfExists('urls', 'tencent')) # out: 0

rb.bfMAdd('urls', 'a', 'b')
print(rb.bfMExists('urls', 'google', 'baidu', 'tencent')) # out: [1, 1, 0]

誤判率的測試demo

def _test1(size, key='book'):
 """測試size個(gè)不存在的"""
 rb.delete(key) # 先清空原來的key
 insert(size, key)
 select(size, key)


def _test2(size, error=0.001, key='book'):
 """指定誤差率和初始大小的布隆過濾器"""
 rb.delete(key)

 rb.bfCreate(key, error, size) # 誤差率為0.1%， 初始個(gè)數(shù)為size

 insert(size, key)
 select(size, key)


if __name__ == '__main__':
 # The default error rate is 0.01 and the default initial capacity is 100.
 # 這個(gè)是默認(rèn)的配置， 初始大小為100， 誤差率默認(rèn)為0.01
 _test1(1000)
 _test1(10000)
 _test1(100000)
 _test2(500000)
Copy
# 輸出的結(jié)果

插入結(jié)束... 花費(fèi)時(shí)間: 0.0409s
size: 1000, 誤判元素個(gè)數(shù): 14, 誤判率1.4000%
查詢結(jié)束... 花費(fèi)時(shí)間: 0.0060s
******************************
插入結(jié)束... 花費(fèi)時(shí)間: 0.1389s
size: 10000, 誤判元素個(gè)數(shù): 110, 誤判率1.1000%
查詢結(jié)束... 花費(fèi)時(shí)間: 0.0628s
******************************
插入結(jié)束... 花費(fèi)時(shí)間: 0.5372s
size: 100000, 誤判元素個(gè)數(shù): 1419, 誤判率1.4190%
查詢結(jié)束... 花費(fèi)時(shí)間: 0.4318s
******************************
插入結(jié)束... 花費(fèi)時(shí)間: 1.9484s
size: 500000, 誤判元素個(gè)數(shù): 152, 誤判率0.0304%
查詢結(jié)束... 花費(fèi)時(shí)間: 2.2177s
******************************

如果想要布隆過濾器知道具體的耗費(fèi)內(nèi)存大小以及對(duì)應(yīng)的錯(cuò)誤率的信息， 可以使用查看這個(gè)布隆過濾器計(jì)算器計(jì)算出最后的結(jié)果。就如下面所示， 1kw數(shù)據(jù)， 誤差為0.01%， 只需要23M內(nèi)存。

五、緩存擊穿

現(xiàn)在又回到開頭的問題， 解決緩存擊穿的問題。

什么是緩存擊穿

我們通常使用redis作為數(shù)據(jù)緩存，當(dāng)請(qǐng)求進(jìn)來時(shí)先通過key去redis緩存查詢，如果緩存中數(shù)據(jù)不存在，需要去查詢數(shù)據(jù)庫的數(shù)據(jù)。當(dāng)數(shù)據(jù)庫和緩存中都不存在的數(shù)據(jù)來查詢時(shí)候，請(qǐng)求都打在數(shù)據(jù)庫的請(qǐng)求中。如果這種請(qǐng)求量很大，會(huì)給數(shù)據(jù)庫造成更大的壓力進(jìn)而影響系統(tǒng)的性能。

解決這類問題的方法

方法一:當(dāng)DB和redis中都不存在key，在DB返回null時(shí)，在redis中插入`當(dāng)key再次請(qǐng)求時(shí),redis直接返回null`，而不用再次請(qǐng)求DB。

方法二:使用redis提供的redisbloom，同樣是將存在的key放入到過濾器中。當(dāng)請(qǐng)求進(jìn)來時(shí)，先去過濾器中校驗(yàn)是否存在，如果不存在直接返回null。

黑名單的小例子

import redis
from redisbloom.client import Client

# 創(chuàng)建一個(gè)連接池來進(jìn)行使用
pool = redis.ConnectionPool(host='192.168.12.78', port=6379, max_connections=100)


def create_key(key, error, capacity):
 rb = Client(connection_pool=pool)
 rb.bfCreate(key, errorRate=error, capacity=capacity)


def get_item(key, item):
 """判斷是否存在"""
 rb = Client(connection_pool=pool)
 return rb.bfExists(key, item)


def add_item(key, item):
 """添加值"""
 rb = Client(connection_pool=pool)
 return rb.bfAdd(key, item)


if __name__ == '__main__':
 # 添加黑名單, 誤差為0.001， 大小為1000
 create_key('blacklist', 0.001, 1000)
 add_item('blacklist', 'user:1')
 add_item('blacklist', 'user:2')
 add_item('blacklist', 'user:3')
 add_item('blacklist', 'user:4')
 print('user:1是否在黑名單-> ', get_item('blacklist', 'user:1'))
 print('user:2是否在黑名單-> ', get_item('blacklist', 'user:2'))
 print('user:6是否在黑名單-> ', get_item('blacklist', 'user:6'))

以上是“python如何實(shí)現(xiàn)布隆過濾器及原理解析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！