Redis系列--布隆过滤器

在 Redis 的使用场景中，基本的架构图如下：

布隆过滤器

如果在缓存中查询不到数据，会直接到 DB 中查询，查询的数据再插入到缓存中。例如我们根据 orderId 查询对应的订单，具体伪代码如下：

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 中的数据中的单列存储在缓存中

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 库可以方便的实现布隆过滤器：

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));