在之前的分布式缓存一文中，提到过缓存穿透一个解决方案是布隆过滤器。本文将对布隆过滤器进行一个详细的介绍。

布隆过滤器原理

布隆过滤器(BloomFilter)实际上是一种数据结构，包括一个很长的二进制向量和一系列随机映射函数。主要用于检索一个元素是否在一个集合中。

优点是空间效率和查询时间效率都很高，缺点是有一定的误判率，并且不支持元素删除。

在布隆过滤器的内部，维护了一个位数组bitArray。开始时所有的位都为0。

当插入一个元素时，通过多个哈希函数计算该元素的哈希值，在哈希值对应的数组下标处，将0置为1。

下面通过一个例子来具体说明。初始数组如下：

插入第一个元素a，假设经过三个哈希函数计算，得到哈希值分别为1,2,3，则将数组(从1开始)对应的位置上的0置位1，得到新的数组如下：

然后插入第二个元素b，假设经过三个哈希函数计算，得到哈希值分别为4,5,6，则将数组对应的位置上的0置位1，得到新的数组如下：

现在判断元素a是否在过滤器中，则查看数组1,2,3位置上的数，都为1说明a存在于过滤器中。

要判断元素c是否在布隆过滤器中，经过三个哈希函数计算获得哈希值1,5,7。查看数组上1,5,7的位置上是否存在0，发现位置7的数为0，因此判定c不在。

那如果元素c经过三个哈希函数计算得到的哈希值为1,5,6呢？此时的结果则是元素c在该过滤器中，这就是误判。
了解哈希表的都知道，c元素被误判的原因是计算c的哈希值时出现了哈希碰撞，并且三个哈希值都发生了碰撞。

通过上述例子可以得到一个结论：布隆过滤器可以确切得判断一个元素不存在，但不能百分之百的判断一个元素存在。

当布隆过滤器中添加的元素越来越多时，被占的bit位就越来越多，此时发生哈希碰撞的概率就越高，误判的可能性就变高。

当所有的bit位都被置为1时，这时候布隆过滤器就失去了过滤的功能，此时任何元素都会判断为存在。因此，选择一个合适的过滤器长度就显得非常重要。

至于不支持元素删除也很好理解，因为元素的哈希值可能存在哈希碰撞(所有的哈希值都碰撞时才会误判)。

比如元素c的哈希值为1,5,7。其中，1与元素a的哈希值碰撞，5与元素b的哈希值碰撞，7没有碰撞。

如果删除元素c，也就是将1,5,7置为0，显然此时元素a和元素b的判断就会出现错误。

准确性

要想提高布隆过滤器的准确性，主要有两点：

• 多个哈希函数，减少hash碰撞的概率。
• 扩大数组范围，使hash值均匀分布，减少hash碰撞的概率。

虽然布隆过滤器已经尽可能减少hash碰撞的概率，但是不能完全消除。关于布隆过滤器的数组大小和相应的hash函数个数的选择，具体推导过程这里不详述，直接给出结论：

(1) 设m为数组大小，n为元素个数，对于固定的m/n，最佳的哈希函数个数为：k = (m/n)ln2（个数越多则布隆过滤器 bit 位置为 1 的速度越快，且布隆过滤器的效率越低）。

(2) 误判率与各参数的取值如下：

在redis中的应用

Redis在4.0之后的版本中提供了提供了布隆过滤器插件，安装之后可以使用其功能。
在https://github.com/RedisBloom/RedisBloom下载最新的release源码，在编译服务器进行解压编译得到动态库：redisbloom.so
将该动态库拷贝到redis目录下。修改redis.conf:

################################## MODULES #####################################

# Load modules at startup. If the server is not able to load modules
# it will abort. It is possible to use multiple loadmodule directives.
loadmodule /usr/local/redis-5.0.5/redisbloom.so
# loadmodule /path/to/my_module.so
# loadmodule /path/to/other_module.so

在配置文件中加载redisbloom这个module。

在redis启动的时候指定配置文件：nohup ./redis-server /usr/local/redis-5.0.5/redis.conf &

当然，生产环境中的redis不能随便重启，可以直接通过命令来热加载redis插件，如下图所示：

127.0.0.1:6379> module list
(empty list or set)
127.0.0.1:6379> module load /usr/local/redis-5.0.5/redisbloom.so 
OK
127.0.0.1:6379> module list
1) 1) "name"
   2) "bf"
   3) "ver"
   4) (integer) 999999

模块名为bf，模块版本号为999999。

布隆过滤器操作命令如下：

• bf.add: 添加元素
• bf.exists: 查询元素是否存在
• bf.madd: 添加多个元素
• bf.mexists: 查询多个元素是否存在

添加元素并判断是否存在：

127.0.0.1:6379> bf.add users 2
(integer) 1
127.0.0.1:6379> bf.exists users 1
(integer) 0
127.0.0.1:6379> bf.exists users 2
(integer) 1

详细命令：

Java中的布隆过滤器

在google的guava工具包中实现了BloomFilter：

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class GuavaBloomFilter {
    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100000, 0.01);

        bloomFilter.put("10086");

        System.out.println(bloomFilter.mightContain("123456"));
        System.out.println(bloomFilter.mightContain("10086"));
    }
}

参考资料

[1]. https://www.zhihu.com/question/38573286
[2]. https://www.jianshu.com/p/f04edbded1b9