1.布隆过滤器
我们平时刷今日头条，今日头条会给我们推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，如何实现推送去重呢？
下意识会想到，我们在数据库里记录好给用户推荐过的新闻，每次给用户推荐前，我们先去记录表里查一下，看是否推荐过。
存在问题：当数据量和并发量都很高时，数据库扛不住
此时有小伙伴会说，那我存redis里，存redis里当数据量大时，会占用大量空间，也不是一个好的方案。
布隆过滤器可以理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。
当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在。
布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过的新内容，它也会过滤掉极小一部分（误判），但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。
Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。
2.基本使用
bf.add 添加元素，bf.exists 查询元素是否存在。
布隆过滤器插件安装
[root@izuf65itgtxe1lpfpb***** redis]# git clone https://github.com/RedisBloom/RedisBloom.git
[root@izuf65itgtxe1lpfpb***** redis]# cd RedisBloom/
[root@izuf65itgtxe1lpfpb***** RedisBloom]# make
[root@izuf65itgtxe1lpfpb***** RedisBloom]# vi /usr/local/redis/redis.conf
## 增加配置
loadmodule /usr/local/redis/RedisBloom/redisbloom.so
## 重启redis就行
127.0.0.1:6379> bf.add bloomFilterKey user1
(integer) 1
127.0.0.1:6379> bf.add bloomFilterKey user2
(integer) 1
127.0.0.1:6379> bf.exists bloomFilterKey user2
(integer) 1
127.0.0.1:6379> bf.exists bloomFilterKey user3
(integer) 0
3.原理
添加元素时，先把value转化为字节（getBytes(value,”UTF-8")），通过算法对元素计算出k（14）个独立的hash值，然后用这k个独立的hash值与位图长度（ 201978）进行取余，对应位置设置1。
判断元素是否存在，对元素计算出k个独立的hash值，然后用这k个独立的hash值与位图长度（201978）进行取余，所有的位置都是1表示存在，只要有一位为0都是不存在。
使用时不要让实际元素远大于初始化大小，当实际元素开始超出初始化大小时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进去（这就要求我们在其它的存储器中记录所有的历史元素）。 因为 error_rate 不会因为数量超出就急剧增加，这就给我们重建过滤器提供了较为宽松的时间。
为什么会存在误差？
因为这个位置为1，有可能是其他key设置的
建议：使用时不要让实际元素远大于初始化大小，当实际元素开始超出初始化大小时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进去（这就要求我们在其它的存储器中记录所有的历史元素）。因为 error_rate 不会因为数量超出就急剧增加，这就给我们重建过滤器提供了较为宽松的时间。
注意：位图长度越长错误率越低，但是需要很大的空间，一般这里都是用预计放入元素量，当实际数量超出这个值时，误判率会上升
错误率计算器：https://krisives.github.io/bloom-calculator/
4.实战
还是用最开始我们说的需求，实现新闻推送去重，假设需求需要我们保证100%的正确率，我们该如何优化呢？
我们需要设计两层校验，第一层是布隆过滤器，第二层是MySQL。
public void exist(String data) {
// 数据是否存在
boolean existFlag = false;
// 1.先去布隆过滤器判断
if(bloomFilter.exist(data)) {
// 2.如果布隆过滤器存在，需要在MySQL中进行二次校验
if(mysqlService.exist(data)) {
// 3.数据存在
existFlag = true;
}
}
return existFlag;
}
public void insertRecord() {
// 1.先插入布隆过滤器
// 2.插入到数据库
}
有些同学说，我的Redis版本低于4.0怎么办？
我们可以使用redis位图自己实现一个布隆过滤器
</br>
布隆过滤器使用场景：
- 黑名单
- 爬虫，爬网页前先判断url是否已经爬过，若爬过就不再爬取
- 缓存穿透
网友评论