跳轉到

6.3 Bloom Filter 與空間節省技巧#

概念說明#

Bloom Filter（1970）是「有假陽性、無假陰性」的成員測試結構：它可能說「在」（其實不在），但絕不會說「不在」（其實在）。結構是 m 個位元的位元陣列 + k 個雜湊函數：

  • 插入 x：對 k 個雜湊值 h₁(x)…h_k(x) 的位置都設 1。
  • 查詢 x：k 個位置全為 1 → 「可能在」；任一為 0 → 「一定不在」。

磁碟上的殺手級應用：LSM 樹的每個 SSTable 附一個 Bloom Filter（常駐記憶體）。查詢一個鍵時，先問各層的 Bloom Filter——「一定不在」的 SSTable 完全不必讀磁碟。以 1% 假陽性率，每鍵只需約 9.6 bits，一百萬鍵的索引約 1.2MB 記憶體，卻能省下數百萬次無謂的磁碟讀取。

誤判率公式：p ≈ (1 − e^{−kn/m})^k，最佳 k = (m/n) ln 2。位元/鍵為 10 時 p ≈ 0.8%，為 15 時 p ≈ 0.03%。

同族的空間節省技巧：

  • 計數型 Bloom Filter（CBF）：每槽存 4-bit 計數器，支援刪除。
  • Cuckoo Filter：支援刪除且空間更省，誤判 3% 時約每鍵 4~6 bits。
  • 壓縮稀疏列（CSR）/ 差分編碼：SSTable 的索引鍵有序，存「前綴差值」可壓縮 5~10 倍。

Python 範例#

import math
import hashlib   # 避免外部依賴，改用內建雜湊

def h_i(key, i, m):
    return int(hashlib.md5(f"{i}:{key}".encode()).hexdigest(), 16) % m

class BloomFilter:
    def __init__(self, n, p=0.01):
        m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
        k = max(1, round((m / n) * math.log(2)))
        self.m, self.k = m, k
        self.bits = [0] * m

    def add(self, key):
        for i in range(self.k):
            self.bits[h_i(key, i, self.m)] = 1

    def may_contain(self, key):
        return all(self.bits[h_i(key, i, self.m)] for i in range(self.k))

n = 10000
bf = BloomFilter(n, p=0.01)
print(f"m={bf.m} bits（{bf.m/n:.1f} bits/鍵）, k={bf.k}")

for i in range(n):
    bf.add(f"key{i}")

false_pos = sum(bf.may_contain(f"ghost{i}") for i in range(n))
print(f"10000 個不存在的鍵 → 誤判 {false_pos} 個（{false_pos/n:.2%}）")
print("key123（存在）:", bf.may_contain("key123"))

# 應用：LSM 的 SSTable 探測，模擬省下的 I/O
class FakeSSTable:
    def __init__(self, keys):
        self.keys = set(keys)
        self.bf = BloomFilter(len(keys), p=0.01)
        for k in keys: self.bf.add(k)
        self.disk_reads = 0
    def probe(self, k):
        if not self.bf.may_contain(k):
            return None                    # 免讀磁碟
        self.disk_reads += 1
        return k in self.keys

tables = [FakeSSTable([f"key{i}" for i in range(lo, lo+1000)])
          for lo in range(0, 10000, 1000)]
misses = 0
for i in range(10000, 20000):              # 全部不存在的查詢
    for t in tables:
        if t.probe(f"key{i}"): misses += 1
reads = sum(t.disk_reads for t in tables)
print(f"10000 次不存在查詢 → 實際磁碟探測 {reads} 次（省下 {10000-reads} 次）")

複雜度與 I/O 成本分析#

  • 插入/查詢：O(k) CPU，0 次磁碟 I/O（位元陣列常駐記憶體）。
  • 空間：O(n log(1/p)) bits；1% 誤判約 9.6 bits/鍵。
  • LSM 讀取放大：無 Bloom 時每查詢需讀各層的索引頁（數次 I/O）；有 Bloom 後，不存在鍵的查詢幾乎 0 I/O——寫多讀少且常有「查無此鍵」的負載（如 UUID 主鍵）受益最大。
  • 注意：Bloom Filter 不能刪除（會誤傷其他鍵）；需要刪除用 CBF 或 Cuckoo Filter。

練習#

  1. 用 p=0.05 與 p=0.001 分別建 10000 鍵的 filter，比較 bits/鍵與實測誤判率。
  2. 把範例的 SSTable 探測接入 6.2 節的 LSM 樹，重新測量讀取 I/O。
  3. 說明為何 Bloom Filter 的「假陽性」在 LSM 場景是安全的，而「假陰性」是致命的。