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

　　一、布隆過(guò)濾器原理

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

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

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

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

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

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

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

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

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

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

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

　　- 查詢(xún)時(shí)間短

　　- 缺點(diǎn):

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

　　- 有一定的誤判率

　　二、布隆過(guò)濾器使用場(chǎng)景

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

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

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

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

　　三、實(shí)踐

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

package com.heima.rbac.controller;

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位數(shù)組的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通過(guò)這個(gè)數(shù)組可以創(chuàng)建 6 個(gè)不同的哈希函數(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ù)的類(lèi)的數(shù)組
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多個(gè)包含 hash 函數(shù)的類(lèi)的數(shù)組，每個(gè)類(lèi)中的 hash 函數(shù)都不一樣
     */
    public MyBloomFilter() {
        // 初始化多個(gè)不同的 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)部類(lè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 中的布隆過(guò)濾器

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

　　```

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

　　> docker exec -it bloomfilter redis-cli

　　```

　　redis 布隆過(guò)濾器主要就兩個(gè)命令：

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

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

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

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

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

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

　　```

　　bf.reserve urls 0.01 100

　　```

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

　　- 第一個(gè)值是過(guò)濾器的名字。

　　- 第二個(gè)值為 `error_rate` 的值。

　　- 第三個(gè)值為 `initial_size` 的值。

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