Bloom filter — Probabilistic membership với 99% RAM tiết kiệm

Một Cassandra cluster lưu 100 triệu record trên mỗi node, phân tán qua hàng trăm SSTable file trên disk. Mỗi read query phải kiểm tra N SSTable để tìm row. Mỗi lần check là một disk seek tốn khoảng 1ms — với 100 SSTable, đó là 100ms chỉ để xác định row có tồn tại hay không. Với workload read-heavy, đây là latency killer.

Giải pháp Cassandra dùng: đặt một Bloom filter trên mỗi SSTable. Filter chiếm khoảng 1 byte mỗi key — 100 triệu key chỉ cần 100MB, fit hoàn toàn trong RAM. Trước khi touch disk, query filter trước. Filter trả lời theo hai cách: "definitely not" (key này chắc chắn không ở file này — skip hoàn toàn) hoặc "maybe yes" (có thể có — kiểm tra disk). "Maybe yes" đôi khi sai (false positive) nhưng "definitely not" không bao giờ sai (không có false negative). Kết quả: 99% disk read bị loại bỏ.

Bài này giải thích cơ chế Bloom filter, công thức false positive rate, trick k hash function với chỉ 2 hash (Kirsch-Mitzenmacher), và các variant counting/scalable Bloom.

1. Analogy — Bảng tick check-in

Hình dung một bảng gồm 100 ô vuông đánh số 0–99, ban đầu tất cả trắng. Khi khách check-in, nhân viên tô đen 3 ô (k=3) được chỉ định bởi tên khách qua 3 công thức hash khác nhau. "Alice" → tô ô 7, 42, 83. "Bob" → tô ô 12, 42, 71.

Để kiểm tra "X đã đến chưa?": tính 3 ô hash của X, xem 3 ô đó. Nếu có 1 ô trắng → "chắc chắn X chưa đến" (tô ô đó thì X đã tô rồi). Nếu cả 3 đều đen → "có thể X đã đến" — nhưng cũng có thể 3 ô đó bị tô bởi khách khác (false positive: X chưa đến nhưng ô bị chiếm bởi người khác).

2. Cấu trúc và thuật toán

Bloom filter gồm hai thứ: một bit array size m (ban đầu toàn 0), và k hash function độc lập, mỗi cái map key thành một index trong khoảng [0, m).

add(x): với mỗi trong k hash function, tính index và set bit tại đó về 1.

mightContain(x): với mỗi hash function, tính index và kiểm tra bit. Nếu mọi k bit đều = 1 → trả true (maybe). Nếu bất kỳ bit nào = 0 → trả false (definitely not).

public class BloomFilter {
    private final BitSet bits;
    private final int m; // bit array size
    private final int k; // number of hash functions

    public BloomFilter(int m, int k) {
        this.m = m;
        this.k = k;
        this.bits = new BitSet(m);
    }

    public void add(byte[] key) {
        long h1 = hash1(key);
        long h2 = hash2(key);
        // Kirsch-Mitzenmacher: derive k indexes from 2 hashes.
        for (int i = 0; i < k; i++) {
            int idx = (int) Math.floorMod(h1 + (long) i * h2, m);
            bits.set(idx);
        }
    }

    public boolean mightContain(byte[] key) {
        long h1 = hash1(key);
        long h2 = hash2(key);
        for (int i = 0; i < k; i++) {
            int idx = (int) Math.floorMod(h1 + (long) i * h2, m);
            if (!bits.get(idx)) return false; // definitely not
        }
        return true; // maybe yes
    }

    // hash1, hash2: non-cryptographic hash (e.g. MurmurHash3 with different seeds).
    private long hash1(byte[] key) { /* ... */ return 0; }
    private long hash2(byte[] key) { /* ... */ return 0; }
}

Lý do dùng Math.floorMod thay %: Java % cho kết quả âm khi h1 + i*h2 âm (overflow). floorMod đảm bảo kết quả luôn trong [0, m).

3. Math — False positive rate

Sau khi insert n element vào filter size m với k hash function:

Probability 1 bit cụ thể vẫn = 0 sau n lần insert:

Mỗi lần insert, mỗi hash function set 1 trong m bit ngẫu nhiên. Probability bit đó không bị set bởi một hash: (m - 1) / m = 1 - 1/m. Sau k×n lần hash (n element, mỗi cái k hash), probability bit vẫn = 0:

