纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

python实现布隆过滤器及Redis缓存穿透 浅析python实现布隆过滤器及Redis中的缓存穿透原理

somenzz   2021-09-14 我要评论
想了解浅析python实现布隆过滤器及Redis中的缓存穿透原理的相关内容吗somenzz在本文为您仔细讲解python实现布隆过滤器及Redis缓存穿透的相关知识和一些Code实例欢迎阅读和指正我们先划重点:python实现布隆过滤器,Redis缓存穿透原理下面大家一起来学习吧

在开发软件时我们经常需要判断一个元素是否在一个集合中比如如何判断单词的拼写是否错误(判断单词是否在已知的字典中);在网络爬虫里如何确认一个网址是否已经爬取过;反垃圾邮件系统中如何判断一个邮件地址是否为垃圾邮件地址等等

如果这些作为面试题那就很有区分度了初级工程师就会说把全部的元素都存在 hash 表中当需要判断元素是否在集合中时可以直接判断时间复杂度是 O(1)比如 Python 的集合:

>>> all_elements = {'a','b','c','d','e'}
>>> 'a' in all_elements
True
>>> 'f' in all_elements
False
>>>

这样回答显然没有考虑到数量级的问题就拿爬虫中的 URL 去重来说假设一个 URL 的平均长度是 64 字节那单纯存储这 10 亿个 URL需要大约 60GB 的内存空间因为哈希表必须维持较小的装载因子才能保证不会出现过多的哈希冲突导致操作的性能下降而且用链表法解决冲突的哈希表还会存储链表指针因此哈希表的存储效率一般只有 50%所以如果将这 10 亿个 URL 构建成哈希表那需要的内存空间会超过 100GB这样的话一般的机器内存就不够用了更别提哈希查找了

因此考虑到这一点中级一点的工程师会说数据量大的时候可以采用分治的思想用多台机器(比如 20 台内存是 8GB 的机器)来存储这 10 亿网页链接这种分治的处理思路也是一种解决办法本质上还是增加硬件资源来解决问题还不够高级

更高级的工程师会提到位图、布隆过滤器可以使用很小的内存来实现大数据量的查询如果你提到了这两个概念那离 offer 也就不远了想回答好这个问题看本文就够了保证你搞懂布隆过滤器要是搞不懂你加我微信我会对你负责的????

在讲布隆过滤器前要先讲一下另一种存储结构位图(BitMap)因为布隆过滤器本身就是基于位图的是对位图的一种改进

同样地为了方便你理解我们来简化问题现在有 1 千万个整数整数的范围在 1 到 1 亿之间如何快速查找某个整数是否在这 1 千万个整数中呢?

当然这个问题还是可以用哈希表来解决不过我们可以使用一种比较“特殊”的哈希表那就是位图我们申请一个大小为 1 亿、数据类型为布尔类型(true 或者 false)的数组我们将这 1 千万个整数作为数组下标将对应的数组值设置成 true比如整数 5 对应下标为 5 的数组值设置为 true也就是 array[5]=true 

当我们查询某个整数 K 是否在这 1 千万个整数中的时候我们只需要将对应的数组值 array[K]取出来看是否等于 true如果等于 true那说明 1 千万整数中包含这个整数 K;相反就表示不包含这个整数 K不过很多语言中提供的布尔类型大小是 1 个字节的并不能节省太多内存空间实际上表示 true 和 false 两个值我们只需要用一个二进制位(bit)就可以了那如何通过编程语言来表示一个二进制位呢?

这个用语言很难表达还是给出代码吧一码胜千言啊

这里先给出 Java 的我觉得 Java 的更容易看懂再给出 Python 的你可以对比着代码看下应该很快就理解了

public class BitMap { // Java中char类型占16bit也即是2个字节
  private char[] bytes;
  private int nbits;  
  public BitMap(int nbits) {
    this.nbits = nbits;
    this.bytes = new char[nbits/16+1];
  } 
  public void set(int k) {
    if (k > nbits) return;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    bytes[byteIndex] |= (1 << bitIndex);
  } 
  public boolean get(int k) {
    if (k > nbits) return false;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    return (bytes[byteIndex] & (1 << bitIndex)) != 0;
  }
}

