前言

在我們?nèi)粘ｉ_(kāi)發(fā)中，Redis使用場(chǎng)景最多的就是作為緩存和分布式鎖等功能來(lái)使用，而其用作緩存最大的目的就是為了降低數(shù)據(jù)庫(kù)訪問(wèn)。但是假如我們某些數(shù)據(jù)并不存在于Redis當(dāng)中，那么請(qǐng)求還是會(huì)直接到達(dá)數(shù)據(jù)庫(kù)，而一旦在同一時(shí)間大量緩存失效或者一個(gè)不存在緩存的請(qǐng)求被惡意訪問(wèn)，這些都會(huì)導(dǎo)致數(shù)據(jù)庫(kù)壓力驟增，這就是本文要講述的緩存穿透，緩存擊穿和緩存雪崩的問(wèn)題，而布隆過(guò)濾器正是緩存穿透的一種解決方案。

緩存雪崩

緩存雪崩指的是Redis當(dāng)中的大量緩存在同一時(shí)間全部失效，而假如恰巧這一段時(shí)間同時(shí)又有大量請(qǐng)求被發(fā)起，那么就會(huì)造成請(qǐng)求直接訪問(wèn)到數(shù)據(jù)庫(kù)，可能會(huì)把數(shù)據(jù)庫(kù)沖垮。

緩存雪崩一般形容的是緩存中沒(méi)有而數(shù)據(jù)庫(kù)中有的數(shù)據(jù)，而因?yàn)闀r(shí)間到期導(dǎo)致請(qǐng)求直達(dá)數(shù)據(jù)庫(kù)。

解決方案

解決緩存雪崩的方法有很多：

1、加鎖，保證單線程訪問(wèn)緩存。這樣就不會(huì)有很多請(qǐng)求同時(shí)訪問(wèn)到數(shù)據(jù)庫(kù)。

2、失效時(shí)間不要設(shè)置成一樣。典型的就是初始化預(yù)熱數(shù)據(jù)的時(shí)候，將數(shù)據(jù)存入緩存時(shí)可以采用隨機(jī)時(shí)間來(lái)確保不會(huì)咋同一時(shí)間有大量緩存失效。

3、內(nèi)存允許的情況下，可以將緩存設(shè)置為永不失效。

緩存擊穿

緩存擊穿和緩存雪崩很類似，區(qū)別就是緩存擊穿一般指的是單個(gè)緩存失效，而同一時(shí)間又有很大的并發(fā)請(qǐng)求需要訪問(wèn)這個(gè)key，從而造成了數(shù)據(jù)庫(kù)的壓力。

解決方案

解決緩存擊穿的方法和解決緩存雪崩的方法很類似：

1、加鎖，保證單線程訪問(wèn)緩存。這樣第一個(gè)請(qǐng)求到達(dá)數(shù)據(jù)庫(kù)后就會(huì)重新寫(xiě)入緩存，后續(xù)的請(qǐng)求就可以直接讀取緩存。2、內(nèi)存允許的情況下，可以將緩存設(shè)置為永不失效。

 緩存穿透

緩存穿透和上面兩種現(xiàn)象的本質(zhì)區(qū)別就是這時(shí)候訪問(wèn)的數(shù)據(jù)其在數(shù)據(jù)庫(kù)中也不存在，那么既然數(shù)據(jù)庫(kù)不存在，所以緩存里面肯定也不會(huì)存在，這樣如果并發(fā)過(guò)大就會(huì)造成數(shù)據(jù)源源不斷的到達(dá)數(shù)據(jù)庫(kù)，給數(shù)據(jù)庫(kù)造成極大壓力。

解決方案

對(duì)于緩存穿透問(wèn)題，加鎖并不能起到很好地效果，因?yàn)楸旧韐ey就是不存在，所以即使控制了線程的訪問(wèn)數(shù)，但是請(qǐng)求還是會(huì)源源不斷的到達(dá)數(shù)據(jù)庫(kù)。

解決緩存穿透問(wèn)題一般可以采用以下方案配合使用：

1、接口層進(jìn)行校驗(yàn)，發(fā)現(xiàn)非法的key直接返回。比如數(shù)據(jù)庫(kù)中采用的是自增id，那么如果來(lái)了一個(gè)非整型的id或者負(fù)數(shù)id可以直接返回，或者說(shuō)如果采用的是32位uuid，那么發(fā)現(xiàn)id長(zhǎng)度不等于32位也可以直接返回。

