一文搞懂布隆過(guò)濾器

在開發(fā)軟件時(shí)，我們經(jīng)常需要判斷一個(gè)元素是否在一個(gè)集合中，比如，如何判斷單詞的拼寫是否錯(cuò)誤（判斷單詞是否在已知的字典中）；在網(wǎng)絡(luò)爬蟲里，如何確認(rèn)一個(gè)網(wǎng)址是否已經(jīng)爬取過(guò)；反垃圾郵件系統(tǒng)中，如何判斷一個(gè)郵件地址是否為垃圾郵件地址等等。

如果這些作為面試題那就很有區(qū)分度了，初級(jí)工程師就會(huì)說(shuō)，把全部的元素都存在 hash 表中，當(dāng)需要判斷元素是否在集合中時(shí)，可以直接判斷，時(shí)間復(fù)雜度是 O(1)，比如 Python 的集合：

>>> all_elements = {'a','b','c','d','e'}
>>> 'a' in all_elements
True
>>> 'f' in all_elements
False
>>>

這樣回答顯然沒(méi)有考慮到數(shù)量級(jí)的問(wèn)題，就拿爬蟲中的 URL 去重來(lái)說(shuō)，假設(shè)一個(gè) URL 的平均長(zhǎng)度是 64 字節(jié)，那單純存儲(chǔ)這 10 億個(gè) URL，需要大約 60GB 的內(nèi)存空間。因?yàn)楣１肀仨毦S持較小的裝載因子，才能保證不會(huì)出現(xiàn)過(guò)多的哈希沖突，導(dǎo)致操作的性能下降。而且，用鏈表法解決沖突的哈希表，還會(huì)存儲(chǔ)鏈表指針，因此哈希表的存儲(chǔ)效率一般只有 50%。所以，如果將這 10 億個(gè) URL 構(gòu)建成哈希表，那需要的內(nèi)存空間會(huì)超過(guò) 100GB。這樣的話一般的機(jī)器，內(nèi)存就不夠用了，更別提哈希查找了。

因此考慮到這一點(diǎn)，中級(jí)一點(diǎn)的工程師會(huì)說(shuō)數(shù)據(jù)量大的時(shí)候可以采用分治的思想，用多臺(tái)機(jī)器（比如 20 臺(tái)內(nèi)存是 8GB 的機(jī)器）來(lái)存儲(chǔ)這 10 億網(wǎng)頁(yè)鏈接。這種分治的處理思路，也是一種解決辦法，本質(zhì)上還是增加硬件資源來(lái)解決問(wèn)題，還不夠高級(jí)。

更高級(jí)的工程師會(huì)提到位圖、布隆過(guò)濾器，可以使用很小的內(nèi)存來(lái)實(shí)現(xiàn)大數(shù)據(jù)量的查詢。如果你提到了這兩個(gè)概念，那離 offer 也就不遠(yuǎn)了。想回答好這個(gè)問(wèn)題，看本文就夠了，保證你搞懂布隆過(guò)濾器，要是搞不懂，你加我微信，我會(huì)對(duì)你負(fù)責(zé)的??。

在講布隆過(guò)濾器前，要先講一下另一種存儲(chǔ)結(jié)構(gòu)，位圖（BitMap）。因?yàn)?，布隆過(guò)濾器本身就是基于位圖的，是對(duì)位圖的一種改進(jìn)。

同樣地，為了方便你理解，我們來(lái)簡(jiǎn)化問(wèn)題，現(xiàn)在有 1 千萬(wàn)個(gè)整數(shù)，整數(shù)的范圍在 1 到 1 億之間。如何快速查找某個(gè)整數(shù)是否在這 1 千萬(wàn)個(gè)整數(shù)中呢？

當(dāng)然，這個(gè)問(wèn)題還是可以用哈希表來(lái)解決。不過(guò)，我們可以使用一種比較“特殊”的哈希表，那就是位圖。我們申請(qǐng)一個(gè)大小為 1 億、數(shù)據(jù)類型為布爾類型（true 或者 false）的數(shù)組。我們將這 1 千萬(wàn)個(gè)整數(shù)作為數(shù)組下標(biāo)，將對(duì)應(yīng)的數(shù)組值設(shè)置成 true。比如，整數(shù) 5 對(duì)應(yīng)下標(biāo)為 5 的數(shù)組值設(shè)置為 true，也就是 array[5]=true 。

