Java开发 - 布隆过滤器初体验

目录

前言

布隆过滤器

什么是布隆过滤器

布隆过滤器的作用

布隆过滤器原理

怎么设计布隆过滤器

布隆过滤器使用案例

安装布隆过滤器

添加依赖

添加配置

添加工具类

添加测试代码

简单测试

特别提醒​​​​​​​

结语

---

前言

前面三篇，已经把消息队列和其所包含的Kafka和RabbitMQ做了说明，并用案例演示了如何使用，今天这一篇，我们要讲解的内容是布隆过滤器，布隆过滤器不同于过滤器Filter，想知道布隆过滤器是什么，和怎样使用布隆过滤器吗？今天这篇博客，将带你了解这些，学完这篇，你将能独立使用布隆过滤器，了解其工作原理。下面，就让我们一起来学习吧。

布隆过滤器

说起过滤器，我们总是想起两种：一种是Filter过滤器，一种是布隆过滤器。Filter过滤器用于在全局捕捉请求，并在请求前后做一些事情，比如：统一编码，URL级别的权限访问控制，过滤敏感词汇，压缩请求信息等。那么布隆过滤器是做什么的呢？这里先卖个关子，我们继续往下看。

什么是布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

布隆过滤器不保存元素，之判断是否存在，不保存，所以也无法取出元素。

布隆过滤器的作用

布隆过滤器主要应用于网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）、数据库防止查询击穿， 使用BloomFilter来减少不存在的行或列的磁盘查找。

在Java开发 - Redis初体验一文中，我们曾提到过布隆过滤器，在缓存击穿的预防上面它是很好的效果的。刚好，学完此篇，你就可以在Redis项目中尝试添加布隆过滤器来防止缓存击穿，因为在当时写那篇博客时，我们采用的方法是给null值，在文中也提到，这是不合适的，因为当时还没有讲解布隆过滤器，学完此篇，大家可以去做个尝试。

布隆过滤器原理

常规检查元素是否存在我们会怎么做？一般是遍历集合，判断元素是否相等，但这种查询的方式在数据量庞大的情况下效率太低，想要实现快速的查找，前面学过的Java开发 - 树（二叉树，二叉排序树，红黑树）中曾经讲解过的数据结构或许会有一些帮助，其Hash散列或类似算法可以保证高效判断元素是否存在，但也存在消耗内存较多的问题，布隆过滤器的存在，正好解决了这个问题。

当要向布隆过滤器中添加一个元素时，该元素会经过N个哈希函数的计算并最终产生k个哈希值，布隆过滤器是个位数组，假设每一位是0，这些值就会根据计算出来的下标放入这个数组中，为1。在查询时，会判断这几个哈希值所在的位置，只要有一个为0就不存在于布隆过滤器中。

下面，我们通过几张图来说明布隆过滤器查询的原理：

假设这是一个空的布隆过滤器：

现在添加了coding单词在布隆过滤器中的状态：

coding算法1加密：1

coding算法2加密：3

coding算法3加密：5

现在添加了fire单词在布隆过滤器中的状态：

fire算法1加密：2

fire算法2加密：4

fire算法3加密：6

现在添加了codingfire单词在布隆过滤器中的状态：

codingfire算法1加密：1

codingfire算法2加密：4

codingfire算法3加密：6

问题来了，我还没添加呢，1，4，6的位置已经有东西了，这时候，布隆过滤器就会误判，认为codingfire已存在于布隆过滤器中。

布隆过滤器误判特点:

• 布隆过滤器判断不存在的元素，一定不在集合中
• 布隆过滤器判断存在的元素，有可能不存在集合中

这是因为我们做测试时布隆过滤器太短了，假设就10格，会导致每个位置值都是1，我们就不用存东西了，误判会很严重，啥都存在，那这就是个失败的布隆过滤器。所以，合适的大小对布隆过滤器非常重要。