2、將不存在的數(shù)據(jù)也進(jìn)行緩存，可以直接緩存一個(gè)空或者其他約定好的無(wú)效value。采用這種方案最好將key設(shè)置一個(gè)短期失效時(shí)間，否則大量不存在的key被存儲(chǔ)到Redis中，也會(huì)占用大量?jī)?nèi)存。

布隆過(guò)濾器（Bloom Filter）

針對(duì)上面緩存穿透的解決方案，我們思考一下：假如一個(gè)key可以繞過(guò)第1種方法的校驗(yàn)，而此時(shí)有大量的不存在key被訪問(wèn)（如1億個(gè)或者10億個(gè)），那么這時(shí)候全部存儲(chǔ)到緩存，會(huì)占用非常大的空間，會(huì)浪費(fèi)大量服務(wù)器內(nèi)存，導(dǎo)致內(nèi)存不足。

那么有沒(méi)有一種更好的解決方案呢？這就是我們接下來(lái)要介紹的布隆過(guò)濾器，布隆過(guò)濾器就可以最大程度的解決key值過(guò)多的這個(gè)問(wèn)題。

什么是布隆過(guò)濾器

可能大部分人都知道有這么一個(gè)面試問(wèn)題：如何在10億的海量的無(wú)序的數(shù)據(jù)中快速判斷一個(gè)元素是否存在？

要解決這個(gè)問(wèn)題就需要用到布隆過(guò)濾器，否則大部分服務(wù)器的內(nèi)存是無(wú)法存儲(chǔ)這么大的數(shù)量級(jí)的數(shù)據(jù)的。

布隆過(guò)濾器（Bloom Filter）是由布隆在1970年提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量（位圖）和一系列隨機(jī)映射函數(shù)（哈希函數(shù)）。

布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識(shí)別率而且刪除困難。

位圖（Bitmap）

Redis當(dāng)中有一種數(shù)據(jù)結(jié)構(gòu)就是位圖，布隆過(guò)濾器其中重要的實(shí)現(xiàn)就是位圖的實(shí)現(xiàn)，也就是位數(shù)組，并且在這個(gè)數(shù)組中每一個(gè)位置只有0和1兩種狀態(tài)，每個(gè)位置只占用1個(gè)比特(bit)，其中0表示沒(méi)有元素存在，1表示有元素存在。如下圖所示就是一個(gè)簡(jiǎn)單的布隆過(guò)濾器示例（一個(gè)key值經(jīng)過(guò)哈希運(yùn)算和位運(yùn)算就可以得出應(yīng)該落在哪個(gè)位置）：

哈希碰撞

上面我們發(fā)現(xiàn)，lonely和wolf落在了同一個(gè)位置，這種不同的key值經(jīng)過(guò)哈希運(yùn)算后得到相同值的現(xiàn)象就稱之為哈希碰撞。發(fā)生哈希碰撞之后再經(jīng)過(guò)位運(yùn)算，那么最后肯定會(huì)落在同一個(gè)位置。

如果發(fā)生過(guò)多的哈希碰撞，就會(huì)影響到判斷的準(zhǔn)確性，所以為了減少哈希碰撞，我們一般會(huì)綜合考慮以下2個(gè)因素：

1、增大位圖數(shù)組的大?。ㄎ粓D數(shù)組越大，占用的內(nèi)存越大）。

2、增加哈希函數(shù)的次數(shù)（同一個(gè)key值經(jīng)過(guò)1個(gè)函數(shù)相等了，那么經(jīng)過(guò)2個(gè)或者更多個(gè)哈希函數(shù)的計(jì)算，都得到相等結(jié)果的概率就自然會(huì)降低了）。

上面兩個(gè)方法我們需要綜合考慮：比如增大位數(shù)組，那么就需要消耗更多的空間，而經(jīng)過(guò)越多的哈希計(jì)算也會(huì)消耗cpu影響到最終的計(jì)算時(shí)間，所以位數(shù)組到底多大，哈希函數(shù)次數(shù)又到底需要計(jì)算多少次合適需要具體情況具體分析。

布隆過(guò)濾器的2大特點(diǎn)

下面這個(gè)就是一個(gè)經(jīng)過(guò)了2次哈希函數(shù)得到的布隆過(guò)濾器，根據(jù)下圖我們很容易看到，假如我們的Redis根本不存在，但是Redis經(jīng)過(guò)2次哈希函數(shù)之后得到的兩個(gè)位置已經(jīng)是1了（一個(gè)是wolf通過(guò)f2得到，一個(gè)是Nosql通過(guò)f1得到）。

