【原】布隆过滤器

贪挽懒月 2022-06-20 发布于广东

展开全文

一、缓存穿透

项目中的热点数据我们一般会放在 redis 中，在数据库前面加了一层缓存，减少数据库的访问，提升性能。但如果，请求的 key 在 redis 中并不存在，那请求还是会抵达数据库，这就叫缓存穿透。

我们无法避免缓存穿透，因为数据库中的数据要全部放到 redis 中不太现实，也不可能保证数据库数据和 redis 中的数据做到实时同步。但我们可以避免高频的缓存穿透。

避免高频缓存穿透的办法：

做好参数检验，对于一些非法参数直接挡掉，比如 id 为负数的请求直接挡掉；
缓存无效的 key，比如某次请求的 key 在数据库中不存在，那就将其缓存到 redis 并设置过期时间，但是这种办法不好，假如黑客每次请求都用不同的 key，那 redis 中的无用数据就会很多；
使用布隆过滤器；

二、布隆过滤器

1. 过滤器的作用：

上面说了，如果大量不存在的 key 请求过来，还是会直接请求到数据库，如果我们能在请求数据库之前判断这个 key 在数据库到底存不存在，不存在就直接返回相关错误信息，那就可以解决缓存穿透的问题。

如何在不请求数据库的前提下判断这个 key 在数据库中存不存在呢？这就需要用到过滤器。难不成又要将数据库的所有数据缓存到过滤器中吗？当然不是，如果这样，那和将所有 key 缓存到 redis 就没啥区别了。接下来看看布隆过滤器是怎么做的。

2. 布隆过滤器原理：

布隆过滤器使用了布隆算法来存储数据，明确一点，布隆算法存储的数据不是 100% 准确的，即布隆过滤器认为这个 key 存在，实际上它也有可能不存在，如果它认为这个key 不存在，那么它一定不存在。布隆算法是通过一定的错误率来换取空间的。

布隆算法通过 bit 数组 来标识 key 是否存在。怎么做的呢？key 经过 hash 函数的运算，得到一个数组的下标，然后将对应下标的值改成1，1就表示该 key 存在。这个 hash 函数要满足的条件有：

对 key 计算的结果必须在 [0, bitArray.length - 1] 之间；
计算出来的结果分布要足够散列；

因为要进行 hash 计算，所有布隆算法的错误率是由于 hash 碰撞导致的。所以降低 hash 碰撞的概率就可以降低错误率。怎么降低 hash 碰撞的概率呢？两种办法：

加大数组的长度：数组长度更长，hash 碰撞的概率自然更小；
增加 hash 函数的个数：假如 key 为 10 的数据，第一个 hash 函数计算出来的下标是 1，第二个 hash 函数计算出来的是 4，第三个 hash 函数计算出来的是 10，那么就要 1,4,10 这三个下标所对应的值都得是 1，才会认为 key 存在，故而也可以减少误判的情况。

3. 为什么要用 bit 数组：

因为节省空间。1k = 1024byte = 1024 * 8 bit = 8192bit，即长度为8192的bit数组只需要1kb的空间。

4. 怎么用？

业界大佬和民间大神已经造了很多轮子了，这里主要说三种，具体用法大家看一下相关 api 即会了。

可以使用 guava 中的布隆过滤器；
使用 hutools 工具包中的布隆过滤器；
redis 有 bitMap，也可以用作布隆过滤器，推荐使用 redisson 构造布隆过滤器；

三、hutool 中的布隆过滤器源码分析

这里带大家分析一下 hutool 中的布隆过滤器源码，看看人家怎么实现的。用法如下：

public static void main(String[] args) {
 BitMapBloomFilter bloomFilter = new BitMapBloomFilter(5);
 bloomFilter.add("aa");
 bloomFilter.add("bb");
 bloomFilter.add("cc");
 bloomFilter.add("dd");
 System.out.println(bloomFilter.contains("aa"));
}

1. 构造方法：

首先来看 new BitMapBloomFilter 的时候做了什么。

