布隆过滤器 - Bloom Filter

[TOC]

参考链接：
1：JavaGuide - 布隆过滤器
2：亿级数据过滤和布隆过滤器

0.引言

douyin.png

P：我们平时在刷抖音时，开发人员如何保证 不会刷到同样的内容 ？

1：把算法推荐中的内容根据历史记录做一遍筛选？在用户量大，用户查看内容多的场景，性能低
2：历史记录全部计入缓存？资源量大，并且会随着时间逐渐上涨，服务器耗费up
3：布隆过滤器？专门用于解决去重问题，存在一定误判概率但是在去重的同时能节省90%的空间

1.使用场景

1：在数据量很大(5亿以上)的场景下判断某一数据是否存在。对比hashMap节省了很大的存储空间
2：黑名单、邮箱的垃圾邮件过滤。正常邮件被放入垃圾邮箱，就是布隆过滤器的误判导致
3：去重。例如爬虫时，对已经爬取过的内容去重
4：缓存穿透（非法用户会使用一般数据库里没有的key来进行访问导致请求一直打到数据库，导致数据库崩溃）。布隆过滤器删除key困难（会影响其他key），更建议直接使用redis set（设置过期时间）

2.什么是布隆过滤器

(1) 数据结构

布隆过滤器（Bloom Filter）1970年由Bloom的老哥提出

init.png

它由一个二进制数组来记录数据的相关性,数组中只有1或0

二进制数组的优势：申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间。

因为数组为固定长度，在数据量越多而空间越少的情况，判断误差率会变大

(2) 原理

add.png

当一个元素加入布隆过滤器时：

布隆过滤器中的多个哈希函数对元素值进行计算，得到索引值，之后数组长度对该索引值取模算的数组位置
多个哈希函数有多个计算后的数组位置，置为1，完成add操作

exist.png

当判断一个元素是否存在时：

多个哈希函数对元素值计算出位置后，如果有一个位置值为0，则肯定不存在
如果多个位置值都为1，则表示极有可能存在（可能其他元素把这几个位置提前置为1了，导致的误判）

(3) 使用

使用注意点：

使用时不要让实际元素数量远大于初始化数量；
当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进行；
初始化的数量和误判率根据实际业务场景分配

场景：

单机场景中 - Guava Bloom Filter

# 1.依赖
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.0-jre</version>
</dependency>

# 2.使用
# 2.1 创建布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create(
        Funnels.integerFunnel(),
        1500,
        0.01);
# 2.2 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
# 2.3 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));

分布式场景中 - Redisson Bloom Filter

# 1.依赖
<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.7.5</version>
</dependency>

# 2.获取存储在redis中的布隆过滤器
RBloomFilter<String> filter = redissonClient.getBloomFilter("BloomFilter");

# 3.不存在时初始化,
filter.tryInit(10000, 0.01);
for (int i=0;i<20;i++){
    # 4.新增
    filter.add(StrUtil.toString(i));
}

# 5.判断是否存在
for (int i=0;i<20;i++){
    log.info("key:{},是否存在：{}",i,filter.contains(StrUtil.toString(i)));
}

最后编辑于：2020.05.19 16:57:13