當(dāng)我們查詢某個(gè)整數(shù) K 是否在這 1 千萬(wàn)個(gè)整數(shù)中的時(shí)候，我們只需要將對(duì)應(yīng)的數(shù)組值 array[K]取出來(lái)，看是否等于 true。如果等于 true，那說(shuō)明 1 千萬(wàn)整數(shù)中包含這個(gè)整數(shù) K；相反，就表示不包含這個(gè)整數(shù) K。不過(guò)，很多語(yǔ)言中提供的布爾類型，大小是 1 個(gè)字節(jié)的，并不能節(jié)省太多內(nèi)存空間。實(shí)際上，表示 true 和 false 兩個(gè)值，我們只需要用一個(gè)二進(jìn)制位（bit）就可以了。那如何通過(guò)編程語(yǔ)言，來(lái)表示一個(gè)二進(jìn)制位呢？

這個(gè)用語(yǔ)言很難表達(dá)，還是給出代碼吧，一碼勝千言啊。

這里先給出 Java 的，我覺(jué)得 Java 的更容易看懂，再給出 Python 的，你可以對(duì)比著代碼看下，應(yīng)該很快就理解了。

public class BitMap { // Java中char類型占16bit，也即是2個(gè)字節(jié)
  private char[] bytes;
  private int nbits;
  
  public BitMap(int nbits) {
    this.nbits = nbits;
    this.bytes = new char[nbits/16+1];
  }

  public void set(int k) {
    if (k > nbits) return;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    bytes[byteIndex] |= (1 << bitIndex);
  }

  public boolean get(int k) {
    if (k > nbits) return false;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    return (bytes[byteIndex] & (1 << bitIndex)) != 0;
  }
}

Python 的實(shí)現(xiàn)：

class BitMap(object):
    def __init__(self, max_value):
        """
        使用多個(gè)整型元素來(lái)儲(chǔ)存數(shù)據(jù)，每個(gè)元素4個(gè)字節(jié)（32位）
        """
        self._size = int((max_value + 31 - 1) / 31)  # 計(jì)算需要的字節(jié)數(shù)，字節(jié)數(shù)也是數(shù)組的大小
        self.array = [0 for i in range(self._size)]  # 數(shù)組的元素都初始化為0，每個(gè)元素有32位

    @staticmethod
    def get_element_index(num):
        """
        獲取該數(shù)即將儲(chǔ)存的字節(jié)在數(shù)組中下標(biāo)
        """
        return num // 31

    @staticmethod
    def get_bit_index(num):
        """
        獲取該數(shù)在元素中的位下標(biāo)
        """
        return num % 31

    def set(self, num):
        """
        將該數(shù)存在對(duì)應(yīng)的元素的對(duì)應(yīng)位置
        """
        element_index = self.get_element_index(num)
        bit_index = self.get_bit_index(num)
        self.array[element_index] = self.array[element_index] | (1 << bit_index)

    def get(self, num):
        """
        查找該數(shù)是否存在與bitmap中
        """
        element_index = self.get_element_index(num)
        bit_index = self.get_bit_index(num)
        if self.array[element_index] & (1 << bit_index):
            return True
        return False

從上面位圖實(shí)現(xiàn)的代碼中，你應(yīng)該可以發(fā)現(xiàn)，位圖通過(guò)數(shù)組下標(biāo)來(lái)定位數(shù)據(jù)，所以，訪問(wèn)效率非常高。而且，每個(gè)數(shù)字用一個(gè)二進(jìn)制位來(lái)表示，在數(shù)字范圍不大的情況下，所需要的內(nèi)存空間非常小。

比如剛剛那個(gè)例子，如果用哈希表存儲(chǔ)這 1 千萬(wàn)的數(shù)據(jù)，數(shù)據(jù)是 32 位的整型數(shù)，每個(gè)整數(shù) 4 個(gè)字節(jié)，那總共至少需要 1 千萬(wàn) * 4  = 40MB 的存儲(chǔ)空間。如果我們通過(guò)位圖的話，數(shù)字范圍在 1 到 1 億之間，只需要 1 億個(gè)二進(jìn)制位，也就是 12MB 左右的存儲(chǔ)空間就夠了。

位圖就是用一個(gè)二進(jìn)制位的 1 來(lái)代表一個(gè)元素存在，是不是挺簡(jiǎn)單的？不過(guò)，這里我們有個(gè)假設(shè)，就是數(shù)字所在的范圍不是很大。如果數(shù)字的范圍很大，比如剛剛那個(gè)問(wèn)題，數(shù)字范圍不是 1 到 1 億，而是 1 到 10 億，那位圖的大小就需要 10 億個(gè)二進(jìn)制位，也就是 120MB 的大小，消耗的內(nèi)存空間，增加了 10 倍，如何不增加內(nèi)存空間來(lái)解決問(wèn)題呢？請(qǐng)繼續(xù)往下看。

