Boolean Filter布隆过滤器

前言

boolean 过滤器，顾名思义就是用来数据过滤，主要用来判断数据是否存在，经常用在redis 中，防止缓存失效，造成雪崩

Boolean Filter

• 布隆过滤器是一个叫“布隆”的人提出的，它本身是一个很长的二进制向量，存储的数据只能是0或1
• 由于采用二进制向量存储(存储结构与bitmap类似)，只能存储状态数据，不存储元数据，非常节省内存空间
• 核心：

  判定不在的数据一定不存在，存在的数据不一定存在

  先记住
• 布隆过滤器存在一定的误判(涉及时间/空间转换)

应用场景

1. redis 缓存雪崩
2. 数据去重，比如：头条、抖音看过的内容不会重复出现(排除少量误判)
3. 涉及大量数据，去重，都可使用布隆

实现逻辑

初始布隆过滤器数据位默认是0

• 查询world 根据hash 算法，取得数据和前两个存储数据有重叠，都是1， 判定数据已存在，但是实际并未存在，有误差。
• 布隆过滤器，初始长度和容错率可以自己设定，容量一旦确定不能修改
• 随着数据越来越多，误判率也会升高，需要定期重新设置过滤器
• 过滤器不允许删除，因为一个数据位可能关联到多个数据

redis 布隆过滤器

redis4,x 以后提供了boolean，使用的redis5.0.8

• 配置插件

# 下载布隆过滤器的插件
wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz
# 解压后在根目录
make
# redis.conf 配置文件的添加boolean filter
loadmodule /root/booleanFilter/RedisBloom/rebloom.so
           

• 测试

127.0.0.1:6379> bf.add bf a 
(integer) 1
127.0.0.1:6379> bf.add bf b
(integer) 1
127.0.0.1:6379> bf.exists bf a
(integer) 1
127.0.0.1:6379> bf.exists bf c
(integer) 0
127.0.0.1:6379> bf.madd bf 1 2 3 4
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
127.0.0.1:6379>  bf.mexists bf 1 3 d
1) (integer) 1
2) (integer) 1
3) (integer) 0
127.0.0.1:6379> bf.reserve bf 0.0001 1000 #设置长度和精确度 Boolean fileter 默认长度是 100，容错是0.01， 已存在布隆过滤，不允许修改
(error) ERR item exists
127.0.0.1:6379> bf.reserve bf1  0.0001 1000
OK
           

Java 使用

• pom

<dependency>
	<groupId>com.redislabs</groupId>
    <artifactId>jrebloom</artifactId>
    <version>1.2.0</version>
</dependency>
           

• 实现

public class BooleanFilterTest

@Test
public void testBf{
        Client bloomClient = new Client("127.0.0.1",6390);
        bloomClient.add("bf01","a");
        bloomClient.add("bf01","b");
        bloomClient.add("bf01","c");
        System.out.println("判断是否存在 :"+bloomClient.exists("bf02","c"));
        bloomClient.createFilter("bf03",10000,0.001);
    }
}
           

总结

• 布隆过滤器只能判断数据一定不存在，不能判断不存在
• 布隆过滤器的初始值估计过大，会浪费空间，估计的过小就会影响准确率，使用之前一定要尽可能的精确估计元素的数量，还需要加上一定的冗余空间避免实践元素过多导致的准确率影响
• 布隆过滤器的fpp(误差)越小，需要的空间就越大，对于不需要特别精确的场合，可以稍微大一些
• 使用的时候不要让实际数据大于初始化大小，当实际元素超出初始化大小时，应该对布隆过滤器进行重建，重新分配一个size更大的布隆过滤器，将所有数据再批量add进去