Bạn có một tỉ URL đã thu thập và muốn biết một URL mới liệu đã gặp bao giờ chưa. Lưu hết vào một bảng băm thì trả lời chính xác tuyệt đối — nhưng tốn hàng chục GB, và với một trình thu thập chạy trên máy vừa phải thì đơn giản là không đủ chỗ. Bloom filter làm gần đúng công việc đó bằng vài trăm MB, đổi một chút sai sót có kiểm soát lấy một khoản tiết kiệm bộ nhớ khổng lồ. Bí quyết nằm ở việc nó không lưu bản thân các URL — nó chỉ lưu dấu vết của chúng.
Cách hoạt động
Cấu trúc chỉ gồm hai thứ: một mảng bit ban đầu toàn số 0, và k hàm băm khác nhau (thường vài hàm).
Thêm một phần tử: đưa nó qua cả k hàm băm, mỗi hàm cho ra một vị trí trong mảng, rồi bật các vị trí đó lên 1. Không lưu URL, chỉ để lại k dấu vết.
Kiểm tra một phần tử: băm nó bằng đúng k hàm đó rồi xem các vị trí tương ứng. Đây là chỗ logic trở nên đẹp: nếu bất kỳ vị trí nào trong số đó bằng 0, thì phần tử này chắc chắn chưa từng được thêm — vì nếu nó đã được thêm, cả k bit đó buộc phải là 1. Còn nếu cả k vị trí đều bằng 1, thì phần tử có thể có mặt — nhưng cũng có thể không, vì các bit đó có thể đã được bật lên bởi những phần tử khác tình cờ băm trúng cùng vị trí. Trường hợp này gọi là dương tính giả.
Tính chất quan trọng nhất
Điểm phải khắc cốt: Bloom filter không bao giờ cho âm tính giả. Khi nó nói "không có", đó là sự thật tuyệt đối. Nó chỉ có thể sai theo một chiều — nói "có thể có" trong khi thực ra không có. Sự bất đối xứng này không phải khuyết điểm cần chịu đựng; nó chính là thứ quyết định cách dùng đúng: đặt Bloom filter trước một phép tra cứu đắt tiền, để loại bỏ nhanh phần lớn trường hợp không cần tra, và chỉ thực hiện phép tra tốn kém khi Bloom filter nói "có thể".
Vì "không" là chắc chắn, mỗi câu trả lời "không" giúp bạn bỏ qua trọn vẹn phép tra đắt tiền mà không sợ bỏ sót. Còn mỗi câu "có thể" chỉ khiến bạn tra thật một lần — và nếu tỉ lệ dương tính giả được giữ thấp, số lần tra thừa đó là rất nhỏ so với số lần được bỏ qua.
Chỗ dùng điển hình
- Cơ sở dữ liệu kiểm tra xem một khoá có nằm trong một tệp trên đĩa không, trước khi thật sự tốn công đọc đĩa — nếu Bloom nói "không", khỏi đọc.
- Bộ nhớ đệm phân tán tránh một cuộc gọi qua mạng cho những khoá chắc chắn không tồn tại, cắt đi độ trễ mạng cho phần lớn truy vấn hụt.
- Trình thu thập web lọc ra những URL đã gặp, để khỏi tải lại cùng một trang triệu lần.
Điều phải chấp nhận
Sức mạnh đó đi kèm hai ràng buộc cứng. Thứ nhất, không xoá được phần tử. Tắt một bit về 0 để "xoá" một phần tử có thể vô tình phá vỡ một phần tử khác đang dùng chung bit đó, biến câu trả lời "không" vốn chắc chắn thành sai — mà một khi âm tính giả xuất hiện, toàn bộ giá trị của cấu trúc sụp đổ. Muốn hỗ trợ xoá phải dùng biến thể phức tạp hơn.
Thứ hai, phải ước lượng số phần tử từ trước để chọn kích thước mảng bit và số hàm băm cho phù hợp. Đây không phải chi tiết vụn: nếu bạn nhét vào nhiều hơn nhiều so với dự tính, mảng bit dần được bật gần hết lên 1, và tỉ lệ dương tính giả tăng vọt — tới mức gần như mọi câu trả lời đều là "có thể có", và cấu trúc trở nên vô dụng vì không còn loại bỏ được gì. Một Bloom filter được cỡ đúng là công cụ tuyệt vời; một Bloom filter bị nhồi quá tải chỉ là một mảng bit toàn số 1 tốn chỗ.
Thảo luận