布隆過(guò)濾器的原理

這個(gè)時(shí)候，布隆過(guò)濾器就要出場(chǎng)了。布隆過(guò)濾器就是為了解決剛剛這個(gè)問(wèn)題，對(duì)位圖這種數(shù)據(jù)結(jié)構(gòu)的一種改進(jìn)。

布隆過(guò)濾器是由伯頓·布隆于 1970 年提出的，為了簡(jiǎn)化說(shuō)明布隆過(guò)濾器的原理，我們降低數(shù)據(jù)量級(jí)：假如數(shù)字范圍是從 1 到 100 提升到 200，為了不占用太多內(nèi)存，我們依然使用 100 個(gè)二進(jìn)制位，如果數(shù)據(jù)個(gè)數(shù)超過(guò) 100 個(gè)，就必然存在哈希沖突，怎么辦？

因?yàn)槲覀兪褂?1 位代表一個(gè)元素，因此 100 個(gè)二進(jìn)制位，最多代表 100 個(gè)元素，但是假如使用 2 位來(lái)代表一個(gè)元素呢？那就是組合 C(100,2) = 100*99/2 = 4950 個(gè)數(shù)，是不是可以代表更多？當(dāng)然了，你還可以使用 3 位代表一個(gè)元素，這樣可以代表 161700 個(gè)數(shù)。

我們以使用 2 位二進(jìn)制位來(lái)代表一個(gè)元素為例，設(shè)計(jì)兩個(gè) HASH 函數(shù)，bit1 = HASH1(num)，bit2 = HASH2(num)，存入 num 時(shí)就把 bit1 和 bit2 都置為 1；判斷時(shí)就判斷 bit1 和 bit2，當(dāng) bit1 和 bit2 都為 1 時(shí)，就表示 num 存在集合中。

這樣會(huì)有個(gè)問(wèn)題：兩個(gè)數(shù) num1 和 num2 經(jīng)過(guò)兩個(gè) HASH 函數(shù)之后，結(jié)果一樣，也就是存在 HASH 沖突，這樣就可能誤判。

實(shí)際上，只要讓誤判的概率足夠低，結(jié)果就是可信的。假設(shè)哈希函數(shù)的個(gè)數(shù)為 k，二進(jìn)制的位數(shù)為 m，元素個(gè)數(shù) n，可以從數(shù)學(xué)上計(jì)算出他們與誤判率的關(guān)系^[1](原麥迪遜威斯康星大學(xué)曹培教授提供)：

可以看出，當(dāng) m/n = 16，n = 8，時(shí)，誤判率為萬(wàn)分之五，這在大多數(shù)應(yīng)用中都是可以接受的，而且這種誤判是這樣的：如果這個(gè)元素在集合中，那么布隆過(guò)濾器絕不會(huì)漏掉，如果不在集合中，則有可能判定為在集合中，比如說(shuō)對(duì)應(yīng)垃圾郵件，布隆過(guò)濾器絕不會(huì)漏掉黑名單中的任何一個(gè)可疑地址，但是它有一定極小的概率將一個(gè)不在黑名單上的電子郵件判定為在黑名單中。

到這里我相信你已經(jīng)明白了個(gè)中原理。

在 Python 中使用布隆過(guò)濾器

pypi 搜了了 Python 中的布隆過(guò)濾器，有 3 個(gè)：

pip install bloom-filter2
pip install pybloom-live
pip install bloompy

第三個(gè) bloompy^[2] 的文檔比較詳細(xì)，推薦使用（如果有興趣，你可以自己實(shí)現(xiàn)一個(gè)）：

bloompy 提供了四種布隆過(guò)濾器：

1、標(biāo)準(zhǔn)布隆過(guò)濾器。

標(biāo)準(zhǔn)布隆過(guò)濾器只能進(jìn)行數(shù)據(jù)的查詢和插入，是其他過(guò)濾器的基類，可以進(jìn)行過(guò)濾器的存儲(chǔ)和恢復(fù)，代碼示例：

>>> import bloompy
>>> bf = bloompy.BloomFilter(error_rate=0.001,element_num=10**3)

# 查詢?cè)厥欠裨谶^(guò)濾器里返回狀態(tài)標(biāo)識(shí)
# 如果不在里面則插入，返回False表示元素不在過(guò)濾器里
>>> bf.add(1) 
False
>>> bf.add(1)
True
>>> 1 in bf
True
>>> bf.exists(1)
True
>>> bf.add([1,2,3])
False
>>> bf.add([1,2,3])
True
>>> [1,2,3] in bf
True
>>> bf.exists([1,2,3])
True

