Bloom Filter là gì? Nó đánh đổi điều gì và được dùng để tối ưu hệ thống ở đâu?

Bloom filter: cấu trúc xác suất, tiết kiệm bộ nhớ, trả lời câu hỏi "phần tử này có thể đã từng được thêm chưa?".

• Một bit array + k hàm hash. Khi add → set k bit. Khi query → kiểm tra k bit đó.
• Không bao giờ false negative: nói "không có" thì chắc chắn không có.
• Có thể false positive: nói "có thể có" nhưng thực ra chưa — vì bit có thể bị phần tử khác set trùng.
• Không xóa được (bản cơ bản) và không lưu phần tử thật — chỉ là dấu vết bit.

Đánh đổi: dùng ~10 bit/phần tử cho tỉ lệ false positive ~1%, nhỏ hơn nhiều so với lưu cả tập key trong set/hash. Đổi lấy sai số dương nhỏ.

Ứng dụng tối ưu hệ thống:
- Tránh I/O đĩa thừa: Cassandra/HBase/RocksDB hỏi Bloom filter trước khi đọc SSTable — nếu "không có" thì khỏi tốn disk seek.
- Cache layer: chặn truy vấn DB cho key chắc chắn không tồn tại (chống cache penetration).
- Lọc URL đã crawl, chống click trùng, kiểm tra username trùng nhanh.

Hình dung: danh sách khách mời nén thành một dãy đèn; đèn của bạn tắt ⇒ chắc chắn chưa mời; đèn sáng ⇒ có lẽ đã mời (cần xác minh).

Lưu ý: sau false positive vẫn cần kiểm tra nguồn thật — Bloom chỉ để loại bớt rẻ, không thay thế nguồn dữ liệu.