Bộ lọc Bloom (Bloom Filter)

1. Tổng quan

A. Định nghĩa

Bộ lọc Bloom (Bloom Filter) là một cấu trúc dữ liệu xác suất (probabilistic) chỉ gồm một mảng bit m bit và k hàm băm độc lập, dùng để xác định một phần tử có thuộc một tập hợp cụ thể hay không; kết quả "không có (negative)" luôn chính xác, nhưng "có (positive)" cho phép dương tính giả (False Positive) với một xác suất nhất định, đổi lại có thể kiểm tra quan hệ thuộc tập hợp với lượng bộ nhớ cực nhỏ.

Bộ lọc Bloom là cấu trúc dữ liệu do Burton H. Bloom đề xuất năm 1970, giải quyết truy vấn thành viên (membership query) "phần tử này có trong tập hợp không?" mà không lưu chính phần tử. Khác với HashSet (HashSet) lưu toàn bộ phần tử để cho câu trả lời chính xác nhưng tiêu tốn bộ nhớ O(n), bộ lọc Bloom không lưu phần tử mà chỉ bật vài bit để để lại dấu vết thuộc tập hợp, nên khi xử lý hàng triệu đến hàng trăm triệu phần tử có thể tiết kiệm bộ nhớ hàng chục lần trở lên. Vì vậy nó được dùng rộng rãi làm bộ lọc tiền xử lý trong các hệ thống quy mô lớn "chấp nhận được dương tính giả nhưng không thể nhượng bộ về bộ nhớ và tốc độ".

B. Bối cảnh ra đời và sự cần thiết

Trong hệ thống dữ liệu quy mô lớn, thao tác tốn kém nhất là truy cập đĩa và mạng. Chẳng hạn, cơ sở dữ liệu dựa trên cây LSM (Cassandra, HBase, RocksDB) có thể phải lục tìm hàng chục SSTable trên đĩa để đọc một khóa, và phần lớn SSTable không chứa khóa đó. Mỗi lần đọc đĩa chỉ để xác nhận một khóa không tồn tại là sự lãng phí khổng lồ. Các tình huống web crawler xác định "URL đã truy cập chưa", CDN kiểm tra "nội dung có trong cache không", hay hệ thống mật khẩu kiểm tra "có nằm trong danh sách mật khẩu bị lộ không" cũng có cùng bản chất — phải lọc rẻ lượng lớn truy vấn mà phần lớn câu trả lời là 'không có' trước khi lục tìm bản gốc.

Khi đó, cách đưa nguyên tập hợp chính xác (HashSet, B-tree) lên bộ nhớ sẽ chạm giới hạn bộ nhớ khi dữ liệu lớn lên. Bộ lọc Bloom tận dụng tính chất chính xác 100% đối với phán định "không có" để chặn ngay trong bộ nhớ đa số truy vấn phủ định (negative) không cần truy cập bản gốc. Chỉ với số ít trường hợp cho ra "có" mới cần xác nhận bản gốc thật, nên số lần truy cập tốn kém giảm đột phá. Ngay cả khi xảy ra dương tính giả, bản gốc được kiểm tra thêm một lần để lọc câu trả lời sai nên độ chính xác cuối cùng được duy trì, chỉ thêm phần công sức vô ích tương ứng — đó là căn cứ để áp dụng trong thực tế.

2. Cấu trúc và nguyên lý hoạt động

Bộ lọc Bloom gồm ① mảng bit m bit được khởi tạo toàn 0 và ② k hàm băm khác nhau h₁, h₂, …, h_k ánh xạ đầu vào thành số nguyên trong phạm vi [0, m-1]. Thao tác chèn và truy vấn dùng cùng k vị trí băm.

flowchart LR
    subgraph INS["Chèn (Insert): phần tử x"]
      X["Đầu vào x"] --> H1["h1(x)=1"]
      X --> H2["h2(x)=4"]
      X --> H3["h3(x)=7"]
    end
    H1 --> BIT["Mảng bit: đặt tất cả vị trí tương ứng 1·4·7 thành 1"]
    H2 --> BIT
    H3 --> BIT

Thao tác chèn tính tất cả k hàm băm cho phần tử x và đặt (set) thành 1 k vị trí bit mà kết quả trỏ tới. Nếu đã là 1 thì giữ nguyên. Bản thân phần tử không được lưu ở bất kỳ đâu, chỉ còn lại "dấu vết của các bit được bật". Việc nhiều phần tử có thể dùng chung (chồng lấn) cùng một bit vừa là nguồn tiết kiệm bộ nhớ vừa là nguyên nhân của dương tính giả.

Thao tác truy vấn tính cùng k vị trí băm cho phần tử truy vấn y rồi kiểm tra bit tại các vị trí đó. Quy tắc phán định như sau.

