Giới thiệu về Bloom filter
Bloom filter là gì?
Bloom filter là 1 cấu trúc dữ liệu xác suất dùng để check xem 1 phần tử có thuộc 1 tập dữ liệu hay không một cách nhanh chóng và tiết kiệm bộ nhớ. Bloom filter chỉ hỗ trợ 2 phương thức tương tác là:
- Test: Test xem 1 phần tử có thuộc 1 tập dữ liệu đã add vào bloom filter hay không. Nếu kết quả trả về là “không” thì kết quả này chính xác 100%. Tuy nhiên khi kết quả trả về là “có” thì xác suất kết quả này không chính xác (false positive) tùy thuộc vào các thông số thiết lập cho bloom filter và số lượng phần tử đã add vào bloom filter (số lượng cần lớn thì phần trăm kết quả sai càng cao)
- Add: Dùng để thêm phần tử vào bloom filter. Phần tử đã thêm vào thì sẽ không thể xóa đi được, nếu xóa sẽ ảnh hưởng đến kết quả khi check. Tuy nhiên, có thể sử dụng kết hợp thêm với 1 số cấu trúc dữ liệu khác để thực hiện thao tác này.
Cấu trúc của bloom filter
Bản chất của bloom filter thực chất là một vector các bit. Một bloom filter rỗng là một vector các bit có giá trị là 0. Ngoài ra, bloom filter còn cần 1 số nhất định các hàm hash với chức năng map một cách ngẫu nhiên và đồng đều các giá trị được add vào bloom filter tới vị trí của 1 bit trong vector. Số lượng các hàm hash và độ dài của bit vector sẽ ảnh hưởng đến độ chính xác khi kết quả của bloom filter là “phần tử đã tồn tại trong tập hợp”. Thường thì số hàm hash (k) là 1 số cố định và nhỏ hơn rất nhiều so với độ dài của bit vector (m).
- Khi add một phần tử vào bloom filter thì giá trị phần tử này sẽ được xử lý bởi k hàm hash. K kết quả trả về là vị trí của k bit trong bit vector, giá trị các bit vector này sẽ được chuyển sang 1.
- Khi test 1 phần tử có thuộc tập hợp đã được add vào bloom filter hay chưa thì giá trị của phần tử này cũng cũng được xử lý bởi k hàm hash. Sau đó các bit có vị trí là các giá trị trả về bởi k hàm hash sẽ được check. Nếu có bất kì bit nào có giá trị là 0 thì tức là phần tử này chắc chắn không thuộc tập hợp. Còn nếu tất cả các bit đều bằng 1 thì phần tử này có thể thuộc tập hợp hoăc cũng có thể là false positive (do việc tất cả các bit bằng 1 có thể là kết quả của việc add các phần tử khác chứ không phải là phần tử đang được check). Tỉ lệ false positive sẽ càng tăng khi có càng nhiều phần tử được add vào bloom filter. Chỉ riêng sử dụng bloom filter thì không thể phân biệt 2 trường hợp này mà cần đến các thuật toán và các cấu trúc dữ liệu khác.
Công thức tính xác suất xảy ra trường hợp false positive (kết quả của bloom filter là phần tử có thuộc tập hợp, nhưng thật ra đây là kết quả của việc các phần tử khác được add vào trước đó):
Trong đó k là số hàm hash, m là độ dài của bit vector và n là số phần tử của tập hợp.
Trong thực tế, ta luôn mong muốn xác suất này nhỏ hơn 1 ngưỡng nhất định. Để tìm độ dài của thích hợp cho bit vector với xác suất false positive mong muốn thì ta có công thức sau:
Trong đó m là độ dài bit vector, n là số phần tử của tập hợp, p là xác suất xảy ra false positive
Còn để tính số lượng hàm hash nên sử dụng thì ta cũng có công thức:
Trong đó m là độ dài bit vector, n là số phần tử của tập hợp, k là số hàm hash
Hash function
Các hàm hash function sử dụng trong bloom filter nên là những hàm hash có tính độc lập và kết quả là một tập hợp được phân bố một cách đồng đều. Các hàm hash này cũng nên có thời gian xử lý nhanh và tốn ít tài nguyên (vì lí do này các hàm hash mang tính mật mã như sha1 thương ít được sử dụng). Các hàm hash thường được sử dụng có thể kể đến murmur, fnv, Jenkins hash, CityHash…
Có 1 vấn đề đặt ra là giả sử ta có 1 bloom filter cần tới k hàm hash (các hàm hash phải khác nhau), vậy chẳng lẽ ta phải tìm k thuật toán hash khác nhau cho bloom filter này? Giải pháp cho vấn đề này là thuật toán Double Hashing. Chỉ với 2 hàm hash độc lập, sử dụng double hashing ta có thể tạo ra một hàm hash hoàn toàn mới:
hashi(x, m) = (hasha(x) + i × hashb(x)) mod m
Trong đó hash i là hàm hash mới được tạo ra từ 2 hàm hash a và hash b, x là giá trị cần hash, m là độ dài của bit vector
Hiệu năng của bloom filter
- Hiệu năng thao tác thêm phần tử vào bloom filter chỉ phụ thuộc 1 cách tuyến tính vào số hàm hash của bloom filter. Do khi add một phần tử vơi k hàm hash, thì cần thay đổi giá trị của các bít ở k vị trí nên độ phức tạp của thao tác này là O(k).
- Cũng tương tự như vậy với thao tác check 1 phần tử có thuộc tập hợp hay không, ta cũng có độ phức tạp thuật toán là O(k) do chỉ cần check giá trị của k bit ở k vị trí trả về từ k hàm hash.
Có thể thấy hiệu năng của bloom filter rất tốt so với các phương pháp thông thường khác sử dụng để kiểm tra sự tồn tại của phần tử trong tập hợp do hiệu năng của bloom filter không phụ thuộc vào số phần tử của tập hơn. Hơn nữa, bloom filter còn rất tiết kiệm bộ nhớ do thay vì lưu trữ trực tiếp các phần tử của tập hợp, bloom filter chỉ lưu trữ thông tin về việc các phần tử có thuộc tập hợp hay không (một bit vector).
Ứng dụng của bloom filter
Với những đặc tính như trên, bloom filter được sử dụng phổ biến trong các hệ thống cache, cơ sở dữ liệu và những ứng dụng cần đến việc kiểm tra sự tồn tại của dữ liệu một cách nhanh chóng và tiết kiệm tài nguyên:
- Google BigTable, Apache HBase and Apache Cassandra, and Postgresql sử dụng bloom filter để hạn chế việc phải tìm kiếm những phần tử không tồn tại trên ổ cứng.
- Google Chrome sử dụng bloom filter để check những URL độc hại.
- Squid Web Proxy sử dụng bloom filter để check cache
- Bitcoin sử dụng bloom filter để tăng tốc việc đồng bộ wallet
- ….