redis 布隆过滤,如何实现布隆过滤器

redis布隆过滤器简单使用

布隆过滤器无法直接在redis里使用，需要redis4.0以上的版本才能安装插件使用，

安装方法请我的以前的博客：https://blog.csdn.net/weixin_42564514/article/details/104880452

当然也可以直接docker安装带布隆过滤器的redis版本

布隆过滤器使用场景：假如现在有一些资讯推送的需求，我们不能给用户推送重复的资讯，那么就需要解决去重的问题，如果把推送的记录都记录进入数据库然后去判重复，那么数据量将会极大，性能也极低，是一种非常不好的方案，如果去全部缓存起来，内存的消耗也是非常的严重，因此redis的布隆过滤器就可以帮我们很好的解决这个去重的问题，还能节省90%以上的空间，那么你可能又要问那为什么不用HyperLogLog去重呢，占用内存还小才12k，那是因为HyperLogLog 只有pfadd和pfcount这两个常用方法，没办法判定特定的数据存不存在，只能统计数量。但是布隆过滤器可以做到这一点，只是可能会有一点误差，它会把出现过的情况分辨的很清楚，没出现过的有可能出现误判，也就是说，推送过的内容就不会再推送，但是没推送过的可能出现漏推。

这里说一下关于误判率的问题：布隆过滤器可以自己设置一些参数来尽量减小误判率

bf.reserve(key,error_rate,initial_size)这个指令可以设置，initial_size默认是100，error_rate默认为0.01，当我们add的值超过了initial_size之后，误判率会上升，error_rate错误率越低，需要得空间也越大，所以这两个参数得斟酌着设置，initial_size初始设的太小，超过这个值后误判率会上升，但是一开始设的太大又会浪费不必要的空间。

另外bf.reserve(key,error_rate,initial_size)这个指令的执行，如果key已经存在的话会报错，所以第一次在还有没key的时候，初始化一次就好。

为什么说布隆过滤器节省空间是因为，传统的set是设置的字符串进去的，假如设置id长度为20，每个元素本身还需要一个指针被set集合引用，这个指针又会占去4个字节（32位）或者8个字节（64位），那么设置一个记录就需要20多个字节，但是布隆过滤器存的是指纹空间，在错误率为0.1%的情况下，一个元素大约需要15bit的空间也就是不到2个字节，所以空间的节省还是很大的。

空间计算器：https://krisives.github.io/bloom-calculator/

1000000数据在0.1%的错误率情况下所需的内存才：1755.07kb=1.71mb，你就说省不省空间

以下为示例代码：示例为springboot项目

<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-redis</artifactId></dependency><dependency> <groupId>redis.clients</groupId> <artifactId>jedis</artifactId> <version>2.9.0</version></dependency>

pom引入这两个依赖

主要结构：

application.yml  项目配置文件

server: port: 8080spring: redis: database: 0 host: localhost jedis: pool: max-active: 8 max-idle: 8 max-wait: -1ms min-idle: 0 lettuce: pool: max-active: 8 max-idle: 8 max-wait: -1ms min-idle: 0 shutdown-timeout: 100ms password: 123456 port: 6379 timeout: 5000ms

bloomFilterAdd.lua  布隆过滤器lua添加脚本

local bloomKey = KEYS[1]local value = KEYS[2]-- 执行添加方法local result = redis.call('BF.ADD', bloomKey, value)return result

bloomFilterExists.lua  布隆过滤器lua判断是否存在脚本

local bloomKey = KEYS[1]local value = KEYS[2]-- 执行检测是否存在方法local result = redis.call('BF.EXISTS', bloomKey, value)return result

bloomFilterReserve.lua  布隆过滤器lua初始化脚本

local bloomKey = KEYS[1]local error_rate = tonumber(KEYS[2])local initial_size = tonumber(KEYS[3])-- 执行初始化local result = redis.call('BF.RESERVE', bloomKey, error_rate,initial_size)return result

RedisStudyApplicationTests  测试文件

package com.redisstudy;import org.junit.Test;import org.junit.runner.RunWith;import org.springframework.boot.test.context.SpringBootTest;import org.springframework.core.io.ClassPathResource;import org.springframework.data.redis.core.RedisTemplate;import org.springframework.data.redis.core.script.DefaultRedisScript;import org.springframework.scripting.support.ResourceScriptSource;import org.springframework.test.context.junit4.SpringRunner;import javax.annotation.Resource;import java.util.ArrayList;import java.util.List;@RunWith(SpringRunner.class)@SpringBootTestpublic class RedisStudyApplicationTests { @Resource private RedisTemplate redisTemplate; @Test public void testBloomFilter() { /*这里只是为了模拟，真实情况想办法只做一次初始化操作*/ if(!reserve("myTest1","0.001","10000")) { System.out.println("已存在，请直接开始添加"); } else { System.out.println("初始化成功"); } add("myTest1","user1"); exists("myTest1","user1"); exists("myTest1","user2"); } /** * 初始化 * @param key * @param error_rate * @param initial_size * @return */ public boolean reserve(String key,String error_rate,String initial_size){ DefaultRedisScript<Boolean> bloomAdd = new DefaultRedisScript<>(); ClassPathResource addPath = new ClassPathResource("bloom/bloomFilterReserve.lua"); bloomAdd.setScriptSource(new ResourceScriptSource(addPath)); bloomAdd.setResultType(Boolean.class); List<Object> addList= new ArrayList<>(); addList.add(key); addList.add(error_rate); addList.add(initial_size); try { return (Boolean) redisTemplate.execute(bloomAdd,addList); }catch (Exception e) { return false; } } /** * 添加 * @param key * @param value */ public void add(String key,String value){ DefaultRedisScript<Boolean> bloomAdd = new DefaultRedisScript<>(); ClassPathResource addPath = new ClassPathResource("bloom/bloomFilterAdd.lua"); bloomAdd.setScriptSource(new ResourceScriptSource(addPath)); bloomAdd.setResultType(Boolean.class); List<Object> addList= new ArrayList<>(); addList.add(key); addList.add(value); Boolean addResult = (Boolean) redisTemplate.execute(bloomAdd,addList); System.out.println("添加结果："+addResult); } /** * 判断 * @param key * @param value */ public void exists(String key,String value){ DefaultRedisScript<Boolean> bloomExists = new DefaultRedisScript<>(); ClassPathResource existsPath = new ClassPathResource("bloom/bloomFilterExists.lua"); bloomExists.setScriptSource(new ResourceScriptSource(existsPath)); bloomExists.setResultType(Boolean.class); List<Object> existsList= new ArrayList<>(); existsList.add(key); existsList.add(value); Boolean existsResult1 = (Boolean) redisTemplate.execute(bloomExists,existsList); System.out.println("查询结果："+existsResult1); }}

运行结果： 没毛病

第一次运行：

第二次运行：