# 將過(guò)濾器存儲(chǔ)在一個(gè)文件里
>>> bf.tofile('filename.suffix')

# 從一個(gè)文件里恢復(fù)過(guò)濾器。自動(dòng)識(shí)別過(guò)濾器的種類。
>>> recovered_bf = bloompy.get_filter_fromfile('filename.suffix')

# 或者使用過(guò)濾器類的類方法 'fromfile' 來(lái)進(jìn)行過(guò)濾器的復(fù)原。對(duì)應(yīng)的類只能恢復(fù)對(duì)應(yīng)的過(guò)濾器
>>> recovered_bf = bloompy.BloomFilter.fromfile('filename.suffix')

# 返回已經(jīng)插入的元素個(gè)數(shù)
>>> bf.count
2

# 過(guò)濾器的容量
>>> bf.capacity
1000

# 過(guò)濾器的位向量
>>> bf.bit_array
bitarray('00....')

# 過(guò)濾器位數(shù)組長(zhǎng)度
>>> bf.bit_num
14400

# 過(guò)濾器的哈希種子，默認(rèn)是素?cái)?shù)，可修改
>>> bf.seeds
[2, 3, 5, 7, 11,...]

# 過(guò)濾器哈希函數(shù)個(gè)數(shù)
>>> bf.hash_num
10

2、計(jì)數(shù)布隆過(guò)濾器。

它是標(biāo)準(zhǔn)布隆過(guò)濾器的子類，但是可以執(zhí)行刪除操作。內(nèi)置默認(rèn)使用 4 位二進(jìn)制位來(lái)表示標(biāo)準(zhǔn)布隆過(guò)濾器的 1 個(gè)位，從而實(shí)現(xiàn)可以增減。

>>> import  bloompy
>>> cbf  = bloompy.CountingBloomFilter(error_rate=0.001,element_num=10**3)

# 與標(biāo)準(zhǔn)布隆過(guò)濾器一樣
>>> cbf.add(12)
False
>>> cbf.add(12)
True
>>> 12 in cbf
True
>>> cbf.count
1

# 查詢?cè)貭顟B(tài)返回標(biāo)識(shí)，如果元素存在過(guò)濾器里則刪除
>>> cbf.delete(12)
True
>>> cbf.delete(12)
False
>>> 12 in cbf
False
>>> cbf.count
0

# 從文件中恢復(fù)過(guò)濾器
>>> recovered_cbf = bloompy.CountingBloomFilter.fromfile('filename.suffix')

3、標(biāo)準(zhǔn)擴(kuò)容布隆過(guò)濾器。

當(dāng)插入的元素個(gè)數(shù)超過(guò)當(dāng)前過(guò)濾器的容量時(shí)，自動(dòng)增加過(guò)濾器的容量，默認(rèn)內(nèi)置一次擴(kuò)容 2 倍。支持查詢和插入功能。

>>> import bloompy
>>> sbf = bloompy.ScalableBloomFilter(error_rate=0.001,initial_capacity=10**3)

# 默認(rèn)初次可以設(shè)置容量1000
>>> len(sbf)
0
>>> 12 in sbf
False
>>> sbf.add(12)
False
>>> 12 in sbf 
True
>>> len(sbf)
1
>>> sbf.filters
[<bloompy.BloomFilter object at 0x000000000B6F5860>]
>>> sbf.capacity
1000

#當(dāng)過(guò)濾器的元素個(gè)數(shù)達(dá)到容量極限時(shí)，過(guò)濾器會(huì)自動(dòng)增加內(nèi)置的標(biāo)準(zhǔn)過(guò)濾器，
#每次增加2倍容量，自動(dòng)實(shí)現(xiàn)擴(kuò)容
>>> for i in range(1000):
        sbf.add(i)
>>> 600 in sbf
True
>>> len(sbf)
2
>>> sbf.filters
[<bloompy.BloomFilter object at 0x000000000B6F5860>, <bloompy.BloomFilter object at 0x000000000B32F748>]
>>> sbf.capacity
3000

# 從文件中恢復(fù)過(guò)濾器
>>> recovered_sbf = bloompy.ScalableBloomFilter.fromfile('filename.suffix')

4、計(jì)數(shù)擴(kuò)容布隆過(guò)濾器。

它是標(biāo)準(zhǔn)擴(kuò)容布隆過(guò)濾器的子類，但支持刪除元素的操作。