怎么设计布隆过滤器

布隆过滤器在启动时需要分配合适的内存大小，这直接决定了它是否准确。设置的大小要满足这几个条件：

• 可接受范围的大小
• 既节省内存，又不会有很高的误判率

关于这两个条件，有一个公式用于计算误判率：

这是根据误判率计算布隆过滤器长度的公式：

n ：是已经添加元素的数量；

k ：哈希的次数；

m ：布隆过滤器的长度(位数的大小)

最终结果结果就是误判率。

反着来也是可以的，知道误判率，反推布隆过滤器长度：

推荐一个在线计算布隆过滤器大小的网站，可以正推，也可以反推：Bloom filter calculator 

布隆过滤器使用案例

安装布隆过滤器

布隆过滤器安装推荐这篇博客：Redis 布隆过滤器命令的使用详解

不过，它里面提到的布隆过滤器我个人不推荐，因为官方也推出了一个结合了Redis和布隆过滤器的软件工具：redis/redis-stack

网址在：Docker

安装方法和推荐博客里是一样的，由于比较简单，博主就不带大家一步步安装了，安装完请回到这里，我们继续。

安装完记得启动：

由于我们是教程，所以密码不设置，端口采用默认，实际可是要改的。 我们在上一篇RabbitMQ所在的子工程stock中继续集成，做一个简单的测试。

添加依赖

<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

添加配置

spring:redis:host: localhostport: 6379password:

添加工具类

在stock包下建utils包，包下新建一个类，代码如下：

package com.codingfire.cloud.stock.utils;import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import org.springframework.data.redis.core.script.RedisScript;
import org.springframework.stereotype.Component;import java.util.Arrays;
import java.util.List;@Component
public class RedisBloomUtils {@Autowiredprivate StringRedisTemplate redisTemplate;private static RedisScript<Boolean> bfreserveScript = new DefaultRedisScript<>("return redis.call('bf.reserve', KEYS[1], ARGV[1], ARGV[2])", Boolean.class);private static RedisScript<Boolean> bfaddScript = new DefaultRedisScript<>("return redis.call('bf.add', KEYS[1], ARGV[1])", Boolean.class);private static RedisScript<Boolean> bfexistsScript = new DefaultRedisScript<>("return redis.call('bf.exists', KEYS[1], ARGV[1])", Boolean.class);private static String bfmaddScript = "return redis.call('bf.madd', KEYS[1], %s)";private static String bfmexistsScript = "return redis.call('bf.mexists', KEYS[1], %s)";public Boolean hasBloomFilter(String key){return redisTemplate.hasKey(key);}/*** 设置错误率和大小（需要在添加元素前调用，若已存在元素，则会报错）* 错误率越低，需要的空间越大* @param key* @param errorRate 错误率，默认0.01* @param initialSize 默认100，预计放入的元素数量，当实际数量超出这个数值时，误判率会上升，尽量估计一个准确数值再加上一定的冗余空间* @return*/public Boolean bfreserve(String key, double errorRate, int initialSize){return redisTemplate.execute(bfreserveScript, Arrays.asList(key), String.valueOf(errorRate), String.valueOf(initialSize));}/*** 添加元素* @param key* @param value* @return true表示添加成功，false表示添加失败（存在时会返回false）*/public Boolean bfadd(String key, String value){return redisTemplate.execute(bfaddScript, Arrays.asList(key), value);}/*** 查看元素是否存在（判断为存在时有可能是误判，不存在是一定不存在）* @param key* @param value* @return true表示存在，false表示不存在*/public Boolean bfexists(String key, String value){return redisTemplate.execute(bfexistsScript, Arrays.asList(key), value);}/*** 批量添加元素* @param key* @param values* @return 按序 1表示添加成功，0表示添加失败*/public List<Integer> bfmadd(String key, String... values){return (List<Integer>)redisTemplate.execute(this.generateScript(bfmaddScript, values), Arrays.asList(key), values);}/*** 批量检查元素是否存在（判断为存在时有可能是误判，不存在是一定不存在）* @param key* @param values* @return 按序 1表示存在，0表示不存在*/public List<Integer> bfmexists(String key, String... values){return (List<Integer>)redisTemplate.execute(this.generateScript(bfmexistsScript, values), Arrays.asList(key), values);}private RedisScript<List> generateScript(String script, String[] values) {StringBuilder sb = new StringBuilder();for(int i = 1; i <= values.length; i ++){if(i != 1){sb.append(",");}sb.append("ARGV[").append(i).append("]");}return new DefaultRedisScript<>(String.format(script, sb.toString()), List.class);}}

