python实现布隆过滤器及原理解析

在学习redis过程中提到一个缓存击穿的问题, 书中参考的解决方案之一是使用布隆过滤器, 那么就有必要来了解一下什么是布隆过滤器。在参考了许多博客之后, 写个总结记录一下。

一、布隆过滤器简介

什么是布隆过滤器?

本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。

布隆过滤器原理

布隆过滤器内部维护一个bitArray(位数组), 开始所有数据全部置 0 。当一个元素过来时,能过多个哈希函数(hash1,hash2,hash3....)计算不同的在哈希值,并通过哈希值找到对应的bitArray下标处,将里面的值 0 置为 1 。 需要说明的是,布隆过滤器有一个误判率的概念,误判率越低,则数组越长,所占空间越大。误判率越高则数组越小,所占的空间越小。

下面以网址为例来进行说明, 例如布隆过滤器的初始情况如下图所示:

现在我们需要往布隆过滤里中插入baidu这个url,经过3个哈希函数的计算,hash值分别为1,4,7,那么我们就需要对布隆过滤器的对应的bit位置1, 就如图下所示:

接下来,需要继续往布隆过滤器中添加tencent这个url,然后它计算出来的hash值分别3,4,8,继续往对应的bit位置1。这里就需要注意一个点, 上面两个url最后计算出来的hash值都有4,这个现象也是布隆不能确认某个元素一定存在的原因,最后如下图所示:

布隆过滤器的查询也很简单,例如我们需要查找python,只需要计算出它的hash值, 如果该值为2,4,7,那么因为对应bit位上的数据有一个不为1, 那么一定可以断言python不存在,但是如果它计算的hash值是1,3,7,那么就只能判断出python可能存在,这个例子就可以看出来, 我们没有存入python,但是由于其他key存储的时候返回的hash值正好将python计算出来的hash值对应的bit位占用了,这样就不能准确地判断出python是否存在。

因此, 随着添加的值越来越多, 被占的bit位越来越多, 这时候误判的可能性就开始变高,如果布隆过滤器所有bit位都被置为1的话,那么所有key都有可能存在, 这时候布隆过滤器也就失去了过滤的功能。至此,选择一个合适的过滤器长度就显得非常重要。

从上面布隆过滤器的实现原理可以看出,它不支持删除, 一旦将某个key对应的bit位置0,可能会导致同样bit位的其他key的存在性判断错误。

布隆过滤器的准确性

布隆过滤器的核心思想有两点:

多个hash,增大随机性,减少hash碰撞的概率扩大数组范围,使hash值均匀分布,进一步减少hash碰撞的概率。

虽然布隆过滤器已经尽可能的减小hash碰撞的概率了,但是,并不能彻底消除,因此正如上面的小例子所举的小例子的结果来看, 布隆过滤器只能告诉我们某样东西一定不存在以及它可能存在。

关于布隆过滤器的数组大小以及相应的hash函数个数的选择, 可以参考网上的其他博客或者是这个维基百科上对应词条上的结果: Probability of false positives .

上图的纵坐标p是误判率,横坐标n表示插入的元素个数,m表示布隆过滤器的bit长度,当然上图结果成立都假设hash函数的个数k满足条件k = (m/n)ln2(忽略k是整数)。

从上面的结果来看, 选择合适后误判率还是比较低的。

布隆过滤器的应用

  1. 网页爬虫对URL的去重,避免爬取相同的URL地址
  2. 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱(同理,垃圾短信)
  3. 缓存穿透,将所有可能存在的数据缓存放到布隆过滤器中,当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。
  4. 黑名单过滤,

二、python中使用布隆过滤器

  1. 先去这个网站下载bitarray这个依赖 https://www.lfd.uci.edu/~gohlke/pythonlibs/#bitarray
  2. 直接安装会报错error: Microsoft Visual C++ 14.0 is required. Get it with "Build Tools for Visual Studio": https://visualstudio.microsoft.com/downloads/
  3. 安装wheel文件, 防止我们主动安装报这样的错误pip3 install bitarray-1.1.0-cp36-cp36m-win_amd64.whl
  4. pip3 install pybloom_live

使用案例:

from pybloom_live import ScalableBloomFilter, BloomFilter

# 可自动扩容的布隆过滤器
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中使用布隆过滤器

详细的文档可以参考官方文档

