Hãy nghĩ về một xét nghiệm sàng lọc rẻ tiền ở bệnh viện. Nó được thiết kế để không bao giờ bỏ sót người bệnh — ai thật sự có bệnh đều bị nó đánh dấu. Đổi lại, thỉnh thoảng nó báo dương với một người khỏe mạnh. Nhưng vì nó không bao giờ bỏ sót, bác sĩ chỉ cần làm xét nghiệm đắt tiền và chính xác cho những ai bị nó đánh dấu, còn lại thì yên tâm cho về. Một xét nghiệm rẻ, sai một chiều an toàn, dùng làm màng lọc trước cho xét nghiệm đắt — đó gần như đúng cách một bloom filter làm việc với dữ liệu.
Mọi cấu trúc kiểm tra thành viên ta đã gặp — hash set, bitset, cây — đều trả lời chính xác: x có trong tập hay không. Nhưng bloom filter cố tình chấp nhận sai đôi chút để đổi lấy bộ nhớ ít đến kinh ngạc. Nghe như một khiếm khuyết, nhưng đây là một trong những công cụ được yêu thích nhất trong hệ thống lớn — cơ sở dữ liệu, cache, web crawler đều dùng. Tôi đo nó so với hash set trong container gcc:13, và con số cho thấy "đánh đổi xác suất" là một món hời khi bạn hiểu chính xác nó sai kiểu gì.
k hàm băm, một mảng bit, và một loại sai duy nhất
Bloom filter là một mảng bit cộng k hàm băm. Thêm phần tử x: băm x bằng k hàm, bật k bit tương ứng lên 1. Hỏi x có trong tập không: kiểm cả k bit — nếu một bit là 0 thì x chắc chắn không có (vì nếu đã thêm, k bit đó phải đều bằng 1); nếu tất cả k bit đều 1 thì x có thể có (hoặc chỉ trùng bit của các phần tử khác).
Điều này tạo ra một tính chất bất đối xứng rất đẹp, đúng cái xét nghiệm sàng lọc ở trên:
- Không bao giờ dương tính giả về việc vắng (no false negative): bloom nói "không có" thì chắc chắn không có. Nó không bao giờ bỏ sót.
- Có dương tính giả (false positive): đôi khi nói "có" nhầm, với xác suất p điều chỉnh được qua số bit mỗi phần tử
m/nvà số hàm băm k. Công thức:p = (1 - e^(-kn/m))^k.
Đổi lại điều gì? Bộ nhớ ít đến khó tin — chỉ
10 bit mỗi phần tử cho p1%, so với ~32 byte mỗi phần tử của hash set. Tôi đo để xem con số thật.
Đo: nhỏ hơn 26 lần, sai đúng như lý thuyết
Tôi lưu 10 triệu phần tử bằng bloom filter (10 bit/phần tử) và unordered_set:
N = 10 triệu phần tử, g++ -O2:
A. BỘ NHỚ:
bloom (10 bit/phần tử) : 12,5 MB
unordered_set<uint64> : ~320 MB (~32 byte/phần tử)
-> bloom nhỏ hơn ~26 lần
B. DƯƠNG TÍNH GIẢ (query 10 triệu phần tử KHÔNG có trong tập):
k=5, m=10 bit/pt : đo được 0,95% | lý thuyết 0,94%
k=7, m=10 bit/pt : đo được 0,82% | lý thuyết 0,82%
k=10, m=10 bit/pt : đo được 1,02% | lý thuyết 1,02%
-> khớp công thức; và KHÔNG BAO GIỜ sai về việc vắng (no false negative)
C. TỐC ĐỘ QUERY (1 triệu test):
bloom (k=7) : 6,0 ns/query (k lần test bit)
unordered_set : 19,5 ns/query
-> bloom nhanh hơn ~3,3 lần
Nhìn A: bloom filter lưu 10 triệu phần tử trong 12,5 MB, còn unordered_set tốn ~320 MB — bloom nhỏ hơn ~26 lần. Vì bloom chỉ lưu bit, không lưu chính giá trị. B là phần tôi thích nhất: tỷ lệ dương tính giả đo được khớp công thức lý thuyết đến hai chữ số thập phân — k=7 cho 0,82% đo, 0,82% lý thuyết, đúng khít. Và điều chỉnh được: k=5 cho 0,95%, k=10 cho 1,02%; với m=10 bit, k=7 là tối ưu (thấp nhất). Quan trọng nhất: trong toàn bộ test, bloom không bao giờ nói "không có" với một phần tử thực sự có — không false negative. C: bloom còn nhanh hơn hash (6,0 so với 19,5 ns), vì nó chỉ test vài bit thay vì băm cả giá trị rồi so sánh.
Vậy bloom cho: RAM ít hơn 26 lần, query nhanh hơn 3,3 lần, đổi lấy ~0,82% nói "có" nhầm — một sai số điều chỉnh được, không bao giờ bỏ sót.
(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, 10 triệu phần tử. Con số tuyệt đối đổi theo máy; điều đáng tin là tỷ lệ dương tính giả đo được trùng khít công thức, và tính chất no-false-negative luôn đúng bất kể máy.)
Hai niềm tin đối nghịch, cùng sai
Tôi vào chủ đề này với phản xạ: "cấu trúc kiểm tra thành viên thì phải chính xác tuyệt đối, một cái đôi khi trả lời sai thì vô dụng". Đo và suy nghĩ lại: bloom đổi ~0,82% dương tính giả (điều chỉnh được, khớp công thức) lấy RAM ít hơn 26 lần và query nhanh hơn 3 lần — một món hời khổng lồ khi sai số nhỏ chấp nhận được.
Nhưng có một niềm tin ngược lại, nguy hiểm hơn: "bloom đôi khi sai nên không tin được kết quả nào của nó". Sai hoàn toàn — bloom không bao giờ sai về việc vắng: nếu nó nói "không có", chắc chắn không có. Chỉ khi nó nói "có" thì mới cần xác nhận. Đây là chìa khóa dùng bloom đúng: làm bộ lọc trước. Nếu bloom nói "không có" → khỏi tra cơ sở dữ liệu/đĩa (tiết kiệm cú tra đắt); nếu nói "có" → mới tra thật để xác nhận. Tuyệt đại đa số truy vấn "không có" được lọc ngay, không tốn I/O — đúng cái bác sĩ chỉ làm xét nghiệm đắt cho người bị sàng lọc đánh dấu.
Về đến code hằng ngày
Điều đầu tiên: dùng bloom filter làm bộ lọc trước cho các cú tra cứu đắt. Cơ sở dữ liệu LSM-tree (LevelDB, RocksDB, Cassandra) dùng bloom filter để tránh đọc đĩa: mỗi file có một bloom filter nhỏ trong RAM; trước khi đọc file, hỏi bloom — nếu nói "không có khóa này" thì bỏ qua file, không tốn I/O. Web crawler dùng bloom để hỏi "URL này đã crawl chưa" mà không lưu hàng tỷ URL. Cache, chống trùng, kiểm tra mật khẩu rò rỉ — tất cả là sân của bloom, khi tập lớn tới mức lưu chính xác quá tốn kém.
Điều thứ hai: điều chỉnh m (bit/phần tử) và k (số hàm băm) theo tỷ lệ sai bạn chấp nhận. Công thức p = (1-e^(-kn/m))^k cho bạn kiểm soát chính xác: muốn p thấp hơn thì tăng m (nhiều bit hơn); với mỗi m có một k tối ưu (≈ 0,7 × m/n). Đừng dùng bloom nếu bạn cần câu trả lời chính xác 100% (dùng hash set); dùng nó khi ~1% sai đổi lấy 26 lần RAM là đáng.
Và nếu bạn viết Java, Go hay dùng cơ sở dữ liệu thì bloom filter đã nằm sẵn trong tay mà có thể bạn chưa để ý. Thư viện Guava của Google có BloomFilter dựng sẵn, Go có nhiều gói phổ biến; còn ở tầng database thì đây là thứ chạy ngầm mỗi ngày — RocksDB và Cassandra bật bloom filter mặc định cho mỗi SSTable, và một truy vấn khóa không tồn tại được trả lời trong RAM thay vì một lần seek đĩa, đúng cái tạo nên sự khác biệt giữa "chậm" và "nhanh" ở quy mô lớn. Các biến thể mở rộng ý tưởng này rất đáng biết khi bạn gặp giới hạn của bloom: counting bloom filter cho phép xóa phần tử, còn cuckoo filter cho tỷ lệ sai tương đương mà xóa được và thường gọn hơn. Cùng một triết lý sàng-lọc-rẻ-trước-xét-nghiệm-đắt, tinh chỉnh cho từng nhu cầu.
Muốn tự thấy thì cài một bloom filter: một mảng bit và k hàm băm (mẹo: tạo k hàm từ hai hàm băm bằng h1 + i*h2). Thêm vài triệu phần tử, rồi query các phần tử chắc chắn KHÔNG có và đếm bao nhiêu lần nó nói "có" nhầm — bạn sẽ thấy tỷ lệ khớp công thức (1-e^(-kn/m))^k. Thử đổi số bit mỗi phần tử và số hàm băm k, xem tỷ lệ sai thay đổi thế nào. Rồi query các phần tử đã thêm và xác nhận nó không bao giờ nói "không có" — đó là tính chất no-false-negative. Cuối cùng, so bộ nhớ bloom với một unordered_set cùng số phần tử: bloom nhỏ hơn hàng chục lần. Vài phút đó cho bạn thấy điều mà "cấu trúc phải chính xác" giấu đi: chấp nhận một sai số nhỏ có kiểm soát, và chỉ sai theo một chiều an toàn, có thể đổi lấy bộ nhớ và tốc độ mà không cấu trúc chính xác nào cho được — miễn là bạn hiểu rõ nó sai kiểu gì.
