基于Redis的BloomFilter实战

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