【資料結構】布隆過濾器 BoomFilter 的應用場景

文章目錄

• • 前言
  • 1. 時間、空間複雜度
  • 2. BoomFilter 的取舍
  • 3. BoomFilter 能做什麼
  • 4. BoomFilter 不能做什麼
  • • 4.1 優化 BoomFilter
  • 5. BoomFilter 的誤判及指導意義
  • 6. BoomFilter 的應用場景
  • • 6.1 業務系統應用
    • 6.2 性能優化的應用
  • 後記

前言

對比資料結構的差別，從其空間、時間複雜度下手觀察。BoomFilter 特殊的地方在于它在元素存儲上做了努力。本文歸納下 BoomFilter 與 HashTable 的差別，進而引出 BoomFilter 善于支援的應用場景。

1. 時間、空間複雜度

BoomFilter 與 HashTable 都用了hash函數對存儲元素進行散列存儲，查找的時候都是 O(1) 的時間複雜度。二進制數組存儲散列值，兩者都是 O(n) 的複雜度

2. BoomFilter 的取舍

BoomFilter 不會存儲 元素，比如 “劉德華” 加入 BoomFilter 後會映射成為散列值。想用散列值還原 “劉德華” 則無法實作。這種取舍的效果：

• 能讓 BoomFilter 有比 HashTable 更少的元素存儲空間 （HashTable 會把 “劉德華” 存進資料結構）
• 失去了根據 key 查找 value 的能力，僅僅保留了 contains 的能力。

3. BoomFilter 能做什麼

上文講到， BoomFilter 保留了 contains 的能力，其實是不準确的。

BoomFilter contains 能力簡述：

• BoomFilter.contains(“劉德華”) == true

  => “劉德華” 可能在 元素集合中

• BoomFilter.contains(“劉德華”) == false

  => “劉德華” 一定不在 元素集合中

具體原因可以看 [布隆過濾器BloomFilter] 舉例說明+證明推導

綜上，BoomFilter 能夠斷定元素不存在集合中，僅能推測元素可能在集合中（存在誤差但是不大）。

4. BoomFilter 不能做什麼

除了失去根據 key 查找 value 的能力，BoomFilter 天然不支援删除功能。其原因是 BoomFilter 不處理哈希沖突。舉一個例子

未映射元素的 BoomFilter 
[0, 0, 0, 0, 0]
           

• 加入劉德華

[0, 0, 0, 0, 0]
⬇
劉德華
⬇
hash映射為: [0, 1, 0, 0, 1]
⬇
加入 BoomFilter
⬇
[0, 1, 0, 0, 1]
           

• 加入張學友

[0, 1, 0, 0, 1]
⬇
張學友 (增量加入)
⬇
hash映射為: [0, 1, 0, 1, 0]
⬇
加入 BoomFilter (發生了hash沖突，但是第二位的 "1" 不做處理)
⬇
[0, 1, 0, 1, 1]
           

• 删除張學友

[0, 1, 0, 0, 1]
⬇
張學友 (删除）
⬇
hash映射為: [0, 1, 0, 1, 0]
⬇
踢出 BoomFilter 
⬇
[0, 0, 0, 1, 0]
           

删除張學友的同時，破壞了劉德華的元素映射，是以 BoomFilter 原生不支援删除操作

4.1 優化 BoomFilter

上文說到 BoomFilter 原生不支援删除操作，是因為 BoomFilter 不處理hash沖突。如果為二進制數組中的每個 “1” 維護一個計數器，就能辨別hash沖突了。在删除元素的時候就不會把 “劉德華” 的 “1” 直接删除，而是讓計數器 -1。通過一個簡單的計數器，BoomFilter 又能支撐删除操作了。

5. BoomFilter 的誤判及指導意義

[布隆過濾器BloomFilter] 舉例說明+證明推導

這篇文章把誤判率給推導出來了。我們可以得到一個結論：當哈希函數個數不變時，BoomFilter 中二進制“1” 的密度越大，誤判率越高。為了減少誤判率：

• 提前訓練 BoomFilter

  如果是白名單政策，可以把系統所有白名單都加入到 BoomFilter 中，在上線後盡量不維護元素。上線前根據 BoomFilter 的訓練情況進行調參，使得 “1” 的密度減少。

• BoomFilter.contains(“劉德華”) == true 依舊要做兜底政策

  隻要存在誤判的可能，通過BoomFilter校驗的元素依舊可能不是白名單，要做權限控制或者服務降級的可能。

6. BoomFilter 的應用場景

6.1 業務系統應用

防止緩存穿透。作為熱點資料（MySQL）的一個緩存層，如果查詢的key不存在資料庫，則不需要再通路資料庫，緩解資料庫的壓力。

6.2 性能優化的應用

BoomFilter.contains("劉德華") == false

的結論特别好用。在IO操作時，提前判斷有沒有必要操作。在表連結時提前判斷有沒有必要連結都是很有用的。當然，訓練BoomFilter的開銷更節約成本時，優化才有意義。

後記

這次博文是看了 《Streaming System》後有的靈感。BoomFilter 處在大資料領域和Web開發領域的交集處。這個書把 BoomFilter 介紹的恰到好處。看這本書也算是了解了下大資料，對大資料領域又充滿了敬畏。未來如果有大資料的工作任務，再回來啃這本書。