这个模块不仅仅实现了布隆过滤器,还实现了 CuckooFilter(布谷鸟过滤器),以及 TopK功能。CuckooFilter是在 BloomFilter的基础上主要解决了BloomFilter不能删除的缺点。 下面只说明了布隆过滤器

安装

传统的redis服务器安装 RedisBloom 插件,详情可以参考centos中安装redis插件bloom-filter

我这里使用docker进行安装,简单快捷。

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}

创建一个空的名为key的布隆过滤器,并设置一个期望的错误率和初始大小。{error_rate}过滤器的错误率在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不存在,过滤器会自动创建。

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
# 上面已经存在的值再次添加会返回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这个模块来操作redis的布隆过滤器插件

pip3 install redisbloom

使用方法,参考官方给出的例子即可。https://github.com/RedisBloom/redisbloom-py

# 自己的简单使用
from redisbloom.client import Client

# 因为我使用的是虚拟机中docker的redis, 填写虚拟机的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个不存在的"""
 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%, 初始个数为size

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

if __name__ == '__main__':
 # The default error rate is 0.01 and the default initial capacity is 100.
 # 这个是默认的配置, 初始大小为100, 误差率默认为0.01
 _test1(1000)
 _test1(10000)
 _test1(100000)
 _test2(500000)
Copy
# 输出的结果

插入结束... 花费时间: 0.0409s
size: 1000, 误判元素个数: 14, 误判率1.4000%
查询结束... 花费时间: 0.0060s
******************************
插入结束... 花费时间: 0.1389s
size: 10000, 误判元素个数: 110, 误判率1.1000%
查询结束... 花费时间: 0.0628s
******************************
插入结束... 花费时间: 0.5372s
size: 100000, 误判元素个数: 1419, 误判率1.4190%
查询结束... 花费时间: 0.4318s
******************************
插入结束... 花费时间: 1.9484s
size: 500000, 误判元素个数: 152, 误判率0.0304%
查询结束... 花费时间: 2.2177s
******************************

如果想要布隆过滤器知道具体的耗费内存大小以及对应的错误率的信息, 可以使用查看这个布隆过滤器计算器计算出最后的结果。就如下面所示, 1kw数据, 误差为0.01%, 只需要23M内存。

五、缓存击穿

现在又回到开头的问题, 解决缓存击穿的问题。

什么是缓存击穿

我们通常使用redis作为数据缓存,当请求进来时先通过keyredis缓存查询,如果缓存中数据不存在,需要去查询数据库的数据。当数据库和缓存中都不存在的数据来查询时候,请求都打在数据库的请求中。如果这种请求量很大,会给数据库造成更大的压力进而影响系统的性能。

解决这类问题的方法

方法一:当DB和redis中都不存在key,在DB返回null时,在redis中插入`key再次请求时,redis直接返回null`,而不用再次请求DB。

方法二:使用redis提供的redisbloom,同样是将存在的key放入到过滤器中。当请求进来时,先去过滤器中校验是否存在,如果不存在直接返回null

黑名单的小例子

import redis
from redisbloom.client import Client

# 创建一个连接池来进行使用
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实现布隆过滤器及原理解析,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!

时间: 2019-12-05

Python Django模板之模板过滤器与自定义模板过滤器示例

本文实例讲述了Python Django模板之模板过滤器与自定义模板过滤器.分享给大家供大家参考,具体如下: 模板过滤器 过滤器用于对模板变量进行操作. date:改变日期的显示格式. length:求长度.字符串,列表. default:设置模板变量的默认值. 格式:模板变量|过滤器:参数 自定义过滤器. 自定义的过滤器函数,至少有一个参数,最多两个 例如: {{ book.btitle|length }} # 返回字符串或列表的长度 {{ book.bpub_date|date:'Y年-m月

对python过滤器和lambda函数的用法详解

1. 过滤器 Python 具有通过列表解析 将列表映射到其它列表的强大能力.这种能力同过滤机制结合使用,使列表中的有些元素被映射的同时跳过另外一些元素. 过滤列表语法: [ mapping-expression for element in source-list if filter-expression ] 这是列表解析的扩展,前三部分都是相同的,最后一部分,以 if开头的是过滤器表达式.过滤器表达式可以是返回值为真或者假的任何表达式 (在 Python 中是几乎任何东西).任何经过滤器表达

python 常见字符串与函数的用法详解