P(bit = 0) = (1 - 1/m)^(k*n) ≈ e^(-kn/m)

(Dùng xấp xỉ (1 - 1/m)^m ≈ e^(-1) khi m lớn.)

False positive rate (cả k bit đều = 1 dù key chưa được add):

FP = (1 - e^(-kn/m))^k

Optimal k cho fixed m và n: đạo hàm theo k, giải bằng 0:

k_optimal = (m/n) × ln(2) ≈ (m/n) × 0.693

Khi dùng k tối ưu: FP rate = (1/2)^k — giảm mũ theo k.

Số liệu thực tế (tính theo công thức):

So sánh với HashSet<String>: 1 triệu String (32 bytes/entry cho object overhead + reference) ≈ 32MB. Bloom filter với 1% FP chỉ cần 1,2MB — tiết kiệm khoảng 27 lần. Đây là lý do Cassandra fit Bloom filter của mỗi SSTable vào RAM.

4. Trick 2 hash — Kirsch-Mitzenmacher

Vấn đề thực tế: cần k hash function độc lập cho k thường từ 7 đến 13. Implement và chạy 7–13 hash function riêng biệt là tốn kém.

Trick: chỉ cần 2 hash function h1 và h2, derive k function bằng:

g_i(x) = h1(x) + i × h2(x)     (i = 0, 1, ..., k-1)

Kirsch & Mitzenmacher (2008) chứng minh rằng cách này đạt asymptotically the same false positive rate như k hash function thực sự độc lập. Không có "extra cost" đáng kể về FP rate so với lý thuyết k-independent.

Triển khai trong thực tế:

• Google Guava BloomFilter dùng đúng trick này với MurmurHash3 128-bit, split thành 2 lần 64-bit làm h1 và h2.
• Cassandra BloomFilter.java dùng murmur3 64-bit với seed khác nhau.

Đây là lý do implementation thực tế đơn giản hơn nhiều so với lý thuyết "k independent hash functions".

5. Pitfall tổng hợp

Pitfall 1 — Cannot delete elements

Bit được chia sẻ giữa nhiều element — không thể xóa 1 element mà không ảnh hưởng element khác.

"Alice" set bit 7, 42, 83. "Bob" set bit 12, 42, 71. Nếu muốn "xóa Alice" bằng cách clear bit 7, 42, 83 → bit 42 bị clear → mightContain("Bob") trả false — sai!

Sửa: dùng Counting Bloom filter — mỗi slot là counter 4-bit thay vì 1 bit. add increment counter, remove decrement. Bit "set" khi counter vượt 0. Trade-off: bộ nhớ tăng 4 lần (4 bit mỗi slot thay 1 bit), và counter có thể overflow nếu một element được add quá 15 lần (với 4-bit counter).

Pitfall 2 — False positive rate tăng khi filter bão hòa

Bloom filter không có cơ chế tự resize. Khi insert nhiều hơn n element đã dự kiến, số bit được set tăng → tỷ lệ false positive tăng mạnh. Khi mọi bit trong array = 1, filter trả true cho mọi query — hoàn toàn vô dụng.

Sửa: pre-size đúng với n dự kiến ngay từ đầu. Nếu n không biết trước, dùng Scalable Bloom filter (Almeida et al. 2007) — chain nhiều filter, mỗi filter nhỏ hơn FP target chặt hơn. Khi filter hiện tại đầy, tạo filter mới và thêm vào chain. Query check tất cả filter trong chain.

Pitfall 3 — Dùng hash cryptographic cho tốc độ

SHA-256 hay SHA-1 quá chậm cho Bloom filter — một lần hash SHA-256 mất khoảng 500ns, với k=7 là 3.5µs chỉ để check membership.

Sửa: dùng non-cryptographic fast hash: MurmurHash3 (Cassandra, Guava), FarmHash (Google), hoặc xxHash (RocksDB). Các hash này không cần cryptographic properties (collision resistance, preimage resistance) — chỉ cần phân phối đều. MurmurHash3 128-bit mất khoảng 10–20ns — nhanh hơn 25–50 lần SHA-256.

6. Variants

Counting Bloom filter: mỗi slot là counter 4-bit thay vì 1 bit. Hỗ trợ remove() bằng decrement. Tốn 4× memory so với standard Bloom. Dùng khi cần delete: ví dụ CDN purge cache, blacklist IP tạm thời.

