Bloom Filter 介紹

簡介

根據維基百科所說，Bloom filter 在 1970 年提出，為了解決傳統 Hash table 需要太大記憶的問題。

Bloom filter 的特性是他的操作都跟 set 數量大小無關，像是為了達到 1% 的誤判率，你永遠只需要為「每一個元素」準備大約 9.6 個 bits，查詢跟插入也都是常數 $ O(k) $ 時間 (k is number of hash functions)。

但隨者元素添加越多，誤判律會越高，當所有 bit 都設定成 1，就會失效。

Bloom Filter 可以應用在不同領域，像是讀取硬碟（資料有沒有在記憶體）、網路黑白名單、防止快取穿透（這是在 Redis 或 Memcached 架構中常見的防禦機制），推薦系統（過濾使用者已經看過得內容）。

實做議題

基礎運作可以參考 [QUERY] IndexType： Bloom - BloomFilter 文章，下面談談實做的時候會討論的議題。

參數

這邊介紹公式，直接拿來用就好。

誤判率 p (也就是有可能你判斷他是 1，他在集合裡面，但有 p 的機率它不在 - false positive rate)。

公式： 假設我們現在 BF 有 m 個 bit，已經塞入 n 個不同資料，誤判律等於 $p \approx \left( 1 - e^{-\frac{kn}{m}} \right)^k$

p 的圖是一個 Convex Function，可以參考此篇文章裡面的圖 - [QUERY] IndexType： Bloom - BloomFilter

而我們要決定現在 k 參數，我們要先定義現在預計有 n 個元素加入，並且可以容忍的錯誤率是 p，可以用公式先得出 bloom filter 大小 m

$$m = - \frac{n \ln p}{(\ln 2)^2}$$

之後根據 m, n 得出 k 個 hash function

$$k = \frac{m}{n} \ln 2 \approx 0.693 \times \frac{m}{n}$$

k 之後會向上取整數。

根據這個最佳公式得出來的 BF，在我們剛好插入元素 n 時，就剛好跟我們想要的 p 一樣剛好 (可能會受到 k 向上向下取整的差別)。

Hash Function

BF 好像說一定要完全不一樣的 hash function，其實不用，我們不需要真的去找 MD5, SHA1, CRC32 等等 k 個完全不同的演算法（這樣計算太慢了）。業界標準做法是使用 Double Hashing 來模擬 k 個雜湊函數。你只需要兩個基礎雜湊函數，就可以模擬多個 hash function。

這已被數學證明與真正隨機的 k 個雜湊函數效果幾乎一樣好。

C 語言實做

直接參考 Github 專案 bloom 解釋一下實做細節。

使用它跟我們上面多的一樣，用 bloom_filter_init 把預計要存多少東西 (n) 和 p 傳進去。

int bloom_filter_init_alt(BloomFilter *bf, uint64_t estimated_elements, float false_positive_rate, BloomHashFunction hash_function) {
    if(estimated_elements == 0 || estimated_elements > UINT64_MAX || false_positive_rate <= 0.0 || false_positive_rate >= 1.0) {
        return BLOOM_FAILURE;
    }
    bf->estimated_elements = estimated_elements;
    bf->false_positive_probability = false_positive_rate;
    __calculate_optimal_hashes(bf);
    bf->bloom = (unsigned char*)calloc(bf->bloom_length + 1, sizeof(char)); // pad to ensure no running off the end
    bf->elements_added = 0;
    bloom_filter_set_hash_function(bf, hash_function);
    bf->__is_on_disk = 0; // not on disk
    return BLOOM_SUCCESS;
}

如上，實做真的用一個很大的 array，它使用 calloc 宣告一個大的 char array。

2004 Sliceed Bloom Filter

雖然預設作法是真的宣告一個很大的 array，但有些人嘗試把陣列分割 2d array，這可以提昇硬體效率。

雖然將位元陣列切開的想法可能在早期的硬體實作中就有人嘗試過，但 Peter C. Dillinger 和 Panagiotis Manolios 在 2004 年 的論文 《Bloom Filters in Probabilistic Verification》 中，對這種「分區（Partitioned）」的結構進行了詳細的數學分析。

他們的發現：他們證明了雖然將陣列切分會導致誤判率（False Positive Rate）些微上升，但這個副作用非常小（通常可以忽略不計），換來的好處是能大幅提升運算速度與平行度。

這篇論文讓軟體工程界開始接受「切分（Slicing/Partitioning）」是一個合理的優化手段，而不僅僅是硬體工程師的「怪招」。

Sliced 優勢：主要是為了平行運算、硬體流水線優化以及記憶體存取效率。

特性

這邊來談談 Bloom filter 特性以及為了解決這些特性限制，延伸的其他資料結構：

• 只能添加元素，不能刪減，解法：

  • Counting Bloom Filter (1998): 每個 bit 使用 counter 紀錄，但會導致空間變很大
  • Cuckoo Filter (2014): 更少的空間，但支援刪除

• 大小固定，解法：

  • 使用 Scalable Bloom Filter (2007): 出現在大數據萌芽期面對資料量未知的場景（如分散式系統），解決傳統 BF 容量固定、滿了就要重建的痛點

• Bloom filter 像是隨機存取，無法利用 CPU cache，不利於記憶體以外的外部儲存裝置 – 布隆過濾器 Bloom Filter

  

  解法：
  • Quotient Filter (2012): 隨著 SSD 普及，人們發現 Bloom Filter 的隨機讀取（Random Access）在 Flash 上效率太差，因此發明了這種對「局部性（Locality）」友善的結構

• 其他場景：例如在 LSM-Tree 資料庫結構中，硬碟上的檔案（SSTables）一旦寫入就不會再修改（Immutable）。這給了我們使用「更緊湊」過濾器的機會。所以在 2021 提出 Ribbon Filter (比 Bloom Filter 省 30% 空間)

  類似的像是 Xor Filter 在 2020 也是類似場景。

• Bit-Sliced Signatures and Bloom Filters: 利用 CPU 的 SIMD 指令（單指令流多數據流）來暴力加速過濾，而不是依賴隨機存取，好文

Reference

• 布隆過濾器 Bloom Filter
• Bloom filters vs Cuckoo filters vs Ribbon filters
• Bloom Filter布隆过滤器