编辑
2023-10-19
缓存中间件
0
请注意,本文编写于 198 天前,最后修改于 37 天前,其中某些信息可能已经过时。

目录

基本概念
使用场景
原理
优化

可以解决什么问题?

存在50亿个电话号码(或者ip、黑名单、url),给10万个电话号码,如何快速准确判断这些号码是否存在?

基本概念

布隆过滤器是一个很长的二进制数组+一系列随机hash算法映射函数,主要用于判断一个元素是否在集合中。

能高效的插入和查询,占用空间少,返回的结果是不确定性的。一个元素如果判断结果为存在的时候元素不一定存在,但是判断结果为不存在时则一定不存在。 布隆过滤器可以添加元素但是不能删除元素,因为删掉元素会导致误判率增加。误判只会发生在过滤器没有添加过的元素,对于添加过的元素不会发生误判。

使用场景

1、主要是解决缓存穿透问题

  • 把已存在的数据的key存在布隆过滤器中,相当于在redis前面挡了一层布隆过滤器。
  • 当有新的请求时,先到布隆过滤器中查询是否已经存在;
  • 如果布隆过滤器中不存在该数据则直接返回;
  • 如果布隆过滤器中已存在,才去查询缓存redis,如果redis里没有查到则到MySQL数据库中查询。

2、黑名单校验

原理

初始化:创建一个位数组(通常是一个二进制数组)并将所有位初始化为 0。位数组的长度(或大小)取决于预期要存储的元素数量和所能容忍的误判率。

添加key时:使用多个hash函数对key进行hash运算得到一个整数索引值,对位数组长度进行取模运算得到一个位置,每个hash函数会得到一个不同的位置,将这几个位置都置1就完成了add操作。

布隆过滤器原理.png

这也是布隆过滤器为什么不能删除,因为无法保证hash之后的位置没有别的key在使用(难免会出现hash冲突,多个key共用某些hash位置)。如果删除了,那么别的key也会受影响。这样会导致误判率增加。

查询key时:向布隆过滤器查询某个key是否存在时,先把这个key通过相同的多个hash函数进行运算,查看对应的位置是否都为1,只要有一个位置是0,则表明不存在,如果这几个位置都为1,则说明可能存在。(因为这些位置的1可能是其他的key导致的)

使用布隆过滤器时,最好不要让实际元素数量远大于初始化数量。当实际元素数量超过初始化数量时,应该对布隆过滤器进行重建,重新分配一个size更大的过滤器,再将所有的历史元素批量add进行。

优化

虽然布隆过滤器具有高效的插入和查询操作,但由于其设计原理的限制,存在一定的误判率。以下是一些方法可以降低布隆过滤器的误判率:

  • 增加位数组的大小:通过增加位数组的大小,可以提供更多的位来表示元素的存在情况,从而降低误判率。较大的位数组可以提供更多的空间来存储哈希值,减少不同元素之间的冲突。

  • 使用更多的哈希函数:布隆过滤器使用多个哈希函数来生成多个哈希值,用于设置位数组中的位。增加哈希函数的数量可以增加布隆过滤器的准确性,并降低误判率。但需要注意的是,增加哈希函数的数量也会增加计算的开销。

  • 组合多个布隆过滤器:通过使用多个独立的布隆过滤器并进行逻辑组合,可以降低误判率。例如,可以使用多个布隆过滤器,每个过滤器使用不同的哈希函数集合或位数组大小。查询时,只有当所有布隆过滤器都返回存在时,才判断元素存在于集合中,从而降低误判率。

  • 结合其他数据结构:将布隆过滤器与其他数据结构结合使用,可以进一步降低误判率。例如,可以将布隆过滤器作为预过滤器,将可能存在的元素进一步验证。对于预测为存在的元素,再使用精确的数据结构进行验证,以确保准确性。

  • 动态调整参数:根据实际使用情况和误判率要求,动态调整布隆过滤器的参数。例如,可以根据系统的负载和数据量变化来动态调整位数组大小、哈希函数数量等参数,以达到最优的误判率和性能平衡。

当然降低误判率通常会带来一些额外的开销,例如更大的位数组、更多的哈希函数或组合多个过滤器。因此,在选择具体的降低误判率方法时,需要综合考虑应用的实际需求、系统的资源和性能要求。

本文作者:whitebear

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!