3 Redisson实现
Redisson 是一个用 Java 编写的 Redis 客户端，它实现了分布式对象和服务，包括集合、映射、锁、队列等。Redisson的API简单易用，使得在分布式环境下使用Redis 更加容易和高效。
1、添加Maven依赖
<dependency> <groupId>org.redisson</groupId> <artifactId>redisson</artifactId> <version>3.16.1</version> </dependency>
2、配置 Redisson 客户端
@Configuration public class RedissonConfig { Bean public RedissonClient redissonClient() { Config config = new Config(); config.useSingleServer().setAddress("redis://localhost:6379"); return Redisson.create(config); } }
3、初始化
public boolean mightcontain(Long id) { return bloomFilter.contains(id); }
4、判断数据是否存在
public boolean mightcontain(Long id) { return bloomFilter.contains(id); }
好，我们来从源码分析 Redisson 布隆过滤器是如何实现的 ？
public boolean tryInit(long expectedInsertions, double falseProbability) { // 位数组大小 size = optimalNumOfBits(expectedInsertions, falseProbability); // 哈希函数次数 hashIterations = optimalNumOfHashFunctions(expectedInsertions, size); CommandBatchService executorService = new CommandBatchService(commandExecutor); // 执行 Lua脚本，生成配置 executorService.evalReadAsync(configName, codec, RedisCommands.EVAL_VOID, "local size = redis.call('hget', KEYS[1], 'size');" + "local hashIterations = redis.call('hget', KEYS[1], 'hashIterations');" + "assert(size == false and hashIterations == false, 'Bloom filter config has been changed')", Arrays.<Object>asList(configName), size, hashIterations); executorService.writeAsync(configName, StringCodec.INSTANCE, new RedisCommand<Void>("HMSET", new VoidReplayConvertor()), configName, "size", size, "hashIterations", hashIterations, "expectedInsertions", expectedInsertions, "falseProbability", BigDecimal.valueOf(falseProbability).toPlainString()); try { executorService.execute(); } catch (RedisException e) { } return true; }
Bf配置信息
Redisson 布隆过滤器初始化的时候，会创建一个 Hash 数据结构的 key ，存储布隆过滤器的4个核心属性。
那么 Redisson 布隆过滤器如何保存元素呢 ？
public boolean add(T object) { long[] hashes = hash(object); while (true) { int hashIterations = this.hashIterations; long size = this.size; long[] indexes = hash(hashes[0], hashes[1], hashIterations, size); CommandBatchService executorService = new CommandBatchService(commandExecutor); addConfigCheck(hashIterations, size, executorService); //创建 bitset 对象， 然后调用setAsync方法，该方法的参数是索引。 RBitSetAsync bs = createBitSet(executorService); for (int i = 0; i < indexes.length; i++) { bs.setAsync(indexes[i]); } try { List<Boolean> result = (List<Boolean>) executorService.execute().getResponses(); for (Boolean val : result.subList(1, result.size()-1)) { if (!val) { return true; } } return false; } catch (RedisException e) { } } }
从源码中，我们发现 Redisson 布隆过滤器操作的对象是 位图（bitMap） 。
在 Redis 中，位图本质上是 string 数据类型，Redis 中一个字符串类型的值最多能存储 512 MB 的内容，每个字符串由多个字节组成，每个字节又由 8 个 Bit 位组成。位图结构正是使用“位”来实现存储的，它通过将比特位设置为 0 或 1来达到数据存取的目的，它存储上限为 2^32 ，我们可以使用getbit/setbit命令来处理这个位数组。
为了方便大家理解，我做了一个简单的测试。
通过 Redisson API 创建 key 为 mybitset 的 位图 ，设置索引 3 ，5，6，8 位为 1 ，右侧的二进制值 也完全匹配。
4 实战要点
通过 Guava 和 Redisson 创建和使用布隆过滤器比较简单，我们下面讨论实战层面的注意事项。
1、缓存穿透场景
首先我们需要初始化 布隆过滤器，然后当用户请求时，判断过滤器中是否包含该元素，若不包含该元素，则直接返回不存在。
若包含则从缓存中查询数据，若缓存中也没有，则查询数据库并回写到缓存里，最后给前端返回。
2、元素删除场景
现实场景，元素不仅仅是只有增加，还存在删除元素的场景，比如说商品的删除。
原理解析这一节，我们已经知晓：布隆过滤器其实并不支持删除元素，因为多个元素可能哈希到一个布隆过滤器的同一个位置，如果直接删除该位置的元素，则会影响其他元素的判断 。
我们有两种方案：
▍计数布隆过滤器
计数过滤器（Counting Bloom Filter）是布隆过滤器的扩展，标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的 k （k 为哈希函数个数）个 Counter 的值分别加 1，删除元素时给对应的 k 个 Counter 的值分别减 1。
虽然计数布隆过滤器可以解决布隆过滤器无法删除元素的问题，但是又引入了另一个问题：“更多的资源占用，而且在很多时候会造成极大的空间浪费 ”。
▍ 定时重新构建布隆过滤器
从工程角度来看，定时重新构建布隆过滤器 这个方案可行也可靠，同时也相对简单。
- 定时任务触发全量商品查询 ;
- 将商品编号添加到新的布隆过滤器 ;
- 任务完成，修改商品布隆过滤器的映射（从旧 A 修改成 新 B ）;
- 商品服务根据布隆过滤器的映射，选择新的布隆过滤器 B进行相关的查询操作 ；
- 选择合适的时间点，删除旧的布隆过滤器 A。
5 总结
布隆过滤器 是一个很长的二进制向量 和一系列随机映射函数 ，用于检索一个元素是否在一个集合中 。
它的空间效率 和查询时间 都远远超过一般的算法 ，但是有一定的误判率 （函数返回 true , 意味着元素可能存在，函数返回 false ，元素必定不存在）。
布隆过滤器的四个核心属性：
- k : 哈希函数个数
- m : 位数组长度
- n : 插入的元素个数
- p : 误判率
Java 世界里 ，通过 Guava 和 Redisson 创建和使用布隆过滤器非常简单。
布隆过滤器无法删除元素，但我们可以通过计数布隆过滤器 和定时重新构建布隆过滤器 两种方案实现删除元素的效果。
为什么这么多的开源项目中使用布隆过滤器 ？
因为它的设计精巧且简洁，工程上实现非常容易，效能高，虽然有一定的误判率，但软件设计不就是要 trade off 吗 ？
参考资料：
https://hackernoon.com/probabilistic-data-structures-bloom-filter-5374112a7832
