Bloom filter: vì sao “không” là chắc chắn, còn “có” chỉ là “có thể”?
Tóm tắt
Bloom filter là mảng bit nằm trong RAM. Mỗi key khi ghi sẽ bật vài bit lên 1. Khi tra cứu, chỉ cần một bit là 0 thì key chắc chắn không tồn tại — không cần chạm đĩa. Nếu mọi bit đều là 1, key “có thể” tồn tại và phải đọc đĩa để chắc chắn.
Cơ chế qua ví dụ
Lấy mảng 16 bit, mỗi key được băm ra 3 vị trí. Ghi user:10, user:22, user:51 → 9 bit được bật.
| Truy vấn | Kết quả filter | Điều gì xảy ra |
|---|---|---|
user:84 | Một bit là 0 → NO | Trả lời ngay trong RAM, không đọc đĩa. |
user:22 | Cả 3 bit là 1 → MAYBE | Đọc đĩa, xác nhận key có thật. |
user:47 | Cả 3 bit là 1 (do key khác bật hộ) → MAYBE | Đọc đĩa rồi mới biết không có — đây là false positive. |
Áp dụng thế nào?
- Backend dev: Dùng Bloom filter trước cache/DB để chặn truy vấn key không tồn tại (chống cache penetration), hoặc để kiểm tra nhanh “đã thấy URL/ID này chưa”.
- Khi tuning: Tỷ lệ báo nhầm phụ thuộc kích thước mảng bit và số hàm băm — tăng bộ nhớ thì giảm false positive.
- Ghi nhớ: Bloom filter cơ bản không hỗ trợ xoá phần tử; cần biến thể như Counting Bloom filter nếu phải xoá.