>>> import bloompy
>>> scbf = bloompy.SCBloomFilter(error_rate=0.001,initial_capacity=10**3)

>>> scbf.add(1)
False
>>> 1 in scbf
True
>>> scbf.delete(1)
True
>>> 1 in scbf
False
>>> len(scbf)
1
>>> scbf.filters
[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>]

# 插入元素使其達(dá)到過(guò)濾器當(dāng)前容量極限值
>>> for i in range(1100):
        scbf.add(i)
>>> len(scbf)
2
>>> scbf.filters
[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>, <bloompy.CountingBloomFilter object at 0x000000000B6F5898>]

# 從文件中恢復(fù)過(guò)濾器
>>> recovered_scbf = bloompy.SCBloomFilter.fromfile('filename.suffix')

Redis 中使用布隆過(guò)濾器

你可以手動(dòng)為 Redis 安裝 RedisBloom 插件，也可以直接使用官方^[3]提供的 docker 版本：

docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

然后在 Redis 中就可以這樣使用：

127.0.0.1:6379> BF.ADD newFilter foo
(integer) 1
127.0.0.1:6379> BF.EXISTS newFilter foo
(integer) 1
127.0.0.1:6379> BF.EXISTS newFilter notpresent
(integer) 0
127.0.0.1:6379> BF.MADD myFilter foo bar baz
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> BF.MEXISTS myFilter foo nonexist bar
1) (integer) 1
2) (integer) 0
3) (integer) 1

其實(shí) Redis 中使用布隆過(guò)濾器還有一個(gè)很大的用處，就是處理緩存穿透。Redis 大部分情況都是通過(guò) Key 查詢對(duì)應(yīng)的值，假如發(fā)送的請(qǐng)求傳進(jìn)來(lái)的 key 是不存在 Redis 中的，那么就查不到緩存，查不到緩存就會(huì)去數(shù)據(jù)庫(kù)查詢。假如有大量這樣的請(qǐng)求，這些請(qǐng)求像“穿透”了緩存一樣直接打在數(shù)據(jù)庫(kù)上，這種現(xiàn)象就叫做緩存穿透。

解決方案：

1、把無(wú)效的 Key 存進(jìn) Redis中。如果 Redis 查不到數(shù)據(jù)，數(shù)據(jù)庫(kù)也查不到，我們把這個(gè) Key 值保存進(jìn)Redis，設(shè)置 value="null"，當(dāng)下次再通過(guò)這個(gè) Key 查詢時(shí)就不需要再查詢數(shù)據(jù)庫(kù)。這種處理方式肯定是有問(wèn)題的，假如傳進(jìn)來(lái)的這個(gè)不存在的 Key 值每次都是隨機(jī)的，那存進(jìn) Redis 也沒(méi)有意義。

2、使用布隆過(guò)濾器。布隆過(guò)濾器的作用是某個(gè) key 不存在，那么就一定不存在，它說(shuō)某個(gè) key 存在，那么很大可能是存在(存在一定的誤判率)。于是我們可以在緩存之前再加一層布隆過(guò)濾器，在查詢的時(shí)候先去布隆過(guò)濾器查詢 key 是否存在，如果不存在就直接返回。

最后的話

布隆過(guò)濾器的數(shù)學(xué)原理在于兩個(gè)完全隨機(jī)的數(shù)字相沖突的概率很小，因此可以在很小的誤判率條件下用很少的空間存儲(chǔ)大量的信息，解決誤判的常見(jiàn)辦法，就是在建立一個(gè)小的白名單，存儲(chǔ)那些可能被誤判的信息。

本文帶你了解了位圖的實(shí)現(xiàn)，布隆過(guò)濾器的原理及 Python 中的使用，以及布隆過(guò)濾器如何應(yīng)對(duì) Redis 中的緩存穿透，相信你對(duì)布隆過(guò)濾器已經(jīng)有了一定的認(rèn)識(shí)。

如果你已經(jīng)看到了這里，說(shuō)明你是一個(gè)真正愛(ài)學(xué)習(xí)且有耐心的人，如果還沒(méi)關(guān)注的話，可以順手關(guān)注下，這里每周工作日分享 Python 技術(shù)，周六周日會(huì)瞎扯淡，如果已經(jīng)關(guān)注，可以加我微信「somenzz」，備注「入群」來(lái)加入學(xué)習(xí)交流群，一個(gè)人走的更快，一群人走的更遠(yuǎn)。

留言討論

推薦閱讀：

一文搞懂 RSA 算法

一文搞懂決策樹

參考資料