上一节我们学会了使用 HyperLogLog 数据结构来进行估数，它非常有价值，可以解决很多精确度不高的统计需求。但是如果我们想知道某一个值是不是已经在 HyperLogLog 结构里面了，它就无能为力了，它只提供了 pfadd 和 pfcount 方法，没有提供 pfcontains 这种方法。
讲个使用场景，比如我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？
布隆过滤器
如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难扛住压力的。
你可能又想到了缓存，但是如此多的历史记录全部缓存起来，那得浪费多大存储空间啊？而且这个存储空间是随着时间线性增长，你撑得住一个月，你能撑得住几年么？但是不缓存的话，性能又跟不上，这该怎么办？
这时，布隆过滤器 (Bloom Filter) 闪亮登场了，它就是专门用来解决这种去重问题的。它在起到去重的同时，在空间上还能节省 90% 以上，只是稍微有那么点不精确，也就是有一定的误判概率。
布隆过滤器是什么？
布隆过滤器可以理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在。
套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过的新内容，它也会过滤掉极小一部分 (误判)，但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。
参考文章给出的示例：https://www.cnblogs.com/wxisme/p/5742456.html
引入Maven：
<dependency>
<groupId>com.github.wxisme</groupId>
<artifactId>bloomfilter</artifactId>
<version>1.0.0</version>
<scope>test</scope>
</dependency>
修改对应的主程序：
/**
* @Auther: majx2
* @Date: 2019-3-22 10:08
* @Description:
*/
public class AdvancedTest {
private static final String CODEHOLE = "codehole";
private static final int EXPECT_VALUE = 1000;
Jedis jedis = RedisDS.create().getJedis();
@Test
public void testHyperLogLog(){
for (int i = 0; i < EXPECT_VALUE; i++) {
jedis.pfadd(CODEHOLE+1, "user" + i);
}
System.out.printf("真实值：%d ,期待值：%d\n", jedis.pfcount(CODEHOLE+1), EXPECT_VALUE);
for (int i = 0; i < EXPECT_VALUE; i++) {
jedis.pfadd(CODEHOLE+2, "user" + i);
}
jedis.pfmerge(CODEHOLE,CODEHOLE+1,CODEHOLE+2);
System.out.printf("真实值：%d ,期待值：%d\n", jedis.pfcount(CODEHOLE), EXPECT_VALUE);
jedis.del(CODEHOLE,CODEHOLE+1,CODEHOLE+2);
}
@Test
public void testBloomFilter(){
//(falsePositiveProbability, expectedNumberOfElements)
BloomFilter<String> filter = new BloomFilter<>(0.001, 500);
filter.bind(new RedisBitSet(jedis, CODEHOLE));
List<String> users = randomUsers(1000);
List<String> usersTrain = users.subList(0, users.size() / 2);
List<String> usersTest = users.subList(users.size() / 2, users.size());
for (String user : usersTrain) {
filter.add( user);
}
int falses = 0;
for (String user : usersTest) {
boolean ret = filter.contains(user);
if (ret) {
falses++;
}
}
System.out.printf("错误判断：%d，测试用户数：%d\n", falses, usersTest.size());
System.out.println("filter总数："+filter.count());
System.out.println("filter是否为空："+filter.isEmpty());
filter.clear();
}
private String chars;
{
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 26; i++) {
builder.append((char) ('a' + i));
}
chars = builder.toString();
}
private String randomString(int n) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < n; i++) {
int idx = ThreadLocalRandom.current().nextInt(chars.length());
builder.append(chars.charAt(idx));
}
return builder.toString();
}
private List<String> randomUsers(int n) {
List<String> users = new ArrayList<>();
for (int i = 0; i < n; i++) {
users.add(randomString(64));
}
return users;
}
}
返回结果：
错误判断：13，测试用户数：500
修改精确率，设置为0.00001
...
BloomFilter<String> filter = new BloomFilter<>(0.00001, 500);
...
返回结果：
错误判断：0，测试用户数：500
利用redis的高性能以及通过pipeline将多条bit操作命令批量提交，实现了多机BloomFilter的bit数据共享。唯一需要注意的是redis的bitmap只支持232 大小，对应到内存也就是512MB,数组的下标最大只能是232-1。不过这个限制我们可以通过构建多个redis的bitmap通过hash取模的方式分散一下即可。万分之一的误判率，512MB可以放下2亿条数据。
布隆过滤器的其它应用
在爬虫系统中，我们需要对 URL 进行去重，已经爬过的网页就可以不用爬了。但是URL 太多了，几千万几个亿，如果用一个集合装下这些 URL 地址那是非常浪费空间的。这时候就可以考虑使用布隆过滤器。它可以大幅降低去重存储消耗，只不过也会使得爬虫系统错过少量的页面。
布隆过滤器在 NoSQL 数据库领域使用非常广泛，我们平时用到的 HBase、Cassandra 还有 LevelDB、RocksDB 内部都有布隆过滤器结构，布隆过滤器可以显著降低数据库的 IO 请求数量。当用户来查询某个 row 时，可以先通过内存中的布隆过滤器过滤掉大量不存在的row 请求，然后再去磁盘进行查询。
邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低。
本文基于《Redis深度历险：核心原理和应用实践》一文的JAVA实践。更多文章请参考：高性能缓存中间件Redis应用实战（JAVA）
备注：单机版本也可考虑使用Guava的实现。参考：https://blog.csdn.net/tianyaleixiaowu/article/details/74739827
网友评论