Scalable Bloom filter: chain nhiều sub-filter. Khi sub-filter đầu tiên đầy (insert vượt ngưỡng), tạo sub-filter mới với kích thước lớn hơn và FP target chặt hơn. Query check toàn bộ chain. Phù hợp khi n không biết trước — ví dụ log deduplication trong streaming pipeline.

Cuckoo filter (alternative, không phải Bloom variant): thay vì bit array, dùng bảng hash với 2 candidate slot per key. Hỗ trợ delete tự nhiên, FP rate tương đương nhưng tốt hơn cho FP target thấp hơn 3%, nhỏ hơn Bloom khoảng 20%. Được dùng trong một số hệ thống hiện đại thay Counting Bloom.

7. Ứng dụng trong hệ thống thực tế

Cassandra SSTable Bloom filter: đây là use case kinh điển và lý do Bloom filter trở nên phổ biến trong hệ thống phân tán. Cassandra dùng LSM tree — write vào MemTable (RAM), flush thành SSTable file trên disk. Read phải check MemTable + tất cả SSTable. Với hàng trăm SSTable, không có Bloom filter thì mỗi read là hàng trăm disk seek. Bloom filter trên mỗi SSTable: "key này có trong file này không?" — "definitely not" → skip hoàn toàn. Configurable FP rate per column family, thường 1–10 byte/key.

HBase, RocksDB, LevelDB: cùng pattern với Cassandra — LSM tree architecture nên đều có Bloom filter per SSTable/level. RocksDB cho phép cấu hình bits-per-key (thường 10 bit/key ≈ 1% FP). Đây là lý do LSM tree competitive về read performance dù về lý thuyết kém B+tree: Bloom filter compensate phần lớn overhead.

Chrome Safe Browsing: trình duyệt giữ local Bloom filter của hàng triệu malicious URL hash. Mỗi lần user truy cập URL, check Bloom filter trước. "Definitely not" → cho phép truy cập ngay, không cần round trip đến Google server. "Maybe yes" → query Google để xác nhận. Lợi ích kép: giảm latency cho 99% URL an toàn, và bảo vệ privacy — Google không biết tất cả URL user visit (chỉ biết URL bị flag là suspicious).

CDN cache lookup: trước khi kiểm tra cache server, một số CDN dùng Bloom filter để xác định "URL này có khả năng được cache không?". "Definitely not" → route thẳng đến origin, tránh round trip không cần thiết đến cache cluster. Đặc biệt hữu ích cho long-tail URLs chỉ được request một lần.

Spell check baseline: hệ thống spell trên Unix cổ điển dùng Bloom filter làm pre-filter "từ này có trong từ điển không?". "Definitely not" → đánh dấu sai chính tả ngay. "Maybe yes" → kiểm tra exact match. Hiện nay replaced bởi trie và automaton (nhanh hơn và hỗ trợ fuzzy match), nhưng Bloom filter vẫn có mặt trong spell check pipeline của một số mobile keyboard.

8. Deep Dive

9. Tóm tắt

• Bloom filter = bit array size m + k hash function. add: set k bit. mightContain: check k bit, tất cả = 1 → maybe, có 1 = 0 → definitely not.
• Chỉ false positive, không bao giờ false negative — đây là invariant cho phép dùng để skip disk read an toàn.
• FP rate = (1 - e^(-kn/m))^k. Optimal k = (m/n) × ln(2). Với k tối ưu, FP = (1/2)^k.
• 1% FP với 1 triệu key chỉ cần 1,2MB — tiết kiệm 27 lần so với HashSet.
• Trick Kirsch-Mitzenmacher g_i = h1 + i×h2 — chỉ cần 2 hash, derive k index, đạt cùng FP rate. Dùng trong Guava, Cassandra.
• Cannot delete — vì bit chia sẻ giữa element. Giải pháp: Counting Bloom (4-bit counter, 4× memory). Cần size đúng ngay từ đầu hoặc dùng Scalable Bloom.
• Dùng non-crypto hash — MurmurHash3, FarmHash, xxHash. SHA-256 quá chậm cho membership check.
• Ứng dụng rộng: Cassandra/HBase/RocksDB SSTable, Chrome Safe Browsing, CDN cache, spell check.

10. Tự kiểm tra

Bài tiếp theo: Mini-challenge: Trie + autocomplete top-K