flowchart TB
    Q["Truy vấn (Query): phần tử y"] --> C{"Bit tại k vị trí băm có đều là 1 không?"}
    C -->|"Có ít nhất một bit 0"| N["Phủ định chắc chắn (Definitely NOT in set) — chính xác 100%"]
    C -->|"Tất cả là 1"| P["Có lẽ tồn tại (Probably in set) — có thể dương tính giả"]

Trong k vị trí, chỉ cần một vị trí là 0 thì chắc chắn phần tử đó chưa từng được chèn (vì nếu đã chèn thì tất cả phải là 1). Đó là lý do bộ lọc Bloom tuyệt đối không cho âm tính giả (False Negative). Ngược lại, nếu k vị trí đều là 1 thì phán định là "có lẽ tồn tại", nhưng các bit này có thể đều là 1 không phải do y mà do các phần tử khác tình cờ đã bật cùng vị trí. Trường hợp này chính là dương tính giả.

Một giới hạn cấu trúc là không thể xóa trong bộ lọc Bloom chuẩn. Vì nếu đưa một bit cụ thể về 0, các phần tử khác dùng chung bit đó cũng có thể bị phán sai là "không có" (âm tính giả). Nếu cần xóa, dùng bộ lọc Bloom đếm (Counting Bloom Filter) đặt mỗi vị trí là một bộ đếm nhỏ thay vì 1 bit.

3. Xác suất dương tính giả và thiết kế tham số

Cốt lõi của thiết kế bộ lọc Bloom là đưa xác suất dương tính giả p, được quyết định bởi quan hệ giữa kích thước mảng bit m, số hàm băm k, số phần tử n, xuống dưới giá trị mục tiêu. Sau khi chèn n phần tử, xác suất một bit bất kỳ vẫn là 0 xấp xỉ (1 − 1/m)^(kn) ≈ e^(−kn/m), và từ đó xác suất dương tính giả được cho bởi công thức gần đúng sau.

p ≈ (1 − e^(−kn/m))^k

Công thức này cho một vài trực giác. Thứ nhất, mảng bit càng lớn (m↑) thì va chạm bit càng ít và p càng thấp. Thứ hai, số hàm băm k quá ít thì sức phân biệt yếu, còn quá nhiều thì lấp đầy bit quá mức khiến va chạm lại tăng, nên khi cho trước m/n tồn tại giá trị tối ưu làm p nhỏ nhất. Số hàm băm tối ưu là k = (m/n)·ln2 ≈ 0.693·(m/n), và khi đó số bit cần cho mỗi phần tử được rút gọn thành m/n ≈ −1.44·log₂(p).

Nắm cảm giác bằng con số cụ thể thì cảm quan thiết kế sẽ rõ ràng. Muốn tỷ lệ dương tính giả mục tiêu p=1% (0.01) thì cần khoảng 9.6 bit mỗi phần tử (≈1.2 byte) và khoảng 7 hàm băm. Tức là để quản lý 10 triệu URL với 1% dương tính giả chỉ cần khoảng 9.6×10⁷ bit ≈ khoảng 12MB. So với việc lưu cùng 10 triệu URL vào HashSet dưới dạng chuỗi trung bình 50 byte mỗi URL tốn tối thiểu vài trăm MB, có thể thấy tiết kiệm bộ nhớ hàng chục lần. Nếu hạ mục tiêu xuống p=0.1% thì tăng lên khoảng 14.4 bit mỗi phần tử, cho thấy độ chính xác và bộ nhớ có quan hệ đánh đổi theo thang logarit.

4. Tình huống ứng dụng và so sánh với các kỹ thuật tương tự

Nhờ tính chất "lọc rẻ các truy vấn phủ định", bộ lọc Bloom có mặt trên đường xử lý cốt lõi của nhiều hệ thống công nghiệp. Tiêu biểu, Google Bigtable, Apache Cassandra, HBase, RocksDB đặt một bộ lọc Bloom cho mỗi SSTable, bỏ qua phần lớn việc đọc đĩa cho các khóa không tồn tại, qua đó giảm mạnh độ trễ đọc. Duyệt web an toàn của trình duyệt (Google Safe Browsing) phân phối danh sách hàng triệu URL độc hại tới client dưới dạng bộ lọc Bloom để phán định sơ bộ tại chỗ, chỉ số ít URL cho kết quả "có khả năng nguy hiểm" mới được xác nhận lại với máy chủ. Ngoài ra còn được dùng rộng rãi trong kiểm tra mật khẩu bị lộ, bộ lọc thư rác, phát hiện gói tin trùng lặp ở router mạng, kiểm tra trước sự tồn tại trong cache phân tán.

