基于redis实现分布式bloomfilter

如果想要判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表(又叫哈希表,Hash table)的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点。这样一来,我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果检查到一个元素不在集合中,那肯定就不在。如果计算到在集合中,虽然也有一定的错误率,但是错误率还是比较低的。

以上内容来自百度百科《布隆过滤器》词条,阐述了bloomfilter的基础原理。BloomFilter常被用于需要唯一性校验的场景,如爬虫等。

java中有许多bloomfilter的实现包,最常用的还是guava中的BloomFilter。但是现在的应用多存在分布式部署的现象,本地的BloomFilter实现已经不能满足需求了,我们需要一个分布式BloomFilter实现。redis的Bitmap是实现分布式BloomFilter的一个好基础。

首先,我们需要计算一个字符串的不同Hash值的方案,这里准备了一个BloomFilterHelper类:

BloomFilterHelper类的构造器需要传入两个参数:expectedInsertionsfpp

  • expectedInsertions : 预期写入的字符串总数
  • fpp :误判率

误判率当然是越低越好,但是也意味着要为存储的数据准备更多的空间,但redis的Bitmap天然是有上限的,因此需要根据实际情况做最优设计。

另外,这里使用了commons-codec这个包来计算字符串的hash值。采用的是Murmur hash64计算。

然后是向redis的Bitmap中写入相应信息:

最后是要验证字符串对应的offset是否在Bitmap中。下面是从Bitmap中取值的代码:

以及相应的校验代码:

大体上就是这些内容了。

完整代码在GitHub:zhyea / springboot-redis

End!


发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据