布隆過濾器 - 實現和特徵

基本概念

布隆過濾器（英語：Bloom Filter）是 1970 年由布隆提出，是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。-- 維基百科

查找問題建模

如何判斷某個元素是否存在於一個集合中？

比較直觀的做法是將所有元素保存起來，然後逐個比較確認結果，建模轉換爲具體的數據結構：

常見的數據結構隨着元素的增加，存儲空間也會越來越大，同時查詢速度也會越來越慢 (散列表結構不受影響)，如果我們希望在保持時間複雜度爲 O(N) 的前提下， 儘可能地降低內存佔用，就需要轉換一下思路：保存特徵數據，而非所有數據。什麼是特徵數據？簡單來說，就是能夠唯一標識出其對應的源數據， 比如常見的 用戶 ID、遊戲中獎 ID、管理後臺審批流 ID 等。

原理和應用場景

布隆過濾器的原理: 當一個元素被加入集合時，通過 K 個哈希函數 將元素映射到一個位圖數據結構 (例如 bitmap) 中的 K 個位置上面，並將這些位置全部置爲 1。判斷元素是否存在於集合時，只需查看 K 個哈希函數 映射後的 K 個位置上面的值即可。

如果這些位置任意一個爲 0，則表示被檢測元素一定不存在於集合中，如果都是 1，則表示被檢測元素有較大可能存在於集合中。

爲什麼不能檢測 “一定存在” ?

檢測元素時可以返回 “一定不存在” 和 “可能存在”，因爲可能有多個元素映射到相同的 bit 上面，導致該位置爲 1, 那麼一個不存在的元素也可能會被誤判爲存在， 所以無法提供 “一定存在” 的語義保證。

爲什麼元素不允許被 “刪除” ?

如果刪除了某個元素，導致對應的 bit 位置爲 0, 但是可能有多個元素映射到相同的 bit 上面，那麼一個存在的元素會被誤判爲不存在 (這是不可接收的)， 所以爲了 “一定不存在” 的語義保證，元素不允許被刪除。

PS: 雖然可以引入一個 刪除計數器 來解決上述問題，不過這需要引入額外的空間，失去了使用過濾器的意義。

兩個語義操作

示例

URL 去重

假設下面的 URL 列表爲採集隊列 (一共 100 條數據)，我們希望採集完成的 URL 可以記錄起來，避免多次採集，如果使用正常的字符串存儲的話 (以 Go 語言爲例，string 佔用 16 bytes)， 大概需要 16 bytes * 100 = 1600 bytes 內存空間。

https://www.example.com/u/101/profile
https://www.example.com/u/102/profile

...

https://www.example.com/u/200/profile

而如果我們改爲 布隆過濾器 的方式來記錄的話，假設哈希函數可以將每個鏈接轉換爲 1 個 0-255 的數字，通過將數據存入一個 bitmap, 那麼理想情況下 (不發生任何碰撞) 最終只需要 1 個 byte 的內存空間即可，內存使用直接降低了 1600 倍。

# 布隆過濾器記錄 URL 只需要 1 個 byte

------------------------------------
| 0   | 1   | 2   | 3  | ... | 255 |
------------------------------------
| URL | URL | URL |    |     | URL |
------------------------------------

網站用戶性別

假設網站的用戶數量爲 1000 萬，每個用戶性別存儲需要 1 個 bytes, 如果正常存儲的話，大概需要 1 byte * 1000 W ≈ 10 MB 內存空間。

而如果我們改爲 布隆過濾器 的方式來記錄的話，假設用戶 ID 是一個數字，通過將數據存入一個 bitmap, 那麼 1 byte 可以表示 256 個 用戶性別， 理想情況下 (不發生任何碰撞) 最終只需要 1000 W / 256 * 1 byte ≈ 0.04 MB 內存空間，內存使用直接降低了 256 倍。

# 布隆過濾器記錄用戶網站性別

--------------------------------------------------
| 0     | 1     | 2     | 3     | ...  | 9999999 |
--------------------------------------------------
| User1 | User2 | User3 | User4 | ...  | User... |
--------------------------------------------------

其他應用場景

兩個核心支撐點

通過上面兩個簡單的應用場景可以看到，要實現一個健壯的 布隆過濾器，需要規劃設計好兩個技術點：

Murmur3，FNV 系列和 Jenkins 等非密碼學算法適合作爲哈希函數，其中 Murmur3 因爲易於實現，並且在速度和隨機分佈上有很好的權衡， 實踐中多選用其作爲 布隆過濾器 的哈希函數。

數學部分

一個 布隆過濾器 至少需要包含如下參數:

哈希函數個數滿足以下公式時，布隆過濾器 有最好的效果 (數學證明部分省略，數學渣暴露了 :( ...)

k = [(ln2)(m/n)]

還是以剛纔的 網站用戶性別 爲例，1000W 用戶需要以不高於 0.00001% 誤判率的的情況下被檢測到，需要多少個哈希函數？需要耗費多少空間？

# 帶入公式計算

n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))))
k = round((m / n) * log(2))

記不住數學公式？沒關係，已經有大佬做好了一個 在線工具 [1]，可以通過輸入參數直接生成對應的哈希函數個數。

開源庫

筆者選擇了 bits-and-blooms/bloom[2] 作爲研究 布隆過濾器 代碼實現，版本爲 v3.3.1。

安裝組件

$ go get -u github.com/bits-and-blooms/bloom/v3

示例

