大白話布隆過(guò)濾器

本文是站在小白的角度去討論布隆過(guò)濾器，如果你是科班出身，或者比較聰明，又或者真正想完全搞懂布隆過(guò)濾器的可以移步。

不知道從什么時(shí)候開(kāi)始，本來(lái)默默無(wú)聞的布隆過(guò)濾器一下子名聲大燥，仿佛身在互聯(lián)網(wǎng)，做著開(kāi)發(fā)的，無(wú)人不知，無(wú)人不曉，哪怕對(duì)技術(shù)不是很關(guān)心的小伙伴也聽(tīng)過(guò)它的名號(hào)。我也花了不少時(shí)間去研究布隆過(guò)濾器，看了不少博客，無(wú)奈不是科班出身，又沒(méi)有那么聰明的頭腦，又比較懶...經(jīng)過(guò)“放棄，拿起，放棄，拿起”的無(wú)限輪回，應(yīng)該算是了解了布隆過(guò)濾器的核心思想，所以想給大家分享下。

布隆過(guò)濾器的應(yīng)用

我們先來(lái)看下布隆過(guò)濾器的應(yīng)用場(chǎng)景，讓大家知道神奇的布隆過(guò)濾器到底能做什么。

緩存穿透

我們經(jīng)常會(huì)把一部分?jǐn)?shù)據(jù)放在Redis等緩存，比如產(chǎn)品詳情。這樣有查詢請(qǐng)求進(jìn)來(lái)，我們可以根據(jù)產(chǎn)品Id直接去緩存中取數(shù)據(jù)，而不用讀取數(shù)據(jù)庫(kù)，這是提升性能最簡(jiǎn)單，最普遍，也是最有效的做法。一般的查詢請(qǐng)求流程是這樣的：先查緩存，有緩存的話直接返回，如果緩存中沒(méi)有，再去數(shù)據(jù)庫(kù)查詢，然后再把數(shù)據(jù)庫(kù)取出來(lái)的數(shù)據(jù)放入緩存，一切看起來(lái)很美好。但是如果現(xiàn)在有大量請(qǐng)求進(jìn)來(lái)，而且都在請(qǐng)求一個(gè)不存在的產(chǎn)品Id，會(huì)發(fā)生什么？既然產(chǎn)品Id都不存在，那么肯定沒(méi)有緩存，沒(méi)有緩存，那么大量的請(qǐng)求都懟到數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)的壓力一下子就上來(lái)了，還有可能把數(shù)據(jù)庫(kù)打死。 雖然有很多辦法都可以解決這問(wèn)題，但是我們的主角是“布隆過(guò)濾器”，沒(méi)錯(cuò)，“布隆過(guò)濾器”就可以解決（緩解）緩存穿透問(wèn)題。至于為什么說(shuō)是“緩解”，看下去你就明白了。

大量數(shù)據(jù)，判斷給定的是否在其中。（空間換時(shí)間的思想）

現(xiàn)在有大量的數(shù)據(jù)，而這些數(shù)據(jù)的大小已經(jīng)遠(yuǎn)遠(yuǎn)超出了服務(wù)器的內(nèi)存，現(xiàn)在再給你一個(gè)數(shù)據(jù)，如何判斷給你的數(shù)據(jù)在不在其中。如果服務(wù)器的內(nèi)存足夠大，那么用HashMap是一個(gè)不錯(cuò)的解決方案，理論上的時(shí)間復(fù)雜度可以達(dá)到O(1)，但是現(xiàn)在數(shù)據(jù)的大小已經(jīng)遠(yuǎn)遠(yuǎn)超出了服務(wù)器的內(nèi)存，所以無(wú)法使用HashMap，這個(gè)時(shí)候就可以使用“布隆過(guò)濾器”來(lái)解決這個(gè)問(wèn)題。但是還是同樣的，會(huì)有一定的“誤判率”。

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

布隆過(guò)濾器是一個(gè)叫“布隆”的人提出的，它本身是一個(gè)很長(zhǎng)的二進(jìn)制向量，既然是二進(jìn)制的向量，那么顯而易見(jiàn)的，存放的不是0，就是1。

現(xiàn)在我們新建一個(gè)長(zhǎng)度為16的布隆過(guò)濾器，默認(rèn)值都是0，就像下面這樣：

現(xiàn)在需要添加一個(gè)數(shù)據(jù)：

我們通過(guò)某種計(jì)算方式，比如Hash1，計(jì)算出了Hash1(數(shù)據(jù))=5，我們就把下標(biāo)為5的格子改成1，就像下面這樣：

我們又通過(guò)某種計(jì)算方式，比如Hash2，計(jì)算出了Hash2(數(shù)據(jù))=9，我們就把下標(biāo)為9的格子改成1，就像下面這樣：

