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.

Bloom filter: a memory-efficient probabilistic structure answering "might this element have been added?".

• A bit array + k hash functions. Add → set k bits. Query → check those k bits.
• Never false negatives: if it says "absent", it truly is absent.
• May give false positives: says "maybe present" when it isn't — bits can collide with other elements.
• No deletion (basic version) and stores no real elements — only bit traces.

Trade-off: ~10 bits/element for ~1% false-positive rate, far smaller than holding all keys in a set/hash. The cost is occasional false positives.

System optimizations:
- Avoid wasted disk I/O: Cassandra/HBase/RocksDB consult a Bloom filter before reading an SSTable — "absent" skips a disk seek.
- Cache layer: block DB queries for keys that definitely don't exist (cache-penetration defense).
- Filtering already-crawled URLs, dedup clicks, fast username-taken checks.

Picture: a guest list compressed into a row of lights; your light off ⇒ definitely not invited; light on ⇒ probably invited (verify).

Note: after a positive you still verify the real source — Bloom is a cheap pre-filter, not a replacement for the data store.