Bloom Filter — Gatekeeper Xác Suất

Cassandra xử lý hàng triệu read request mỗi giây. Mỗi lần client hỏi "row này có tồn tại không?", nếu phải đọc disk để kiểm tra, latency sẽ nhảy từ microseconds lên milliseconds — và ở quy mô 1 triệu QPS, đó là sự khác biệt giữa hệ thống hoạt động bình thường và sụp đổ hoàn toàn.

Giải pháp: đặt một gatekeeper trước mỗi lần đọc disk. Gatekeeper này không cần trả lời chính xác 100% — nó chỉ cần nói "chắc chắn không có" hoặc "có thể có". Với câu trả lời đầu tiên, ta bỏ qua disk hoàn toàn. Với câu trả lời thứ hai, ta mới thực sự đọc. Cái giá? Khoảng 1% false positive — và bù lại, bộ nhớ giảm từ hàng GB xuống còn vài MB.

Đó chính là Bloom Filter — cấu trúc dữ liệu mà Cassandra, Chrome Safe Browsing, Akamai CDN, và Bitcoin SPV đều sử dụng trong production hàng ngày.

Bức tranh tư duy

Hình dung Bloom Filter như một bảng bấm lỗ tại quán phở. Mỗi khi khách mua một tô, nhân viên bấm lỗ ở vài vị trí cố định trên thẻ (tương ứng với hash functions). Khi kiểm tra khách có phải thành viên không:

• Nếu bất kỳ lỗ nào chưa bấm → chắc chắn khách chưa từng mua (false negative = 0%)
• Nếu tất cả lỗ đều đã bấm → khách có thể đã mua... hoặc các lỗ đó trùng hợp do khách khác bấm (false positive > 0%)

Thêm "phở bò":
  hash1("phở bò") → vị trí 3  ──→  [0,0,0,1,0,0,0,0,0,0,0,0]
  hash2("phở bò") → vị trí 7  ──→  [0,0,0,1,0,0,0,1,0,0,0,0]
  hash3("phở bò") → vị trí 11 ──→  [0,0,0,1,0,0,0,1,0,0,0,1]

Kiểm tra "bún chả":
  hash1("bún chả") → vị trí 3  ──→  bit[3]=1 ✓
  hash2("bún chả") → vị trí 5  ──→  bit[5]=0 ✗ → CHẮC CHẮN KHÔNG CÓ

Điểm mạnh nhất của mô hình này: phép phủ định luôn tuyệt đối. Nếu chỉ một bit bằng 0, element chắc chắn chưa từng được thêm. Phép khẳng định thì có thể nhầm — nhưng xác suất nhầm có thể tính toán và điều chỉnh chính xác.

Cốt lõi kỹ thuật

Cấu tạo Bloom Filter

Bloom Filter gồm hai thành phần:

1. Bit array có kích thước m bits, khởi tạo toàn bộ bằng 0
2. k hash functions độc lập, mỗi function map element vào một vị trí trong bit array

Insert: Hash element qua k functions, set tất cả k bit positions thành 1.

Query: Hash element qua k functions, kiểm tra tất cả k bit positions. Nếu tất cả bằng 1 → "có thể có". Nếu bất kỳ bit nào bằng 0 → "chắc chắn không có".

Toán học: Tham số tối ưu

Xác suất false positive:

$$P_{fp}={(1-e^{-kn/m})}^k$$

Trong đó: m = số bits, n = số elements đã insert, k = số hash functions.

Số hash functions tối ưu:

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

Kích thước bit array tối ưu cho target false positive rate:

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

Ví dụ thực tế: Với 10 triệu elements, target FP rate = 1%:

$$m\approx 9.6\times {10}^7\text{ bits}\approx \mathbf{\text{11.5 MB}}$$

So với HashSet cần 10 triệu × 100 bytes = 1 GB → tiết kiệm gần 100 lần.

Triển khai cơ bản

C++

#include <vector>
#include <functional>
#include <string>
#include <cmath>

