Java培訓(xùn)：防緩存穿透利器-布隆濾器(BloomFilter)

　　一、布隆過濾器原理

　　 如果想要判斷一個元素是不是在一個集合中存在，一般的想法是將所有元素保存起來，然后再拿著這個元素在集合中一個一個進(jìn)行比對。但是隨著集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢。 針對這種需要在大量數(shù)據(jù)中去判斷某一個值是事否存在的情況，1970年由布隆提出了布隆過濾器的概念。布隆過濾器本質(zhì)是一個位數(shù)組，位數(shù)組就是數(shù)組的每個元素都只占用 1 bit 。每個元素只能是 0 或者 1。這樣申請一個 10000 個元素的位數(shù)組只占用 10000 / 8 = 1250 字節(jié) 的空間。布隆過濾器除了一個位數(shù)組，還有 n個哈希函數(shù)。

　　 它具體的實(shí)現(xiàn)思想是并不將具體的數(shù)據(jù)存儲在數(shù)組中，而是通過hash函數(shù)對要存儲的數(shù)據(jù)進(jìn)行三次hash運(yùn)算，并將hash運(yùn)算的結(jié)果做為位數(shù)組的下標(biāo)，將對應(yīng)的數(shù)組元素修改為1。

　　 例如：我們要將"oracle"、"database"、"filter"存儲到布隆過濾器中可以這樣做。如下圖所示

<img src=" 防緩存穿透利器-隆過濾器(BloomFilter).assets/image-20220716172346986.png" 
alt="image-20220716172346986" style="zoom:67%;" />

　　 從上圖中可以看到，我們有三個hash函數(shù)(h1()、h2()、h3())和一個位數(shù)組，oracle經(jīng)過三個hash函數(shù)，得到第1、4、5位為1，database同理得到2、5、10位1，這樣如果我們需要判斷oracle是否在此位數(shù)組中，則通過hash函數(shù)判斷位數(shù)組的1、4、5位是否均為1，如果均為1，則判斷oracle在此位數(shù)組中，database同理。這就是布隆過濾器判斷元素是否在集合中的原理。

　　 但同學(xué)們也會發(fā)現(xiàn)，如果我們現(xiàn)在要判斷"mysql"是否存在，例如它通過三次hash運(yùn)算得到的值分別是4,5,10?，F(xiàn)在即使你的位數(shù)中沒有存儲“mysql”,布隆過濾器也會判斷它存在。這是因?yàn)?quot;oracle"、"database"、"filter"算出的hash值已經(jīng)導(dǎo)致上面的三個位置的值被改為了1，這樣就會導(dǎo)致誤判。但是可以保證的是，如果布隆過濾器判斷一個元素不在一個集合中，那這個元素一定不會再集合中。

　　 產(chǎn)生上面誤判的主要原因是hash碰撞導(dǎo)致的。但如果我們將位數(shù)組設(shè)置的足夠大，并且讓hash運(yùn)算執(zhí)行的次數(shù)多一些，這樣就會降低誤判率。

　　 布隆過率器還有另一個問題就是不能刪除。這是因?yàn)樵谖粩?shù)組上的同一個點(diǎn)有可能有多個輸入值的映射，如果刪除了會影響布隆過濾器里其他元素的判斷結(jié)果。

　　 所以我們可以總結(jié)出布隆過濾器的優(yōu)缺點(diǎn)如下：

　　- 優(yōu)點(diǎn)：

　　- 所占空間小(并不存儲真正的數(shù)據(jù))，空間效率高

　　- 查詢時間短

　　- 缺點(diǎn):

　　- 元素添加到數(shù)組中后，不能被刪除

　　- 有一定的誤判率

　　二、布隆過濾器使用場景

　　- 解決緩存穿透問題，緩存穿透是指查詢一個一定不存在的數(shù)據(jù)，由于緩存是不命中就到數(shù)據(jù)庫中去查，并且出于容錯考慮，如果從數(shù)據(jù)庫中查不到數(shù)據(jù)則不寫入緩存，這將導(dǎo)致這個不存在的數(shù)據(jù)每次請求都要到數(shù)據(jù)庫中去查詢，失去了緩存的意義。在流量大時，可能數(shù)據(jù)庫就掛掉了，要是有人利用不存在的key頻繁攻擊我們的應(yīng)用，這就是漏洞。這時候可以用布隆過濾器當(dāng)緩存的索引，只有在布隆過濾器中，才去查詢緩存，如果沒查詢到，則再到數(shù)據(jù)庫中查。如果不在布隆器中，則直接返回。

　　- 在業(yè)務(wù)場景中可以用來判斷用戶是否閱讀過某些文章或視頻，比如抖音或頭條，當(dāng)然會導(dǎo)致一定的誤判，但不會讓用戶看到重復(fù)的內(nèi)容。

　　- 黑名單：比如在郵件系統(tǒng)中可以使用布隆器設(shè)置黑名單，判斷郵件地址是否在黑名單中。也可以設(shè)IP黑名單防止網(wǎng)格爬蟲等。

　　- 垃圾郵件過濾，從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱。

　　三、實(shí)踐

　　3.1 通過 Java 編程手動實(shí)現(xiàn)布隆過濾器

package com.heima.rbac.controller;

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位數(shù)組的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通過這個數(shù)組可以創(chuàng)建 6 個不同的哈希函數(shù)
     */
    private static final int[] SEEDS = new int[]{5, 17, 48, 73, 93, 132};

    /**
     * 位數(shù)組。數(shù)組中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函數(shù)的類的數(shù)組
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多個包含 hash 函數(shù)的類的數(shù)組，每個類中的 hash 函數(shù)都不一樣
     */
    public MyBloomFilter() {
        // 初始化多個不同的 Hash 函數(shù)
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位數(shù)組
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判斷指定元素是否存在于位數(shù)組
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 靜態(tài)內(nèi)部類。用于 hash 操作！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 計(jì)算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

　　3.2 Redis 中的布隆過濾器

　　redis 在 4.0 的版本中加入了 module 功能，布隆過濾器可以通過 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通過加載 [module](https://github.com/RedisLabsModules/rebloom) 來使用 redis 中的布隆過濾器。但是這不是最簡單的方式，使用 docker 可以直接在 redis 中體驗(yàn)布隆過濾器。

　　```

　　> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom

　　> docker exec -it bloomfilter redis-cli

　　```

　　redis 布隆過濾器主要就兩個命令：

　　- `bf.add` 添加元素到布隆過濾器中：`bf.add urls http://www.itcast.com`。

　　- `bf.exists` 判斷某個元素是否在過濾器中：`bf.exists urls http://www.itcast.com`。

　　上面說過布隆過濾器存在誤判的情況，在 redis 中有兩個值決定布隆過濾器的準(zhǔn)確率：

　　- `error_rate`：允許布隆過濾器的錯誤率，這個值越低過濾器的位數(shù)組的大小越大，占用空間也就越大。

　　- `initial_size`：布隆過濾器可以儲存的元素個數(shù)，當(dāng)實(shí)際存儲的元素個數(shù)超過這個值之后，過濾器的準(zhǔn)確率會下降。

　　redis 中有一個命令可以來設(shè)置這兩個值：

　　```

　　bf.reserve urls 0.01 100

　　```

　　三個參數(shù)的含義：

　　- 第一個值是過濾器的名字。

　　- 第二個值為 `error_rate` 的值。

　　- 第三個值為 `initial_size` 的值。

　　使用這個命令要注意一點(diǎn)：執(zhí)行這個命令之前過濾器的名字應(yīng)該不存在，如果執(zhí)行之前就存在會報(bào)錯：`(error) ERR item exists`。