基于Redis的BloomFilter实战
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了基于Redis的BloomFilter实战，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2743字，纯文字阅读大概需要4分钟。
内容图文
离线数据处理与实时数据处理有很大的不同，其中一个例子就是去重。在聚数据中，访问UV和购买UV都需要实时的去重。离线处理的时候，我们可以通过count(groupby)或者count(distinct)等方式比较容易的计算出UV，而且不用太担心性能，大不了就是多一点map或者执
离线数据处理与实时数据处理有很大的不同，其中一个例子就是去重。在聚数据中，访问UV和购买UV都需要实时的去重。离线处理的时候，我们可以通过count(groupby)或者count(distinct)等方式比较容易的计算出UV，而且不用太担心性能，大不了就是多一点map或者执行时间久一点。那么在实时计算的时候，我们有什么好的办法来做这个事情呢？
在聚数据中有两种场景：
1，数据的准确性要求高，最好就是完全准确的，例如购买UV。同时交易数据量比较小，聚划算每天的交易笔数仅在百万级别。对于这样的情况，我们采用了基于HBase的过滤。具体做法如下：
建立HBase去重表，对ColumnFamily设置过期时间，如：HColumnDescriptor.setTimeToLive(3*24*60*60);这样3天后的数据将自动删除，以免表过大。然后利用hbase的increment计数，判断计数值是否等于1即可。非常简单粗暴。
2，数据的准确性要求不是很严格，允许有少许的误差，例如访问UV。往往数据量也比较大，聚划算每天的访问UV在千万级别。这种情况我们想到了BloomFilter，也就是本文的重点。
BloomFilter原理：
简单的说就是：通过将一个key的hash值分布到一个大的bit数组上面，判断一个key是否存在时只需判断该的hash对应的bit位是否都是1，如果全是1则表示存在，否则不存在。
优点：性能很高主要在hash算法上面，空间占用小，能够极大的缩小存储空间。
缺点：存在误判。既对应的bit位刚好被其他的key置为1了。
好在误判率是可控的，我们假设kn<m且各个哈希函数是完全随机的。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时，误判率的计算公式是：
(1 – e^(-k * n / m)) ^ k ?对应的java代码：Math.pow((1 – Math.exp(-k * numberOfElements?/ (double) bitSetSize)), k);
对于公式对应的具体原理，个人觉得不必去深究，只需要记住下面两句话，即可将BloomFilter应用自如：
1，如果他告诉你不存在，则一定不存在；
2，如果他告诉你存在，则可能不存在。
因此BloomFilter最理想的应用场景是在一些复杂的查询时，在DB上做一层BloomFilter判断，如果BloomFilter判断不存在，则没必要到DB去查了。顶多就是出现误判时，多到DB查询一下，而这个概率是很低的。
上面说到的BloomFilter还紧紧是单机内存的，在淘宝这个环境下，显然是不适用的。那么我们如何把他变成分布式的呢？看了标题我想你已经知道了，对了，那就是redis。
BloomFilter需要的bit数组与redis的bit操作真是完美契合啊。利用redis的高性能以及通过pipeline将多条bit操作命令批量提交，实现了多机BloomFilter的bit数据共享。唯一需要注意的是redis的bitmap只支持2^32大小，对应到内存也就是512MB,数组的下标最大只能是2^32-1。不过这个限制我们可以通过构建多个redis的bitmap通过hash取模的方式分散一下即可。同时利用上面的公式计算一下：万分之一的误判率，512MB可以放下2亿左右的数据，而目前全网的uv也就8千万，所以，你懂的。
内容总结
以上是互联网集市为您收集整理的基于Redis的BloomFilter实战全部内容，希望文章能够帮你解决基于Redis的BloomFilter实战所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。