基于Redis的BloomFilter实战
作者 斯人 | 发布于 2014 年 4 月 24 日
Redis

离线数据处理与实时数据处理有很大的不同,其中一个例子就是去重。在聚数据中,访问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千万,所以,你懂的。

原文出处:http://www.imsiren.com/archives/988