Backend hay gặpBloom filter là cấu trúc dữ liệu xác suất, tiết kiệm bộ nhớ để kiểm tra một phần tử có thuộc tập hợp hay không. Cấu tạo: một mảng bit và k hàm băm; khi thêm phần tử, băm nó ra k vị trí và bật các bit đó lên. Khi kiểm tra, nếu bất kỳ bit tương ứng bằng 0 → chắc chắn KHÔNG có; nếu tất cả bằng 1 → có thể có (có xác suất false positive).
Đặc tính then chốt:
- Không có false negative: đã nói "không có" thì chắc chắn không có.
- Có false positive: đôi khi nói "có thể có" nhưng thực ra không — chấp nhận đánh đổi này để chỉ tốn vài bit cho mỗi phần tử.
- Bản chuẩn không xoá được phần tử (có biến thể counting để xoá).
Dùng trong backend để tránh thao tác đắt tiền cho phần tử không tồn tại:
- Chống cache penetration: trước khi truy vấn DB/đĩa, hỏi Bloom filter — nếu "chắc chắn không có" thì bỏ qua luôn, khỏi tốn một lần đọc.
- LSM-tree database (Cassandra, RocksDB, HBase): mỗi SSTable có Bloom filter để bỏ qua file chắc chắn không chứa key, giảm số lần đọc đĩa.
- Chống trùng (đã thấy URL/email chưa), lọc sơ bộ ở CDN/proxy.