美文网首页SSM+shiro等javaweb收藏
Redis应用五:布隆过滤器

Redis应用五:布隆过滤器

作者: 一寂知千秋 | 来源:发表于2018-08-22 16:11 被阅读687次

问题一: 我们已经知道了有 HyperLogLog这种数据结构来进行估数,它可以解决很多对精确度要求不高的统计需求。

但是 HyperLogLog只提供了 pfadd 和 pfcount 方法,没有提供 pfcontains这种方法,它无法知道某一个值是否已经在HyperLogLog中。

问题二: 我们举个场景,比如说我们在网页上看新闻的时候,后台的推荐算法会给我们推荐新的内容,它每次推荐是要去重的,去掉我们之前看过的内容。那么问题来了,新闻后台的推荐系统是如何实现推送去重的呢?

也许你会想到服务器记录了用户看过的历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录。问题是当用户量很大,每个用户看过的新闻又很多的情况下,这种方式,推荐系统的去重工作在性能上跟的上么?

实际上,如果历史记录存储在关系数据库里,去重就需要频繁地对数据库进行 exists 查询,当系统并发量很高时,数据库是很难扛住压力的。

也许你会说缓存,但是这么多的历史记录得浪费多少的存储空间啊?而且历史记录和用户是没有上限的,你又能撑多久?更要命的是,redis还有LRU算法呢。

对于问题一、二,布隆过滤器 (Bloom Filter) 闪亮登场了,它是专门用来解决这种去重问题的。它在起到去重的同时,在空间上还能节省 90% 以上,只是稍微有那么点不精确,也就是有一定的误判概率。

布隆过滤器是什么

当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在。

布隆过滤器可以理解为一个不怎么精确的 set 结构,当你使用它的 contains 方法判断某个对象是否存在时,它可能会误判。但是布隆过滤器也不是特别不精确,只要参数设置的合理,它的精确度可以控制的相对足够精确,只会有小小的误判概率。

套在上面的使用场景中,布隆过滤器能准确过滤掉那些已经看过的内容,那些没有看过的新内容,它也会过滤掉极小一部分 (误判),但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。

redis中的布隆过滤器

redis官方提供的布隆过滤器是在redis4.0提供了插件功能后才有的。布隆过滤器作为一个插件加载到 Redis Server 中,给 Redis 提供了强大的布隆去重功能。

bf.add 添加元素,一次只能添加一个
bf.madd 添加元素,一次添加多个
bf.exists 查询元素是否存在,它的用法和 set 集合的 sadd 和 sismember 差不多
bf.mexists 一次查询多个元素

127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1
127.0.0.1:6379> bf.exists codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

我们搞把大的

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 {

  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");
    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();
  }

}

结果可以看出误判率是1%多一点。

total users 100000
all trained
628 50000

布隆过滤器的原理

每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。

向布隆过滤器中添加 key 时,会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置,每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

向布隆过滤器询问 key 是否存在时,跟 add 一样,也会把 hash 的几个位置都算出来,看看位数组中这几个位置是否都位 1,只要有一个位为 0,那么说明布隆过滤器中这个 key 不存在。如果都是 1,这并不能说明这个 key 就一定存在,只是极有可能存在,因为这些位被置为 1 可能是因为其它的 key 存在所致。如果这个位数组比较稀疏,判断正确的概率就会很大,如果这个位数组比较拥挤,判断正确的概率就会降低。

我们可以通过调参来增加正确的概率。redis提供自定义参数的布隆过滤器,需要我们在 add 之前使用bf.reserve指令显式创建。如果对应的 key 已经存在,bf.reserve会报错。bf.reserve有三个参数,分别是 key, error_rateinitial_size 。错误率越低,需要的空间越大。initial_size参数表示预计放入的元素数量,当实际数量超出这个数值时,误判率会上升。

// 对应 bf.reserve 指令
client.createFilter("codehole", 50000, 0.001);

布隆过滤器的其它应用

在爬虫系统中,我们需要对 URL进行去重,已经爬过的网页就可以不用爬了。但是 URL 太多了,几千万几个亿,如果用一个集合装下这些 URL 地址那是非常浪费空间的。这时候就可以考虑使用布隆过滤器。它可以大幅降低去重存储消耗,只不过也会使得爬虫系统错过少量的页面。

邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器,因为用了这个过滤器,所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中,这个就是误判所致,概率很低。

相关文章

  • redis插件安装-bloom模块

    布隆过滤器 Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为...

  • Redis-001、安装布隆过滤器

    一、在Redis上安装布隆过滤器 二、Redis的布隆过滤器使用

  • 布隆过滤器

    布隆过滤器起源 为什么我们要用布隆过滤器? 布隆过滤器是在海量数据找到想要的结果,经常应用于redis的缓存穿透(...

  • 布隆过滤器

    布隆过滤器 布隆过滤器不是专属于redis,此处是用来和 redis 结合使用。 1、场景 我们用 HyperLo...

  • 6.布隆过滤器

    Redis Modules[https://redis.io/modules] Redis 扩展组件库,布隆过滤器...

  • Redis应用五:布隆过滤器

    问题一: 我们已经知道了有 HyperLogLog这种数据结构来进行估数,它可以解决很多对精确度要求不高的统计需求...

  • Redis之布隆过滤器

    转载于详细解析Redis中的布隆过滤器及其应用 - 万猫学社 - 博客园[https://www.cnblogs....

  • Guava - 布隆过滤器的使用

    布隆过滤器简单介绍 布隆过滤器介绍 maven引入 布隆过滤器的使用 参考及拓展 Guava的布隆过滤器 布隆过滤...

  • Redis应用-布隆过滤器

    系列文章Redis应用-分布式锁Redis应用-异步消息队列与延时队列Redis应用-位图Redis应用-Hype...

  • redis-安装布隆过滤器插件及PHP调用

    redis-安装布隆过滤器插件及PHP调用 redis >= 4.0手册:https://oss.redislab...

网友评论

  • 克己丶丶:转载请注明出处,把老钱的东西拿来改一点就当成自己的了?

本文标题:Redis应用五:布隆过滤器

本文链接:https://www.haomeiwen.com/subject/wtsyiftx.html