Redis–集成布隆过滤器

总结于《Redis 深度历险：核心原理与应用实践》

业务场景

我们在推荐不重复的热点内容给用户观看，避免重复推送。
或者判断一个信息是否在黑名单或白名单中

是什么？

对于上一个场景我们可能想到缓存，来缓存每次用户看过的数据，但是时间一长缓存也会变的非常大浪费空间。

这个时候布隆过滤器就出场了，它可以节省 90 % 的空间，只不过可能存在一些误判的情况。

布隆过滤器可以看作是一个不是百分百精确的一个 Set 集合，当使用它的 contains 方法时可能会出现误判的情况，但是这种误判也可以通过参数的设置把概率降的很低。

可以这么理解布隆过滤器说他不存在，那么他就一定不存在；如果说他存在，那么他有一定几率不存在。有点宁错杀三千不放过一个的意思。

这个特性可以用在推送上面，比如客户每天收到推荐的新消息如何做到不重复。我们可能会想到用 SQL 语句中的 exists 来判断是否存在，但是性能上数据库并不能扛住很高的并发量。这时就可以用布隆过滤器来进行过滤，筛选出用户没有看过的信息。

bloom filter 的使用

首先要确保安装 redis 4.0 以上的版本，因为 4 及以上的版本才支持布隆插件。下载链接
我这里下载的是 5.0.5 版本，基本的安装教程略过网上有很多，这里讲一下插件的安装

第一步：下载插件

1	wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz

第二步：解压并安装，生成 so 文件

[root@redis]# tar -zxvf v1.1.1.tar.gz
[root@redis]# cd RedisBloom-1.1.1/
[root@RedisBloom-1.1.1]# ls
contrib  Dockerfile  docs  LICENSE  Makefile  mkdocs.yml  ramp.yml  README.md  rebloom.so  src  tests

第三步：找到配置文件（redis.conf）加入该模块

根据自己的目录情况，我的配置文件是在 /usr/local/redis/bin 下的
下载的插件在 /opt/redis/ 下面

[root@redis]# cd /usr/local/redis/bin
[root@bin]# ls
redis.conf
[root@bin]# vim redis.conf

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

# it will abort. It is possible to use multiple loadmodule directives.
# 这里改成自己插件的所在位置
loadmodule /opt/redis/RedisBloom-1.1.1/rebloom.so

第四步：启动 redis 即可

1	[root@bin]# ./redis-server redis.conf

第五步：验证是否启用成功

127.0.0.1:6379> ping
PONG
127.0.0.1:6379> bf.add users user1
(integer) 1
127.0.0.1:6379> bf.add users user2
(integer) 1
127.0.0.1:6379> bf.add users user3
(integer) 1
127.0.0.1:6379> BF.EXISTS users user4
(integer) 0
127.0.0.1:6379> BF.EXISTS users user3
(integer) 1

Java 客户端 Jedis-2.x 没有提供指令扩展机制，所以你无法直接使用 Jedis 来访问 Redis Module 提供的 bf.xxx 指令。RedisLabs 提供了一个单独的包 JReBloom，但是它是基于 Jedis-3.0，Jedis-3.0 这个包目前还没有进入 release，没有进入 maven 的中央仓库，需要在 Github 上下载。在使用上很不方便，如果怕麻烦，还可以使用 lettuce，它是另一个 Redis 的客户端，相比 Jedis 而言，它很早就支持了指令扩展。

public class BloomTest {

  public static void main(String[] args) {
    Client client = new Client();

    client.delete("codehole");
    for (int i = 0; i < 100000; i++) {
      client.add("codehole", "user" + i);
      boolean ret = client.exists("codehole", "user" + i);
      if (!ret) {
        System.out.println(i);
        break;
      }
    }

    client.close();
  }

}

我们使用的是默认参数下的布隆过滤器，在 add 之前执行bf.reserve可以显示的设置参数来进一步降低误判率，如果已经有 key 则会报错。bf.reserve有三个参数分别是：key、error_rate、initial_size。错误率越低需要的空间越大initial_size参数表示预计放入的元素数量，当实际数量超出这个数值时，误判率会上升。

