聊聊布隆過濾器

前言

布隆過濾器作為一個(gè)精巧且實(shí)用的數(shù)據(jù)結(jié)構(gòu)，對于后端程序員來講，學(xué)習(xí)和理解布隆過濾器有很大的必要性。希望通過這篇文章讓更多人了解布隆過濾器的原理，并且會實(shí)際去使用它！

什么是布隆過濾器？

布隆過濾器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出，我們可以把它看作由二進(jìn)制向量（或者說位數(shù)組）和一系列隨機(jī)映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結(jié)構(gòu)。相比于我們平時(shí)常用的的 List、Map、Set 等數(shù)據(jù)結(jié)構(gòu)，它占用空間更少并且效率更高，但是缺點(diǎn)是其返回的結(jié)果是概率性的，而不是非常準(zhǔn)確的。理論情況下添加到集合中的元素越多，誤報(bào)的可能性就越大。而且，存放在布隆過濾器的數(shù)據(jù)不容易刪除。

Bloom Filter 會使用一個(gè)較大的 bit 數(shù)組來保存所有的數(shù)據(jù)，數(shù)組中的每個(gè)元素都只占用 1 bit ，并且每個(gè)元素只能是 0 或者 1（代表 false 或者 true），這也是 Bloom Filter 節(jié)省內(nèi)存的核心所在。這樣來算的話，申請一個(gè) 100w 個(gè)元素的位數(shù)組只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空間。

位數(shù)組

總結(jié)：一個(gè)名叫 Bloom 的人提出了一種來檢索元素是否在給定大集合中的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)是高效且性能很好的，但缺點(diǎn)是具有一定的錯誤識別率和刪除難度。并且，理論情況下，添加到集合中的元素越多，誤報(bào)的可能性就越大。

布隆過濾器使用場景

判斷給定數(shù)據(jù)是否存在：比如判斷一個(gè)數(shù)字是否存在于包含大量數(shù)字的數(shù)字集中（數(shù)字集很大，上億）、 防止緩存穿透（判斷請求的數(shù)據(jù)是否有效避免直接繞過緩存請求數(shù)據(jù)庫）等等、郵箱的垃圾郵件過濾（判斷一個(gè)郵件地址是否在垃圾郵件列表中）、黑名單功能（判斷一個(gè)IP地址或手機(jī)號碼是否在黑名單中）等等。

網(wǎng)頁爬蟲對URL去重，避免爬取相同的 URL 地址。

比如用戶日常刷新聞，每次推薦給該用戶的內(nèi)容不能重復(fù)，過濾已經(jīng)看過的內(nèi)容。

以上場景都需要判斷給定數(shù)據(jù)是否存在，因此布隆過濾器主要是為了解決海量數(shù)據(jù)的存在性問題。

布隆過濾器的原理介紹

當(dāng)一個(gè)元素加入布隆過濾器中的時(shí)候，會進(jìn)行如下操作：

使用布隆過濾器中的哈希函數(shù)對元素值進(jìn)行計(jì)算，得到哈希值（有幾個(gè)哈希函數(shù)得到幾個(gè)哈希值）。

根據(jù)得到的哈希值，在位數(shù)組中把對應(yīng)下標(biāo)的值置為 1。

當(dāng)我們需要判斷一個(gè)元素是否存在于布隆過濾器的時(shí)候，會進(jìn)行如下操作：

對給定元素再次進(jìn)行相同的哈希計(jì)算；

得到值之后判斷位數(shù)組中的每個(gè)元素是否都為 1，如果值都為 1，那么說明這個(gè)值在布隆過濾器中，如果存在一個(gè)值不為 1，說明該元素不在布隆過濾器中。

Bloom Filter 的簡單原理圖如下：

Bloom Filter 的簡單原理示意圖

如圖所示，當(dāng)字符串存儲要加入到布隆過濾器中時(shí)，該字符串首先由多個(gè)哈希函數(shù)生成不同的哈希值，然后將對應(yīng)的位數(shù)組的下標(biāo)設(shè)置為 1（當(dāng)位數(shù)組初始化時(shí)，所有位置均為 0）。當(dāng)?shù)诙未鎯ο嗤址畷r(shí)，因?yàn)橄惹暗膶?yīng)位置已設(shè)置為 1，所以很容易知道此值已經(jīng)存在（去重非常方便）。

如果我們需要判斷某個(gè)字符串是否在布隆過濾器中時(shí)，只需要對給定字符串再次進(jìn)行相同的哈希計(jì)算，得到值之后判斷位數(shù)組中的每個(gè)元素是否都為 1，如果值都為 1，那么說明這個(gè)值在布隆過濾器中，如果存在一個(gè)值不為 1，說明該元素不在布隆過濾器中。

不同的字符串可能哈希出來的位置相同，這種情況我們可以適當(dāng)增加位數(shù)組大小或者調(diào)整我們的哈希函數(shù)。

綜上，我們可以得出：布隆過濾器說某個(gè)元素存在，小概率會誤判。布隆過濾器說某個(gè)元素不在，那么這個(gè)元素一定不在。

如何實(shí)現(xiàn)布隆過濾器

Guava 實(shí)現(xiàn)

Guava 中布隆過濾器的實(shí)現(xiàn)算是比較權(quán)威的，所以實(shí)際項(xiàng)目中我們不需要自己去實(shí)現(xiàn)一個(gè)布隆過濾器。

首先我們需要在項(xiàng)目中引入 Guava 的依賴：

com.google.guava
guava
28.0-jre

實(shí)際使用如下：

我們創(chuàng)建了一個(gè)最多存放 最多 1500 個(gè)整數(shù)的布隆過濾器，并且我們可以容忍誤判的概率為百分之（0.01）

//創(chuàng)建布隆過濾器對象
BloomFilterfilter=BloomFilter.create(
Funnels.integerFunnel(),
1500,
0.01);
//判斷指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
//將元素添加進(jìn)布隆過濾器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));

在我們的示例中，當(dāng)mightContain()方法返回true時(shí)，我們可以 99％確定該元素在過濾器中，當(dāng)過濾器返回false時(shí)，我們可以 100％確定該元素不存在于過濾器中。

Guava 提供的布隆過濾器的實(shí)現(xiàn)還是很不錯的（想要詳細(xì)了解的可以看一下它的源碼實(shí)現(xiàn)），但是它有一個(gè)重大的缺陷就是只能單機(jī)使用（另外，容量擴(kuò)展也不容易），而現(xiàn)在互聯(lián)網(wǎng)一般都是分布式的場景。為了解決這個(gè)問題，我們就需要用到 Redis 中的布隆過濾器了。

Redis 中的布隆過濾器

Redis v4.0 之后有了 Module（模塊/插件）功能，Redis Modules 讓 Redis 可以使用外部模塊擴(kuò)展其功能 ，使用戶可以根據(jù)需要額外集成一些實(shí)用功能。

審核編輯：劉清