所以通過(guò)上面的現(xiàn)象，我們從布隆過(guò)濾器的角度可以得出布隆過(guò)濾器主要有2大特點(diǎn)：

1、如果布隆過(guò)濾器判斷一個(gè)元素存在，那么這個(gè)元素可能存在。

2、如果布隆過(guò)濾器判斷一個(gè)元素不存在，那么這個(gè)元素一定不存在。

而從元素的角度也可以得出2大特點(diǎn)：

1、如果元素實(shí)際存在，那么布隆過(guò)濾器一定會(huì)判斷存在。

2、如果元素不存在，那么布隆過(guò)濾器可能會(huì)判斷存在。

PS：需要注意的是，如果經(jīng)過(guò)N次哈希函數(shù)，則需要得到的N個(gè)位置都是1才能判定存在，只要有一個(gè)是0，就可以判定為元素不存在布隆過(guò)濾器中。

fpp

因?yàn)椴悸∵^(guò)濾器中總是會(huì)存在誤判率，因?yàn)楣Ｅ鲎彩遣豢赡馨俜职俦苊獾摹?strong>布隆過(guò)濾器對(duì)這種誤判率稱之為假陽(yáng)性概率，即：False Positive Probability，簡(jiǎn)稱為fpp。

在實(shí)踐中使用布隆過(guò)濾器時(shí)可以自己定義一個(gè)fpp，然后就可以根據(jù)布隆過(guò)濾器的理論計(jì)算出需要多少個(gè)哈希函數(shù)和多大的位數(shù)組空間。需要注意的是這個(gè)fpp不能定義為100%，因?yàn)闊o(wú)法百分保證不發(fā)生哈希碰撞。

布隆過(guò)濾器的實(shí)現(xiàn)(Guava)

在Guava的包中提供了布隆過(guò)濾器的實(shí)現(xiàn)，下面就通過(guò)Guava來(lái)體會(huì)一下布隆過(guò)濾器的應(yīng)用：
1、引入pom依賴

dependency>
   groupId>com.google.guava/groupId>
   artifactId>guava/artifactId>
   version>29.0-jre/version>
/dependency>

2、新建一個(gè)布隆過(guò)濾器的測(cè)試demo：

package com.lonelyWolf.redis;

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

public class BloomFilterDemo {
    private static final int expectedInsertions = 1000000;

    public static void main(String[] args) {
        BloomFilterString> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),expectedInsertions);

        ListString> list = new ArrayList>(expectedInsertions);


        for (int i = 0; i  expectedInsertions; i++) {
            String uuid = UUID.randomUUID().toString();
            bloomFilter.put(uuid);
            list.add(uuid);
        }

        int rightNum1 = 0;
        int wrongNum1 = 0;

        NumberFormat percentFormat =NumberFormat.getPercentInstance();
        percentFormat.setMaximumFractionDigits(2); //最大小數(shù)位數(shù)

        for (int i=0;i  500;i++){
            String key = list.get(i);
            if (bloomFilter.mightContain(key)){
                if (list.contains(key)){
                    rightNum1++;
                }else {
                    wrongNum1++;
                }
            }
        }
        System.out.println("布隆過(guò)濾器認(rèn)為存在的key值數(shù)：" + rightNum1);
        System.out.println("-----------------------分割線---------------------------------");

        int rightNum2 = 0;
        int wrongNum2 = 0;

        for (int i=0;i  5000;i++){
            String key = UUID.randomUUID().toString();
            if (bloomFilter.mightContain(key)){
                if (list.contains(key)){
                    rightNum2++;
                }else {
                    wrongNum2++;
                }
            }
        }

        System.out.println("布隆過(guò)濾器認(rèn)為存在的key值數(shù)：" + rightNum2);
        System.out.println("布隆過(guò)濾器認(rèn)為不存在的key值數(shù)：" + wrongNum2);
        System.out.println("布隆過(guò)濾器的誤判率為：" + percentFormat.format((float)wrongNum2 / 5000));
    }
}

運(yùn)行之后，第一部分輸出的值一定是和for循環(huán)內(nèi)的值相等，也就是百分百匹配，即滿足了原則1：如果元素實(shí)際存在，那么布隆過(guò)濾器一定會(huì)判斷存在。
第二部分的輸出的誤判率即fpp總是在3%左右，而且隨著for循環(huán)的次數(shù)越大，越接近3%。即滿足了原則2：如果元素不存在，那么布隆過(guò)濾器可能會(huì)判斷存在。

