【项目实践03】【布隆过滤器】

一、前言

本系列用来记录一些在实际项目中的小东西，并记录在过程中想到一些小东西，因为是随笔记录，所以内容不会过于详细。

二、项目背景

甲方要求，每一个客户的每一份订单里的每个商品如果第一次出现商品金额大于200w 时，需要提示信息。为了保证项目灵活性（，实际实现是通过数据库记录每一份商品出现的最高价格以及时间，同时在缓存中记录着每个客户每个商品当前最大的金额数量。这样如果亲爱的（善变的 ）甲方哪一天要求金额变成为100w或者只比对近一年的单子的商品单价时都可以做及时变更，只需要将Redis 中的缓存清一下重新计算即可。

虽说按照上述方案实现了，但是其实当时想到了使用布隆过滤器的方案，当商品金额大于 200w 时将商品放入布隆过滤器中，下次判断如果布隆过滤器中不存在则说明当前商品没有出现过200w金额的订单。但实际上，这里是不适合使用布隆过滤器的，一是布隆过滤器会出现假阳性情况，二是无法处理上面提到的甲方可能的需求变更（事实证明，甲方真的变了 ）。

所以本篇只是为了使用布隆过滤器实现玩一玩。

布隆过滤器，Bloom Filter是1970年由Bloom提出的，它是由一组哈希（Hash）函数和一个位阵列组成。布隆过滤器可以用于查询一个元素是否存在于一个集合当中，查询结果为以下二者之一：

• 这个元素可能存在于这个集合当中。
• 这个元素一定不存在于这个集合当中。

布隆过滤器的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

布隆过滤器在实际中主要用来解决网页URL去重复，垃圾邮件检测，大集合中重复元素判断和缓存击穿等问题。

三、实现方案

1. 谷歌 布隆过滤器

谷歌在 guava 依赖包中实现了基于内存的布隆过滤器，如下：

   <dependency>
       <groupId>com.google.guava</groupId>
       <artifactId>guava</artifactId>
   </dependency>

Demo 如下：

    public static void main(String[] args) {
        int bfSize = 10000;
        // 创建布隆过滤器，过滤器的元素类型为 Integer, 初始大小为 1000000，差错率为 0.01
        final BloomFilter<Integer> bloomFilter =
                BloomFilter.create(Funnels.integerFunnel(), bfSize, 0.01);

        // 初始化 布隆过滤器的元素
        for (int i = 0; i < bfSize; i++) {
            bloomFilter.put(i);
        }


        int count = 0;
        for (int i = 0; i < bfSize; i++) {
            if (!bloomFilter.mightContain(i)){
                count++;
            }
        }
        System.out.println("逃脱的数量 ：" + count);

        count = 0;
        for (int i = bfSize; i < bfSize + 10000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
            }
        }

        System.out.println("误伤的数量 ：" + count);
    }

2. Redis 布隆过滤器

    public static void main(String[] args) {
        int bfSize = 10000;
        Config config = new Config();
        config.useSingleServer()
                .setTimeout(10000)
                .setDatabase(0)
                .setAddress("redis://127.0.0.1:6379");
        RedissonClient redissonClient = Redisson.create(config);

        final RBloomFilter<Object> bloomFilter =
                redissonClient.getBloomFilter("default");
        bloomFilter.tryInit(bfSize, 0.01);
        for (int i = 0; i < bfSize; i++) {
            bloomFilter.add(i);

        }
        int count = 0;
        for (int i = 0; i < bfSize; i++) {
            if (!bloomFilter.contains(i)){
                count++;
            }
        }
        System.out.println("逃脱的数量 ：" + count);


        count = 0;
        for (int i = bfSize; i < bfSize + bfSize; i++) {
            if (bloomFilter.contains(i)) {
                count++;
            }
        }

        System.out.println("误伤的数量 ：" + count);
    }

四、思路延伸

1. 布隆过滤器的实现原理

布隆过滤器的实现其实很简单，下面直接参考其他人的总结（来源： ）

一个Bloom Filter是基于一个m位的位阵列（b1,…bm），这些位阵列的初始值为0。另外，还有一系列的hash函数（h1,…hk），这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图：

插入x时，三个hash函数分别得到蓝线对应的三个值，并将对应的位向量改为1，插入y，z时，类似的，分别将红线，紫线对应的位向量改为1。

查找时，当查找x时，三个hash值对应的位向量都为1，因此判断x在此数据集中。y，z也是如此。但是当查找w时，w有个hash值对应的位向量为0，因此可以判断不在此集合中。但是，假如w的最后那个hash值比上图中的大1，这是就会认为w在此集合中，而事实上，w可能不在此集合中，因此可能出现误报。显然的，插入数据越多，1的位数越多，误报的概率越大。

总结：

2. 布隆过滤器的一些扩展

以下思路参考 ：布隆过滤器由于本身的不可逆性无法完成删除、扩容等操作，因此当 一个布隆过滤器容量到达上限后，创建一个更大的布隆过滤器，将新增的数据都存入新的布隆过滤器中，这样多个布隆过滤器组成过滤器链，判断Key 是否存在的时候需要判断所有的过滤器。此种方案还可以用于带有时效性的布隆过滤器，如需要判断最近30天内的，即可以创建30个布隆过滤器，每个过滤器存储一天的数据，当30天后将第一个过滤器清除重新使用。

3. 布谷鸟过滤器

布谷鸟过滤器可以说是一个增强版的布隆过滤器，可以删除元素，查询效率更高，空间利用率更高。如有需要详参：

五、参考内容