布隆过滤器

布隆过滤器不是专属于redis，此处是用来和 redis 结合使用。

1、场景

我们用 HyperLogLog 来估计一个数，有偏差但是也够用。HyperLogLog 主要提供两个方法：

• pfadd

• pfcount

但是 HyperLogLog 没有判断是否包含的方法，例如 pfexists 、pfcontains 等。没有这样的方法存在，但是我们有这样的业务需求。

例如刷今日头条，推送的内容有相似的，但是没有重复的。这就涉及到如何在推送的时候去重？

解决方案很多，例如将用户的浏览历史记录下来，然后每次推送时去比较该条消息是否已经给用户推送了。但是这种方式效率极低，不推荐。

解决这个问题，就要靠我们今天要说的布隆过滤器。

2、Bloom Filter 介绍

Bloom Filter 专门用来解决我们上面所说的去重问题的，使用 Bloom Filter 不会像使用缓存那么浪费空间。当然，他也存在一个小小问题，就是不太精确。

Bloom Filter 相当于是一个不太精确的 set 集合，我们可以利用它里边的 contains 方法去判断某一个对象是否存在，但是需要注意，这个判断不是特别精确。一般来说，通过 contains 判断某个值不存在，那就一定不存在，但是判断某个值存在的话，则他可能不存在。

以今日头条为例，假设我们将用户的浏览记录用 B 表示，A 表示用户没有浏览的新闻，现在要给用户推送消息，先去 B 里边判断这条消息是否已经推送过，如果判断结果说没推送过（B 里边没有这条记录），那就一定没有推送过。如果判断结果说有推送过（B 里边也有可能没有这条消息），这个时候该条消息就不会推送给用户，导致用户错过该条消息，当然这是概率极低的。

3、Bloom Filter 原理

每一个布隆过滤器，在 Redis 中都对应了一个大型的位数组以及几个不同的 hash 函数。

所谓的 add 操作是这样的：

首先根据几个不同的 hash 函数给元素进行 hash 运算一个整数索引值，拿到这个索引值之后，对位数组的长度进行取模运算，得到一个位置，每一个 hash 函数都会得到一个位置，将位数组中对应的位置设置为 1 ，这样就完成了添加操作。

image-20210419110458793

当判断元素是否粗存在时，依然先对元素进行 hash 运算，将运算的结果和位数组取模，然后去对应的位置查看是否有相应的数据，如果有，表示元素可能存在（因为这个有数据的地方也可能是其他元素存进来的），如果没有表示元素一定不存在。

Bloom Filter 中，误判的概率和位数组的大小有很大关系，位数组越大，误判概率越小，当然占用的存储空间越大；位数组越小，误判概率越大，当然占用的存储空间就小。

4、Bloom Filter 安装

官网： https://oss.redislabs.com/redisbloom/Quick_Start/

4.1 docker 安装

docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

4.2 编译安装

# 先克隆 （在redis的安装目录下执行的）
git clone https://github.com/RedisBloom/RedisBloom.git
 
# 再编译
cd RedisBloom
make
 
 
# 启动 （根据对应的路径） 
src/redis-server --loadmodule ./RedisBloom/redisbloom.so
 
# 后台启动
src/redis-server redis.conf --loadmodule ./RedisBloom/redisbloom.so 

安装完成后，执行 bf.add 命令，测试安装是否成功。

127.0.0.1:6379> BF.ADD k1 v1
(integer) 1
127.0.0.1:6379> 

每次启动时都输入 src/redis-server redis.conf --loadmodule ./RedisBloom/redisbloom.so 比较麻烦，我们可以将要加载的模块在 redis.conf 中提前配置好。

vim redis.conf
 
 # 添加一行：
loadmodule /home/redis/redis-6.0.8/RedisBloom/redisbloom.so

最下面这一句，配置完成后，以后只需要 redis-server redis.conf 来启动 Redis 即可。

5、基本用法

主要是两类命令，添加和判断是否存在。

• bf.add\bf.madd 添加和批量添加

• bf.exists\bf.mexists 判断是否存在和批量判断

# 添加
127.0.0.1:6379> bf.add k1 v1
(integer) 1
# 判断是否存在，存在返回 1，不存在返回 0
127.0.0.1:6379> bf.exists k1 v1
(integer) 1
127.0.0.1:6379> bf.exists k1 v2
(integer) 0

# 批量添加
127.0.0.1:6379> bf.madd k1 v2 v3 v4 v5
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
# 批量判断是否存在
127.0.0.1:6379> bf.mexists k1 v1 v2 v3 v7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
127.0.0.1:6379> 

使用 Jedis 操作布隆过滤器，首先添加依赖：

<dependency>
    <groupId>com.redislabs</groupId>
    <artifactId>jrebloom</artifactId>
    <version>2.1.0</version>
</dependency>

测试使用：

public class BloomFilter {
    public static void main(String[] args) {
        GenericObjectPoolConfig config = new GenericObjectPoolConfig();
        // 连接池最大空闲数
        config.setMaxIdle(300);
        // 连接池最大连接数
        config.setMaxTotal(1000);
        // 连接最大等待时间，如果是 -1， 表示没有限制
        config.setMaxWaitMillis(3000);
        // 在空闲时检查有效性
        config.setTestOnBorrow(true);
        /*
            1.Redis地址
            2.Redis端口
            3.连接超时时间
            4.Redis密码
         */
        JedisPool pool = new JedisPool(config, "172.81.247.170", 6379, 30000, "lucky");

        Client client = new Client(pool);

        // 存入数据
        for (int i = 0; i < 100000; i++) {
            client.add("name", "lucky-" + i);
        }

        // 检查数据是否存在
        boolean exists = client.exists("name", "lucky-999999");
        System.out.println(exists);
    }
}

默认情况下，我们使用的布隆过滤器的错误率是 0.01，默认的元素大小是 100。但是这两个参数也是可以配置的。

我们可以调用 bf.reserve 方法进行配置：

127.0.0.1:6379> BF.RESERVE key1 0.0001 1000000
OK

第一个参数是 key，第二个参数是错误率，错误率越低，占用的空间越大，第三个参数预计存储的数量，当实际数量超出预计数量时，错误率会上升。

6、典型场景

新闻推送过滤算是一个应用场景。

解决 Redis 穿透 或者又叫缓存击穿问题。

场景如下：

假设我有 1亿 条用户数据，现在查询用户要去数据库中查，效率低而且数据库压力大，所以我们会把请求首先在 Redis 中处理（活跃用户存在 Redis 中），Redis 中没有的用户，再去数据库中查询。

现在可能会存在一种恶意请求，这个请求携带上了很多不存在的用户，这个时候 Redis 无法拦截下来请求，所以请求会直接跑到数据库里去。这个时候，这些恶意请求会击穿我们的缓存，甚至数据库，进而引起“雪崩效应”。

为了解决这个问题，我们就可以使用布隆过滤器。将 1亿条用户数据存在 Redis 中不现实，但是可以存在布隆过滤器中，请求来了，首先去判断数据是否存在，如果存在，再去数据库中查询，否则就不去数据库中查询。