Redis如何使用元素刪除的布隆過濾器來解決緩存穿透問題

這篇文章給大家分享的是有關Redis如何使用元素刪除的布隆過濾器來解決緩存穿透問題的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

前言

在我們日常開發中，Redis使用場景最多的就是作為緩存和分布式鎖等功能來使用，而其用作緩存最大的目的就是為了降低數據庫訪問。但是假如我們某些數據并不存在于Redis當中，那么請求還是會直接到達數據庫，而一旦在同一時間大量緩存失效或者一個不存在緩存的請求被惡意訪問，這些都會導致數據庫壓力驟增，這就是本文要講述的緩存穿透，緩存擊穿和緩存雪崩的問題，而布隆過濾器正是緩存穿透的一種解決方案。

緩存雪崩

緩存雪崩指的是Redis當中的大量緩存在同一時間全部失效，而假如恰巧這一段時間同時又有大量請求被發起，那么就會造成請求直接訪問到數據庫，可能會把數據庫沖垮。

緩存雪崩一般形容的是緩存中沒有而數據庫中有的數據，而因為時間到期導致請求直達數據庫。

解決方案

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

1、加鎖，保證單線程訪問緩存。這樣就不會有很多請求同時訪問到數據庫。

2、失效時間不要設置成一樣。典型的就是初始化預熱數據的時候，將數據存入緩存時可以采用隨機時間來確保不會咋同一時間有大量緩存失效。

3、內存允許的情況下，可以將緩存設置為永不失效。

緩存擊穿

緩存擊穿和緩存雪崩很類似，區別就是緩存擊穿一般指的是單個緩存失效，而同一時間又有很大的并發請求需要訪問這個key，從而造成了數據庫的壓力。

解決方案

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

1、加鎖，保證單線程訪問緩存。這樣第一個請求到達數據庫后就會重新寫入緩存，后續的請求就可以直接讀取緩存。2、內存允許的情況下，可以將緩存設置為永不失效。

 緩存穿透

緩存穿透和上面兩種現象的本質區別就是這時候訪問的數據其在數據庫中也不存在，那么既然數據庫不存在，所以緩存里面肯定也不會存在，這樣如果并發過大就會造成數據源源不斷的到達數據庫，給數據庫造成極大壓力。

解決方案

對于緩存穿透問題，加鎖并不能起到很好地效果，因為本身key就是不存在，所以即使控制了線程的訪問數，但是請求還是會源源不斷的到達數據庫。

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

1、接口層進行校驗，發現非法的key直接返回。比如數據庫中采用的是自增id，那么如果來了一個非整型的id或者負數id可以直接返回，或者說如果采用的是32位uuid，那么發現id長度不等于32位也可以直接返回。

2、將不存在的數據也進行緩存，可以直接緩存一個空或者其他約定好的無效value。采用這種方案最好將key設置一個短期失效時間，否則大量不存在的key被存儲到Redis中，也會占用大量內存。

布隆過濾器（Bloom Filter）

針對上面緩存穿透的解決方案，我們思考一下：假如一個key可以繞過第1種方法的校驗，而此時有大量的不存在key被訪問（如1億個或者10億個），那么這時候全部存儲到緩存，會占用非常大的空間，會浪費大量服務器內存，導致內存不足。

那么有沒有一種更好的解決方案呢？這就是我們接下來要介紹的布隆過濾器，布隆過濾器就可以最大程度的解決key值過多的這個問題。

什么是布隆過濾器

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

要解決這個問題就需要用到布隆過濾器，否則大部分服務器的內存是無法存儲這么大的數量級的數據的。

布隆過濾器（Bloom Filter）是由布隆在1970年提出的。它實際上是一個很長的二進制向量（位圖）和一系列隨機映射函數（哈希函數）。

布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率而且刪除困難。

位圖（Bitmap）

Redis當中有一種數據結構就是位圖，布隆過濾器其中重要的實現就是位圖的實現，也就是位數組，并且在這個數組中每一個位置只有0和1兩種狀態，每個位置只占用1個比特(bit)，其中0表示沒有元素存在，1表示有元素存在。如下圖所示就是一個簡單的布隆過濾器示例（一個key值經過哈希運算和位運算就可以得出應該落在哪個位置）：

