Có một họ cấu trúc dữ liệu mà lần đầu gặp ai cũng thấy như ma thuật: chúng trả lời câu hỏi về hàng triệu phần tử bằng bộ nhớ nhỏ đến vô lý — đổi lại một chút sai số có kiểm soát. Đây là cấu trúc dữ liệu xác suất, và chúng có mặt trong gần như mọi hệ thống lớn: database, cache, phân tích luồng, mạng CDN. Loạt bài này đi qua những cái quan trọng nhất, và mở đầu bằng cái nổi tiếng nhất: Bloom filter. Nó trả lời một câu hỏi tưởng chừng cần lưu cả tập — "x có trong tập không?" — mà chỉ dùng một mảng bit và vài hàm băm. Bài này (phần 1 loạt Xác suất) tự cài Bloom filter và đo thật để thấy nó tiết kiệm bộ nhớ khủng khiếp thế nào, và sai số của nó khớp lý thuyết ra sao.

Vấn đề và cơ chế

Bài toán: bạn có một tập lớn (1 triệu URL, email, khóa cache...) và cần kiểm tra nhanh xem một phần tử có thuộc tập không. Cách thông thường — lưu cả tập vào một set/hash — cho tra cứu O(1) nhưng tốn RAM tỉ lệ số phần tử: một triệu chuỗi có thể ngốn hàng chục MB, chỉ để trả lời CÓ/KHÔNG.

Bloom filter đổi cách nghĩ: nếu chấp nhận thỉnh thoảng báo nhầm (nói "có" khi thực ra không), ta làm được việc đó bằng một mảng m bit và k hàm băm:

  • Thêm x: bật k bit ở vị trí hash_1(x), ..., hash_k(x).
  • Kiểm x: nếu mọi k bit đều bật → "CÓ THỂ có"; nếu một bit tắt → "CHẮC CHẮN không".

Điểm mấu chốt về sai số: Bloom không bao giờ báo sót (no false negative) — nếu đã thêm x thì các bit của nó chắc chắn đã bật, nên luôn trả "có". Nhưng nó có thể báo nhầm (false positive): các bit của một phần tử khác vô tình bật trùng đủ k vị trí. Sai số chỉ đi một chiều.

Ảnh chụp đoạn mã nền tối minh hoạ Bloom filter kiểm tra có trong tập không bằng bộ nhớ tí hon mảng bit cộng k hàm băm không báo sót đổi chút sai số lấy 46x bộ nhớ, vấn đề x có trong tập triệu phần tử không tốn RAM lưu cả tập vào set hash để tra cứu O 1 tốn RAM tỉ lệ số phần tử 1 triệu URL email khóa hàng chục MB chỉ để trả lời có không nếu chấp nhận một chút báo nhầm Bloom filter làm việc đó bằng khoảng 1MB, cơ chế m bit cộng k hàm băm thêm x bật k bit tại hash 1 x tới hash k x kiểm x mọi k bit đều bật thì có thể có một bit tắt thì chắc chắn không chắc chắn không không báo sót no false negative có thể có có thể báo nhầm false positive bit bị các phần tử khác bật trùng sinh báo nhầm nhưng không thể có báo sót đã thêm thì các bit chắc chắn đã bật, tự cài bytearray cộng 2 hash kết hợp Kirsch-Mitzenmacher def _idx self x d bằng hashlib sha1 x digest h1 bằng int from_bytes d 8 h2 bằng int from_bytes d 8 16 for i trong range self k yield h1 cộng i nhân h2 phần trăm self m k chỉ số từ chỉ 2 hash add bật bit contains all bit đã bật bytearray bằng mảng bit gọn, công thức tỉ lệ báo nhầm FP bằng 1 trừ e mũ trừ kn trên m mũ k n phần tử m bit k hàm băm k tối ưu bằng m trên n nhân ln2 chọn k để FP thấp nhất m trên n bằng 10 bit mỗi phần tử k bằng 7 FP khoảng 0.8 phần trăm đo thực tế có khớp không

Hình 1: Bloom filter dùng m bit + k hàm băm — thêm x bật k bit, kiểm x xem k bit có bật hết; "một bit tắt = CHẮC CHẮN không" (không báo sót), "mọi bit bật = CÓ THỂ có" (có thể báo nhầm); tự cài bằng bytearray + hai hash kết hợp; tỉ lệ báo nhầm theo công thức (1-e^(-kn/m))^k.

Đo thật: 46 lần nhỏ hơn, sai số khớp công thức

Mình tự cài Bloom (dùng hai hash từ SHA-1 kết hợp kiểu Kirsch-Mitzenmacher để sinh k chỉ số), thêm 1 triệu phần tử vào một Bloom m=10 triệu bit (10 bit/phần tử), k=7, rồi kiểm 500.000 phần tử không thuộc tập để đo tỉ lệ báo nhầm:

