一、緩存穿透

項(xiàng)目中的熱點(diǎn)數(shù)據(jù)我們一般會(huì)放在 redis 中，在數(shù)據(jù)庫(kù)前面加了一層緩存，減少數(shù)據(jù)庫(kù)的訪問(wèn)，提升性能。但如果，請(qǐng)求的 key 在 redis 中并不存在，那請(qǐng)求還是會(huì)抵達(dá)數(shù)據(jù)庫(kù)，這就叫緩存穿透。

我們無(wú)法避免緩存穿透，因?yàn)閿?shù)據(jù)庫(kù)中的數(shù)據(jù)要全部放到 redis 中不太現(xiàn)實(shí)，也不可能保證數(shù)據(jù)庫(kù)數(shù)據(jù)和 redis 中的數(shù)據(jù)做到實(shí)時(shí)同步。但我們可以避免高頻的緩存穿透。

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

• 做好參數(shù)檢驗(yàn)，對(duì)于一些非法參數(shù)直接擋掉，比如 id 為負(fù)數(shù)的請(qǐng)求直接擋掉；

• 緩存無(wú)效的 key，比如某次請(qǐng)求的 key 在數(shù)據(jù)庫(kù)中不存在，那就將其緩存到 redis 并設(shè)置過(guò)期時(shí)間，但是這種辦法不好，假如黑客每次請(qǐng)求都用不同的 key，那 redis 中的無(wú)用數(shù)據(jù)就會(huì)很多；

• 使用布隆過(guò)濾器；

二、布隆過(guò)濾器

1. 過(guò)濾器的作用：

上面說(shuō)了，如果大量不存在的 key 請(qǐng)求過(guò)來(lái)，還是會(huì)直接請(qǐng)求到數(shù)據(jù)庫(kù)，如果我們能在請(qǐng)求數(shù)據(jù)庫(kù)之前判斷這個(gè) key 在數(shù)據(jù)庫(kù)到底存不存在，不存在就直接返回相關(guān)錯(cuò)誤信息，那就可以解決緩存穿透的問(wèn)題。

如何在不請(qǐng)求數(shù)據(jù)庫(kù)的前提下判斷這個(gè) key 在數(shù)據(jù)庫(kù)中存不存在呢？這就需要用到過(guò)濾器。難不成又要將數(shù)據(jù)庫(kù)的所有數(shù)據(jù)緩存到過(guò)濾器中嗎？當(dāng)然不是，如果這樣，那和將所有 key 緩存到 redis 就沒(méi)啥區(qū)別了。接下來(lái)看看布隆過(guò)濾器是怎么做的。

2. 布隆過(guò)濾器原理：

布隆過(guò)濾器使用了布隆算法來(lái)存儲(chǔ)數(shù)據(jù)，明確一點(diǎn)，布隆算法存儲(chǔ)的數(shù)據(jù)不是 100% 準(zhǔn)確的，即布隆過(guò)濾器認(rèn)為這個(gè) key 存在，實(shí)際上它也有可能不存在，如果它認(rèn)為這個(gè)key 不存在，那么它一定不存在。布隆算法是通過(guò)一定的錯(cuò)誤率來(lái)?yè)Q取空間的。

布隆算法通過(guò) bit 數(shù)組 來(lái)標(biāo)識(shí) key 是否存在。怎么做的呢？key 經(jīng)過(guò) hash 函數(shù)的運(yùn)算，得到一個(gè)數(shù)組的下標(biāo)，然后將對(duì)應(yīng)下標(biāo)的值改成1，1就表示該 key 存在。這個(gè) hash 函數(shù)要滿足的條件有：

• 對(duì) key 計(jì)算的結(jié)果必須在 [0, bitArray.length - 1] 之間；

• 計(jì)算出來(lái)的結(jié)果分布要足夠散列；

因?yàn)橐M(jìn)行 hash 計(jì)算，所有布隆算法的錯(cuò)誤率是由于 hash 碰撞導(dǎo)致的。所以降低 hash 碰撞的概率就可以降低錯(cuò)誤率。怎么降低 hash 碰撞的概率呢？?jī)煞N辦法：

• 加大數(shù)組的長(zhǎng)度：數(shù)組長(zhǎng)度更長(zhǎng)，hash 碰撞的概率自然更?。?/p>

• 增加 hash 函數(shù)的個(gè)數(shù)：假如 key 為 10 的數(shù)據(jù)，第一個(gè) hash 函數(shù)計(jì)算出來(lái)的下標(biāo)是 1，第二個(gè) hash 函數(shù)計(jì)算出來(lái)的是 4，第三個(gè) hash 函數(shù)計(jì)算出來(lái)的是 10，那么就要 1,4,10 這三個(gè)下標(biāo)所對(duì)應(yīng)的值都得是 1，才會(huì)認(rèn)為 key 存在，故而也可以減少誤判的情況。

3. 為什么要用 bit 數(shù)組：