Python 的实现:

class BitMap(object):
    def __init__(self, max_value):
        """
        使用多个整型元素来储存数据每个元素4个字节(32位)
        """
        self._size = int((max_value + 31 - 1) / 31)  # 计算需要的字节数字节数也是数组的大小
        self.array = [0 for i in range(self._size)]  # 数组的元素都初始化为0每个元素有32位
    @staticmethod
    def get_element_index(num):
        """
        获取该数即将储存的字节在数组中下标
        """
        return num // 31 
    @staticmethod
    def get_bit_index(num):
        """
        获取该数在元素中的位下标
        """
        return num % 31
 
    def set(self, num):
        """
        将该数存在对应的元素的对应位置
        """
        element_index = self.get_element_index(num)
        bit_index = self.get_bit_index(num)
        self.array[element_index] = self.array[element_index] | (1 << bit_index)
    def get(self, num):
        """
        查找该数是否存在与bitmap中
        """
        element_index = self.get_element_index(num)
        bit_index = self.get_bit_index(num)
        if self.array[element_index] & (1 << bit_index):
            return True
        return False

从上面位图实现的代码中你应该可以发现位图通过数组下标来定位数据所以访问效率非常高而且每个数字用一个二进制位来表示在数字范围不大的情况下所需要的内存空间非常小

比如刚刚那个例子如果用哈希表存储这 1 千万的数据数据是 32 位的整型数每个整数 4 个字节那总共至少需要 1 千万 * 4  = 40MB 的存储空间如果我们通过位图的话数字范围在 1 到 1 亿之间只需要 1 亿个二进制位也就是 12MB 左右的存储空间就够了

位图就是用一个二进制位的 1 来代表一个元素存在是不是挺简单的?不过这里我们有个假设就是数字所在的范围不是很大如果数字的范围很大比如刚刚那个问题数字范围不是 1 到 1 亿而是 1 到 10 亿那位图的大小就需要 10 亿个二进制位也就是 120MB 的大小消耗的内存空间增加了 10 倍如何不增加内存空间来解决问题呢?请继续往下看

布隆过滤器的原理

这个时候布隆过滤器就要出场了布隆过滤器就是为了解决刚刚这个问题对位图这种数据结构的一种改进

布隆过滤器是由伯顿·布隆于 1970 年提出的为了简化说明布隆过滤器的原理我们降低数据量级:假如数字范围是从 1 到 100 提升到 200为了不占用太多内存我们依然使用 100 个二进制位如果数据个数超过 100 个就必然存在哈希冲突怎么办?

因为我们使用 1 位代表一个元素因此 100 个二进制位最多代表 100 个元素但是假如使用 2 位来代表一个元素呢?那就是组合 C(100,2) = 100*99/2 = 4950 个数是不是可以代表更多?当然了你还可以使用 3 位代表一个元素这样可以代表 161700 个数

我们以使用 2 位二进制位来代表一个元素为例设计两个 HASH 函数bit1 = HASH1(num)bit2 = HASH2(num)存入 num 时就把 bit1 和 bit2 都置为 1;判断时就判断 bit1 和 bit2当 bit1 和 bit2 都为 1 时就表示 num 存在集合中

这样会有个问题:两个数 num1 和 num2 经过两个 HASH 函数之后结果一样也就是存在 HASH 冲突这样就可能误判

实际上只要让误判的概率足够低结果就是可信的假设哈希函数的个数为 k二进制的位数为 m元素个数 n可以从数学上计算出他们与误判率的关系[1](原麦迪逊威斯康星大学曹培教授提供):

可以看出当 m/n = 16n = 8时误判率为万分之五这在大多数应用中都是可以接受的而且这种误判是这样的:如果这个元素在集合中那么布隆过滤器绝不会漏掉如果不在集合中则有可能判定为在集合中比如说对应垃圾邮件布隆过滤器绝不会漏掉黑名单中的任何一个可疑地址但是它有一定极小的概率将一个不在黑名单上的电子邮件判定为在黑名单中

