what? 還不知道布隆過濾器嗎?

前言

在好早之前，我在看面試寶典的時(shí)候，關(guān)于預(yù)防緩存雪崩，其中有一個(gè)解決方案就是在緩存前面增加布隆過濾器，時(shí)至今日，我依然清晰地記著布隆過濾器，但是卻不曾深入的了解它，所以今天我想花一點(diǎn)時(shí)間來詳細(xì)了解下布隆過濾器。

布隆過濾器

什么是布隆過濾器？

簡(jiǎn)單來說，布隆過濾器是一種算法，用于判斷某個(gè)值是否在一個(gè)集合中。

通常來說，我們要判斷一個(gè)值是否存在集合中，我們是需要將目標(biāo)值和集合中的每個(gè)值進(jìn)行比較，最終確定是否包含，這樣的缺點(diǎn)也很明顯，如果數(shù)據(jù)量本身很龐大的話，我們需要存儲(chǔ)的數(shù)據(jù)量會(huì)很多，而且比較的時(shí)候也會(huì)比較耗時(shí)。

相比而言，布隆過濾器的設(shè)計(jì)就獨(dú)特了很多，它通過一個(gè)Hash函數(shù)將一個(gè)元素映射成一個(gè)位陣列（Bit array）中的一個(gè)點(diǎn)。這樣一來，我們只要看看這個(gè)點(diǎn)是不是1就可以知道集合中有沒有它了，這就是布隆過濾器的基本思想。

但是Hash面臨的最大問題就是hash沖突。假設(shè)Hash函數(shù)是良好的，如果我們的位陣列長度為m個(gè)點(diǎn)，那么如果我們想將沖突率降低到例如 1%，這個(gè)散列表就只能容納m / 100個(gè)元素。顯然這就不叫空間效率了（Space-efficient）了。解決方法也簡(jiǎn)單，就是使用多個(gè)Hash，如果它們有一個(gè)說元素不在集合中，那肯定就不在。如果它們都說在，雖然也有一定可能性它們?cè)谡f謊，不過直覺上判斷這種事情的概率是比較低的，這個(gè)概率我們通常稱之為誤差率。

所以，簡(jiǎn)單總結(jié)下，布隆過濾器其實(shí)就是通過hash來描述一個(gè)數(shù)據(jù)，然后保存該數(shù)據(jù)的hash值，從而實(shí)現(xiàn)數(shù)據(jù)的判斷，但是由于hash的沖突（具體取決于hash表的大小），會(huì)導(dǎo)致數(shù)據(jù)的誤判，所以本質(zhì)上我們布隆過濾器的誤判是由于hash表的有限性。

關(guān)于hash

hash算法我這里不打算展開（目前我也不是很熟悉i??），但是我這里想要通過一個(gè)簡(jiǎn)單的示例，來解釋下什么是hash。

我們小學(xué)二年級(jí)的時(shí)候，學(xué)過平面上兩個(gè)坐標(biāo)可以確定唯一一個(gè)點(diǎn)（坐標(biāo)），而我們判斷兩個(gè)點(diǎn)是否是同一個(gè)點(diǎn)，是可以通過坐標(biāo)對(duì)比來實(shí)現(xiàn)，而hash算法其實(shí)本身就相當(dāng)于一套坐標(biāo)系，通過這套坐標(biāo)系理論上我們是可以描述所有數(shù)據(jù)，且可以確定數(shù)據(jù)的唯一性（當(dāng)然具體取決于hash表大小）。

另外一種hash的典型應(yīng)用就是我們的身份證，每個(gè)人的身份證號(hào)就是我們每個(gè)人的hash code，通過這個(gè)hash code就可以在14億人中確定唯一的你，所以身份證號(hào)算法就是一種類似于hash的算法。

博隆過濾器的應(yīng)用

上面其實(shí)我們已經(jīng)列舉了博隆過濾器的典型應(yīng)用場(chǎng)景——校驗(yàn)?zāi)硞€(gè)數(shù)據(jù)是否存在，所以我們經(jīng)常把他用在一些需要進(jìn)行數(shù)據(jù)否存在的校驗(yàn)上，最典型的就是用在緩存的key的判斷上，作為緩存系統(tǒng)最后的屏障。

在通常的系統(tǒng)開發(fā)中，我們經(jīng)常要用到緩存組件，而緩存中最核心的一個(gè)場(chǎng)景就是查詢，而緩存查詢中操作頻次最高就是判斷某個(gè)key是否存在，正常情況下簡(jiǎn)單的業(yè)務(wù)判斷是沒有問題的，就算批量很大，也不會(huì)出現(xiàn)大批量key不存在的情況，但是如果遇到惡意攻擊時(shí)，一切都變得不那么確定了，比如有人發(fā)送大量惡意請(qǐng)求專門查詢不存在的key，這時(shí)候就會(huì)導(dǎo)致redis服務(wù)不可用，從而導(dǎo)致緩存雪崩。