還是通過(guò)某種計(jì)算方式，比如Hash3，計(jì)算出了Hash3(數(shù)據(jù))=2，我們就把下標(biāo)為2的格子改成1，就像下面這樣：

這樣，剛才添加的數(shù)據(jù)就占據(jù)了布隆過(guò)濾器“5”，“9”，“2”三個(gè)格子。

可以看出，僅僅從布隆過(guò)濾器本身而言，根本沒(méi)有存放完整的數(shù)據(jù)，只是運(yùn)用一系列隨機(jī)映射函數(shù)計(jì)算出位置，然后填充二進(jìn)制向量。

這有什么用呢？比如現(xiàn)在再給你一個(gè)數(shù)據(jù)，你要判斷這個(gè)數(shù)據(jù)是否重復(fù)，你怎么做？

你只需利用上面的三種固定的計(jì)算方式，計(jì)算出這個(gè)數(shù)據(jù)占據(jù)哪些格子，然后看看這些格子里面放置的是否都是1，如果有一個(gè)格子不為1，那么就代表這個(gè)數(shù)字不在其中。這很好理解吧，比如現(xiàn)在又給你了剛才你添加進(jìn)去的數(shù)據(jù)，你通過(guò)三種固定的計(jì)算方式，算出的結(jié)果肯定和上面的是一模一樣的，也是占據(jù)了布隆過(guò)濾器“5”，“9”，“2”三個(gè)格子。

但是有一個(gè)問(wèn)題需要注意，如果這些格子里面放置的都是1，不一定代表給定的數(shù)據(jù)一定重復(fù)，也許其他數(shù)據(jù)經(jīng)過(guò)三種固定的計(jì)算方式算出來(lái)的結(jié)果也是相同的。這也很好理解吧，比如我們需要判斷對(duì)象是否相等，是不可以僅僅判斷他們的哈希值是否相等的。

也就是說(shuō)布隆過(guò)濾器只能判斷數(shù)據(jù)是否一定不存在，而無(wú)法判斷數(shù)據(jù)是否一定存在。

按理來(lái)說(shuō)，介紹完了新增、查詢的流程，就要介紹刪除的流程了，但是很遺憾的是布隆過(guò)濾器是很難做到刪除數(shù)據(jù)的，為什么？你想想，比如你要?jiǎng)h除剛才給你的數(shù)據(jù)，你把“5”，“9”，“2”三個(gè)格子都改成了0，但是可能其他的數(shù)據(jù)也映射到了“5”，“9”，“2”三個(gè)格子啊，這不就亂套了嗎？

相信經(jīng)過(guò)我這么一介紹，大家對(duì)布隆過(guò)濾器應(yīng)該有一個(gè)淺顯的認(rèn)識(shí)了，至少你應(yīng)該清楚布隆過(guò)濾器的優(yōu)缺點(diǎn)了：

• 優(yōu)點(diǎn)：由于存放的不是完整的數(shù)據(jù)，所以占用的內(nèi)存很少，而且新增，查詢速度夠快；
• 缺點(diǎn)： 隨著數(shù)據(jù)的增加，誤判率隨之增加；無(wú)法做到刪除數(shù)據(jù)；只能判斷數(shù)據(jù)是否一定不存在，而無(wú)法判斷數(shù)據(jù)是否一定存在。

可以看到，布隆過(guò)濾器的優(yōu)點(diǎn)和缺點(diǎn)一樣明顯。

在上文中，我舉的例子二進(jìn)制向量長(zhǎng)度為16，由三個(gè)隨機(jī)映射函數(shù)計(jì)算位置，在實(shí)際開(kāi)發(fā)中，如果你要添加大量的數(shù)據(jù)，僅僅16位是遠(yuǎn)遠(yuǎn)不夠的，為了讓誤判率降低，我們還可以用更多的隨機(jī)映射函數(shù)、更長(zhǎng)的二進(jìn)制向量去計(jì)算位置。

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

現(xiàn)在相信你對(duì)布隆過(guò)濾器應(yīng)該有一個(gè)比較感性的認(rèn)識(shí)了，布隆過(guò)濾器核心思想其實(shí)并不難，難的在于如何設(shè)計(jì)隨機(jī)映射函數(shù)，到底映射幾次，二進(jìn)制向量的長(zhǎng)度設(shè)置為多少比較好，這可能就不是一般的開(kāi)發(fā)可以駕馭的了，好在Google大佬給我們提供了開(kāi)箱即用的組件，來(lái)幫助我們實(shí)現(xiàn)布隆過(guò)濾器，現(xiàn)在就讓我們看看怎么Google大佬送給我們的“禮物”吧。

首先在pom引入“禮物”：

<dependency>
           <groupId>com.google.guava</groupId>
           <artifactId>guava</artifactId>
           <version>19.0</version>
</dependency>