到这里我相信你已经明白了个中原理

在 Python 中使用布隆过滤器

pypi 搜了了 Python 中的布隆过滤器有 3 个:

pip install bloom-filter2
pip install pybloom-live
pip install bloompy

第三个 bloompy[2] 的文档比较详细推荐使用(如果有兴趣你可以自己实现一个):

bloompy 提供了四种布隆过滤器:

1、标准布隆过滤器

标准布隆过滤器只能进行数据的查询和插入是其他过滤器的基类可以进行过滤器的存储和恢复代码示例:

>>> import bloompy
>>> bf = bloompy.BloomFilter(error_rate=0.001,element_num=10**3)
# 查询元素是否在过滤器里返回状态标识
# 如果不在里面则插入返回False表示元素不在过滤器里
>>> bf.add(1) 
False
>>> bf.add(1)
True
>>> 1 in bf
True
>>> bf.exists(1)
True
>>> bf.add([1,2,3])
False
>>> bf.add([1,2,3])
True
>>> [1,2,3] in bf
True
>>> bf.exists([1,2,3])
True
# 将过滤器存储在一个文件里
>>> bf.tofile('filename.suffix') 
# 从一个文件里恢复过滤器自动识别过滤器的种类
>>> recovered_bf = bloompy.get_filter_fromfile('filename.suffix') 
# 或者使用过滤器类的类方法 'fromfile' 来进行过滤器的复原对应的类只能恢复对应的过滤器
>>> recovered_bf = bloompy.BloomFilter.fromfile('filename.suffix') 
# 返回已经插入的元素个数
>>> bf.count
2 
# 过滤器的容量
>>> bf.capacity
1000
# 过滤器的位向量
>>> bf.bit_array
bitarray('00....')
# 过滤器位数组长度
>>> bf.bit_num
14400
# 过滤器的哈希种子默认是素数可修改
>>> bf.seeds
[2, 3, 5, 7, 11,...]
# 过滤器哈希函数个数
>>> bf.hash_num
10
 

2、计数布隆过滤器

它是标准布隆过滤器的子类但是可以执行删除操作内置默认使用 4 位二进制位来表示标准布隆过滤器的 1 个位从而实现可以增减

>>> import  bloompy
>>> cbf  = bloompy.CountingBloomFilter(error_rate=0.001,element_num=10**3)
# 与标准布隆过滤器一样
>>> cbf.add(12)
False
>>> cbf.add(12)
True
>>> 12 in cbf
True
>>> cbf.count
1 
# 查询元素状态返回标识如果元素存在过滤器里则删除
>>> cbf.delete(12)
True
>>> cbf.delete(12)
False
>>> 12 in cbf
False
>>> cbf.count
0
# 从文件中恢复过滤器
>>> recovered_cbf = bloompy.CountingBloomFilter.fromfile('filename.suffix')
 

3、标准扩容布隆过滤器

当插入的元素个数超过当前过滤器的容量时自动增加过滤器的容量默认内置一次扩容 2 倍支持查询和插入功能

>>> import bloompy
>>> sbf = bloompy.ScalableBloomFilter(error_rate=0.001,initial_capacity=10**3)
# 默认初次可以设置容量1000
>>> len(sbf)
0
>>> 12 in sbf
False
>>> sbf.add(12)
False
>>> 12 in sbf 
True
>>> len(sbf)
1
>>> sbf.filters
[<bloompy.BloomFilter object at 0x000000000B6F5860>]
>>> sbf.capacity
1000
#当过滤器的元素个数达到容量极限时过滤器会自动增加内置的标准过滤器
#每次增加2倍容量自动实现扩容
>>> for i in range(1000):
        sbf.add(i)
>>> 600 in sbf
True
>>> len(sbf)
2
>>> sbf.filters
[<bloompy.BloomFilter object at 0x000000000B6F5860>, <bloompy.BloomFilter object at 0x000000000B32F748>]
>>> sbf.capacity
3000 
# 从文件中恢复过滤器
>>> recovered_sbf = bloompy.ScalableBloomFilter.fromfile('filename.suffix')
 