class BloomFilter {
    std::vector<bool> bits_;
    int num_hashes_;
    int size_;

    size_t hash(const std::string& item, int seed) const {
        size_t h = std::hash<std::string>{}(item + std::to_string(seed));
        return h % size_;
    }

public:
    BloomFilter(int expected_items, double fp_rate = 0.01) {
        size_ = static_cast<int>(
            -(expected_items * std::log(fp_rate)) / (std::log(2) * std::log(2))
        );
        num_hashes_ = std::max(1, static_cast<int>(
            (static_cast<double>(size_) / expected_items) * std::log(2)
        ));
        bits_.assign(size_, false);
    }

    void add(const std::string& item) {
        for (int i = 0; i < num_hashes_; ++i)
            bits_[hash(item, i)] = true;
    }

    bool might_contain(const std::string& item) const {
        for (int i = 0; i < num_hashes_; ++i)
            if (!bits_[hash(item, i)]) return false;
        return true;
    }
};

Python

import math
import hashlib
from typing import Any


class BloomFilter:
    def __init__(self, expected_items: int, fp_rate: float = 0.01) -> None:
        self.size = int(-(expected_items * math.log(fp_rate)) / (math.log(2) ** 2))
        self.num_hashes = max(1, int((self.size / expected_items) * math.log(2)))
        self.bit_array = bytearray((self.size + 7) // 8)

    def _hash(self, item: Any, seed: int) -> int:
        data = f"{item}:{seed}".encode("utf-8")
        h = int(hashlib.sha256(data).hexdigest(), 16)
        return h % self.size

    def add(self, item: Any) -> None:
        for i in range(self.num_hashes):
            idx = self._hash(item, i)
            self.bit_array[idx // 8] |= 1 << (idx % 8)

    def might_contain(self, item: Any) -> bool:
        for i in range(self.num_hashes):
            idx = self._hash(item, i)
            if not (self.bit_array[idx // 8] & (1 << (idx % 8))):
                return False
        return True

    def __contains__(self, item: Any) -> bool:
        return self.might_contain(item)

Java

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.BitSet;

public class BloomFilter {
    private final BitSet bits;
    private final int size;
    private final int numHashes;

    public BloomFilter(int expectedItems, double fpRate) {
        this.size = (int) (-(expectedItems * Math.log(fpRate))
                    / (Math.log(2) * Math.log(2)));
        this.numHashes = Math.max(1,
            (int) ((double) size / expectedItems * Math.log(2)));
        this.bits = new BitSet(size);
    }

    private int hash(String item, int seed) {
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            byte[] digest = md.digest(
                (item + ":" + seed).getBytes(StandardCharsets.UTF_8));
            int h = ((digest[0] & 0xFF) << 24) | ((digest[1] & 0xFF) << 16)
                   | ((digest[2] & 0xFF) << 8)  | (digest[3] & 0xFF);
            return Math.floorMod(h, size);
        } catch (Exception e) { throw new RuntimeException(e); }
    }

    public void add(String item) {
        for (int i = 0; i < numHashes; i++) bits.set(hash(item, i));
    }

    public boolean mightContain(String item) {
        for (int i = 0; i < numHashes; i++)
            if (!bits.get(hash(item, i))) return false;
        return true;
    }
}

Go

package bloom

import (
	"crypto/sha256"
	"encoding/binary"
	"fmt"
	"math"
)

type BloomFilter struct {
	bits      []bool
	size      int
	numHashes int
}

func New(expectedItems int, fpRate float64) *BloomFilter {
	sz := int(-(float64(expectedItems) * math.Log(fpRate)) /
		(math.Log(2) * math.Log(2)))
	nh := int(math.Max(1, float64(sz)/float64(expectedItems)*math.Log(2)))
	return &BloomFilter{bits: make([]bool, sz), size: sz, numHashes: nh}
}

func (bf *BloomFilter) hash(item string, seed int) int {
	data := []byte(fmt.Sprintf("%s:%d", item, seed))
	h := sha256.Sum256(data)
	val := binary.BigEndian.Uint32(h[:4])
	return int(val) % bf.size
}

func (bf *BloomFilter) Add(item string) {
	for i := 0; i < bf.numHashes; i++ {
		bf.bits[bf.hash(item, i)] = true
	}
}

func (bf *BloomFilter) MightContain(item string) bool {
	for i := 0; i < bf.numHashes; i++ {
		if !bf.bits[bf.hash(item, i)] { return false }
	}
	return true
}

Counting Bloom Filter

Bloom Filter tiêu chuẩn không hỗ trợ xóa — vì reset bit về 0 có thể ảnh hưởng đến element khác dùng chung bit đó. Counting Bloom Filter giải quyết bằng cách thay mỗi bit bằng counter:

Python

class CountingBloomFilter:
    def __init__(self, expected_items: int, fp_rate: float = 0.01) -> None:
        import math
        self.size = int(-(expected_items * math.log(fp_rate)) / (math.log(2) ** 2))
        self.num_hashes = max(1, int((self.size / expected_items) * math.log(2)))
        self.counters = [0] * self.size

    def add(self, item: str) -> None:
        for i in range(self.num_hashes):
            self.counters[self._hash(item, i)] += 1

    def remove(self, item: str) -> None:
        for i in range(self.num_hashes):
            idx = self._hash(item, i)
            if self.counters[idx] > 0:
                self.counters[idx] -= 1

    def might_contain(self, item: str) -> bool:
        return all(
            self.counters[self._hash(item, i)] > 0
            for i in range(self.num_hashes)
        )

C++

class CountingBloomFilter {
    std::vector<uint8_t> counters_;
    int num_hashes_, size_;

    size_t hash(const std::string& item, int seed) const {
        return std::hash<std::string>{}(item + std::to_string(seed)) % size_;
    }

public:
    CountingBloomFilter(int expected, double fp = 0.01)
        : size_(int(-(expected * std::log(fp)) / (std::log(2) * std::log(2)))),
          num_hashes_(std::max(1, int(double(size_) / expected * std::log(2)))),
          counters_(size_, 0) {}

    void add(const std::string& item) {
        for (int i = 0; i < num_hashes_; ++i)
            if (counters_[hash(item, i)] < 255) ++counters_[hash(item, i)];
    }

    void remove(const std::string& item) {
        for (int i = 0; i < num_hashes_; ++i)
            if (counters_[hash(item, i)] > 0) --counters_[hash(item, i)];
    }

    bool might_contain(const std::string& item) const {
        for (int i = 0; i < num_hashes_; ++i)
            if (counters_[hash(item, i)] == 0) return false;
        return true;
    }
};

Java

public class CountingBloomFilter {
    private final int[] counters;
    private final int size;
    private final int numHashes;

    public CountingBloomFilter(int expected, double fpRate) {
        this.size = (int) (-(expected * Math.log(fpRate))
                    / (Math.log(2) * Math.log(2)));
        this.numHashes = Math.max(1,
            (int) ((double) size / expected * Math.log(2)));
        this.counters = new int[size];
    }

    public void add(String item) {
        for (int i = 0; i < numHashes; i++) counters[hash(item, i)]++;
    }

    public void remove(String item) {
        for (int i = 0; i < numHashes; i++) {
            int idx = hash(item, i);
            if (counters[idx] > 0) counters[idx]--;
        }
    }

    public boolean mightContain(String item) {
        for (int i = 0; i < numHashes; i++)
            if (counters[hash(item, i)] == 0) return false;
        return true;
    }
}

Go

type CountingBloomFilter struct {
	counters  []uint8
	size      int
	numHashes int
}

func (cbf *CountingBloomFilter) Add(item string) {
	for i := 0; i < cbf.numHashes; i++ {
		idx := cbf.hash(item, i)
		if cbf.counters[idx] < 255 { cbf.counters[idx]++ }
	}
}

func (cbf *CountingBloomFilter) Remove(item string) {
	for i := 0; i < cbf.numHashes; i++ {
		idx := cbf.hash(item, i)
		if cbf.counters[idx] > 0 { cbf.counters[idx]-- }
	}
}

func (cbf *CountingBloomFilter) MightContain(item string) bool {
	for i := 0; i < cbf.numHashes; i++ {
		if cbf.counters[cbf.hash(item, i)] == 0 { return false }
	}
	return true
}

Trade-off: Counting BF cần 4-8 bits/counter thay vì 1 bit → bộ nhớ tăng gấp nhiều lần. Chỉ dùng khi cần hỗ trợ xóa element.

Thực chiến

Tình huống: Cache Gating cho Database Layer

Bối cảnh: Hệ thống e-commerce xử lý 500K read requests/giây. 70% requests hỏi về product ID không tồn tại (bot scan, stale links). Mỗi lần miss đều trigger disk I/O trên database.

Mục tiêu: Loại bỏ 70% disk reads không cần thiết mà không cần cache toàn bộ dataset.

Python

class ProductCacheGate:
    def __init__(self, product_ids: list[str]) -> None:
        self.bloom = BloomFilter(
            expected_items=len(product_ids),
            fp_rate=0.001  # 0.1% false positive
        )
        for pid in product_ids:
            self.bloom.add(pid)
        self._stats = {"bloom_reject": 0, "db_lookup": 0}

    def get_product(self, product_id: str) -> dict | None:
        if product_id not in self.bloom:
            self._stats["bloom_reject"] += 1
            return None  # Chắc chắn không tồn tại
        self._stats["db_lookup"] += 1
        return self._db_lookup(product_id)

    def _db_lookup(self, product_id: str) -> dict | None:
        # Thực hiện database query
        ...

Java

public class ProductCacheGate {
    private final BloomFilter bloom;
    private int bloomRejects = 0;
    private int dbLookups = 0;

    public ProductCacheGate(List<String> productIds) {
        this.bloom = new BloomFilter(productIds.size(), 0.001);
        for (String id : productIds) bloom.add(id);
    }

    public Optional<Product> getProduct(String productId) {
        if (!bloom.mightContain(productId)) {
            bloomRejects++;
            return Optional.empty();
        }
        dbLookups++;
        return dbLookup(productId);
    }
}

Phân tích:

• 70% requests bị reject ngay tại Bloom Filter → không chạm database
• 0.1% false positive → cứ 1000 requests "có thể có", ~1 request là false positive
• Bộ nhớ: 10 triệu products × ~14 bits/element ≈ 17 MB

Tình huống: Email Spam URL Detection

Bối cảnh: Hệ thống email kiểm tra mỗi URL có nằm trong blacklist 50 triệu URL spam không.

Mục tiêu: Filter nhanh mà không cần truy vấn external service cho mỗi URL.

class SpamUrlDetector:
    def __init__(self, blacklist_urls: list[str]) -> None:
        self.bloom = BloomFilter(
            expected_items=len(blacklist_urls),
            fp_rate=0.0001  # 0.01% — thấp vì false positive = block nhầm email
        )
        for url in blacklist_urls:
            self.bloom.add(url)

    def scan_email_urls(self, urls: list[str]) -> list[str]:
        return [url for url in urls if url in self.bloom]

Sai lầm điển hình

❌ Sai lầm 1: Dùng cho quyết định tài chính

Vấn đề: False positive dẫn đến phê duyệt giao dịch không hợp lệ.

# SAI: False positive có thể duyệt giao dịch sai
if transaction_id in bloom_filter:
    approve_transaction()  # 1% FP = mất tiền!

Tại sao sai: Bloom Filter nói "có thể có" khi thực ra "không" với tỷ lệ FP > 0. Trong banking, điều này có thể gây tổn thất tài chính thực sự.

# ĐÚNG: Bloom Filter làm pre-filter, database verify
if transaction_id not in bloom_filter:
    reject_fast()  # Chắc chắn không hợp lệ
else:
    verify_in_database(transaction_id)  # Double-check

❌ Sai lầm 2: Xóa element từ standard Bloom Filter

Vấn đề: Reset bit về 0 khi xóa element.

# SAI: Corrupt toàn bộ filter
def remove(self, item):
    for i in range(self.num_hashes):
        idx = self._hash(item, i)
        self.bit_array[idx // 8] &= ~(1 << (idx % 8))

Tại sao sai: Bit đó có thể được set bởi nhiều elements khác nhau. Reset tạo false negative — phá vỡ tính chất cốt lõi.

# ĐÚNG: Counting Bloom Filter hoặc rebuild
cbf = CountingBloomFilter(expected_items=1_000_000)
cbf.add("item_a")
cbf.remove("item_a")  # An toàn vì dùng counters

❌ Sai lầm 3: Không tính tham số tối ưu

Vấn đề: Chọn kích thước bit array tùy ý.

# SAI: 1 triệu items, chỉ 10K bits → FP > 90%
bf.size = 10_000
bf.num_hashes = 3

Tại sao sai: Bloom Filter dựa trên cân bằng m/n/k. Phá vỡ cân bằng này khiến FP rate tăng vọt.

# ĐÚNG: Tính tự động từ expected items và target FP rate
bf = BloomFilter(expected_items=1_000_000, fp_rate=0.01)

❌ Sai lầm 4: Hash functions tương quan

Vấn đề: Dùng hash function phân phối không đều hoặc correlated.

# SAI: Các positions bị tương quan
def bad_hash(item, seed):
    return (hash(item) + seed) % size

Tại sao sai: Positions bị cluster → FP rate cao hơn lý thuyết.

# ĐÚNG: Hash riêng biệt hoặc double hashing
def good_hash(item, seed):
    data = f"{item}:{seed}".encode("utf-8")
    return int(hashlib.sha256(data).hexdigest(), 16) % size

Under the Hood

Hiệu năng

Thao tác	Time	Space
add	O(k)	—
might_contain	O(k)	—
Khởi tạo	O(m)	O(m) bits

Với k thường = 7-10 (hằng số nhỏ), cả add và query gần như O(1).

Approach	Bộ nhớ (10M items)	Query	Accuracy
HashSet	~1 GB	O(1) amortized	100%
Sorted Array + BSearch	~1 GB	O(log n)	100%
Bloom Filter (FP 1%)	~11.5 MB	O(k) ≈ O(1)	~99%
Bloom Filter (FP 0.1%)	~17 MB	O(k) ≈ O(1)	~99.9%

Nội bộ triển khai

Memory layout: Bit array liên tục trong memory. Truy cập bit tại vị trí i cần byte_index = i / 8 và bit_offset = i % 8 — cả hai phép bitwise rất nhanh.

Cache locality: Bit array nằm liên tục, các lần truy cập cho k hash functions thường trong cùng cache line (64 bytes = 512 bits). Với m = 10M bits, toàn bộ array ~1.2 MB — vừa L2 cache.

Hash optimization: Kỹ thuật double hashing tính 2 hash values h1, h2 rồi sinh k positions bằng h(i) = h1 + i × h2. Giảm chi phí từ O(k) hash computations xuống O(2).

Trade-offs

Khi NÊN dùng	Khi KHÔNG NÊN dùng
Pre-filter trước expensive lookup	Exact membership (banking, auth)
Dataset lớn, memory giới hạn	Dataset nhỏ (< 10K) — HashSet đủ
Chấp nhận FP nhỏ	FP gây hậu quả nghiêm trọng
Read-heavy workload	Cần delete thường xuyên
Distributed (compact để truyền)	Cần đếm frequency

Checklist ghi nhớ

✅ Checklist triển khai

Thiết kế

• [ ] Xác định expected items (n) và target FP rate trước khi khởi tạo
• [ ] Tính optimal m và k từ công thức
• [ ] Chọn Counting BF nếu cần hỗ trợ delete

Triển khai

• [ ] Hash functions phân phối đều (SHA-256, MurmurHash, xxHash)
• [ ] Double hashing để giảm chi phí k hash computations
• [ ] Kiểm tra memory usage thực tế khớp lý thuyết

Production

• [ ] Bloom Filter là pre-filter, không phải quyết định cuối cùng
• [ ] Monitor FP rate — rebuild nếu vượt ngưỡng
• [ ] Serialize/deserialize bit array cho persistence
• [ ] Metric tracking: bloom_reject vs db_lookup ratio

Bài tập luyện tập

Bài 1: Tính tham số tối ưu — Foundation

Đề bài: Hệ thống lưu 5 triệu email addresses, target FP rate = 0.5%. Tính m, k, và memory.

🧠 Quiz

Câu hỏi: Với n = 5 triệu, FP = 0.5%, m xấp xỉ bao nhiêu?

• [ ] A. 5 triệu bits (~625 KB)
• [ ] B. 25 triệu bits (~3 MB)
• [x] C. 53 triệu bits (~6.3 MB)
• [ ] D. 100 triệu bits (~12 MB) Giải thích: m = -n × ln(p) / (ln2)² ≈ 5.3×10⁷. A quá nhỏ (FP rất cao), D quá lớn (lãng phí).

💡 Gợi ý

• Công thức: m = -(n × ln(p)) / (ln2)²
• k = (m/n) × ln2
• Memory = m / 8 bytes

✅ Lời giải

import math

n, p = 5_000_000, 0.005
m = int(-(n * math.log(p)) / (math.log(2) ** 2))
k = int((m / n) * math.log(2))
memory_mb = m / 8 / 1024 / 1024

print(f"m = {m:,} bits, k = {k}, memory = {memory_mb:.2f} MB")
# m ≈ 53,150,849 bits, k ≈ 7, memory ≈ 6.33 MB

Phân tích: 6.3 MB cho 5 triệu items, 0.5% FP. So với HashSet ~500 MB → tiết kiệm ~80 lần.

Bài 2: Union hai Bloom Filters — Intermediate

Đề bài: Hai server có BF riêng với cùng (m, k). Triển khai union và giải thích tại sao intersection không chính xác.

🧠 Quiz

Câu hỏi: Bloom Filter union dùng phép toán nào?

• [ ] A. AND bit arrays
• [x] B. OR bit arrays
• [ ] C. XOR bit arrays
• [ ] D. Không thể thực hiện Giải thích: OR đúng vì element có trong bất kỳ filter nào → bit đã set = 1. AND cho approximation of intersection nhưng nhiều FP. XOR phá hỏng cấu trúc.

✅ Lời giải

def bloom_union(bf1: BloomFilter, bf2: BloomFilter) -> BloomFilter:
    assert bf1.size == bf2.size and bf1.num_hashes == bf2.num_hashes
    result = BloomFilter.__new__(BloomFilter)
    result.size = bf1.size
    result.num_hashes = bf1.num_hashes
    result.bit_array = bytearray(b1 | b2 for b1, b2 in zip(bf1.bit_array, bf2.bit_array))
    return result

Intersection không chính xác vì AND bit arrays cho FP cao — bits set trong cả hai có thể đến từ elements khác nhau.

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← Scale & Approximation Overview — Tổng quan module
• → HyperLogLog — Ước lượng cardinality với constant memory
• Quadtree — Spatial indexing cho nearest-neighbor
• Data Structures — Hash Table, Tree và cấu trúc dữ liệu nền tảng

Từ khóa glossary: Bloom Filter, probabilistic data structure, false positive, set membership, counting bloom filter, bit array, hash function

Tìm kiếm liên quan: bloom filter là gì, cấu trúc dữ liệu xác suất, kiểm tra phần tử trong tập hợp, cache optimization