So sánh với các cấu trúc dữ liệu có mục đích tương tự sẽ thấy rõ tiêu chí lựa chọn. Cốt lõi là đánh đổi giữa độ chính xác, bộ nhớ, chức năng (xóa, đếm), và câu trả lời thay đổi tùy "có thể nhượng bộ điều gì".

HashSet chính xác nhưng chi phí bộ nhớ lớn nên không phù hợp quy mô lớn; nếu cần xóa thì bộ lọc Bloom đếm là phương án thay thế, còn nếu muốn đồng thời xóa và tỷ lệ dương tính giả thấp mà vẫn tiết kiệm bộ nhớ thì bộ lọc Cuckoo là phương án thay thế. Ngược lại, trong kịch bản tĩnh, chỉ bổ sung (append-only) chỉ có chèn và muốn tiết kiệm bộ nhớ đến cực hạn, bộ lọc Bloom chuẩn vẫn là đơn giản và hiệu quả nhất.

5. Lưu ý và hàm ý

Khi áp dụng bộ lọc Bloom vào thực tế, cần cân nhắc tổng hợp các điểm sau theo góc nhìn Kỹ sư chuyên nghiệp (Professional Engineer).

• Phải đánh giá trước khả năng chấp nhận dương tính giả. Bộ lọc Bloom lấy kiểm chứng hai bước — kiểm tra bản gốc thêm một lần khi dương tính giả — làm tiền đề. Nó không phù hợp với miền mà dương tính giả dẫn thẳng đến kết quả sai (không có đường kiểm tra lại), và nhất định phải thiết kế kèm đường dự phòng "phán định dương → xác nhận bản gốc".

• Phải tính trước tham số theo số phần tử dự kiến n. Bộ lọc Bloom chuẩn có kích thước cố định, nên nếu n thực tế vượt giả định thiết kế, bit sẽ bão hòa và tỷ lệ dương tính giả tăng vọt. Nếu số phần tử không chắc chắn hoặc liên tục tăng, xem xét dạng mở rộng (Scalable Bloom Filter) mở rộng sang bộ lọc mới khi đầy dung lượng.

• Phải xác định sớm yêu cầu xóa và cập nhật. Dạng chuẩn không thể xóa, nên với workload có phần tử bị loại bỏ theo thời gian (ví dụ: cache TTL), bộ lọc Bloom đếm hoặc bộ lọc Cuckoo là phù hợp. Chọn sai thì về sau phải thay toàn bộ cấu trúc dữ liệu.

• Chất lượng và tính độc lập của hàm băm quyết định hiệu năng. Nếu k hàm băm tương quan với nhau thì bit bị dồn lệch, làm tỷ lệ dương tính giả xấu hơn lý thuyết. Trong thực tế, kỹ thuật dùng một hàm băm phi mật mã tốc độ cao như MurmurHash, xxHash để rút ra hai giá trị rồi sinh k giá trị bằng băm kép (double hashing) được dùng rộng rãi. Tuy nhiên, trong môi trường nhạy cảm bảo mật nơi đầu vào độc hại có thể gây va chạm băm, cần xem xét hàm băm có khóa.

• Cân nhắc chi phí đồng bộ và tuần tự hóa trong môi trường phân tán. Khi chia sẻ và hợp nhất bộ lọc giữa các nút có ưu điểm là gộp dễ dàng bằng phép OR bit, nhưng phát sinh chi phí truyền mạng và quản lý phiên bản cho bộ lọc dung lượng lớn, nên phải thiết kế đồng thời chu kỳ cập nhật và cách lan truyền.

Tổng hợp lại, bộ lọc Bloom là điển hình của phép gần đúng (approximation) mang tính kỹ thuật, "nhường một phần độ chính xác (dương tính giả) để đổi lấy lợi ích thực chất về bộ nhớ và tốc độ". Trong môi trường AI và dữ liệu lớn nơi quy mô dữ liệu bùng nổ, giá trị của nó như bộ lọc tiền xử lý giảm truy cập bản gốc càng tăng lên, và cốt lõi của thiết kế là chọn biến thể phù hợp trong dạng chuẩn, dạng đếm, bộ lọc Cuckoo, dạng mở rộng dựa trên khả năng chấp nhận dương tính giả, nhu cầu xóa, biến động số phần tử.

Tóm tắt một câu: Bộ lọc Bloom là cấu trúc dữ liệu xác suất xác định quan hệ thuộc tập hợp bằng mảng m bit và k hàm băm; "không có" chính xác 100% và chỉ "có" cho phép dương tính giả, đổi lại lọc rẻ các truy vấn thành viên quy mô lớn với lượng bộ nhớ cực nhỏ.