淺析python實現(xiàn)布隆過濾器及Redis中的緩存穿透原理

更新時間：2021年09月14日 11:07:40 作者：somenzz

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

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

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

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

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

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

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

在講布隆過濾器前，要先講一下另一種存儲結(jié)構(gòu)，位圖（BitMap）。因為，布隆過濾器本身就是基于位圖的，是對位圖的一種改進。

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

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

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

這個用語言很難表達，還是給出代碼吧，一碼勝千言啊。

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

public class BitMap { // Java中char類型占16bit，也即是2個字節(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 的實現(xiàn)：

class BitMap(object):
    def __init__(self, max_value):
        """
        使用多個整型元素來儲存數(shù)據(jù)，每個元素4個字節(jié)（32位）
        """
        self._size = int((max_value + 31 - 1) / 31)  # 計算需要的字節(jié)數(shù)，字節(jié)數(shù)也是數(shù)組的大小
        self.array = [0 for i in range(self._size)]  # 數(shù)組的元素都初始化為0，每個元素有32位
    @staticmethod
    def get_element_index(num):
        """
        獲取該數(shù)即將儲存的字節(jié)在數(shù)組中下標
        """
        return num // 31 
    @staticmethod
    def get_bit_index(num):
        """
        獲取該數(shù)在元素中的位下標
        """
        return num % 31
 
    def set(self, num):
        """
        將該數(shù)存在對應(yīng)的元素的對應(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

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

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

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

布隆過濾器的原理

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

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

因為我們使用 1 位代表一個元素，因此 100 個二進制位，最多代表 100 個元素，但是假如使用 2 位來代表一個元素呢？那就是組合 C(100,2) = 100*99/2 = 4950 個數(shù)，是不是可以代表更多？當然了，你還可以使用 3 位代表一個元素，這樣可以代表 161700 個數(shù)。

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

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

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

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

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

在 Python 中使用布隆過濾器

pypi 搜了了 Python 中的布隆過濾器，有 3 個：

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

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

bloompy 提供了四種布隆過濾器：

1、標準布隆過濾器。

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

>>> import bloompy
>>> bf = bloompy.BloomFilter(error_rate=0.001,element_num=10**3)
# 查詢元素是否在過濾器里返回狀態(tài)標識
# 如果不在里面則插入，返回False表示元素不在過濾器里
>>> 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
# 將過濾器存儲在一個文件里
>>> bf.tofile('filename.suffix') 
# 從一個文件里恢復(fù)過濾器。自動識別過濾器的種類。
>>> recovered_bf = bloompy.get_filter_fromfile('filename.suffix') 
# 或者使用過濾器類的類方法 'fromfile' 來進行過濾器的復(fù)原。對應(yīng)的類只能恢復(fù)對應(yīng)的過濾器
>>> recovered_bf = bloompy.BloomFilter.fromfile('filename.suffix') 
# 返回已經(jīng)插入的元素個數(shù)
>>> bf.count
2 
# 過濾器的容量
>>> bf.capacity
1000
# 過濾器的位向量
>>> bf.bit_array
bitarray('00....')
# 過濾器位數(shù)組長度
>>> bf.bit_num
14400
# 過濾器的哈希種子，默認是素數(shù)，可修改
>>> bf.seeds
[2, 3, 5, 7, 11,...]
# 過濾器哈希函數(shù)個數(shù)
>>> bf.hash_num
10

2、計數(shù)布隆過濾器。

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

>>> import  bloompy
>>> cbf  = bloompy.CountingBloomFilter(error_rate=0.001,element_num=10**3)
# 與標準布隆過濾器一樣
>>> cbf.add(12)
False
>>> cbf.add(12)
True
>>> 12 in cbf
True
>>> cbf.count
1 
# 查詢元素狀態(tài)返回標識，如果元素存在過濾器里則刪除
>>> cbf.delete(12)
True
>>> cbf.delete(12)
False
>>> 12 in cbf
False
>>> cbf.count
0
# 從文件中恢復(fù)過濾器
>>> recovered_cbf = bloompy.CountingBloomFilter.fromfile('filename.suffix')

3、標準擴容布隆過濾器。

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

>>> import bloompy
>>> sbf = bloompy.ScalableBloomFilter(error_rate=0.001,initial_capacity=10**3)
# 默認初次可以設(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
#當過濾器的元素個數(shù)達到容量極限時，過濾器會自動增加內(nèi)置的標準過濾器，
#每次增加2倍容量，自動實現(xiàn)擴容
>>> 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ù)過濾器
>>> recovered_sbf = bloompy.ScalableBloomFilter.fromfile('filename.suffix')

4、計數(shù)擴容布隆過濾器。

它是標準擴容布隆過濾器的子類，但支持刪除元素的操作。

>>> 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>]
# 插入元素使其達到過濾器當前容量極限值
>>> for i in range(1100):
        scbf.add(i)
>>> len(scbf)
2
>>> scbf.filters
[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>, <bloompy.CountingBloomFilter object at 0x000000000B6F5898>]
# 從文件中恢復(fù)過濾器
>>> recovered_scbf = bloompy.SCBloomFilter.fromfile('filename.suffix')

Redis 中使用布隆過濾器

你可以手動為 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

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

解決方案：

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

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