初始化過濾器時，需要知道對應的業務場景有多少元素（期望的容量），以及期望的誤判概率。常見的誤判率爲 1%, 誤報率越低，需要的內存就越多， 同時容量越大，需要的內存就越多。

初始化過濾器時，應該儘可能明確需要的元素數量，因爲 布隆過濾器 不是動態數據結構，如果指定的元素數量太少，則可能會超出誤判概率範圍。

package main

import "github.com/bits-and-blooms/bloom"

func main() {
 // 初始化能夠接收 100 萬個元素且誤判率爲 1% 的布隆過濾器
 filter := bloom.NewWithEstimates(1000000, 0.01)

 hw := []byte(`hello world`)
 hg := []byte(`hello golang`)

 filter.Add(hw)

 println(filter.Test(hw)) // true
 println(filter.Test(hg)) // false
}

我們只添加了 hello world 字符串到過濾器中，所以正常的輸出應該是 true false:

$ go run main.go

true
false

源碼分析

接下來，我們來簡單分析下 bits-and-blooms/bloom 的實現代碼。

哈希算法選擇

module github.com/bits-and-blooms/bloom/v3

go 1.14

require (
 github.com/bits-and-blooms/bitset v1.3.1
 github.com/twmb/murmur3 v1.1.6
)

從 bits-and-blooms/bloom 的依賴包中，可以看到其選擇了 murmur3 算法作爲哈希函數實現。

BloomFilter

BloomFilter 結構體表示一個 布隆過濾器，包含 3 個字段，分別對應上文提到的 布隆過濾器 的必要參數。

type BloomFilter struct {
 m uint              // 哈希空間大小
 k uint              // 哈希函數個數
 b *bitset.BitSet    // bitmap
}

初始化過濾器

NewWithEstimates 方法創建一個 布隆過濾器，內部調用了 EstimateParameters 方法來計算 m 和 k 的值， 最後通過 m 和 k 初始化一個 BloomFilter 結構體並返回。

func NewWithEstimates(n uint, fp float64) *BloomFilter {
 m, k := EstimateParameters(n, fp)
 return New(m, k)
}

func EstimateParameters(n uint, p float64) (m uint, k uint) {
    m = uint(math.Ceil(-1 * float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))
    k = uint(math.Ceil(math.Log(2) * float64(m) / float64(n)))
    return
}

添加元素

BloomFilter.Add 方法添加一個元素到 布隆過濾器，返回當前的 BloomFilter 對象來支持鏈式調用。

func (f *BloomFilter) Add(data []byte) *BloomFilter {
 h := baseHashes(data)
 for i := uint(0); i < f.k; i++ {
  f.b.Set(f.location(h, i))
 }
 return f
}

baseHashes 函數返回哈希函數計算出的哈希值，其內部調用了 murmur3 算法。

func baseHashes(data []byte) [4]uint64 {
    ...
}

location 函數返回哈希值對應的 bitmap 的位置索引，通過將 bitmap 對應的位置進行設置，就可以將元素添加到 布隆過濾器 了。

func location(h [4]uint64, i uint) uint64 {
 ...
}

檢測元素

BloomFilter.Test 方法檢測一個元素是否存在於 布隆過濾器 中，可以看到，其內部實現就是 BloomFilter.Add 方法的逆過程。

func (f *BloomFilter) Test(data []byte) bool {
 h := baseHashes(data)
 for i := uint(0); i < f.k; i++ {
  if !f.b.Test(f.location(h, i)) {
   return false
  }
 }
 return true
}

調用流程圖

小結

本文簡述了 布隆過濾器 的基本概念和原理，並通過開源庫 bits-and-blooms/bloom 的實現代碼分析了實現 布隆過濾器 的核心技術點， 最後引用維基百科關於 布隆過濾器 的優缺點作爲文章結尾。

優點

布隆過濾器 在算法的空間複雜度和時間複雜度方面都有巨大的優勢，Add 和 Test 操作的時間複雜度都是常數 O(K) (K: 哈希函數個數)。由於哈希函數相互之間沒有關聯，因此可以通過硬件並行實現計算加速，此外，由於 布隆過濾器 不存儲源數據，在某些對數據保密要求非常嚴格的場景 (數據可用，但不可見) 有明顯優勢。最後，在哈希空間向量長度相同的情況下，使用同一組哈希函數的兩個 布隆過濾器 的 集合相關運算可以使用位操作進行。

缺點

布隆過濾器 最明顯的的缺點就是 誤判率，隨着元素數量增加，誤判率 也隨之增加，所以如果元素數量很少的情況下，使用 map 就可以了。此外，布隆過濾器 不支持刪除元素， 因爲 布隆過濾器 只能確定元素一定不存在於集合中，無法確定元素一定存在於集合中，如果一定要刪除某個元素， 則必須重新構建整個 布隆過濾器。

Reference

鏈接

[1]

在線工具: https://hur.st/bloomfilter/

[2]

bits-and-blooms/bloom: https://github.com/bits-and-blooms/bloom

[3]

布隆過濾器 - 維基百科: https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8

[4]

bits-and-blooms/bloom: https://github.com/bits-and-blooms/bloom

[5]

Bloom Filters: https://www.jasondavies.com/bloomfilter/

[6]

Bloom and Cuckoo Filters - Awesome Go: https://awesome-go.com/bloom-and-cuckoo-filters/

[7]

redis bitmap: https://redis.io/commands/?group=bitmap

[8]

CUCKOO FILTER：設計與實現: https://coolshell.cn/articles/17225.html

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/d5-THQTldzhyeI9CF9-TuQ

猜你喜歡