Khái niệm

Cấu trúc dữ liệu Bloom Filter là một dãy n bit được đánh thứ tự từ 0. Tất cả bit được khởi tạo là 0. Bloom Filter không lưu trữ giá trị của phần tử mà chỉ lưu lại dãy các bit sau khi thực hiện các hàm băm trên phần tử đó.

Thêm phần tử.

• Mỗi phần tử được hash bởi k hash functions.

• Phép toán modulo n được thực hiện trên kết quả của hash function để xác định vị trí bucket trong mảng bit.

• Set bit ở vị trí xác định thành 1

Kiểm tra một phần tử có tồn tại trong Bloom Filter không?

Tương tự như các bước ở thao tác thêm phần tử nhưng sẽ kiểm tra xem ở những vị trí đó giá trị của bit có là 1 không? Nếu tồn tại 1 vị trí mà bit ở đó là 0 thì kết luận phần tử không tồn tại trong Bloom Filter. Do một vị trí có thể được set thành 1 nhiều lần do xung đột băm nên sẽ có xác suất False Positive (Ví dụ hình bên dưới).

Ví dụ minh hoạ

• Mảng bit (bit array) có kích thước n = 10 (chỉ số từ 0 đến 9).

• Có k = 3 hash functions.

• Ta muốn thêm phần tử "hello" vào Bloom Filter.

Bước 1: Hash phần tử "hello" bằng 3 hash function

Giả sử ta dùng 3 hàm băm đơn giản (để minh họa, không thực tế):

Bước 2: Đặt bit ở các vị trí [5, 7, 3] thành 1

[0, 0, 0, 1, 0, 1, 0, 1, 0, 0]
          ↑     ↑     ↑
         (3)   (5)   (7)

Bước 3: Kiểm tra một phần tử có thể tồn tại

Giả sử bạn muốn kiểm tra "world":

• hash1("world") % 10 = 1

• hash2("world") % 10 = 7

• hash3("world") % 10 = 5

Bạn kiểm tra các bit ở [1, 7, 5]:

• Bit tại 1 = 0 → ⇒ "world" chắc chắn không tồn tại.

Công thức tính

• n: số lượng phần tử bạn muốn lưu

• p: xác suất false positive mong muốn (ví dụ: 0.01% = 0.0001)

• m: tính ra sẽ là số bit, chia 8 để ra số byte

Ứng dụng

Google Chrome làm sao biết một trang web có độc hại hay không – mà không cần gọi server mỗi lần bạn gõ URL? → Google Chrome sử dụng Bloom Filter trong tính năng Safe Browsing để giúp người dùng tránh truy cập vào các trang web độc hại như trang chứa phần mềm độc hại (malware), lừa đảo (phishing) hoặc nội dung không an toàn. Thay vì lưu trữ toàn bộ danh sách các URL độc hại – vốn có thể lên đến hàng triệu mục – Chrome lưu trữ một Bloom Filter chứa các tiền tố hash (hash-prefix) của các URL này. Khi người dùng truy cập một trang web, Chrome sẽ băm URL đó và kiểm tra xem hash-prefix có khớp với Bloom Filter hay không. Nếu có khả năng khớp, Chrome sẽ gửi một yêu cầu đến máy chủ Google để kiểm tra full hash nhằm xác nhận chính xác. Cách tiếp cận này giúp Chrome tiết kiệm bộ nhớ, tăng tốc độ kiểm tra, đồng thời vẫn bảo vệ quyền riêng tư của người dùng vì không phải gửi tất cả URL cho Google.

Nếu không sử dụng Bloom Filter, trình duyệt sẽ phải gửi mọi URL người dùng truy cập về máy chủ của Google để kiểm tra, nhằm xác định xem đó có phải là trang web độc hại hay không. Với số lượng người dùng Chrome khổng lồ và tần suất truy cập web liên tục mỗi giây, cách làm này sẽ tạo ra lượng truy vấn khổng lồ đến máy chủ, gây gánh nặng lớn về hạ tầng, băng thông và chi phí vận hành. Chưa kể, việc liên tục gửi URL có thể làm ảnh hưởng đến quyền riêng tư của người dùng. Bằng cách dùng Bloom Filter để lọc sơ bộ ngay trên thiết bị, Chrome chỉ cần gửi một số rất nhỏ các truy vấn nghi ngờ về server để xác minh, từ đó giảm tải đáng kể cho hệ thống trung tâm mà vẫn đảm bảo hiệu quả bảo vệ người dùng

Kết luận

Bloom Filter là một cấu trúc dữ liệu hữu ích trong các hệ thống có tốc độ tiếp nhận dữ liệu cao (high-ingestion systems). Bloom Filter cung cấp độ phức tạp thời gian và bộ nhớ ổn định (constant). Tuy nhiên, điểm đánh đổi là kết quả trả về của Bloom Filter mang tính xác suất, tức có thể xảy ra sai lệch (false positive).

Tài liệu tham khảo

[1] https://sec.vnpt.vn/2024/08/toi-uu-tim-kiem-du-lieu-text-voi-bloom-filter

[2] https://systemdesign.one/bloom-filters-explained/

[3] https://cloud.google.com/blog/products/databases/cloud-bigtable-improves-single-row-read-throughput-by-up-to-50-percent