這個(gè)3%的誤判率是如何來(lái)的呢？我們進(jìn)入創(chuàng)建布隆過(guò)濾器的create方法，發(fā)現(xiàn)默認(rèn)的fpp就是0.03：

對(duì)于這個(gè)默認(rèn)的3%的fpp需要多大的位數(shù)組空間和多少次哈希函數(shù)得到的呢？在BloomFilter類下面有兩個(gè)default方法可以獲取到位數(shù)組空間大小和哈希函數(shù)的個(gè)數(shù)：

• optimalNumOfHashFunctions：獲取哈希函數(shù)的次數(shù)
• optimalNumOfBits：獲取位數(shù)組大小

debug進(jìn)去看一下：

得到的結(jié)果是7298440 bit=0.87M，然后經(jīng)過(guò)了5次哈希運(yùn)算?？梢园l(fā)現(xiàn)這個(gè)空間占用是非常小的，100W的key才占用了0.87M。

PS：點(diǎn)擊這里可以進(jìn)入網(wǎng)站計(jì)算bit數(shù)組大小和哈希函數(shù)個(gè)數(shù)。

布隆過(guò)濾器的如何刪除

上面的布隆過(guò)濾器我們知道，判斷一個(gè)元素存在就是判斷對(duì)應(yīng)位置是否為1來(lái)確定的，但是如果要?jiǎng)h除掉一個(gè)元素是不能直接把1改成0的，因?yàn)檫@個(gè)位置可能存在其他元素，所以如果要支持刪除，那我們應(yīng)該怎么做呢？最簡(jiǎn)單的做法就是加一個(gè)計(jì)數(shù)器，就是說(shuō)位數(shù)組的每個(gè)位如果不存在就是0，存在幾個(gè)元素就存具體的數(shù)字，而不僅僅只是存1，那么這就有一個(gè)問(wèn)題，本來(lái)存1就是一位就可以滿足了，但是如果要存具體的數(shù)字比如說(shuō)2，那就需要2位了，所以帶有計(jì)數(shù)器的布隆過(guò)濾器會(huì)占用更大的空間。

帶有計(jì)數(shù)器的布隆過(guò)濾器

下面就是一個(gè)帶有計(jì)數(shù)器的布隆過(guò)濾器示例
1、引入依賴：

dependency>
    groupId>com.baqend/groupId>
    artifactId>bloom-filter/artifactId>
    version>1.0.7/version>
/dependency>

2、新建一個(gè)帶有計(jì)數(shù)器的布隆過(guò)濾器demo：

package com.lonelyWolf.redis.bloom;

import orestes.bloomfilter.FilterBuilder;

public class CountingBloomFilter {
    public static void main(String[] args) {
        orestes.bloomfilter.CountingBloomFilterString> cbf = new FilterBuilder(10000,
                0.01).countingBits(8).buildCountingBloomFilter();

        cbf.add("zhangsan");
        cbf.add("lisi");
        cbf.add("wangwu");
        System.out.println("是否存在王五：" + cbf.contains("wangwu")); //true
        cbf.remove("wangwu");
        System.out.println("是否存在王五：" + cbf.contains("wangwu")); //false
    }
}

構(gòu)建布隆過(guò)濾器前面2個(gè)參數(shù)一個(gè)就是期望的元素?cái)?shù)，一個(gè)就是fpp值，后面的countingBits參數(shù)就是計(jì)數(shù)器占用的大小，這里傳了一個(gè)8位，即最多允許255次重復(fù)，如果不傳的話這里默認(rèn)是16位大小，即允許65535次重復(fù)。

總結(jié)

本文主要講述了使用Redis存在的三種問(wèn)題：緩存雪崩，緩存擊穿和緩存穿透。并分別對(duì)每種問(wèn)題的解決方案進(jìn)行了描述，最后著重介紹了緩存穿透的解決方案：布隆過(guò)濾器。原生的布隆過(guò)濾器不支持刪除，但是可以引入一個(gè)計(jì)數(shù)器實(shí)現(xiàn)帶有計(jì)數(shù)器的布隆過(guò)濾器來(lái)實(shí)現(xiàn)刪除功能，同時(shí)在最后也提到了，帶有計(jì)數(shù)器的布隆過(guò)濾器會(huì)占用更多的空間問(wèn)題。

到此這篇關(guān)于Redis使用元素刪除的布隆過(guò)濾器來(lái)解決緩存穿透問(wèn)題的文章就介紹到這了,更多相關(guān)Redis 緩存穿透內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！