一、场景
- 缓存穿透问题
一般情况下，先查询Redis缓存，如果Redis中没有，再查询MySQL。当某一时刻访问redis的大量key都在redis中不存在时，所有查询都要访问数据库，造成数据库压力顿时上升，这就是缓存穿透。八股文背多了都知道：在Redis前面添加一层布隆过滤器，请求先在布隆过滤器中判断，如果布隆过滤器不存在时，直接返回，不再访问Redis和MySQL。如果布隆过滤器中存在时，再访问Redis，再访问数据库。完美解决缓存穿透问题。说白了：布隆过滤器就是redis的缓存
除此之外还有以下场景：
- 黑名单 ：如果黑名单非常大，上千万了，存放起来很耗费空间，在布隆过滤器中实现黑名单功能，是一个很好的选择。
- 网页爬虫对URL的去重，避免爬取相同的URL地址
二、布隆过滤器
- 布隆过滤器BloomFilter是什么
布隆过滤器BloomFilter是一种专门用来解决去重问题的高级数据结果。实质就是一个大型位数组和几个不同的无偏hash函数，无偏表示分布均匀。由一个初值为零的bit数组和多个哈希函数组成，用来判断某个数据是否存在，它和HyperLogLog一样，不是那么的精准，存在一定的误判概率。
- 布隆过滤器BloomFilter能干嘛？
-
高效地插入和查询，占用空间少，返回的结果是不确定的，
一个元素如果判断结果为存在，它不一定存在；不存在时，一定不存在。 查询某个变量的时候我们只要看看这些点是不是都是 1， 就可以大概率知道集合中有没有它了。如果这些点， 有任何一个为零则被查询变量一定不在， 如果都是 1，则被查询变量很 可能存在。 为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。 -
布隆过滤器BloomFilter只能添加元素，不能删除元素。这和上面提到的hashcode判定原理是一样的，相同hashcode的字符串会存储在一个index，删除时，是将某个index移除，此时，就可能移除拥有相同hashcode的不同字符串
三、实现原理和数据结构
- 初始化
布隆过滤器 本质上 是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为
- 添加
当我们向布隆过滤器中添加数据时，为了尽量地址不冲突， 会使用多个 hash 函数对 key 进行运算 ，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。 例如，我们添加一个字符串wmyskxz:
- 判断是否存在
向布隆过滤器查询某个key是否存在时，先把这个 key 通过相同的多个 hash 函数进行运算 ，查看对应的位置是否都为 1， 只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在； 如果这几个位置全都是 1，那么说明极有可能存在； 因为这些位置的 1 可能是因为其他的 key 存在导致的，也就是前面说过的hash冲突。
例子：我们在 add 了字符串wmyskxz数据之后，很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的； 此时我们查询一个没添加过的不存在的字符串inexistent-key，它有可能计算后坑位也是1/3/5 ，这就是误判了。
- 误判率，为什么不能删除元素？
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的， 因此误判的根源在于相同的 bit 位被多次映射且置 1。 这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素 共享了某一位 。 如果我们直接删除这一位的话，会影响其他的元素。
- 如何解决不能删除
- 布谷鸟过滤器
为了解决布隆过滤器不能删除元素的问题 ，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》
作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足： 查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数
- 常用命令
在Redis中，布隆过滤器有两个基本命令，分别是：
- bf.add：添加元素到布隆过滤器中，类似于集合的sadd命令，不过bf.add命令只能一次添加一个元素，
如果想一次添加多个元素，可以使用bf.madd命令。- bf.exists：判断某个元素是否在过滤器中，类似于集合的sismember命令，不过bf.exists命令只能一次查询一个元素，
如果想一次查询多个元素，可以使用bf.mexists命令。
四、Redis使用布隆过滤器
- redis版本：推荐版本6.x，最低4.x版本
- 下载布隆过滤器插件（版本自选）
wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz
- 解压，编译，得到.so
- tar -zxvf v2.2.6.tar.gz
- cd RedisBloom-2.2.6/
- make
- Redis配置文件修改
在redis.conf配置文件中加入如RedisBloom的redisbloom.so文件的地址
loadmodule /usr/local/soft/RedisBloom-2.2.6/redisbloom.so
如果是集群则每个配置文件中都需要加入redisbloom.so文件的地址
- 添加完成后需要重启redis
- 集成布隆过滤器的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;//jedis
static RBloomFilter rBloomFilter = null;//redis版内置的布隆过滤器
static {
Config config = new Config();
config.useSingleServer().setAddress("redis://192.168.1.8:6379").setPassword("cxm199610133914")
.setDatabase(2);
//构造redisson
redissonClient = Redisson.create(config);
//通过redisson构造rBloomFilter
rBloomFilter = 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;
}
// 重新将数据更新回redis
redissonClient.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();
}
}
参考文章
参考文章
