Bloom filters là một cấu trúc dữ liệu xác suất đã tồn tại từ năm 1970 và ngày nay được sử dụng rộng rãi trong việc tìm kiếm và lưu trữ thông tin. Trong bài viết này, chúng ta sẽ tìm hiểu về cách hoạt động của bloom filters, những ứng dụng của chúng và tại sao chúng thường được sử dụng trong các mạng blockchain.
1.1. Lưu trữ
Bloom filters bao gồm một mảng nhị phân với m phần tử (mỗi phần tử có giá trị là 0 hoặc 1) và k hàm băm được thiết kế để cho ra kết quả là số nguyên trong khoảng từ 1 đến m.
Các hàm băm không hoạt động ngẫu nhiên. Điều này có nghĩa là cùng một đầu vào sẽ cho ra cùng một đầu ra.
Ví dụ, một bloom filter với m=16 và k=3:
Ban đầu, tất cả các phần tử trong mảng đều có giá trị là 0. Để thêm một bản ghi A vào bloom filter, bản ghi A sẽ đi qua hàm băm đầu tiên và phần tử tương ứng với kết quả của hàm băm (trong khoảng từ 1 đến m) sẽ được đặt thành 1. Tương tự, bản ghi A sẽ đi qua các hàm băm còn lại.
Ví dụ, thêm bản ghi A vào bloom filter:
Tương tự, khi thêm bản ghi B, nếu hàm băm trả về index của một phần tử có giá trị là 1, thì giá trị đó vẫn được giữ nguyên. Điều này dẫn đến tình trạng các phần tử trùng nhau tăng lên, làm giảm độ chính xác của bloom filter. Đó là lý do tại sao bloom filters được xem là cấu trúc dữ liệu xác suất.
Ví dụ, thêm bản ghi B và sự trùng lặp của phần tử đầu tiên:
1.2. Tìm Kiếm
Để kiểm tra xem một bản ghi X có tồn tại trong bloom filter hay không, chúng ta sẽ dùng các hàm băm tương tự như đã trình bày ở trên. Sau đó, kết quả của các hàm băm được so sánh với mảng lưu trữ. Nếu tất cả các phần tử trong mảng đều có giá trị là 1, thì có thể "có lẽ" bản ghi đó đã được lưu trữ. Tuy nhiên, vì một phần tử trong mảng có thể là kết quả của nhiều bản ghi khác nhau, đáp án vẫn chưa được xác định chính xác.
Ví dụ, kiểm tra xem bản ghi X có nằm trong bloom filter hay không, kết quả trả về là "Có lẽ":
Ngược lại, nếu bất kỳ phần tử nào từ kết quả của các hàm băm có giá trị là 0, thì có thể khẳng định rằng bản ghi đó "chắc chắn không" nằm trong bloom filters.
Ví dụ, kiểm tra xem bản ghi Y có nằm trong bloom filter hay không, kết quả trả về là "Chắc chắn không":
Có thể khẳng định rằng độ chính xác của bloom filters phụ thuộc vào số lượng bản ghi, kích thước mảng lưu trữ (m) và số hàm băm (k). Tổng quát, khi tăng kích thước mảng và số hàm băm, bloom filters có thể lưu trữ nhiều bản ghi với độ chính xác cao hơn, tuy nhiên sẽ có những đánh đổi cần xem xét.
1.3. Ứng dụng trong các mạng blockchain
Bloom filters được sử dụng rộng rãi trong các mạng blockchain và có những ứng dụng quan trọng. Dưới đây là một số ví dụ:
-
Google Bigtable, Apache HBase, Apache Cassandra và Postgresql sử dụng bloom filters trong quá trình tìm kiếm để nhanh chóng xác định một bản ghi có tồn tại hay không. Điều này giúp giảm chi phí và tăng hiệu suất của hệ thống.
-
Google Chrome sử dụng bloom filters để xác định các URL độc hại. Mọi URL đều phải được kiểm tra thông qua bloom filter và chỉ những URL có kết quả positive mới được kiểm tra chi tiết, và nếu positive thì cảnh báo sẽ được hiển thị cho người dùng.
-
Medium sử dụng bloom filters trong hệ thống gợi ý để kiểm tra xem một bài viết đã được đọc hay chưa bởi một người dùng.
Trên đây là một số ví dụ về việc sử dụng bloom filters trong các mạng blockchain và các hệ thống tương tự. Bloom filters cung cấp một cách hiệu quả để tìm kiếm và lưu trữ thông tin, đồng thời giảm chi phí và tăng hiệu suất của hệ thống.
Ảnh: Bloom Filters: Tại sao các mạng blockchain lại thường sử dụng nó.
Nguồn: Medium
