布隆过滤器

布隆过滤器是解决 Redis 缓存穿透的常用方案之一，本篇介绍它的原理、优缺点及 Java 实现方式。

1. 布隆过滤器简介

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射（hash）函数，可以用于检索一个元素是否在一个集合中。

本质上布隆过滤器是一种数据结构，一种比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你："某样东西一定不存在或者可能存在"。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。以 Redis 的 set 加 sismember 判断为例，传统方式的时间和空间复杂度都是 O(n)，而布隆过滤器只维护一个二进制位数组。

重要

布隆过滤器"可能存在"的含义：查询返回"存在"时，元素有可能实际不存在（误判）；但返回"不存在"时，元素一定不存在。所以它适合做"拦截"用途，比如过滤非法请求。

2. 存入过程

布隆过滤器上面说了，就是一个二进制位数据的集合。当一个数据加入这个集合时：

1. 通过 K 个哈希函数计算该数据，返回 K 个计算出的 hash 值；
2. 将 K 个 hash 值转换为 K 个二进制数组的下标；
3. 将 K 个下标对应的二进制位改成 1。

3. 查询判断过程

布隆过滤器主要作用就是查询一个数据在不在这些二进制位的集合中，查询过程如下：

1. 通过 K 个哈希函数计算该数据，对应计算出的 K 个 hash 值；
2. 将 K 个 hash 值转换为 K 个二进制数组的下标；
3. 判断：如果存在一处位置的二进制位是 0，那么该数据一定不存在；如果都是 1，则该数据可能存在（可能被其他元素置 1，产生误判）。

4. 布隆过滤器优缺点

维度	说明
优点一	由于存储的是二进制数据，所以占用的空间很小
优点二	插入和查询速度非常快，时间复杂度是 O(K)，可以联想一下 HashMap 的过程
优点三	保密性很好，因为本身不存储任何原始数据，只有二进制数据
缺点	存在误判，但可以通过加长二进制数组的长度以及增加 hash 的次数来降低误判率

5. 使用场景

• 字处理软件中，需要检查一个英语单词是否拼写正确；
• 在 FBI，判断一个嫌疑人的名字是否已经在嫌疑名单上；
• 在网络爬虫里，判断一个网址是否被访问过；
• Yahoo、Gmail 等邮箱的垃圾邮件过滤功能；
• 解决 Redis 缓存穿透（查询请求先过布隆过滤器，一定不存在的数据直接拦截）。

以上只是简单的用途举例，大家可以举一反三，灵活运用在工作中。

6. 布隆过滤器实现

6.1 Google Guava 实现

pom 依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>29.0-jre</version>
</dependency>

package com.wxb.bloom;

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

public class BloomFilterCase {

    /**
     * 预计要插入多少数据
     */
    private static int size = 1000000;

    /**
     * 期望的误判率
     */
    private static double fpp = 0.01;

    /**
     * 布隆过滤器
     */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);

    public static void main(String[] args) {
        // 插入100万样本数据
        for (int i = 0; i < size; i++) {
            bloomFilter.put(i);
        }

        // 用另外十万测试数据，测试误判率
        int count = 0;
        for (int i = size; i < size + 100000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
                System.out.println(i + "误判了");
            }
        }
        System.out.println("总共的误判数:" + count);
    }
}

说明：前 100 万条是真实插入的数据，后 10 万条是从未插入过的数据，用它们测试误判率。在 fpp 为 0.01 时，误判数大约在 1000 条左右，与预期一致。

6.2 Redis 实现（Redisson）

上面使用 Guava 实现的布隆过滤器是把数据放在了本地内存中，分布式的场景中就不合适了，无法共享内存。

我们还可以用 Redis 来实现布隆过滤器，这里使用 Redis 封装好的客户端工具 Redisson。其底层使用的数据结构是 bitMap，大家可以把它理解成上面说的二进制结构。

Redis 操作 bitMap 的相关命令：

# 设置值，其中value只能是 0 和 1
setbit key offset value

# 获取值
getbit key offset

# 获取指定范围内值为 1 的个数
# start 和 end 以字节为单位
bitcount key start end

pom 依赖：

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.12.0</version>
</dependency>

@Test
public void test7() {
    Config config = new Config();
    // 集群模式的配置方式：
    // config.useClusterServers()
    //     .setScanInterval(2000)
    //     .addNodeAddress("redis://10.0.29.30:6379", "redis://10.0.29.95:6379")
    //     .addNodeAddress("redis://10.0.29.205:6379");

    // 单机模式
    config.useSingleServer().setAddress("redis://127.0.0.1:6379");
    // 如需密码和库号，可继续调用 .setPassword(...).setDatabase(...)

    RedissonClient redisson = Redisson.create(config);

    // 初始化布隆过滤器
    RBloomFilter<Object> bloomFilter = redisson.getBloomFilter("nums");
    bloomFilter.tryInit(100000000L, 0.03);

    bloomFilter.add("baidu");
    bloomFilter.add("tencent");

    // baidu1 未插入过，输出 false；若查询 baidu 则输出 true
    System.out.println(bloomFilter.contains("baidu1"));
}

7. 小结

• 布隆过滤器 = 一个二进制位数组 + K 个哈希函数，插入时把 K 个位置置 1，查询时看 K 个位置是否全为 1；
• 结论语义是"一定不存在或可能存在"，适合做拦截，不适合做精确判断；
• 误判率可通过加长位数组、增加哈希次数降低；
• 单机用 Guava，分布式用 Redisson（底层 bitMap），常用于解决缓存穿透。