基于Redisson的Redis结合布隆过滤器使用

一、场景

• 缓存穿透问题

一般情况下，先查询Redis缓存，如果Redis中没有，再查询MySQL。当某一时刻访问redis的大量key都在redis中不存在时，所有查询都要访问数据库，造成数据库压力顿时上升，这就是缓存穿透。八股文背多了都知道：在Redis前面添加一层布隆过滤器，请求先在布隆过滤器中判断，如果布隆过滤器不存在时，直接返回，不再访问Redis和MySQL。如果布隆过滤器中存在时，再访问Redis，再访问数据库。完美解决缓存穿透问题。说白了：布隆过滤器就是redis的缓存

除此之外还有以下场景：

• 黑名单 ：如果黑名单非常大，上千万了，存放起来很耗费空间，在布隆过滤器中实现黑名单功能，是一个很好的选择。
• 网页爬虫对URL的去重，避免爬取相同的URL地址

二、布隆过滤器

1. 布隆过滤器BloomFilter是什么

布隆过滤器BloomFilter是一种专门用来解决去重问题的高级数据结果。实质就是一个大型位数组和几个不同的无偏hash函数，无偏表示分布均匀。由一个初值为零的bit数组和多个哈希函数组成，用来判断某个数据是否存在，它和HyperLogLog一样，不是那么的精准，存在一定的误判概率。

2. 布隆过滤器BloomFilter能干嘛？
   

• 高效地插入和查询，占用空间少，返回的结果是不确定的，一个元素如果判断结果为存在，它不一定存在；不存在时，一定不存在。 查询某个变量的时候我们只要看看这些点是不是都是 1， 就可以大概率知道集合中有没有它了。如果这些点， 有任何一个为零则被查询变量一定不在， 如果都是 1，则被查询变量很 可能存在。 为什么说是可能存在，而不是一定存在呢？ 那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

• 布隆过滤器BloomFilter只能添加元素，不能删除元素。这和上面提到的hashcode判定原理是一样的，相同hashcode的字符串会存储在一个index，删除时，是将某个index移除，此时，就可能移除拥有相同hashcode的不同字符串

三、实现原理和数据结构

1. 初始化

布隆过滤器 本质上 是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为

2. 添加

当我们向布隆过滤器中添加数据时，为了尽量地址不冲突， 会使用多个 hash 函数对 key 进行运算 ，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。 例如，我们添加一个字符串wmyskxz:

3. 判断是否存在

向布隆过滤器查询某个key是否存在时，先把这个 key 通过相同的多个 hash 函数进行运算 ，查看对应的位置是否都为 1， 只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在； 如果这几个位置全都是 1，那么说明极有可能存在； 因为这些位置的 1 可能是因为其他的 key 存在导致的，也就是前面说过的hash冲突。

例子：我们在 add 了字符串wmyskxz数据之后，很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的； 此时我们查询一个没添加过的不存在的字符串inexistent-key，它有可能计算后坑位也是1/3/5 ，这就是误判了。

4. 误判率，为什么不能删除元素？

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的， 因此误判的根源在于相同的 bit 位被多次映射且置 1。 这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素 共享了某一位 。 如果我们直接删除这一位的话，会影响其他的元素。

5. 如何解决不能删除

• 布谷鸟过滤器

为了解决布隆过滤器不能删除元素的问题 ，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》
作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足： 查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数

6. 常用命令

在Redis中，布隆过滤器有两个基本命令，分别是：

• bf.add：添加元素到布隆过滤器中，类似于集合的sadd命令，不过bf.add命令只能一次添加一个元素，如果想一次添加多个元素，可以使用bf.madd命令。
• bf.exists：判断某个元素是否在过滤器中，类似于集合的sismember命令，不过bf.exists命令只能一次查询一个元素，如果想一次查询多个元素，可以使用bf.mexists命令。

四、Redis使用布隆过滤器

1. redis版本：推荐版本6.x，最低4.x版本
2. 下载布隆过滤器插件（版本自选）

wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

3. 解压，编译，得到.so

1. tar -zxvf v2.2.6.tar.gz
2. cd RedisBloom-2.2.6/
3. make

4. Redis配置文件修改

在redis.conf配置文件中加入如RedisBloom的redisbloom.so文件的地址

loadmodule /usr/local/soft/RedisBloom-2.2.6/redisbloom.so

如果是集群则每个配置文件中都需要加入redisbloom.so文件的地址

5. 添加完成后需要重启redis
6. 集成布隆过滤器的redis项目：Rebloom插件布隆过滤器，有原生镜像可以直接使用

五、代码层面调用（java）

• 基于redisson实现

package com.ruoyi.demo;import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RBucket;
import org.redisson.api.RedissonClient;
import org.redisson.client.codec.StringCodec;
import org.redisson.config.Config;import java.util.concurrent.TimeUnit;public class RedissonBloomFilterDemo {public static final int _1W = 10000;//布隆过滤器里预计要插入多少数据public static int size = 100 * _1W;//误判率,它越小误判的个数也就越少public static double fpp = 0.03;static RedissonClient redissonClient = null;//jedisstatic RBloomFilter rBloomFilter = null;//redis版内置的布隆过滤器static {Config config = new Config();config.useSingleServer().setAddress("redis://192.168.1.8:6379").setPassword("cxm199610133914").setDatabase(2);//构造redissonredissonClient = Redisson.create(config);//通过redisson构造rBloomFilterrBloomFilter = redissonClient.getBloomFilter("phoneListBloomFilter",new StringCodec());rBloomFilter.tryInit(size,fpp);// 1测试  布隆过滤器有+redis有rBloomFilter.add("10086");redissonClient.getBucket("10086",new StringCodec()).set("chinamobile10086");// 2测试  布隆过滤器有+redis无rBloomFilter.add("10087");//3 测试 ，布隆过滤器无+redis无}private static String getPhoneListById(String IDNumber) {String result = null;if (IDNumber == null) {return null;}//1 先去布隆过滤器里面查询if (rBloomFilter.contains(IDNumber)) {//2 布隆过滤器里有，再去redis里面查询RBucket<String> rBucket = redissonClient.getBucket(IDNumber, new StringCodec());result = rBucket.get();if(result != null) {return "i come from redis: "+result;}else{result = getPhoneListByMySQL(IDNumber);if (result == null) {return null;}// 重新将数据更新回redisredissonClient.getBucket(IDNumber, new StringCodec()).set(result);}return "i come from mysql: "+result;}return result;}private static String getPhoneListByMySQL(String IDNumber) {return "chinamobile"+IDNumber;}public static void main(String[] args) {//String phoneListById = getPhoneListById("10086");//String phoneListById = getPhoneListById("10087"); //请测试执行2次String phoneListById = getPhoneListById("10088");System.out.println("------查询出来的结果： "+phoneListById);//暂停几秒钟线程try {TimeUnit.SECONDS.sleep(1);}catch (InterruptedException e) {e.printStackTrace();}redissonClient.shutdown();}
}

参考文章
参考文章