Bài toán gốc rễ

Hãy tưởng tượng mày là kỹ sư tại Google. Hệ thống có 2 tỷ tài khoản Gmail. Mỗi ngày có hàng triệu người thử đăng ký. Với mỗi request, mày cần trả lời một câu hỏi duy nhất:

Nghe đơn giản. Nhưng scale mới là vấn đề.

Approach 1 — Query thẳng vào Database

Cách naive nhất: SELECT 1 FROM users WHERE email = ?. Với 2 tỷ record, mỗi query dù có index cũng mất vài milliseconds, cộng network latency. Hàng triệu request/ngày → database trở thành bottleneck ngay.

Approach 2 — Cache toàn bộ email vào RAM

Dùng Redis/Memcached lưu tất cả email vào memory. Nhanh hơn nhiều. Nhưng 2 tỷ email, trung bình 25 bytes/email → ~50 GB RAM chỉ để lưu email. Tốn tiền, không thực tế.

Approach 3 — Bloom Filter

Cùng 2 tỷ email, false positive rate 1% → chỉ tốn ~2.4 GB RAM. Nhanh hơn 20x so với Redis lookup thông thường. Đây chính là vấn đề Bloom Filter sinh ra để giải quyết.

Cơ chế hoạt động

Bloom Filter là một bit array kích thước m, kết hợp với k hash functions độc lập. Ban đầu tất cả các bit đều là 0.

INSERT — Thêm một phần tử

Khi insert item x vào filter:

1. Tính k hash values: h₁(x), h₂(x), ..., hₖ(x)
2. Mỗi hash value map sang một vị trí trong bit array (mod m)
3. Set tất cả k bit tương ứng lên 1

// Insert "hello"
h1("hello") = 3  → set bit[3] = 1
h2("hello") = 7  → set bit[7] = 1
h3("hello") = 12 → set bit[12] = 1

// Insert "world"
h1("world") = 5  → set bit[5] = 1
h2("world") = 7  → bit[7] đã = 1, không sao
h3("world") = 9  → set bit[9] = 1

QUERY — Kiểm tra sự tồn tại

Khi query item x:

1. Tính tương tự k hash values
2. Kiểm tra tất cả k bit tương ứng
3. Nếu bất kỳ bit nào = 0 → Definitely NOT in set
4. Nếu tất cả bit đều = 1 → Probably in set

Tại sao có false positive?

Xét item y chưa được insert. Nhưng qua quá trình insert nhiều items khác, các bit mà h₁(y), h₂(y), h₃(y) trỏ tới đã vô tình bị set bởi những items khác nhau. Bloom Filter không thể phân biệt — nó chỉ thấy "tất cả bit = 1" và trả về "probably yes".

Toán học đằng sau

Bloom Filter có nền tảng toán học rất đẹp. Hiểu được sẽ giúp ích lớn trong phỏng vấn system design.

Xác suất false positive

Cho m bits, k hash functions, n items đã insert. Xác suất false positive:

Số hash functions tối ưu

Tính số bits cần thiết

Muốn lưu n items với false positive rate p:

Bảng sizing thực tế

Interactive Demo

Thử tự tay insert và query để hiểu cơ chế hoạt động. Khi bit array đầy dần, tỉ lệ false positive sẽ tăng lên — mày sẽ thấy rõ điều này.

💡 Gợi ý: Insert ~10 từ rồi thử check một từ chưa insert — mày sẽ thấy false positive xảy ra khi nhiều bit bị set.

False Positive thực sự là gì?

Đây là phần nhiều người hiểu nhầm nhất. False positive trong Bloom Filter không phải bug — nó là trade-off có thể kiểm soát.

Hệ quả thực tế

Trong production, khi Bloom Filter trả về "probably yes", mày vẫn phải verify với DB. Bloom Filter không thay thế DB — nó là tầng lọc đầu tiên để tránh những lookup DB chắc chắn không cần thiết.

Với FPR = 1%, chỉ 1% request bị false positive và phải query DB không cần thiết. 99% request còn lại được fast-reject không tốn I/O.

Trade-off và khi nào dùng

Ứng dụng thực tế

Các biến thể của Bloom Filter

Implement từ scratch

TypeScript

class BloomFilter {
  private bits: Uint8Array;
  private m: number;
  private k: number;
  private count = 0;

  constructor(expectedItems: number, fpr: number) {
    // m = -n * ln(p) / (ln2)²
    this.m = Math.ceil(
      -expectedItems * Math.log(fpr) / (Math.LN2 ** 2)
    );
    // k = (m/n) * ln2
    this.k = Math.ceil((this.m / expectedItems) * Math.LN2);
    this.bits = new Uint8Array(Math.ceil(this.m / 8));
  }

  add(item: string): void {
    for (const pos of this.positions(item)) {
      this.bits[Math.floor(pos / 8)] |= (1 << (pos % 8));
    }
    this.count++;
  }

  has(item: string): boolean {
    return this.positions(item).every(pos =>
      ((this.bits[Math.floor(pos / 8)] >> (pos % 8)) & 1) === 1
    );
  }

  private positions(item: string): number[] {
    // Double hashing: h(i) = h1(x) + i * h2(x)
    let h1 = 5381, h2 = 52711;
    for (const c of item) {
      const code = c.charCodeAt(0);
      h1 = ((h1 << 5) + h1) ^ code;
      h2 = ((h2 << 5) - h2) ^ code;
    }
    return Array.from({length: this.k}, (_, i) =>
      Math.abs((h1 + i * h2) >>> 0) % this.m
    );
  }

  estimatedFPR(): number {
    return (1 - Math.exp(-this.k * this.count / this.m)) ** this.k;
  }
}

// Usage
const filter = new BloomFilter(1_000_000, 0.01); // 1M items, FPR 1%
filter.add("user@gmail.com");
filter.has("user@gmail.com");   // probably true
filter.has("other@gmail.com");  // definitely false OR ~1% false positive

Go

package bloom

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

type BloomFilter struct {
    bits []byte
    m, k uint
}

func New(n uint, fpr float64) *BloomFilter {
    m := uint(-float64(n) * math.Log(fpr) / math.Ln2 / math.Ln2)
    k := uint(float64(m) / float64(n) * math.Ln2)
    return &BloomFilter{bits: make([]byte, (m+7)/8), m: m, k: k}
}

func (bf *BloomFilter) Add(item []byte) {
    h1, h2 := bf.hashes(item)
    for i := uint(0); i < bf.k; i++ {
        pos := (h1 + i*h2) % bf.m
        bf.bits[pos/8] |= 1 << (pos % 8)
    }
}

func (bf *BloomFilter) Has(item []byte) bool {
    h1, h2 := bf.hashes(item)
    for i := uint(0); i < bf.k; i++ {
        pos := (h1 + i*h2) % bf.m
        if bf.bits[pos/8] & (1 << (pos % 8)) == 0 {
            return false
        }
    }
    return true
}

func (bf *BloomFilter) hashes(data []byte) (uint, uint) {
    h := sha256.Sum256(data)
    return uint(binary.BigEndian.Uint64(h[:8])),
           uint(binary.BigEndian.Uint64(h[8:16]))
}

Bloom Filter trong phỏng vấn

Bloom Filter là một trong những câu trả lời gây "wow effect" tốt nhất trong system design interview vì ít người junior nghĩ tới.

Pattern nhận diện — khi nào mention

Các bài system design hay trigger

Follow-up questions phải biết