這時(shí)候如果我們用了布隆過濾器這樣的組件，這樣的問題就不會(huì)影響如此嚴(yán)重，因?yàn)椴悸∵^濾器可以幫我們屏蔽到絕大多數(shù)的請(qǐng)求，從而降低redis雪崩的風(fēng)險(xiǎn)。

關(guān)于布隆過濾器的實(shí)現(xiàn)，網(wǎng)上其實(shí)有很多實(shí)現(xiàn)，但最典型的當(dāng)屬guava包中提供的BloomFilter。要說guava真是個(gè)好用的工具包，提供了各種各樣好用的工具，比如限流組件、容器組件以及今天我們分享的布隆過濾器，下面我們看下如何使用BloomFilter：

由于BloomFilter的構(gòu)造方案是私有的，所以我們沒有辦法通過new的方式實(shí)例化BloomFilter，但是官方提供了實(shí)例化的方式——create方法：

其他的create方法都是在此基礎(chǔ)上做的封裝，所以我們只簡(jiǎn)單分析上面這個(gè)方法。

這個(gè)方案有四個(gè)參數(shù)：

• Funnel表示我們要過濾的數(shù)據(jù)類別，它相當(dāng)于我們的漏斗，也算是容器，用于判斷數(shù)據(jù)是否存在，目前在Funnels類中提供了六種實(shí)現(xiàn)，應(yīng)該可以滿足我們絕大多數(shù)場(chǎng)景；

• expectedInsertions表示預(yù)期樣本，也就類似于我們前面說的hash表的大小，如果該數(shù)據(jù)太小，誤差率會(huì)很大，原則上來說，這個(gè)數(shù)要大于等于我們要判斷的樣本數(shù)量，否則沒有辦法保證準(zhǔn)確度，當(dāng)然也不能太大，過大會(huì)有性能問題

• fpp表示誤差率，默認(rèn)是0.003

  

下面是一個(gè)簡(jiǎn)單的示例

public?class?BloomFilterTest?{
????public?static?void?main(String[]?args)?{
????????Funnel?charSequenceFunnel?=?Funnels.stringFunnel(Charset.defaultCharset());
????????String?test?=?"hello";
????????BloomFilter?bloomFilter?=?BloomFilter.create(charSequenceFunnel,?100);
????????for?(int?i?=?0;?i?100;?i++)?{
????????????bloomFilter.put(test?+?i);
????????}
????????String?object?=?test?+?-888;
????????if?(bloomFilter.mightContain(object))?{
????????????System.out.println("包含"?+?object);
????????}?else?{
????????????System.out.println("不包含"?+?object);
????????}
????}
}

正常情況下，會(huì)打印輸入不包含hello-888：

但是如果我將樣本數(shù)量變小或者將數(shù)據(jù)量變大，這時(shí)候就會(huì)出現(xiàn)誤判的情況。

比如這里我判斷的是hello-888，bloomFilter中保存的應(yīng)該是hello0到hello999，應(yīng)該是不存在才對(duì)，但是由于hash表（代稱）不夠大，所以會(huì)出現(xiàn)數(shù)據(jù)描述精度丟失問題：

但是如果樣本數(shù)量和數(shù)據(jù)本身數(shù)量差別不大時(shí)，則不會(huì)出現(xiàn)這種情況。

擴(kuò)展

Redis v4.0 ?之后的版本有了 Module（模塊/插件） 功能，Redis Modules 可以讓 Redis 通過使用外部模塊擴(kuò)展其功能 ，而布隆過濾器就是其中的 Module。詳情可以查看 Redis 官方對(duì) Redis Modules 的介紹 ：

https://redis.io/modules

另外，官網(wǎng)推薦了一個(gè)RedisBloom 作為 Redis 布隆過濾器的Module，地址：

https://github.com/RedisBloom/RedisBloom

另外，redis客戶端工具Redisson也提供了布隆過濾器的實(shí)現(xiàn)，其底層使用數(shù)據(jù)結(jié)構(gòu)是bitMap，有興趣的小伙伴可以去了解下。

結(jié)語

布隆過濾器這個(gè)東東，已經(jīng)在我心頭縈繞了很久了，但是一直都沒有花時(shí)間探索過，對(duì)它只能算知道有這么個(gè)組件，知道它的大概用途，但是對(duì)于它的原理和實(shí)現(xiàn)邏輯，卻不曾了解。今天抽時(shí)間做一次簡(jiǎn)單的探索，也算是搞清楚了布隆過濾器的應(yīng)用場(chǎng)景和簡(jiǎn)單的實(shí)現(xiàn)原理，當(dāng)然也清楚了自己在數(shù)據(jù)底層的短板，比如數(shù)據(jù)結(jié)構(gòu)——散列，說明我也該好好補(bǔ)下數(shù)據(jù)結(jié)構(gòu)這塊的知識(shí)了，數(shù)據(jù)結(jié)構(gòu)那本書該翻一翻了??，好了，今天就到這里吧，各位小伙伴，晚安吧！