【原】布隆過濾器

貪挽懶月 2022-06-20 發(fā)布于廣東

展開全文

一、緩存穿透

項目中的熱點數據我們一般會放在 redis 中，在數據庫前面加了一層緩存，減少數據庫的訪問，提升性能。但如果，請求的 key 在 redis 中并不存在，那請求還是會抵達數據庫，這就叫緩存穿透。

我們無法避免緩存穿透，因為數據庫中的數據要全部放到 redis 中不太現實，也不可能保證數據庫數據和 redis 中的數據做到實時同步。但我們可以避免高頻的緩存穿透。

避免高頻緩存穿透的辦法：

做好參數檢驗，對于一些非法參數直接擋掉，比如 id 為負數的請求直接擋掉；
緩存無效的 key，比如某次請求的 key 在數據庫中不存在，那就將其緩存到 redis 并設置過期時間，但是這種辦法不好，假如黑客每次請求都用不同的 key，那 redis 中的無用數據就會很多；
使用布隆過濾器；

二、布隆過濾器

1. 過濾器的作用：

上面說了，如果大量不存在的 key 請求過來，還是會直接請求到數據庫，如果我們能在請求數據庫之前判斷這個 key 在數據庫到底存不存在，不存在就直接返回相關錯誤信息，那就可以解決緩存穿透的問題。

如何在不請求數據庫的前提下判斷這個 key 在數據庫中存不存在呢？這就需要用到過濾器。難不成又要將數據庫的所有數據緩存到過濾器中嗎？當然不是，如果這樣，那和將所有 key 緩存到 redis 就沒啥區(qū)別了。接下來看看布隆過濾器是怎么做的。

2. 布隆過濾器原理：

布隆過濾器使用了布隆算法來存儲數據，明確一點，布隆算法存儲的數據不是 100% 準確的，即布隆過濾器認為這個 key 存在，實際上它也有可能不存在，如果它認為這個key 不存在，那么它一定不存在。布隆算法是通過一定的錯誤率來換取空間的。

布隆算法通過 bit 數組 來標識 key 是否存在。怎么做的呢？key 經過 hash 函數的運算，得到一個數組的下標，然后將對應下標的值改成1，1就表示該 key 存在。這個 hash 函數要滿足的條件有：

對 key 計算的結果必須在 [0, bitArray.length - 1] 之間；
計算出來的結果分布要足夠散列；

因為要進行 hash 計算，所有布隆算法的錯誤率是由于 hash 碰撞導致的。所以降低 hash 碰撞的概率就可以降低錯誤率。怎么降低 hash 碰撞的概率呢？兩種辦法：

加大數組的長度：數組長度更長，hash 碰撞的概率自然更?。?/p>
增加 hash 函數的個數：假如 key 為 10 的數據，第一個 hash 函數計算出來的下標是 1，第二個 hash 函數計算出來的是 4，第三個 hash 函數計算出來的是 10，那么就要 1,4,10 這三個下標所對應的值都得是 1，才會認為 key 存在，故而也可以減少誤判的情況。

3. 為什么要用 bit 數組：

因為節(jié)省空間。1k = 1024byte = 1024 * 8 bit = 8192bit，即長度為8192的bit數組只需要1kb的空間。

4. 怎么用？

業(yè)界大佬和民間大神已經造了很多輪子了，這里主要說三種，具體用法大家看一下相關 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，然后創(chuàng)建了一個 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;
}