哈希碰撞

上面我們發現，lonely和wolf落在了同一個位置，這種不同的key值經過哈希運算后得到相同值的現象就稱之為哈希碰撞。發生哈希碰撞之后再經過位運算，那么最后肯定會落在同一個位置。

如果發生過多的哈希碰撞，就會影響到判斷的準確性，所以為了減少哈希碰撞，我們一般會綜合考慮以下2個因素：

1、增大位圖數組的大小（位圖數組越大，占用的內存越大）。

2、增加哈希函數的次數（同一個key值經過1個函數相等了，那么經過2個或者更多個哈希函數的計算，都得到相等結果的概率就自然會降低了）。

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

布隆過濾器的2大特點

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

所以通過上面的現象，我們從布隆過濾器的角度可以得出布隆過濾器主要有2大特點：

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

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

而從元素的角度也可以得出2大特點：

1、如果元素實際存在，那么布隆過濾器一定會判斷存在。

2、如果元素不存在，那么布隆過濾器可能會判斷存在。

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

fpp

因為布隆過濾器中總是會存在誤判率，因為哈希碰撞是不可能百分百避免的。布隆過濾器對這種誤判率稱之為假陽性概率，即：False Positive Probability，簡稱為fpp。

在實踐中使用布隆過濾器時可以自己定義一個fpp，然后就可以根據布隆過濾器的理論計算出需要多少個哈希函數和多大的位數組空間。需要注意的是這個fpp不能定義為100%，因為無法百分保證不發生哈希碰撞。

布隆過濾器的實現(Guava)

在Guava的包中提供了布隆過濾器的實現，下面就通過Guava來體會一下布隆過濾器的應用：
1、引入pom依賴

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

2、新建一個布隆過濾器的測試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) {
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),expectedInsertions);

        List<String> 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); //最大小數位數

        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("布隆過濾器認為存在的key值數：" + 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("布隆過濾器認為存在的key值數：" + rightNum2);
        System.out.println("布隆過濾器認為不存在的key值數：" + wrongNum2);
        System.out.println("布隆過濾器的誤判率為：" + percentFormat.format((float)wrongNum2 / 5000));
    }
}

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

這個3%的誤判率是如何來的呢？我們進入創建布隆過濾器的create方法，發現默認的fpp就是0.03：

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

• optimalNumOfHashFunctions：獲取哈希函數的次數

• optimalNumOfBits：獲取位數組大小

debug進去看一下：

得到的結果是7298440 bit=0.87M，然后經過了5次哈希運算。可以發現這個空間占用是非常小的，100W的key才占用了0.87M。

PS：點擊這里可以進入網站計算bit數組大小和哈希函數個數。

布隆過濾器的如何刪除

上面的布隆過濾器我們知道，判斷一個元素存在就是判斷對應位置是否為1來確定的，但是如果要刪除掉一個元素是不能直接把1改成0的，因為這個位置可能存在其他元素，所以如果要支持刪除，那我們應該怎么做呢？最簡單的做法就是加一個計數器，就是說位數組的每個位如果不存在就是0，存在幾個元素就存具體的數字，而不僅僅只是存1，那么這就有一個問題，本來存1就是一位就可以滿足了，但是如果要存具體的數字比如說2，那就需要2位了，所以帶有計數器的布隆過濾器會占用更大的空間。

帶有計數器的布隆過濾器

下面就是一個帶有計數器的布隆過濾器示例
1、引入依賴：

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

2、新建一個帶有計數器的布隆過濾器demo：

package com.lonelyWolf.redis.bloom;

import orestes.bloomfilter.FilterBuilder;

public class CountingBloomFilter {
    public static void main(String[] args) {
        orestes.bloomfilter.CountingBloomFilter<String> 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
    }
}

構建布隆過濾器前面2個參數一個就是期望的元素數，一個就是fpp值，后面的countingBits參數就是計數器占用的大小，這里傳了一個8位，即最多允許255次重復，如果不傳的話這里默認是16位大小，即允許65535次重復。

感謝各位的閱讀！關于“Redis如何使用元素刪除的布隆過濾器來解決緩存穿透問題”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！