遇到的问题
在业务中,我需要给每个用户保存1w条浏览记录,之后每一次的返回值都要和历史记录做一个去重,即保证用户不会重复看到同一篇文章.
这个需求有两个比较麻烦的地方:
1.空间问题
每个用户1w条,10w用户就是10亿条数据,应该保存在哪里呢?
Redis?哪里有那么大内存给你用.
Hbase?Hbase我不太了解具体原理,据说每次全量查询有点慢啊(后来听大佬说这点数据无压力的).
Mysql?倒是能存下这么多,但是太影响性能了.
2.时间问题
这个需求对即时性要求还是比较高的,用户两次刷新的间隔可能只有几秒钟,在此期间就要完成历史数据的添加以及过滤.
每次返回用户10条数据,每一条都需要和数据库中的1w条做比对,听起来效率就很差的样子.
在大佬的推荐下,我去了解了一下布隆过滤器,最后初步使用布隆过滤器 Redis Hbase完成了一个版本,效率和空间占用都还可以.
布隆过滤器
介绍
以下摘自维基百科:
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
说直白一点就是:布隆过滤器用自己的算法,实现了快速的检索一个元素是否在一个较大的元素列表之中.
原理
当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
假设我们现在获得了一个size=10000的布隆过滤器,分配给我们的其实是10000个二进制位,假设k=8,那么当新添加huyanshi这个元素时,通过8个不同的hash函数,可以拿到8个index值,假设为1,2300,222,11...,我们就将这8个index为下标的位置,置为1.
当我们想要检索huyanshi是否存在时,再次用8个hash函数获得8个index,如果这8个index的位置都为1,那么这个元素就很可能存在.如果其中有一位为0,则该元素一定不存在.
注意上面的可能加粗了,下面就要说优缺点了.
优点
- 效率高,插入和查询操作都是O(k).
- 空间节省,每一个元素映射为一个二进制位,必须节省.
- 安全,保存了数据的全集,但是没有保存数据本身.
缺点
- 误算率,使用了Hash算法,那么久必然会存在极限巧合下的hash碰撞.会将不存在的数据认为是存在的.但是存在的数据一定是可以正确判断的.
- 很难删除数据.
使用场景
根据优缺点,我们可以分析出他的使用场景,那么就是的正确率要求不是100%,同时存在海量的数据集.
- 字处理软件中，需要检查一个英语单词是否拼写正确
- 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上
- 在网络爬虫里，一个网址是否被访问过
- yahoo, gmail等邮箱垃圾邮件过滤功能
具体实现
布隆过滤器作为一个成熟的过滤器,应该学会实现自己了.
啊,不对,是网上有许多的简易版实现,代码不到100行就可以,因此这里不贴代码了.
我在项目中使用了google guava项目下的BloomFilter,挺好用的.
我的解决方案
1. hbase部分
hbase负责存储用户浏览记录的原始数据,只保存用户浏览的文章的id或者url,这里以id为例.
通过范围查询可以获得name:huyanshi,history=[1,2,4,5,6]格式的数据.
2. redis部分
在这里面使用redis,主要是考虑到,针对活跃用户,及频繁刷新的用户,每次请求都全量从Hbase拉取数据,然后构造布隆过滤器,即时Hbase扛得住,我觉得这个构造过滤器的时间也太长了.因此使用redis对过滤器进行缓存.
在redis中存储序列化后的布隆过滤器对象,时间为30分钟,30分钟内用户如果再次访问,直接从redis中获取过滤器,然后进行过滤操作.
3. 布隆过滤器部分
主要是添加以及查询两个操作,从hbase拿到数据之后,构造过滤器,然后对当前返回的10条内容进行判重.之后将新的10条内容加入过滤器,再次写入redis.
流程图
好久没画图了,,,慌得一批.
完.
ChangeLog
2018-12-18 完成
以上皆为个人所思所得，如有错误欢迎评论区指正。
欢迎转载，烦请署名并保留原文链接。
联系邮箱：huyanshi2580@gmail.com