因?yàn)楣?jié)省空間。1k = 1024byte = 1024 * 8 bit = 8192bit，即長(zhǎng)度為8192的bit數(shù)組只需要1kb的空間。

4. 怎么用？

業(yè)界大佬和民間大神已經(jīng)造了很多輪子了，這里主要說(shuō)三種，具體用法大家看一下相關(guān) api 即會(huì)了。

• 可以使用 guava 中的布隆過(guò)濾器；

• 使用 hutools 工具包中的布隆過(guò)濾器；

• redis 有 bitMap，也可以用作布隆過(guò)濾器，推薦使用 redisson 構(gòu)造布隆過(guò)濾器；

三、hutool 中的布隆過(guò)濾器源碼分析

這里帶大家分析一下 hutool 中的布隆過(guò)濾器源碼，看看人家怎么實(shí)現(xiàn)的。用法如下：

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. 構(gòu)造方法：

首先來(lái)看 new BitMapBloomFilter 的時(shí)候做了什么。

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

用傳進(jìn)來(lái)的 m 計(jì)算得到一個(gè) size，然后創(chuàng)建了一個(gè) BloomFilter 數(shù)組。這個(gè)數(shù)組有五個(gè)不同實(shí)現(xiàn)的對(duì)象，可以簡(jiǎn)單地理解為 hutool 中的布隆過(guò)濾器用了五個(gè) hash 函數(shù)去計(jì)算 key 對(duì)應(yīng)的索引。注意：如果傳進(jìn)來(lái)的 m 小于 5，那么 size 就是 0，調(diào)用 hash 的時(shí)候就會(huì)報(bào)錯(cuò)，因?yàn)?hash 函數(shù)中用這個(gè) size 做除數(shù)了，如下：

@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;
}

這里就是遍歷上面構(gòu)造的五個(gè)對(duì)象，也即分別調(diào)用那五個(gè)對(duì)象的 add 方法。再看看這里調(diào)用的那個(gè) 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;
}

這里首先計(jì)算 hash 值，這里的 hash 就是那五個(gè)對(duì)象的 hash函數(shù)，計(jì)算出了 hash 值后，判斷是否已經(jīng)存在了，存在了就直接返回 false，否則就進(jìn)行 add 操作。這個(gè) contains 等會(huì)兒再看，先看看這個(gè) add 方法。它的實(shí)現(xiàn)有兩個(gè)，如圖：

默認(rèn)用的是 IntMap 中的 add 方法，再去看看它的實(shí)現(xiàn)：

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

這里是不是有點(diǎn)兒懵逼呢？首先看看這個(gè) ints 數(shù)組是啥：

private final int[] ints;

它竟然是個(gè) int 數(shù)組，說(shuō)好的 bit 數(shù)組呢？

先來(lái)回顧一下，一個(gè) int 占 4 個(gè) byte，而一個(gè) byte 是 32 bit。所以，一個(gè)長(zhǎng)度為 10 的 int 數(shù)組，其實(shí)就可以存放 320 bit數(shù)據(jù)。這里正是用 int 數(shù)組來(lái)表示 bit。明白了這個(gè)之后，再來(lái)看上面的代碼。首先讓 i 除以 32，然后再讓 i 對(duì) 32 求余，最后再做了一堆計(jì)算就完事了。不懂沒(méi)關(guān)系，舉個(gè)例子就秒懂了。

假如有一個(gè) int 數(shù)組：int[] ints = new int[10]，那么它可以存放 32 * 10 = 320 bit 數(shù)據(jù)。

現(xiàn)在我想將第 66 位的 bit 值改成 1，第 66 位索引其實(shí)是 65，那么做法如下：

int r = 65 / 32 = 2; int c = 65 % 32 = 1;

1<<1 = 2，二進(jìn)制就是0000……0010，10 前面是 30 個(gè) 0，ints[2] 是0，二進(jìn)制就是 32 個(gè) 0;

它們做與運(yùn)算，結(jié)果就是還是 2，二進(jìn)制就是 0000……0010。

然后讓把 0000……0010 賦值給 ints[2]。為什么這樣就表示把第 66 個(gè) bit 值改成 1 了呢？

ints[0] 和 ints[1] 都是 0 對(duì)不對(duì)，也即 ints[0] 和 ints[1] 中都有 32 個(gè) 0，加起來(lái)就是 64 個(gè) 0。

也就是前 64 bit 都是 0。ints[2] 存的是 2，二進(jìn)制是 0000……0010，這個(gè)二進(jìn)制第一位是 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)));
}

再點(diǎn)進(jìn)去看這個(gè) 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;
}

還是上面的例子，r 還是 2，c 還是 1，ints[2] = 2，2>>>1 結(jié)果是 1，

1 & 1 結(jié)果是 1，所以返回true，也就是說(shuō)，如果傳進(jìn)來(lái)的 i 還是 65 的話，那就返回 true，因?yàn)閯偛乓呀?jīng) add 過(guò)了。