Bloom Filter là gì? Cách hoạt động và vì sao Big Tech sử dụng nó khắp nơi

Trong các hệ thống lớn, việc kiểm tra “một phần tử có tồn tại hay không?” diễn ra liên tục. Nếu mỗi lần kiểm tra đều truy vấn database hoặc đọc disk, hệ thống sẽ nhanh chóng trở thành bottleneck.

Vì vậy, nhiều công ty công nghệ lớn sử dụng Bloom Filter để giảm tải I/O và tối ưu hiệu năng.

Bloom Filter là một cấu trúc dữ liệu xác suất (probabilistic data structure) cho phép:

• Xác định phần tử chắc chắn không tồn tại
• Hoặc có thể tồn tại
• Với bộ nhớ rất nhỏ và độ phức tạp O(1)

Bloom Filter hoạt động như thế nào?

Bloom Filter gồm hai thành phần chính:

1. Bit Array

Một mảng bit kích thước m, ban đầu toàn bộ giá trị là 0.

Ví dụ:

[0 0 0 0 0 0 0 0 0 0]

2. Nhiều Hash Function

Giả sử ta có k hash function khác nhau.

Khi thêm một phần tử vào Bloom Filter:

1. Phần tử được đưa qua k hash function
2. Mỗi hash trả về một vị trí trong mảng
3. Ta set các vị trí đó thành 1

Ví dụ thêm “apple”:

hash1("apple") -> 2
hash2("apple") -> 7
hash3("apple") -> 9

Bit array trở thành:

[0 0 1 0 0 0 0 1 0 1]

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

Khi cần kiểm tra “banana”:

1. Hash “banana” qua k hash function
2. Kiểm tra các vị trí tương ứng trong bit array

• Nếu có ít nhất một bit = 0 -> chắc chắn không tồn tại
• Nếu tất cả đều = 1 -> có thể tồn tại

Điểm quan trọng:
Bloom Filter không bao giờ trả về false negative
Nhưng có thể trả về false positive

False Positive là gì?

Tuy nhiên, Bloom Filter không hoàn hảo.

Trong một số trường hợp, các bit của “banana” có thể trùng với bit đã được set bởi phần tử khác. Khi đó, hệ thống trả về kết quả “có thể tồn tại”, dù thực tế chưa từng thêm phần tử này.

Đây được gọi là false positive.

Điều quan trọng là:

• Bloom Filter không bao giờ có false negative
• Nhưng có thể có false positive

Tỷ lệ false positive phụ thuộc vào:

• Kích thước mảng bit (m)
• Số hash function (k)
• Số phần tử đã thêm (n)

Vì vậy, khi thiết kế hệ thống, ta cần cân bằng giữa memory và accuracy.

Vì sao Big Tech dùng Bloom Filter?

1. Giảm truy vấn database

Ví dụ:

• User nhập username
• Hệ thống cần kiểm tra username đã tồn tại chưa

Nếu không dùng Bloom Filter:
-> Truy vấn DB mỗi lần

Nếu dùng Bloom Filter:
-> Nếu Bloom trả về “không tồn tại”
-> Không cần query DB
-> Giảm load cực lớn

2. Cache penetration protection

Trong hệ thống cache:

• Nếu attacker spam request với key không tồn tại
• Mỗi lần cache miss -> hit database
• Dẫn đến overload

Bloom Filter giúp:

• Chặn ngay từ đầu những key chắc chắn không tồn tại
• Ngăn cache penetration attack

Redis và nhiều hệ thống lớn đều sử dụng cách này.

3. Database & Storage Engine

Ví dụ:

• Cassandra
• LevelDB
• RocksDB

Trước khi đọc disk:

• Kiểm tra Bloom Filter trước
• Nếu “không tồn tại” -> khỏi cần đọc file
• Giảm I/O disk đáng kể

4. CDN và hệ thống phân tán

Trong distributed system:

• Cần kiểm tra object có nằm trên node nào không
• Bloom Filter giúp giảm network call

Google Bigtable và nhiều distributed storage sử dụng kỹ thuật này.

Ưu điểm của Bloom Filter

• Bộ nhớ cực nhỏ
• Tốc độ O(1)
• Không cần lưu dữ liệu thật
• Phù hợp hệ thống lớn

Nhược điểm

• Có false positive
• Không thể xóa phần tử (trừ khi dùng Counting Bloom Filter)
• Không biết phần tử cụ thể là gì

Khi nào nên dùng Bloom Filter?

Nên dùng khi:

• Bạn chỉ cần biết “có thể tồn tại”
• Muốn giảm truy vấn DB
• Hệ thống có traffic lớn
• Chấp nhận một tỷ lệ false positive nhỏ

Không nên dùng khi:

• Cần độ chính xác tuyệt đối
• Cần truy xuất giá trị thật
• Cần xóa phần tử thường xuyên

Kết luận

Bloom Filter là một trong những cấu trúc dữ liệu đơn giản nhưng cực kỳ mạnh mẽ trong hệ thống lớn.

Chỉ với một mảng bit và vài hash function, ta có thể:

• Giảm tải database
• Tối ưu I/O disk
• Bảo vệ cache
• Scale hệ thống hiệu quả

Đó là lý do Bloom Filter xuất hiện trong Redis, Cassandra, Bigtable và nhiều hệ thống Big Tech khác.