基于Redis的布隆过滤器(Bloom Filter)

基于Redis的布隆过滤器

首先来看一个问题，现在有50亿个号码，要快速准确判断另外10万个号码是否在这50亿个号码中是否存在？

• 如果通过数据库查询，数据库实现快速很难

• 数据提前放在集合中，但是内存占用空间很大 50亿*8字节 约等于 40G，内存不够

• hyperloglog: 准确有点难

类似问题：

• 垃圾邮件过滤

• 网络爬虫重复url检测

• 文字处理软件，错误单词检测

• Hbase行过滤

布隆过滤器

1970年提出的，用很小的空间，解决上面的问题。

• 一个很长的二进制向量和若干个哈希函数

参数：m个二进制向量，n个预备数据，k个hash函数

构建布隆过滤器：n个预备数据使用hash函数映射到向量上

判断一个元素是否存在: 判断hash函数后的值，如果都是1，则表明存在，如果不是1则不存在

案例

上面每一个空的格子代表一个bit，下面的数字是bit的索引，添加一个元素到布隆过滤器中，我们只需要用多个hash函数，然后设置那些对应的索引的bit为1.

比如：添加字符串"aihe"

经过两个hash函数，得出的结果是3和9.那么在对应的索引标记bit为1，如下

如果想要测试其它的字符串是否在布隆过滤器中，使用相同的hash函数，然后看获得的值是否在布隆过滤器中。如果有一位不是，那么就可以判断这个元素不在集合中。如果对应的位都有值，那么这个元素可能在布隆过滤器中。

因为布隆过滤器只能判断这个元素可能集合中，所以它是有一定的误差率的。

本地布隆过滤器

我们可以使用Guava的库来进行实现本地布隆过滤器。

1. 引入maven依赖

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>22.0</version>
</dependency>

1. 编写代码创建过滤器，假设我们想要创建一个布隆过滤器容忍0.01的误差率，估计大约有500次插入

publicclassBloomFilterDemo{
   publicstaticvoidmain(String[] args) {
       BloomFilter<Integer>filter=BloomFilter.create(
               Funnels.integerFunnel(),
               500,
               0.01);
       filter.put(1);
       filter.put(2);
       filter.put(3);

       System.out.println(filter.mightContain(1));
       System.out.println(filter.mightContain(2));
       System.out.println(filter.mightContain(3));

       System.out.println(filter.mightContain(100));

  }
}

1. 以上就构建完成了

   
   

本地布隆过滤器的缺点：

• 容量会受限制

• 多个应用存在多个布隆过滤器，构建同步复杂。代码冗余

基于Redis的布隆过滤器

Redis中有setbit,getbit的函数，所以很适合实现

过程：

• 首先定义布隆过滤器的构造参数：m,n,k,误差率

• 定义布隆过滤器操作：add 和 contain

• 封装Redis位图操作

• 开发测试样例

底层主要依赖Redis的BitMap，Bitmap最大的好处就是提供了极度的空间存储，比如我们想要记录用户是否登录过系统，只以一个bit来表示的话，存储40亿个用户是否登录信息只需要512M的空间。

bitmap不算是redis的数据结构，其主要是按位操作redis的字符串。

单机Redis问题：

• 相比于本地，速度会更慢一点。如果允许，可以与应用部署在同机房

• Redis最大的字符串容量是512M，可以使用Redis Cluster实现

Redis相关开发规范

因为谈到了Redis，顺便提一下Redis一些基本的规范要求，键值设计的好，Redis会有良好的体验

key设计

• 可读性与可管理性 以业务名前缀，冒号分隔。比如  业务名:表名， ucar:carpay

• 简洁性，控制key的长度，当key较多时，内存的占用也不可忽视

• 不要包含特殊字符，空格，换行之类的

value设计

• 拒绝bigkey，这是导致线上问题最多的问题。可以使用redis-cli --bigkey发现bigkey；一般value大于10KB的，hash,list,zet元素个数超过5000个的被称为bigkey。 注意要对bigkey进行监控

• 会造成网络拥塞

• redis阻塞，慢查询

• 集群节点数据不均匀

• 频繁序列化，导致服务器CPU飙高

• 选择合适的数据结构

• 过期设计

图中即节点数量差不多，但是其内存使用却明显高于其它节点，这就是bigkey的影响。

bigkey频繁序列化导致的cpu飙高

发现bigkey

• 应用方发现

• redis-cli --bigkeys，建议在从节点执行，另外在redis运行的节点执行，减少网络阻塞

• scan + debug object

• 主动报警，网络流量监控，客户端监控

删除bigkey

直接删除集合很可能造成阻塞。对于String类型直接使用del一般不会造成阻塞

Redis 4.0之后，提供了lazy delete

Redis 4.0以下，对于集合使用循环删除其子key

最后

这里主要是讲解一下布隆过滤器是什么，以及使用Redis实现布隆过滤器的原理，另外顺便提了下Redis的一些开发规范问题，希望能帮大家

参考

• Bloom Filter in Java using Guava

• Bloom Filters by Example

注：

本文独家发布自金蝶云社区