Mọi cấu trúc tra cứu ta gặp cho tới giờ — bảng băm, cây tìm kiếm, B-tree — đều trả lời câu hỏi "phần tử này có trong tập không?" một cách chính xác. Bloom filter làm điều gần như phản trực giác: nó trả lời câu hỏi đó không chính xác — đôi khi nói "có" khi thực ra không — và đổi lấy điều đó, nó dùng ít bộ nhớ đến mức khó tin. Bài này đo cái đánh đổi ấy: dương tính giả thật sự bao nhiêu, giảm được tới đâu, và tiết kiệm được cỡ nào — vì "gần như chính xác" là một khái niệm chỉ có con số mới làm rõ được.
Một tập không lưu phần tử
Bloom filter chỉ gồm một mảng bit (ban đầu toàn 0) và k hàm băm. Để thêm một phần tử, băm nó bằng k hàm, được k vị trí, và bật k bit đó lên 1. Để hỏi một phần tử có trong tập không, băm nó bằng đúng k hàm và xem k bit: nếu có bất kỳ bit nào bằng 0, phần tử chắc chắn không có (vì nếu đã thêm thì cả k bit phải là 1); nếu tất cả k bit đều bằng 1, phần tử có thể có — nhưng cũng có thể chỉ là k bit đó tình cờ bị các phần tử khác bật lên. Trường hợp sau là dương tính giả (false positive): filter nói "có" nhưng thực ra không.
Điểm mấu chốt là sự bất đối xứng của sai lầm này. Bloom filter không bao giờ cho âm tính giả — nếu nó nói "không có", điều đó chắc chắn đúng. Nó chỉ có thể sai theo một chiều: nói "có" khi không. Và vì nó không lưu chính các phần tử (chỉ lưu bit), nó nhỏ đến kinh ngạc. Cái giá của sự nhỏ đó là tỉ lệ dương tính giả — thứ tôi đo.
Đo: dương tính giả là thật, và không bao giờ về 0
Tôi cài một Bloom filter, thêm một triệu phần tử, rồi hỏi một triệu phần tử không nằm trong tập và đếm bao nhiêu lần filter sai (nói "có"). Đo với số bit dành cho mỗi phần tử khác nhau (dùng số hàm băm tối ưu cho mỗi mức):
bit/phần tử k dương tính giả (đo) lý thuyết
4 3 14,73 % 14,69 %
8 6 2,18 % 2,16 %
10 7 0,81 % 0,82 %
16 11 0,046% 0,046%
Hai điều nổi lên. Thứ nhất, số đo khớp lý thuyết tới từng phần trăm nhỏ — Bloom filter là một trong những cấu trúc mà toán học dự đoán hành vi thực tế chính xác đến đẹp. Thứ hai, và đây là điều đáng nhớ: tỉ lệ dương tính giả giảm theo hàm mũ khi thêm bit (14,7% → 2,2% → 0,81% → 0,046%) nhưng không bao giờ chạm 0. Bạn có thể ép nó nhỏ tùy ý — 16 bit mỗi phần tử cho 0,046%, tức khoảng một phần hai nghìn — nhưng luôn còn một xác suất dương tính giả khác không. Đây là chỗ tôi vào bài với một hiểu nhầm.
Một lần tôi đo hớ: "có thể có" nghĩa là "đôi khi sai"
Cú hớ của tôi là quán tính từ mọi cấu trúc tra cứu trước: kiểm tra thành viên thì phải chính xác. Tôi dễ dàng gật đầu với mô tả "Bloom filter kiểm tra thành viên" mà quên mất chữ "xác suất" và cái dương tính giả đi kèm. Đo ra, dương tính giả không phải chi tiết lý thuyết mà là con số cụ thể, sống động: cứ 10 bit mỗi phần tử thì khoảng 8 trên 1000 câu trả lời "có" là sai, và ở 4 bit thì tới 15%. "Có thể có" thực sự nghĩa là "đôi khi sai", và bạn không thể mua sự chắc chắn tuyệt đối bằng bất kỳ lượng bit hữu hạn nào.
Nhưng cùng phép đo cho thấy mặt kia của đánh đổi, và nó biện minh cho tất cả. Tôi hỏi lại toàn bộ một triệu phần tử đã thêm: số âm tính giả là 0 — không một lần nào filter nói "không có" một phần tử thực sự có. Sự sai một chiều được xác nhận. Và về bộ nhớ: một triệu phần tử với 10 bit mỗi cái chiếm 1,2 MB, trong khi một tập băm thật lưu các khóa 64-bit cộng chi phí con trỏ/ô trống dễ dàng ngốn ~25 MB — Bloom nhỏ hơn khoảng 20 lần. Bài học đo lường: Bloom filter đổi độ chính xác lấy bộ nhớ, và đó là một đánh đổi có thật, đo được, điều chỉnh được — không phải phép màu; bạn chọn tỉ lệ sai chấp nhận được rồi trả bằng đúng số bit tương ứng.
Còn một chi tiết đo được nữa: số hàm băm k không phải càng nhiều càng tốt. Cố định 10 bit mỗi phần tử và quét k từ 1 tới 12, tỉ lệ dương tính giả tạo thành một đường cong hình chữ U — k=1 cho 9,6%, giảm dần tới đáy 0,80% ở k=7, rồi tăng lại (k=12 lên 1,36%). Quá ít hàm băm thì mỗi phần tử để lại quá ít dấu vết (dễ trùng); quá nhiều thì bật quá nhiều bit, mảng mau đầy 1 (cũng dễ trùng). Có một k tối ưu, xấp xỉ 0,7 × số bit mỗi phần tử, và đo đường cong theo k cho thấy rõ cái đáy — đúng tinh thần "đo đường cong, đừng đo một điểm".
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, về cách dùng đúng: Bloom filter là một bộ lọc đứng trước một tra cứu đắt tiền, không phải câu trả lời cuối cùng. Mẫu hình kinh điển: trước khi tra một khóa trên đĩa hoặc trong cơ sở dữ liệu (tốn kém), hỏi Bloom filter trong bộ nhớ trước. Nếu nó nói "không có" — chắc chắn đúng — bạn bỏ qua luôn cú tra đắt tiền. Nếu nó nói "có thể có", bạn mới thực sự đi tra nguồn thật để xác nhận. Vài lần dương tính giả chỉ nghĩa là thỉnh thoảng bạn tra một cú vô ích, không sai kết quả cuối cùng (vì nguồn thật vẫn là trọng tài). Đây là lý do Bloom filter nằm trong nhiều cơ sở dữ liệu (chặn truy vấn khóa không tồn tại), bộ nhớ đệm, và trình duyệt (kiểm URL độc hại).
Hệ quả thứ hai: chọn một cấu trúc xác suất là chấp nhận một tỉ lệ sai để đổi lấy tài nguyên — và bạn phải biết tỉ lệ đó, không được quên nó tồn tại. Bloom filter chỉ đúng đắn khi hệ thống của bạn chịu được dương tính giả (có một tầng xác nhận phía sau). Dùng nó ở nơi một câu "có" sai gây hậu quả không sửa được là dùng sai. Luôn hỏi: một dương tính giả ở đây tốn gì, và tỉ lệ của tôi là bao nhiêu?
Hệ quả thứ ba là con số mang theo: Bloom filter đổi độ chính xác lấy bộ nhớ — dương tính giả là thật (0,81% ở 10 bit/phần tử, 14,7% ở 4 bit), giảm theo hàm mũ khi thêm bit nhưng không bao giờ về 0; bù lại không bao giờ có âm tính giả (nói "không" là chắc chắn) và chỉ tốn 1,2MB so với ~25MB của tập băm thật; có số hàm băm tối ưu ~0,7×bit/phần tử. "Kiểm tra thành viên" không nhất thiết phải chính xác, và chấp nhận một sai số nhỏ có kiểm soát đôi khi mua được một khoản tiết kiệm khổng lồ — miễn là bạn biết chính xác mình đang đổi cái gì.
Thử ba mươi giây
Lần tới khi bạn định dựng một tập lớn trong bộ nhớ chỉ để trả lời "phần tử này đã thấy chưa / có trong danh sách không", hỏi một câu: mình có chịu được thỉnh thoảng một câu trả lời "có" sai không? Nếu phía sau còn một nguồn thật để xác nhận (đĩa, cơ sở dữ liệu, danh sách gốc), thì câu trả lời thường là có — và một Bloom filter có thể thay cái tập đồ sộ của bạn bằng vài megabyte bit. Cách ước lượng nhanh trong đầu: khoảng 10 bit mỗi phần tử cho tỉ lệ sai dưới 1%, mỗi 5 bit thêm vào chia đôi sai số vài lần. Nếu bạn không chịu được câu "có" sai nào, thì Bloom filter không dành cho bạn — hãy dùng một tập chính xác và trả cái giá bộ nhớ của nó. Điều quan trọng là quyết định đó phải là một lựa chọn có ý thức về đánh đổi, không phải một sự cố bất ngờ khi một dương tính giả xuất hiện trong sản phẩm.