然后就可以測(cè)試?yán)玻?/p>

    private static int size = 1000000;//預(yù)計(jì)要插入多少數(shù)據(jù)
    private static double fpp = 0.01;//期望的誤判率
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
    public static void main(String[] args) {
        //插入數(shù)據(jù)
        for (int i = 0; i < 1000000; i++) {
            bloomFilter.put(i);
        }
        int count = 0;
        for (int i = 1000000; i < 2000000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
                System.out.println(i + "誤判了");
            }
        }
        System.out.println("總共的誤判數(shù):" + count);
    }

代碼簡(jiǎn)單分析： 我們定義了一個(gè)布隆過(guò)濾器，有兩個(gè)重要的參數(shù)，分別是 我們預(yù)計(jì)要插入多少數(shù)據(jù)，我們所期望的誤判率，誤判率不能為0。 我向布隆過(guò)濾器插入了0-1000000，然后用1000000-2000000來(lái)測(cè)試誤判率。

運(yùn)行結(jié)果：

1999501誤判了
1999567誤判了
1999640誤判了
1999697誤判了
1999827誤判了
1999942誤判了
總共的誤判數(shù):10314

現(xiàn)在總共有100萬(wàn)數(shù)據(jù)是不存在的，誤判了10314次，我們計(jì)算下誤判率

和我們定義的期望誤判率0.01相差無(wú)幾。

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

上面使用guava實(shí)現(xiàn)布隆過(guò)濾器是把數(shù)據(jù)放在本地內(nèi)存中，無(wú)法實(shí)現(xiàn)布隆過(guò)濾器的共享，我們還可以把數(shù)據(jù)放在redis中，用 redis來(lái)實(shí)現(xiàn)布隆過(guò)濾器，我們要使用的數(shù)據(jù)結(jié)構(gòu)是bitmap，你可能會(huì)有疑問(wèn)，redis支持五種數(shù)據(jù)結(jié)構(gòu)：String，List，Hash，Set，ZSet，沒(méi)有bitmap呀。沒(méi)錯(cuò)，實(shí)際上bitmap的本質(zhì)還是String。

可能有小伙伴會(huì)說(shuō)，納尼，布隆過(guò)濾器還沒(méi)介紹完，怎么又出來(lái)一個(gè)bitmap，沒(méi)事，你可以把bitmap就理解為一個(gè)二進(jìn)制向量。

要用redis來(lái)實(shí)現(xiàn)布隆過(guò)濾器，我們需要自己設(shè)計(jì)映射函數(shù)，自己度量二進(jìn)制向量的長(zhǎng)度，這對(duì)我來(lái)說(shuō)，無(wú)疑是一個(gè)不可能完成的任務(wù)，只能借助搜索引擎，下面直接放出代碼把。

public class RedisMain {
    static final int expectedInsertions = 1000;//要插入多少數(shù)據(jù)
    static final double fpp = 0.01;//期望的誤判率
    //bit數(shù)組長(zhǎng)度
    private static long numBits;
    //hash函數(shù)數(shù)量
    private static int numHashFunctions;
    static {
        numBits = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    }
    public static void main(String[] args) {
        Jedis jedis = new Jedis("localhost", 6379);
        for (int i = 0; i < 1000; i++) {
            long[] indexArray = getIndexArray(String.valueOf(i));
            for (long index : indexArray) {
                jedis.setbit("codebear:bloom", index, true);
            }
        }
        int num = 0;
        for (int i = 1000; i < 2000; i++) {
            long[] indexArray = getIndexArray(String.valueOf(i));
            for (long index : indexArray) {
                if (!jedis.getbit("codebear:bloom", index)) {
                    System.out.println(i + "一定不存在");
                    num++;
                    break;
                }
            }
        }
        System.out.println("一定不存在的有" + num + "個(gè)");
    }
    /**
     * 根據(jù)key獲取bitmap下標(biāo)
     */
    private static long[] getIndexArray(String key) {
        long hash1 = hash(key);
        long hash2 = hash1 >>> 16;
        long[] result = new long[numHashFunctions];
        for (int i = 0; i < numHashFunctions; i++) {
            long combinedHash = hash1 + i * hash2;
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            result[i] = combinedHash % numBits;
        }
        return result;
    }
    private static long hash(String key) {
        return Hashing.MURMUR_HASH.hash(key);
    }
    //計(jì)算hash函數(shù)個(gè)數(shù)
    private static int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
    //計(jì)算bit數(shù)組長(zhǎng)度
    private static long optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
}

運(yùn)行結(jié)果：

1997一定不存在
1998一定不存在
1999一定不存在
一定不存在的有989個(gè)

到此這篇關(guān)于Java中Redis的布隆過(guò)濾器詳解的文章就介紹到這了,更多相關(guān)Redis布隆過(guò)濾器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論