strip去除空格 s = ' abcd efg ' print(s.strip()) #去除所有空格 print(s.lstrip()) #去除左边空格 print(s.rstrip()) #去除右边空格 print(s) abcd efg abcd efg abcd efg abcd efg 大小写 s = 'abc defg' print(s.upper()) print(s.upper().lower()) print(s.capitalize()) #首字母大写 ABC DEFG ab

python 函数中的内置函数及用法详解

今天来介绍一下Python解释器包含的一系列的内置函数,下面表格按字母顺序列出了内置函数: 下面就一一介绍一下内置函数的用法: 1.abs() 返回一个数值的绝对值,可以是整数或浮点数等. print(abs(-18)) print(abs(0.15)) result: 18 0.15 2.all(iterable) 如果iterable的所有元素不为0.''.False或者iterable为空,all(iterable)返回True,否则返回False. print(all(['a','b',

Python Lambda函数使用总结详解

这篇文章主要介绍了Python Lambda函数使用总结详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 lambda表达式是一种匿名函数,对应python中的自定义函数def,是定义某个函数时比较高级的一种写法.作为python初学者,本文整理了lambda的一些基本用法和特点. lambda和def的对应关系 定义func函数,计算给定数x的平方 def func(x): return x*x 等价于 func = lambda x: x

Python中index()和seek()的用法(详解)

1.index() 一般用处是在序列中检索参数并返回第一次出现的索引,没找到就会报错,比如: >>> t=tuple('Allen') >>> t ('A', 'l', 'l', 'e', 'n') >>> t.index('a') Traceback (most recent call last): File "<pyshell#2>", line 1, in <module> t.index('a') V

python操作列表的函数使用代码详解

python的列表很重要,学习到后面你会发现使用的地方真的太多了.最近在写一些小项目时经常用到列表,有时其中的方法还会忘哎! 所以为了复习写下了这篇博客,大家也可以来学习一下,应该比较全面和详细了 列表(list): 用来存放相同或者不同元素(字符)用逗号隔开的一个存储方式. list我个人认为最重要的有一点大家可能都容易忽略那就是复制列表,这点文章最后来讲解 定义三个列表的样例 lis = [1, 2, 3, 4, 5, 6] lis = ['a', 'b', 'c', 'd'] lis =

对python中assert、isinstance的用法详解

1. assert 函数说明: Assert statements are a convenient way to insert debugging assertions into a program: assert语句是一种插入调试断点到程序的一种便捷的方式. 使用范例: assert 3 == 3 assert 1 == True assert (4 == 4) print('-----------') assert (3 == 4) ''' 抛出AssertionError异常,后面程序不

Python中 Global和Nonlocal的用法详解

nonlocal 和 global 也很容易混淆.简单记录下自己的理解. 解释 global 总之一句话,作用域是全局的,就是会修改这个变量对应地址的值. global 语句是一个声明,它适用于整个当前代码块. 这意味着列出的标识符将被解释为全局变量. 尽管自由变量可能指的是全局变量而不被声明为全局变量. global 语句中列出的名称不得用于该全局语句之前的文本代码块中. global 语句中列出的名称不能定义为形式参数,也不能在 for 循环控制目标. class 定义.函数定义. impo

Oracle中的INSTR,NVL和SUBSTR函数的用法详解

Oracle中INSTR的用法: INSTR方法的格式为 INSTR(源字符串, 要查找的字符串, 从第几个字符开始, 要找到第几个匹配的序号) 返回找到的位置,如果找不到则返回0. 例如:INSTR('CORPORATE FLOOR','OR', 3, 2)中,源字符串为'CORPORATE FLOOR', 在字符串中查找'OR',从第三个字符位置开始查找"OR",取第三个字后第2个匹配项的位置. 默认查找顺序为从左到右.当起始位置为负数的时候,从右边开始查找. 所以SELECT I

ES6中Array.find()和findIndex()函数的用法详解

ES6为Array增加了find(),findIndex函数. find()函数用来查找目标元素,找到就返回该元素,找不到返回undefined. findIndex()函数也是查找目标元素,找到就返回元素的位置,找不到就返回-1. 他们的都是一个查找回调函数. [1, 2, 3, 4].find((value, index, arr) => { }) 查找函数有三个参数. value:每一次迭代查找的数组元素. index:每一次迭代查找的数组元素索引. arr:被查找的数组. 例: 1.查找