代码都是模版，使用时直接添加此类即可。 

添加测试代码

我们quartz包下有个QuartzJob类，我们曾在里面测试Quartz功能和RabbitMQ，现在，我们来添加布隆过滤器的测试代码：

package com.codingfire.cloud.stock.quartz;import com.codingfire.cloud.stock.utils.RedisBloomUtils;
import org.quartz.Job;
import org.quartz.JobExecutionContext;
import org.quartz.JobExecutionException;
import org.springframework.amqp.rabbit.core.RabbitTemplate;
import org.springframework.beans.factory.annotation.Autowired;import java.time.LocalDateTime;public class QuartzJob implements Job {// RabbitTemplate就是amqp框架提供的发送消息的对象@Autowiredprivate RabbitTemplate rabbitTemplate;@Autowiredprivate RedisBloomUtils redisBloomUtils;@Overridepublic void execute(JobExecutionContext jobExecutionContext) throws JobExecutionException {//输出当前时间System.out.println("--------------"+ LocalDateTime.now() +"---------------");// 先简单的发送一串文字
//        rabbitTemplate.convertAndSend(RabbitMQConfig.STOCK_EX,RabbitMQConfig.STOCK_ROUT,"黄河之水天上来，奔流到海不复还。");//  首先确定要向布隆过滤器中保存的元素String[] numbers={"zero","one","two","three","four","five","six","seven","eight","nine","ten"};//  使用RedisBloomUtils类将上面的数组元素保存在Redis(布隆过滤器)中redisBloomUtils.bfmadd("numberBloom",numbers);// 下面就可以判断一个元素是否在这个布隆过滤器中了String elm="six";System.out.println("布隆过滤器判断"+elm+"是否存在:"+ redisBloomUtils.bfexists("numberBloom",elm));}
}

大阿甲不用纠结代码为什么写在这个类里，随便你写在哪里，写在测试类中也行，只要你项目能运行我们写的测试方法，随便你写在哪。 

简单测试

下面我们来简单测试下布隆过滤器的使用，看情况启动服务，如果十一路学习过来，和博主用的是相同工程的同学，请启动nacos，seata，mysql，还有最重要的redisbloom，可能还要启动RabbitMQ，否则会报错，启动后，运行项目，查看控制台输出：

能输出图中内容的就是测试成功了。

特别提醒

设置错误率和大小在使用前记得调用，不设置默认0.01，自己看哈。  

QuartzJob中布隆过滤器虽然进行了测试，但我们要知道QuartzJob的工作驱动，还有一个类叫QuartzConfig，这里面的代码相当于是注册+触发条件。我这么说，大家懂吗？不懂得可以去看看驱动QuartzJob运行的触发器的设置：Java开发 - Quartz初体验。

结语

简单来说，布隆过滤器就是用来判断某个元素是否存在于某一个集中的东西，而且，其判断效率非常高，是一个在大数据情况下常用的工具，但它本身代码量并不大，但要注意布隆过滤器存在误判率，所以使用起来，在设置重要参数时还是要注意些的。今天的布隆过滤器介绍到此结束， 不知道大家对最近的博客还满意吗？欢迎留言沟通交流。