Ảnh chụp bảng kết quả chạy thật Bloom filter output thật go-lab python Bloom tự cài 1 triệu phần tử, cấu hình và bộ nhớ n bằng 1 triệu m bằng 10 triệu bit k bằng 7 bộ nhớ Bloom bằng 1250001 byte khoảng 1.3 MB bộ nhớ set ước bằng 57000000 byte khoảng 57 MB Bloom nhỏ hơn khoảng 46x trả lời có không bằng 1 trên 46 bộ nhớ, tỉ lệ báo nhầm đo thực tế vs công thức lý thuyết FP thực tế bằng 0.830 phần trăm 4150 trên 500000 phần tử không thuộc bị báo nhầm FP lý thuyết bằng 0.819 phần trăm công thức 1 trừ e mũ trừ kn trên m mũ k khớp nhau chênh chỉ 0.011 điểm phần trăm lý thuyết đúng, không bao giờ báo sót no false negative báo sót false negative bằng 0 mọi phần tử đã thêm đều trả về có các bit chắc chắn đã bật Bloom chỉ sai một chiều có thể có báo nhầm không bao giờ không nhầm, vì sao điều này hữu ích dùng Bloom lọc trước nếu Bloom nói không chắc chắn không bỏ qua ngay khỏi tra DB đĩa nếu có thể có mới tra thật cắt phần lớn truy vấn ứng dụng cache tránh truy vấn vô ích DB LSM-tree duyệt URL độc hại

Hình 2: Chạy thật — n=1.000.000, m=10.000.000 bit, k=7: Bloom 1.250.001 byte (~1.3MB) vs set ước tính ~57MB (nhỏ hơn ~46x); FP thực tế 0.830% (4150/500000) khớp FP lý thuyết 0.819% (chênh 0.011 điểm phần trăm); báo sót = 0.

  • Tiết kiệm bộ nhớ 46 lần: Bloom chỉ chiếm 1.25MB (đúng bằng 10 triệu bit gói trong bytearray), trong khi một set python lưu 1 triệu chuỗi ước tính ~57MB — Bloom nhỏ hơn ~46 lần. Với hệ thống có hàng chục triệu phần tử, đây là chênh lệch giữa "vừa RAM" và "hết RAM".
  • Sai số khớp lý thuyết gần hoàn hảo: đây là điều đẹp nhất về Bloom — sai số của nó tính trước được. Công thức FP = (1-e^(-kn/m))^k cho 0.819%, và đo thực tế trên 500.000 phần tử ngoài tập cho 0.830% — chênh chỉ 0.011 điểm phần trăm. Bạn không phải "hy vọng" sai số nhỏ; bạn tính được nó từ m, n, k trước khi triển khai (chi tiết chọn m, k ở phần 2).
  • Không bao giờ báo sót: đo thật, mọi phần tử đã thêm đều trả "có" — báo sót = 0. Đây là tính chất đảm bảo (không phải xác suất): Bloom chỉ sai một chiều. Nhờ vậy nó dùng được làm bộ lọc trước an toàn.

Đánh đổi cần cân nhắc

Sai số một chiều làm Bloom thành bộ lọc trước hoàn hảo. Vì "CHẮC CHẮN không" là chắc chắn, bạn dùng Bloom để cắt các truy vấn vô ích: nếu Bloom nói "không có", bỏ qua ngay — khỏi tra database/đĩa (thao tác đắt). Chỉ khi Bloom nói "có thể có" mới tra thật; lúc đó nếu là báo nhầm, bạn chỉ tốn một lần tra thừa (hiếm, ~0.8%). Đây chính là cách LSM-tree (RocksDB, Cassandra) tránh đọc đĩa cho khóa không tồn tại, và cách cache tránh truy vấn backend vô ích. Sai số nhỏ đổi lấy việc cắt phần lớn thao tác đắt.

Không xóa được, và không đếm được — chỉ trả lời "có thể có / chắc chắn không". Bloom cơ bản không hỗ trợ xóa một phần tử (tắt bit có thể phá phần tử khác dùng chung bit đó) — cần Counting Bloom (phần 3). Nó cũng không cho biết có bao nhiêu phần tử, không liệt kê được các phần tử, không lấy lại được dữ liệu gốc. Bloom chỉ làm đúng một việc: kiểm tra thành viên với sai số một chiều. Cần thao tác khác thì dùng cấu trúc khác (các phần sau).

Chọn m, k sai làm sai số bùng lên — phải tính trước theo n dự kiến. Sai số phụ thuộc tỉ lệ m/n (số bit mỗi phần tử) và k. Nếu bạn nhét nhiều phần tử hơn dự kiến vào một Bloom cố định, m/n giảm và sai số tăng vọt (Bloom "đầy" — quá nhiều bit bật). Phải ước lượng n trước và cấp m đủ, hoặc dùng scalable Bloom filter. Đây là chủ đề của phần 2: chọn m và k tối ưu.

Ba ý mang về

  1. Bloom filter trả lời thành viên bằng bộ nhớ tí hon: đo thật thay 57MB set bằng 1.25MB (nhỏ hơn ~46 lần) cho 1 triệu phần tử — dùng m bit + k hàm băm, thêm là bật bit, kiểm là xem bit có bật hết.
  2. Sai số một chiều và tính trước được: đo thật FP thực tế 0.830% khớp công thức (1-e^(-kn/m))^k = 0.819%, và báo sót = 0 — Bloom không bao giờ báo sót, chỉ có thể báo nhầm, nên là bộ lọc trước an toàn (cắt truy vấn DB/đĩa vô ích).
  3. Biết giới hạn: Bloom không xóa được (cần Counting Bloom - phần 3), không đếm/liệt kê được, và sai số bùng lên nếu nhét quá nhiều phần tử — phải chọn m, k theo n dự kiến (phần 2).

Nguồn

Phần sau ta trả lời câu hỏi thực tế: cho trước số phần tử và tỉ lệ báo nhầm mong muốn, chọn m (số bit) và k (số hàm băm) bao nhiêu là tối ưu — và đo thật đường cong sai số theo từng lựa chọn.