System DesignBloom filter là 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ể đã có trong tập chưa?".
- Kết quả có hai loại: "chắc chắn không có" hoặc "có thể có" → có false positive nhưng không bao giờ false negative.
- Dùng một mảng bit + nhiều hàm hash; thêm phần tử = bật các bit; kiểm tra = xem tất cả bit đó có bật không.
- Không lưu phần tử thật, không xóa được (biến thể counting Bloom filter mới xóa được).
Ứng dụng: tránh truy vấn tốn kém — DB (Cassandra/HBase) kiểm tra nhanh "key này có ở SSTable không" trước khi đọc disk; CDN/cache tránh lookup vô ích; chống trùng URL trong crawler.