布隆过滤器原理及使用

2024-03-02 12:24:22

原理

布隆过滤器由一个长度为 m 的位数组和 k 个哈希函数组成。数组初始化为0。

  • 当添加一个元素时，分别用 k 个哈希函数计算出该元素的哈希值，这 k 个哈希值作为数组的下标，并将数组中下标对应的值置为1
  • 当查询一个元素时，同样的，用 k 个哈希函数计算出该元素的哈希值，这 k 个哈希值作为数组的下标。我们去查询数组中对应下标的值，如果存在一个值为0，则表明被查询的元素一定不在集合中；如果对应下标的值都为1，则表明被查询的元素可能在集合中。如果一个元素其实并不存在，但被误认为存在，我们称其为“假阳性（false positive）”。

优点

  1. 用比特数组表示，不用存储数据本身，对空间的节省相比于传统方式占据绝对的优势。
  2. 布隆过滤器存储空间和插入 / 查询时间复杂度都是常数O(k)。
  3. 散列函数相互之间没有关系，方便由硬件并行实现。
  4. 布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点

  1. 随着存入元素的增加，存在误判的情况
  2. 存入元素无法删除（一般不支持delete操作，Counting filters可支持元素删除操作的方法，具体参见扩展）

使用场景

  1. 判断给定数据是否存在：比如判断一个数字是否在于包含大量数字的数字集中（数字集很大，5亿以上！）、防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤、黑名单功能等等。
  2. 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。

常用的布隆过滤器

Google布隆过滤器

引入 Guava 的maven依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>21.0</version>
</dependency>

实际使用如下：
我们创建了一个最多存放 最多 1500个整数的布隆过滤器，并且我们可以容忍误判的概率为百分之（0.01）

// 创建布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(),
        1500, 0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));

在我们的示例中，当mightContain（） 方法返回true时，我们可以99％确定该元素在过滤器中，当过滤器返回false时，我们可以确定该元素一定不存在过滤器中。

Redis 中的布隆过滤器
redis环境

推荐使用docker

docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
docker exec -it redis-redisbloom bash
root@21396d02c252:/data# redis-cli
127.0.0.1:6379>
常用命令
  1. BF.ADD ：将元素添加到布隆过滤器中，如果该过滤器尚不存在，则创建该过滤器。格式：BF.ADD {key} {item}
  2. BF.MADD :将一个或多个元素添加到“布隆过滤器”中，并创建一个尚不存在的过滤器。该命令的操作方式BF.ADD与之相同，只不过它允许多个输入并返回多个值。格式：BF.MADD {key} {item} [item ...]
  3. BF.EXISTS : 确定元素是否在布隆过滤器中存在。格式：BF.EXISTS {key} {item}
  4. BF.MEXISTS ： 确定一个或者多个元素是否在布隆过滤器中存在格式：BF.MEXISTS {key}{item} [item ...]

注意： key:布隆过滤器的名称，item : 添加的元素。

另外还有BF.RESERVE 命令可自定义布隆过滤器初始化参数，如果不使用 bf.reserve，默认的error_rate是 0.01，默认的capacity是 100：
这个命令的格式如下：

BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]

下面简单介绍一下每个参数的具体含义：

  1. key：布隆过滤器的名称
  2. error_rate：误报的期望概率。这应该是介于0到1之间的十进制值。例如，对于期望的误报率0.1％（1000中为1），error_rate应该设置为0.001。该数字越接近零，则每个项目的内存消耗越大，并且每个操作的CPU使用率越高。
  3. capacity：过滤器的容量。当实际存储的元素个数超过这个值之后，性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长，性能将线性下降。
  4. 可选参数：
    expansion：如果创建了一个新的子过滤器，则其大小将是当前过滤器的大小乘以expansion。默认扩展值为2。这意味着每个后续子过滤器将是前一个子过滤器的两倍
实际使用
127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0
Google布隆过滤器与Redis布隆过滤器对比
Google布隆过滤器
  1. 基于JVM内存的一种布隆过滤器
  2. 重启即失效
  3. 本地内存无法用在分布式场景
  4. 不支持大数据量存储
Redis布隆过滤器
  1. 可扩展性Bloom过滤器：一旦Bloom过滤器达到容量，就会在其上创建一个新的过滤器
  2. 不存在重启即失效或者定时任务维护的成本：基于Google实现的布隆过滤器需要启动之后初始化布隆过滤器
  3. 需要网络IO，性能比Google布隆过滤器低

扩展

Counting filters

基本的布隆过滤器不支持删除（Deletion）操作，但是 Counting filters 提供了一种可以不用重新构建布隆过滤器但却支持元素删除操作的方法。在Counting filters中原来的位数组中的每一位由 bit 扩展为 n-bit 计数器，实际上，基本的布隆过滤器可以看作是只有一位的计数器的Counting filters。原来的插入操作也被扩展为把 n-bit 的位计数器加1，查找操作即检查位数组非零即可，而删除操作定义为把位数组的相应位减1，但是该方法也有位的算术溢出问题，即某一位在多次删除操作后可能变成负值，所以位数组大小 m 需要充分大。另外一个问题是Counting filters不具备伸缩性，由于Counting filters不能扩展，所以需要保存的最大的元素个数需要提前知道。否则一旦插入的元素个数超过了位数组的容量，false positive的发生概率将会急剧增加。当然也有人提出了一种基于 D-left Hash 方法实现支持删除操作的布隆过滤器，同时空间效率也比Counting filters高。

上一篇：c#-串口通信-进程间-简单实验


下一篇：玩转布隆过滤器，其实很简单！