数据量庞大时如何去重?

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!
我们平时刷今日头条,今日头条会给我们推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,如何实现推送去重呢?
下意识会想到,我们在数据库里记录好给用户推荐过的新闻,每次给用户推荐前,我们先去记录表里查一下,看是否推荐过。
存在问题:当数据量和并发量都很高时,数据库扛不住
此时有小伙伴会说,那我存redis里,存redis里当数据量大时,会占用大量空间,也不是一个好的方案。
布隆过滤器可以理解为一个不怎么精确的 set 结构,当你使用它的 contains 方法判断某个对象是否存在时,它可能会误判。但是布隆过滤器也不是特别不精确,只要参数设置的合理,它的精确度可以控制的相对足够精确,只会有小小的误判概率。
当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在
布隆过滤器能准确过滤掉那些已经看过的内容,那些没有看过的新内容,它也会过滤掉极小一部分(误判),但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。
Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中,给 Redis 提供了强大的布隆去重功能。
数据量庞大时如何去重?

布隆过滤器常用命令

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
数据量庞大时如何去重?

布隆过滤器实现原理

添加元素时,先把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/
数据量庞大时如何去重?

布隆过滤器实战

还是用最开始我们说的需求,实现新闻推送去重,假设需求需要我们保证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位图自己实现一个布隆过滤器
布隆过滤器使用场景:
  • 黑名单
  • 爬虫,爬网页前先判断url是否已经爬过,若爬过就不再爬取
  • 缓存穿透

原文始发于微信公众号(Java程序鱼):数据量庞大时如何去重?