层峦叠嶂 —— 布隆过滤器

上一节我们学会了使用 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只支持2³² 大小，对应到内存也就是512MB,数组的下标最大只能是2^32-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