tions);
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;
}
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
如果我的文章对你有所帮助,还请帮忙点赞、在看、转发一下,你的支持会激励我输出更高质量的文章,非常感谢!