public BitMapBloomFilter(int m) {
 long mNum = NumberUtil.div(String.valueOf(m), String.valueOf(5)).longValue();
 long size = mNum * 1024 * 1024 * 8;

 filters = new BloomFilter[]{
   new DefaultFilter(size),
   new ELFFilter(size),
   new JSFilter(size),
   new PJWFilter(size),
   new SDBMFilter(size)
 };
}

用传进来的 m 计算得到一个 size，然后创建了一个 BloomFilter 数组。这个数组有五个不同实现的对象，可以简单地理解为 hutool 中的布隆过滤器用了五个 hash 函数去计算 key 对应的索引。注意：如果传进来的 m 小于 5，那么 size 就是 0，调用 hash 的时候就会报错，因为 hash 函数中用这个 size 做除数了，如下：

@Override
public long hash(String str) {
 return HashUtil.javaDefaultHash(str) % size;
}

2. add 方法：

@Override
public boolean add(String str) {
 boolean flag = false;
 for (BloomFilter filter : filters) {
  flag |= filter.add(str);
 }
 return flag;
}

这里就是遍历上面构造的五个对象，也即分别调用那五个对象的 add 方法。再看看这里调用的那个 add 方法：

@Override
public boolean add(String str) {
 final long hash = Math.abs(hash(str));
 if (bm.contains(hash)) {
  return false;
 }

 bm.add(hash);
 return true;
}

这里首先计算 hash 值，这里的 hash 就是那五个对象的 hash函数，计算出了 hash 值后，判断是否已经存在了，存在了就直接返回 false，否则就进行 add 操作。这个 contains 等会儿再看，先看看这个 add 方法。它的实现有两个，如图：

默认用的是 IntMap 中的 add 方法，再去看看它的实现：

@Override
public void add(long i) {
 int r = (int) (i / BitMap.MACHINE32);
 int c = (int) (i % BitMap.MACHINE32);
 ints[r] = (int) (ints[r] | (1 << c));
}

这里是不是有点儿懵逼呢？首先看看这个 ints 数组是啥：

private final int[] ints;

它竟然是个 int 数组，说好的 bit 数组呢？

先来回顾一下，一个 int 占 4 个 byte，而一个 byte 是 32 bit。所以，一个长度为 10 的 int 数组，其实就可以存放 320 bit数据。这里正是用 int 数组来表示 bit。明白了这个之后，再来看上面的代码。首先让 i 除以 32，然后再让 i 对 32 求余，最后再做了一堆计算就完事了。不懂没关系，举个例子就秒懂了。

假如有一个 int 数组：int[] ints = new int[10]，那么它可以存放 32 * 10 = 320 bit 数据。
现在我想将第 66 位的 bit 值改成 1，第 66 位索引其实是 65，那么做法如下：
int r = 65 / 32 = 2; int c = 65 % 32 = 1;
1<<1 = 2，二进制就是0000……0010，10 前面是 30 个 0，ints[2] 是0，二进制就是 32 个 0;
它们做与运算，结果就是还是 2，二进制就是 0000……0010。
然后让把 0000……0010 赋值给 ints[2]。为什么这样就表示把第 66 个 bit 值改成 1 了呢？
ints[0] 和 ints[1] 都是 0 对不对，也即 ints[0] 和 ints[1] 中都有 32 个 0，加起来就是 64 个 0。
也就是前 64 bit 都是 0。ints[2] 存的是 2，二进制是 0000……0010，这个二进制第一位是 0，第二位是 1……
所以 ints[2] 中的第一位是 0，第二位是 1，后面的 30 位都是0。32 + 32 + 2 = 66，所以第 66 位就变成了 1。

3. contains 方法：

@Override
public boolean contains(String str) {
 return bm.contains(Math.abs(hash(str)));
}

再点进去看这个 contains 方法：

@Override
public boolean contains(long i) {
 int r = (int) (i / BitMap.MACHINE32);
 int c = (int) (i % BitMap.MACHINE32);
 return ((int) ((ints[r] >>> c)) & 1) == 1;
}