Redis系列--布隆过滤器

在 Redis 的使用场景中,基本的架构图如下:
布隆过滤器
如果在缓存中查询不到数据,会直接到 DB 中查询,查询的数据再插入到缓存中。例如我们根据 orderId 查询对应的订单,具体伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
OrderEntity getOrder(String orderId){
//1. 查询缓存
OrderEntity orderEntity= getFromRedis(orderId);
if (orderEntity != null) {
return orderEntity;
}
//2. 缓存不存在
orderEntity=getFromDb(orderId);
//3. 塞入缓存
setRedis(orderEntity);
//4. 返回查询的值
return orderEntity;
}

如果这是时候客户端查询的 orderId 绝大多数都不在缓存中,这样就会带来一个 缓存穿透 的问题。如果有客户端恶意攻击,例如客户端使用 UUID 来访问我们的数据或者接口,势必会导致访问压力都落到 DB 上面,导致 DB 压力的上升。

为了解决这个缓存穿透,可以在 Redis 和 DB 中间增加一个过滤器,在访问 DB 前询问下过滤器,然后再决定是否查询 DB,具体结构图如下:

布隆过滤器

hash过滤

Hash 是一个简单 key — value 结构,如果在数据量不大的情况下,可以尝试把 DB 中的数据中的单列存储在缓存中

1
2
3
4
5
00001 1
00002 1
....

99999 1

在客户端访问时,可以先到 hash 中看下是否有值,然后根据过滤器返回值来确定是否查询 DB。

使用 Hash 过滤器准确率很高,但是维度比较单一(只能针对某一列拦截),同样 Hash key-value的占用的空间也很多。

布隆过滤器

布隆过滤器是 Hash 过滤的优化版本,使用 1 bit 来代表当前 key 是否存在。

布隆过滤器

如上图,在数据库中存在 1,5,8,9 四条数据,原始数据经过数据清洗后产生新的数据,当一个 key 经过 hash 后,根据 hash 数据判断数据是否存在。在上图中,可以明确返回数据已存在。

使用 hash + bit 结构代替传统的 key - value 模式,降低的数据的大小,也同样的保证了访问的速度,同样也会带来一些问题。

  • 哈希冲突带来数据误判的问题

    如果有一个 key 和现有数据产生的 hash 冲突, 经过 hash 函数得到的值也在(1,5,8,9)中间,这样就导致过滤器错误的返回数据已经存在。实际上布隆过滤器是一个牺牲正确性换取性能和空间的过滤器,如果判断存在,有可能不存在,如果过滤器判断不存在,则一定不存在。在实际使用中,尽量避免产生 hash 冲突和选择一个合适的 bit 数据长度。

在避免 hash 冲突的方案中,可以采用多个 hash 函数和多个 bit 位来决定最终结果:

布隆过滤器

在经过三个 hash 函数的得到对应的 bit 对应的 3 个数据,通过判断 bit 位上值来决定最终的结果。

  1. 数据删除如果被删除数据同步问题

    在数据删除的时候,同样需要删除 bit 数组中的数据,由于索引是根据 hash 函数计算的,有可能存在数据的 “公用”。

Screen Shot 2020-11-05 at 22.26.31

如果 Key1 和 Key2 对应的是同一个值,此时删除了 Key1 ,同样会导致 Key2 的结果也不存在。

为了解决这个问题,有两个解决方案

  1. 对 bit 数据升级为 int 数组,采用计数的方式。hash 到的数据进行 +1 ,删除的数据进行 -1.
  2. 使用多维的bit ,把当前的 bit 改成一个数组,采用“拉链法”对数据进行尾部追加。

布隆过滤器的代码实现

使用 Guava 库可以方便的实现布隆过滤器:

1
2
3
4
5
6
7
8
9
10
11
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 500, 0.01);

// 判断指定元素是否存在
System.out.println(filter.mightContain(10));
System.out.println(filter.mightContain(20));
// 将元素添加进布隆过滤器
filter.put(10);
filter.put(20);
// 再判断指定元素是否存在
System.out.println(filter.mightContain(10));
System.out.println(filter.mightContain(20));
作者

付威

发布于

2020-11-03

更新于

2020-11-03

许可协议

评论