Hướng dẫn cho người mới bắt đầu về bộ lọc Bloom

Nov 26 2022

Làm cách nào để kiểm tra hiệu quả xem tên người dùng đã được đăng ký chưa?

Đưa ra một tên người dùng trên trang đăng ký người dùng, làm cách nào để chúng tôi biết nếu nó đã được đăng ký? Mặc dù việc truy vấn cơ sở dữ liệu được lập chỉ mục giúp ích, nhưng nó chậm và phát sinh các cuộc gọi mạng. Để tăng tốc mọi thứ, chúng tôi có thể lưu trữ danh sách tên người dùng đã đăng ký trong kho lưu trữ khóa-giá trị như Redis.

Ảnh của Rahul Pandit trên Pexels

Đưa ra một tên người dùng trên trang đăng ký người dùng, làm cách nào để chúng tôi biết nếu nó đã được đăng ký?

Mặc dù việc truy vấn cơ sở dữ liệu được lập chỉ mục giúp ích, nhưng nó chậm và phát sinh các cuộc gọi mạng.

Để tăng tốc mọi thứ, chúng tôi có thể lưu trữ danh sách tên người dùng đã đăng ký trong kho lưu trữ khóa-giá trị như Redis.

Tuy nhiên, điều đó có nghĩa là lưu vào bộ nhớ đệm hàng triệu bản ghi và tăng gấp đôi dung lượng bộ nhớ của chúng tôi.

Làm thế nào chúng ta có thể làm tốt hơn trong vấn đề có vẻ tầm thường này?

Bộ lọc nở có thể là câu trả lời, hãy kiểm tra nó!

Bộ lọc Bloom là gì?

Bộ lọc nở kiểm tra xem một mục có trong bộ không

Bộ lọc nở trả lời một câu hỏi đơn giản,

Liệu một phần tử tồn tại trong một tập hợp nhất định?

Bộ lọc nở hoa là một cấu trúc dữ liệu xác suất. Đưa ra câu hỏi trên, nó đưa ra một trong các câu trả lời sau

Có lẽ Có
100% Không

Và lợi thế lớn nhất của nó là, nó thực hiện điều này trong thời gian và không gian LIÊN TỤC .

Làm thế nào nó hoạt động?

Một bộ lọc nở bao gồm hai thành phần

Một mảng bit kích thước N
Một số hàm băm

Bộ lọc nở là một mảng bit kích thước N

Đầu tiên, nó được khởi tạo dưới dạng một mảng bit kích thước N với tất cả các bit của nó được đặt thành 0. Bây giờ giả sử độ dài của mảng là 10.

Thêm một mục

Một mục được băm và sửa đổi để có được chỉ số giới hạn

Thêm một mục là tầm thường

Mục có tên là “tiger”, được băm bằng hàm băm
Hàm băm được tạo được sửa đổi theo độ dài mảng để có được chỉ mục giới hạn
Chỉ số của mảng bit sau đó được đặt thành 1

Nếu chỉ mục được đặt thành 1, mục CÓ THỂ nằm trong tập hợp. Mặt khác, nó CHẮC CHẮN KHÔNG có trong bộ này.

Tương tự như việc thêm một mục, chúng tôi băm phần tử bằng cách sử dụng hàm băm và sửa đổi phần tử đó để có được chỉ số giới hạn.

Đầu ra được đánh giá như sau,

Nếu giá trị chỉ mục của mảng bit là 0, thì mục đó KHÔNG có trong tập hợp.
Mặt khác, mục này CÓ THỂ nằm trong bộ

Lưu trữ bộ lọc nở hoa

Thay vì lưu trữ bộ lọc nở dưới dạng một mảng, chúng ta có thể chuyển đổi biểu diễn bit của nó thành một số thập phân.

Chẳng hạn, chúng ta có thể chuyển đổi một mảng chứa 10011thành 19 và lưu trữ nó trong bộ đệm.

Nếu danh sách không thay đổi thường xuyên, máy chủ có thể gửi số thập phân cho máy khách, cho phép thực hiện xác thực ở phía máy khách.

Chúng ta có thể làm tốt hơn không?

Nếu hàm băm đưa ra chỉ số 1 cho cả “hổ” và “bò”, việc kiểm tra xem “bò” có trong tập hợp hay không sẽ mang lại câu trả lời Có ngay cả khi không có .

Chúng ta có thể giảm nguy cơ dương tính giả thông qua các giải pháp sau.

Tăng độ dài của mảng
Tăng số lượng hàm băm

Có được nhiều chỉ mục bằng cách sử dụng một số hàm băm

Thay vì một chỉ mục, chúng ta có thể lấy nhiều chỉ mục bằng cách sử dụng một số giá trị băm.

Khi thêm một mục, tất cả các chỉ số thu được sẽ được đặt thành 1.

Một mục được cho là có thể nằm trong tập hợp, chỉ khi TẤT CẢ các chỉ mục được đặt thành 1.

Tận dụng các phương pháp này, chúng tôi có thể giảm đáng kể xác suất dương tính giả.

Các ứng dụng

Hãy cùng xem một số ví dụ thực tế.

Kiểm tra xem tên người dùng có tồn tại trong quy trình đăng ký người dùng không

Khi tên người dùng được tạo, tên người dùng sẽ được thêm vào bộ lọc nở được lưu trữ trong kho lưu trữ khóa-giá trị.
Khi người dùng nhập tên người dùng trên trang đăng ký người dùng, trước tiên, máy chủ sẽ truy vấn bộ lọc nở.
Nếu tên người dùng KHÔNG có trong bộ lọc nở, máy chủ sẽ ngay lập tức trả về lỗi cho máy khách.
Mặt khác, máy chủ truy vấn và kiểm tra chéo trong cơ sở dữ liệu.

Phương tiện duy trì bộ lọc nở cho mỗi người dùng.
Trước khi đề xuất một bài viết, Phương tiện sẽ kiểm tra xem ID bài viết có tồn tại trong bộ lọc nở của người dùng hay không.
Các bài báo chắc chắn KHÔNG có trong bộ lọc nở hoa được khuyến nghị cho người dùng.

Khi truy cập một URL, trước tiên, Chrome sẽ xác thực xem URL đó có nằm trong danh sách độc hại hay không.
Thay vì truy vấn máy chủ Google mỗi lần, Google xây dựng bộ lọc nở bằng cách sử dụng danh sách độc hại được xác định trước và gửi nó tới trình duyệt.
Trình duyệt băm URL và kiểm tra chéo bằng bộ lọc nở trước khi truy cập trang web.

Mặc dù có thể có kết quả dương tính giả , nhưng bộ lọc nở rất hữu ích khi chúng tôi muốn biết liệu một mục có chắc chắn không có trong danh sách hay không.