what? 还不知道布隆过滤器吗?

前言

在好早之前，我在看面试宝典的时候，关于预防缓存雪崩，其中有一个解决方案就是在缓存前面增加布隆过滤器，时至今日，我依然清晰地记着布隆过滤器，但是却不曾深入的了解它，所以今天我想花一点时间来详细了解下布隆过滤器。

布隆过滤器

什么是布隆过滤器？

简单来说，布隆过滤器是一种算法，用于判断某个值是否在一个集合中。

通常来说，我们要判断一个值是否存在集合中，我们是需要将目标值和集合中的每个值进行比较，最终确定是否包含，这样的缺点也很明显，如果数据量本身很庞大的话，我们需要存储的数据量会很多，而且比较的时候也会比较耗时。

相比而言，布隆过滤器的设计就独特了很多，它通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了，这就是布隆过滤器的基本思想。

但是Hash面临的最大问题就是hash冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%，这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的，这个概率我们通常称之为误差率。

所以，简单总结下，布隆过滤器其实就是通过hash来描述一个数据，然后保存该数据的hash值，从而实现数据的判断，但是由于hash的冲突（具体取决于hash表的大小），会导致数据的误判，所以本质上我们布隆过滤器的误判是由于hash表的有限性。

关于hash

hash算法我这里不打算展开（目前我也不是很熟悉i😂），但是我这里想要通过一个简单的示例，来解释下什么是hash。

我们小学二年级的时候，学过平面上两个坐标可以确定唯一一个点（坐标），而我们判断两个点是否是同一个点，是可以通过坐标对比来实现，而hash算法其实本身就相当于一套坐标系，通过这套坐标系理论上我们是可以描述所有数据，且可以确定数据的唯一性（当然具体取决于hash表大小）。

另外一种hash的典型应用就是我们的身份证，每个人的身份证号就是我们每个人的hash code，通过这个hash code就可以在14亿人中确定唯一的你，所以身份证号算法就是一种类似于hash的算法。

博隆过滤器的应用

上面其实我们已经列举了博隆过滤器的典型应用场景——校验某个数据是否存在，所以我们经常把他用在一些需要进行数据否存在的校验上，最典型的就是用在缓存的key的判断上，作为缓存系统最后的屏障。

在通常的系统开发中，我们经常要用到缓存组件，而缓存中最核心的一个场景就是查询，而缓存查询中操作频次最高就是判断某个key是否存在，正常情况下简单的业务判断是没有问题的，就算批量很大，也不会出现大批量key不存在的情况，但是如果遇到恶意攻击时，一切都变得不那么确定了，比如有人发送大量恶意请求专门查询不存在的key，这时候就会导致redis服务不可用，从而导致缓存雪崩。

这时候如果我们用了布隆过滤器这样的组件，这样的问题就不会影响如此严重，因为布隆过滤器可以帮我们屏蔽到绝大多数的请求，从而降低redis雪崩的风险。

关于布隆过滤器的实现，网上其实有很多实现，但最典型的当属guava包中提供的BloomFilter。要说guava真是个好用的工具包，提供了各种各样好用的工具，比如限流组件、容器组件以及今天我们分享的布隆过滤器，下面我们看下如何使用BloomFilter：

由于BloomFilter的构造方案是私有的，所以我们没有办法通过new的方式实例化BloomFilter，但是官方提供了实例化的方式——create方法：

其他的create方法都是在此基础上做的封装，所以我们只简单分析上面这个方法。

这个方案有四个参数：

• Funnel表示我们要过滤的数据类别，它相当于我们的漏斗，也算是容器，用于判断数据是否存在，目前在Funnels类中提供了六种实现，应该可以满足我们绝大多数场景；

• expectedInsertions表示预期样本，也就类似于我们前面说的hash表的大小，如果该数据太小，误差率会很大，原则上来说，这个数要大于等于我们要判断的样本数量，否则没有办法保证准确度，当然也不能太大，过大会有性能问题

• fpp表示误差率，默认是0.003

  

下面是一个简单的示例

public class BloomFilterTest {
    public static void main(String[] args) {
        Funnel charSequenceFunnel = Funnels.stringFunnel(Charset.defaultCharset());
        String test = "hello";
        BloomFilter bloomFilter = BloomFilter.create(charSequenceFunnel, 100);
        for (int i = 0; i < 100; i++) {
            bloomFilter.put(test + i);
        }
        String object = test + -888;
        if (bloomFilter.mightContain(object)) {
            System.out.println("包含" + object);
        } else {
            System.out.println("不包含" + object);
        }
    }
}

正常情况下，会打印输入不包含hello-888：

但是如果我将样本数量变小或者将数据量变大，这时候就会出现误判的情况。

比如这里我判断的是hello-888，bloomFilter中保存的应该是hello0到hello999，应该是不存在才对，但是由于hash表（代称）不够大，所以会出现数据描述精度丢失问题：

但是如果样本数量和数据本身数量差别不大时，则不会出现这种情况。

扩展

Redis v4.0  之后的版本有了 Module（模块/插件） 功能，Redis Modules 可以让 Redis 通过使用外部模块扩展其功能 ，而布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 ：

https://redis.io/modules

另外，官网推荐了一个RedisBloom 作为 Redis 布隆过滤器的Module，地址：

https://github.com/RedisBloom/RedisBloom

另外，redis客户端工具Redisson也提供了布隆过滤器的实现，其底层使用数据结构是bitMap，有兴趣的小伙伴可以去了解下。

结语

布隆过滤器这个东东，已经在我心头萦绕了很久了，但是一直都没有花时间探索过，对它只能算知道有这么个组件，知道它的大概用途，但是对于它的原理和实现逻辑，却不曾了解。今天抽时间做一次简单的探索，也算是搞清楚了布隆过滤器的应用场景和简单的实现原理，当然也清楚了自己在数据底层的短板，比如数据结构——散列，说明我也该好好补下数据结构这块的知识了，数据结构那本书该翻一翻了😂，好了，今天就到这里吧，各位小伙伴，晚安吧！