1. 布隆过滤器

• 简要介绍布隆过滤器的概念和特点，详细知识请参考几篇参考文献或其它文章。

1.1 概念

简单点说，布隆过滤器本质是一个位数组。

• 当一个元素加入过滤器时，使用多个hash函数对元素求值，并将位数组中对应位置为1；
• 判断一个元素是否在过滤器中时，使用多个函数对元素求值，并判断位数组对应位置是否为1。如果都为1，认为元素在过滤器中；否则认为元素不在过滤器中。

1.2 特点

• 布隆过滤器判断元素存在，可能存在误判；但判断元素不存在，必然不存在。
• 布隆过滤器通过多个hash函数来降低冲突，增加hash函数数目可以降低冲突率。
• 当过滤器中元素达到一定数目时，增加hash函数不能有效降低冲突率。
• 使用位数组，占用数据空间小。
• 删除元素困难。

2

3. 布隆过滤器解决缓存穿透问题

3.1 为什么使用布隆过滤器来解决缓存穿透问题

（1）布隆过滤器与redis set结果对比

为什么不将所有value都存储在redis的set中，在请求数据库之前先访问查询value是否存在？主要有以下几点原因：

• 缓存穿透问题是因为查询了一个数据库中没有的值，需要能够在请求数据库之前判断数据库中是否存在该值。
• 由于redis用来作缓存，本身不可能存储所有的数据（因为内存是昂贵的，就算有32G内存，和T级的存储相比也显得渺小），只能用来存储热点数据。但是又需要有一个速度很快的内存结构来存储所有值，显然没法使用常规的map和set（空间开销巨大）
• 布隆过滤器使用位数组，占用空间极小。
• 布隆过滤器以较低的误判率换取了大量的空间。（存在较低的假阳性，会使得向数据库请求极少的不存在的值，带来较少的时间开销）

布隆过滤器与set空间消耗对比:

（2）布隆过滤器与md5等单向映射算法对比

在value占用空间较大大时（比如网址），还可以将所有的value通过算法单向映射成一个值（比如使用md5），这样只存储映射后的值，而不需要存储value，从而达到节约空间的目的。

布隆过滤器与单向映射后取值空间消耗对比

假设仍有100亿条URL，那么大概需要一个34位（4.25b）的value来表示才能保证较低的冲突率，仍需要大约42.5GB的空间大小，对应布隆过滤器方案如（1）所示只需要25GB

2^34=171 7986 9184

（3）几种方案对比可参考：

3.2 如何使用布隆过滤器解决缓存穿透问题

3.2.1 基本步骤

应用布隆过滤器解决Redis缓存穿透问题主要有以下步骤：

• （1）在添加数据库记录时，向过滤器中增加元素。
• （2）收到请求时，先查询redis缓存，缓存中没有查询布隆过滤器；布隆过滤器中没有直接返回，有查询数据库；
• （3）暂时还不清楚需不需要对过滤器中元素进行删除，以及如何删除，是否可以考虑定时对过滤器进行清空动作？还是需要使用CountBloomFilter结构来实现删除？

3.2.2 请求流程

增加了布隆过滤器的Redis作缓存系统的一次请求过程如下：

4. Redis布隆过滤器实现

4.1.1 借助Redis原生位图实现布隆过滤器

借助位图的话，需要自行实现多个hash函数，以及布隆过滤器的其它特性，可参考：用Redis快速实现BloomFilter

4.1.2 使用Redisson封装的RBloomFilter

redisson封装实体类RBloomFilter，分析源码同样是使用位图实现的，相关细节可分析源码。
RBloomFilter使用代码示例：

public void test1() {
    String filterName = "filterA";

    RBloomFilter bloomFilter = redissonService.redissonClient().getBloomFilter(filterName);
    bloomFilter.tryInit(1000000L, 0.01);

    bloomFilter.add("value1");
    boolean value1Exists = bloomFilter.contains("value1");
    boolean value2Exists = bloomFilter.contains("value2");

    System.out.println("1. Redisson value1 exists: " + value1Exists);
    System.out.println("1. Redisson value2 exists: " + value2Exists);
}

执行结果：

1. Redisson value1 exists: true
1. Redisson value2 exists: false

4.2. RedisBloom模块

Redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。还可以使用 docker 可以直接在 redis 中布隆过滤器。

4.2.1 Redis集成布隆过滤器模块

参考网址：

https://oss.redislabs.com/redisbloom/Quick_Start/

（1）安装RedisBloom模块

git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make

（2）启动redis-server

修改相应的server、conf、redisbloom.so的路径

./redis-server ./redis.conf --loadmodule ./redisbloom.so

4.2.2 主要命令

命令含义BF.ADD filterName value在过滤器中增加某个valueBF.MADD filterName value1 value2增加多个valueBF.EXISTS filterName value判断过滤器中是否存在某个valueBF.MEXISTS filterName value1 value2判断多个value是否存在BF.RESERVE 显式创建过滤器

BF.RESERVE

• error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
• initial_size：布隆过滤器预计储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

错误率越小，需要的空间越大；预计元素个数越大，需要的空间越大。
示例：

bf.reserve urls 0.01 100

4.2.3 Java使用RedisBloom

在Java中如何使用RedisBloom模块呢？
考虑可以通过lua脚本（或其它可以执行原生Redis命令的方式）执行BF.ADD和BF.EXISTS等命令，RedisBloom官方中还推荐了JReBloom库。

（1）lua脚本执行原生命令

代码示例如下：

public void test2() {
    String filterName = "filterB";
    String addValueScript = "return redis.call('BF.ADD', KEYS[1], ARGV[1]); ";
    redisService.executeLuaScript(addValueScript,
            RScript.ReturnType.BOOLEAN,
            Lists.newArrayList(filterName),
            Lists.newArrayList("value1"));

    String valueExistsScript = "return redis.call('BF.EXISTS', KEYS[1], ARGV[1]); ";

    Boolean value1Exists = redisService.executeLuaScript(valueExistsScript,
            RScript.ReturnType.BOOLEAN,
            Lists.newArrayList(filterName),
            Lists.newArrayList("value1"));
    Boolean value2Exists = redisService.executeLuaScript(valueExistsScript,
            RScript.ReturnType.BOOLEAN,
            Lists.newArrayList(filterName),
            Lists.newArrayList("value2"));
    System.out.println("2. LuaScript value1 exists: " + value1Exists);
    System.out.println("2. LuaScript value2 exists: " + value2Exists);
}
复制代码

执行结果：

2. LuaScript value1 exists: true
2. LuaScript value2 exists: false

（2）JRedisBloom

引入jar包和仓库：

    com.redislabs
    jrebloom
    2.0.0-SNAPSHOT

    snapshots-repo
    https://oss.sonatype.org/content/repositories/snapshots

代码示例：

public void test3() {
    String filterName = "filterC";
    Client client = new Client("localhost", 7379);
    client.add(filterName, "value1");
    boolean value1Exists = client.exists(filterName, "value1"); // true
    boolean value2Exists = client.exists(filterName, "value2"); // False
    System.out.println("3. JRedisBloom value1 exists: " + value1Exists);
    System.out.println("3. JRedisBloom value2 exists: " + value2Exists);
}

执行结果：

3. JRedisBloom value1 exists: true
3. JRedisBloom value2 exists: false

5. 总结

布隆过滤器应用诸多，可用来过滤垃圾邮箱、海量URL识别等。用其来解决Redis缓存穿透问题，也只是缓存穿透问题的一种解决方案。