默认情况下的error_rate是 0.01，默认的initial_size是 100。

public class BloomTest {

  private String chars;
  {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < 26; i++) {
      builder.append((char) ('a' + i));
    }
    chars = builder.toString();
  }

  private String randomString(int n) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < n; i++) {
      int idx = ThreadLocalRandom.current().nextInt(chars.length());
      builder.append(chars.charAt(idx));
    }
    return builder.toString();
  }

  private List<String> randomUsers(int n) {
    List<String> users = new ArrayList<>();
    for (int i = 0; i < 100000; i++) {
      users.add(randomString(64));
    }
    return users;
  }

  public static void main(String[] args) {
    BloomTest bloomer = new BloomTest();
    List<String> users = bloomer.randomUsers(100000);
    List<String> usersTrain = users.subList(0, users.size() / 2);
    List<String> usersTest = users.subList(users.size() / 2, users.size());

    Client client = new Client();
    client.delete("codehole");
    // 对应 bf.reserve 指令
    client.createFilter("codehole", 50000, 0.001);
    for (String user : usersTrain) {
      client.add("codehole", user);
    }
    int falses = 0;
    for (String user : usersTest) {
      boolean ret = client.exists("codehole", user);
      if (ret) {
        falses++;
      }
    }
    System.out.printf("%d %d\n", falses, usersTest.size());
    client.close();
  }

}

注意事项

布隆过滤器的initial_size估计的过大，会浪费存储空间，估计的过小，就会影响准确率，用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。

布隆过滤器的error_rate越小，需要的存储空间就越大，对于不需要过于精确的场合，error_rate设置稍大一点也无伤大雅。比如在新闻去重上而言，误判率高一点只会让小部分文章不能让合适的人看到，文章的整体阅读量不会因为这点误判率就带来巨大的改变。

原理

他在 add key 的时候会借助多个 hash 函数进行 hash 运算，得到的值再去与数组长度取模得到一个位置，每个hash都会得到一个不同的位置，然后把这些数对应的位置置为 1 即可算 add 完成

当布隆过滤器询问这个 key 是否存在时，跟 add 一样把这几个 hash 都算出来，看如果有一个为 0 ，那么就判断没有，如果全部是 1 那么也只是极有可能存在，因为也要可能是其他的 key 导致。如果这个位数组比较稀疏，那么正确率就会比较大，如果比较拥挤那么正确率就会降低

使用时不要让实际元素远大于初始大小，当大于时就应该重建布隆过滤器，重新分配一个更大的size 的过滤器，再将历史元素批量 add进去（这就要求我们在其他存储器中记录所有元素），不过 error_rate不会因为数量超出而急剧增加，所以这就为重建提供了富裕的时间

布隆过滤器对空间的简单计算

两个输入参数：预计的元素数量 n，第二个是错误率 f

两个输出参数：位数组的长度 l，hash函数数量 k

1
2
3

k=0.7\*(l/n)    # 约等于

f=0.6185^(l/n)  # ^ 表示次方计算，也就是 math.pow

位数组越长则错误率越低。

优势

记住布隆过滤器不存储元素对象内容，仅仅是元素的“指纹”，大概2kb

而想用set实现去重的效果，要存储元素本身的内容就远不止2kb了所以布隆过滤器的空间优势很明显

缺点

算法本身缺点：

元素可以添加到集合中，但不能被删除。
匹配结果只能是“绝对不在集合中”，并不能保证匹配成功的值已经在集合中。
当集合快满时，即接近预估最大容量时，误报的概率会变大。
数据占用空间放大。一般来说，对于1％的误报概率，每个元素少于10比特，与集合中的元素的大小或数量无关。 - 查询过程变慢，hash函数增多，导致每次匹配过程，需要查找多个位（hash个数）来确认是否存在。