4、计数扩容布隆过滤器

它是标准扩容布隆过滤器的子类但支持删除元素的操作

>>> import bloompy
>>> scbf = bloompy.SCBloomFilter(error_rate=0.001,initial_capacity=10**3)
>>> scbf.add(1)
False
>>> 1 in scbf
True
>>> scbf.delete(1)
True
>>> 1 in scbf
False
>>> len(scbf)
1
>>> scbf.filters
[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>]
# 插入元素使其达到过滤器当前容量极限值
>>> for i in range(1100):
        scbf.add(i)
>>> len(scbf)
2
>>> scbf.filters
[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>, <bloompy.CountingBloomFilter object at 0x000000000B6F5898>]
# 从文件中恢复过滤器
>>> recovered_scbf = bloompy.SCBloomFilter.fromfile('filename.suffix')
 

Redis 中使用布隆过滤器

你可以手动为 Redis 安装 RedisBloom 插件也可以直接使用官方[3]提供的 docker 版本:

docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

然后在 Redis 中就可以这样使用:

127.0.0.1:6379> BF.ADD newFilter foo
(integer) 1
127.0.0.1:6379> BF.EXISTS newFilter foo
(integer) 1
127.0.0.1:6379> BF.EXISTS newFilter notpresent
(integer) 0
127.0.0.1:6379> BF.MADD myFilter foo bar baz
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> BF.MEXISTS myFilter foo nonexist bar
1) (integer) 1
2) (integer) 0
3) (integer) 1
 

其实 Redis 中使用布隆过滤器还有一个很大的用处就是处理缓存穿透Redis 大部分情况都是通过 Key 查询对应的值假如发送的请求传进来的 key 是不存在 Redis 中的那么就查不到缓存查不到缓存就会去数据库查询假如有大量这样的请求这些请求像“穿透”了缓存一样直接打在数据库上这种现象就叫做缓存穿透

解决方案:

1、把无效的 Key 存进 Redis中如果 Redis 查不到数据数据库也查不到我们把这个 Key 值保存进Redis设置 value="null"当下次再通过这个 Key 查询时就不需要再查询数据库这种处理方式肯定是有问题的假如传进来的这个不存在的 Key 值每次都是随机的那存进 Redis 也没有意义

2、使用布隆过滤器布隆过滤器的作用是某个 key 不存在那么就一定不存在它说某个 key 存在那么很大可能是存在(存在一定的误判率)于是我们可以在缓存之前再加一层布隆过滤器在查询的时候先去布隆过滤器查询 key 是否存在如果不存在就直接返回

最后的话

布隆过滤器的数学原理在于两个完全随机的数字相冲突的概率很小因此可以在很小的误判率条件下用很少的空间存储大量的信息解决误判的常见办法就是在建立一个小的白名单存储那些可能被误判的信息

参考资料

[1]

关系:

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

[2]

bloompy:

https://github.com/01ly/bloompy/blob/master/zh-cn.md

[3]

官方:

https://oss.redis.com/redisbloom/Quick_Start/


相关文章

猜您喜欢

  • vue点击切换按钮 vue中点击切换按钮功能之点启用后按钮变为禁用

    想了解vue中点击切换按钮功能之点启用后按钮变为禁用的相关内容吗大师的修炼之路在本文为您仔细讲解vue点击切换按钮的相关知识和一些Code实例欢迎阅读和指正我们先划重点:vue点击切换按钮,vue按钮点击禁用下面大家一起来学习吧..
  • OpenCV手势识别 C++基于OpenCV实现手势识别的源码

    想了解C++基于OpenCV实现手势识别的源码的相关内容吗OKjokull在本文为您仔细讲解OpenCV手势识别的相关知识和一些Code实例欢迎阅读和指正我们先划重点:OpenCV手势识别,c++,OpenCV手势识别下面大家一起来学习吧..

网友评论

Copyright 2020 www.sopisoft.net 【绿软下载站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式