Redis的分布式布隆过滤器

1. 为什么要使用布隆过滤器

现有50亿个电话号码，现有10万个电话号码，要快速准确判断这些电话号码是否已经存在？

1. 通过数据库查询：实现快速有点难
2. 数据预放在集合中：50亿 * 8字节 ~40GB (内存浪费或不够)
3. hyperloglog：但是准确度不高

类似问题很多

• 垃圾邮件过滤
• 文字处理中的错误单词检测
• 网络爬虫重复URL检测
• 会员抽奖
• 判断一个元素在亿级数据中是否存在
• 缓存穿透

2. 布隆过滤器原理

一个很长的二进制向量和若干个哈希函数
实现原理就是我们需要一个很长的二进制数组（也叫向量）；在添加数据时，使用多个hash函数对key进行hash运算得到一个索引值（即二进制数组的索引值）

image.png

上图中，下面是很长的二进制数组，第二层就是多个hash函数，再上面就是数据。

image.png

上图中，每个数据经过多个hash函数计算，得到索引值，并把二进制数组对应的索引值那边设置为1，我们发现经过三次hash，就会在三个索引的地方设置为1，也就是代表此数据存在。

2.1 布隆过滤器构建

参数：m个二进制向量，n个预备数据，k个hash函数
构建布隆过滤器：n个预备数据走一遍上面过程
判断元素存在：走一遍面过程：如果都是1，则在表明存在，反之不存在。

2.2 布隆过滤器误差率

• 肯定存在误差：恰好都命中了。
• 直观因素：m/n的比率，hash函数的个数
• 实际误差公式

(1)1个元素。1个hash函数，任意一个比特为1的概率为，依然为0的概率

(2)k个函数，依然为0的概率

n个元素，依然为0的概率为

(3)被设置为1的概率

(4) 新元素全中的概率为

结论：m/n与误差率成反比，k与误差率成反比。

3 本地布隆过滤器

现有库：guava
本地布隆过滤器的问题：
(1) 容量受限制
(2) 多个应用存在多个布隆过滤器，构建同步复杂。

image.png

4 基于Redis布隆过滤器

image.png

基于位图实现

1. 定义布隆过滤器构造参数：m、n、k、误差概率
2. 定义布隆过滤器操作函数：add和contains
3. 封装Redis位图操作
4. 开发测试样例

        <dependency>
            <groupId>com.github.wxisme</groupId>
            <artifactId>bloomfilter</artifactId>
            <version>1.0.0</version>
        </dependency>

        BloomFilter<String> filter = new BloomFilter<String>(0.0001, 10000);
        Jedis jedis = new Jedis("39.105.71.50", 6379);
        jedis.auth("iHuaBen123ReDis");
        filter.bind(new RedisBitSet(jedis, "bloomfilter:key:name"));

        filter.add("http://www.google.com");
        filter.add("http://www.twitter.com");
        filter.add("http://www.baidu.com");

        System.out.println(filter.contains("http://www.google.com"));
        System.out.println(filter.contains("http://www.twitter.com"));
        System.out.println(filter.contains("http://www.baidu.com"));
        System.out.println(filter.contains("http://www.aliyun.com"));

true
true
true
false

基于Redis单机实现存在的问题

• 速度慢：比较慢，输在网络
  解决：单机部署，与应用同机房甚至机架部署
• 容量受限：Redis最大字符串为512MB、Redis单机容量

解决：基于Redis Cluster实现

5 Redis布隆过滤器代码实现端

1.Java调用Redis Bitmap Api

2.Rebloom插件方式实现布隆过滤器

redis4.0 之后支持插件支持布隆过滤器 git: 开源项目：github.com/RedisBloom/…

docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

测试

> BF.ADD newFilter foo
1
> BF.EXISTS newFilter foo
1
> BF.EXISTS newFilter xxxx
0