Nguồn
Bloom Filters | Algorithms You Should Know #2 | Real-world Examples
Mở đầu
Bloom Filter (bộ lọc nở hoa) là một cấu trúc dữ liệu có nhiều ứng dụng thực tế. Ta có thể thấy nó trong các router mạng, database và trình duyệt web, vân vân. Ta đã từng nói về Bloom Filter trong một bài viết về cây LSM. Ta cùng xem nó là gì qua bài viết sau nhé.
Bloom Filter là gì?
Bloom filter là một cấu trúc dữ liệu xác suất, hiệu quả về mặt không gian, đã ra đời được tầm 50 năm. Nó được sử dụng để trả lời cho câu hỏi: phần tử này có ở trong tập hợp không? Bloom filter sẽ trả lời "chắc chắn là không" hoặc "có lẽ là có". Nói cách khác, ta có thể gặp trường hợp khẳng định sai, nghĩa là phần tử không ở trong tập hợp nhưng bloom filter lại cho kết quả là có. Ngược lại, phủ định sai không thể xảy ra, nghĩa là phần tử có trong tập hợp nhưng bloom filter cho ra kết quả là không.
Phần "có lẽ là có" chính là điều làm cho bloom filter có tính xác suất. Cũng như nhiều thứ khác trong công nghệ phần mềm, đây là một sự đánh đổi. Sự đánh đổi ở đây là: đôi khi câu trả lời "có" có thể sai vài lần, nhưng bloom filter tiêu tốn rất ít bộ nhớ, so với các cấu trúc dữ liệu có ứng dụng tương tự, chẳng hạn như hash table, thứ sẽ luôn cho kết quả đúng. Nếu một use case chấp nhận một số câu trả lời "có" sai, nhưng không chấp nhận câu trả lời "không" sai, bloom filter sẽ là một giải pháp tuyệt vời. Một điểm quan trọng nữa là, ta không thể xoá phần tử ra khỏi bloom filter.
Bloom filter được ứng dụng như thế nào?
Nhiều database NoSQL sử dụng các bloom filter để giảm việc đọc đĩa với các key không tồn tại. Với một database dựa vào cây LSM, việc tìm một key không có trong database cần phải tra cứu qua nhiều file và rất tốn kém.
Các CDN như Akamai dùng bloom filter để tránh cache các "one-hit-wonder". Đây là các trang web chỉ được request một lần. Theo Akamai, 75% số trang là "one-hit-wonder". Sử dụng bloom filter để theo dõi tất cả các URL được xem và chỉ cache các trang trong lần request thứ hai đã giúp giảm đáng kể việc cache và tăng tỉ lệ truy cập cache.
Các trình duyệt như Chrome từng dùng bloom filter để xác định các URL độc hại. Bất kỳ URL nào trước hết cũng phải được kiểm tra trong bloom filter. Nó chỉ thực hiện kiểm tra kỹ URL sau khi bloom filter trả về "có thể là độc hại". Tuy nhiên, số lượng URL độc hại tăng lên hàng triệu nên bloom filter không còn được sử dụng nữa, mà thay vào đó là một giải pháp hiểu quả nhưng phức tạp hơn.
Tương tự vậy, một số trình xác thực mật khẩu sẽ dùng bloom filter để tránh cho người dùng dùng các mật khẩu yếu. Đôi khi một mật khẩu mạnh sẽ không qua được do khẳng định sai, nhưng trong trường hợp này, nó chỉ có thể hỏi người dùng cung cấp mật khẩu khác.
Trên đây chỉ là một số ví dụ phổ biến. Bloom filter còn rất nhiều ứng dụng khác nữa.
Bloom filter hoạt động như thế nào?
Một thành phần quan trọng của một bloom filter ngon lành là các hàm hash tốt. Các hàm hash này cần phải nhanh và chúng phải cho ra các output được phân phối đồng đều và ngẫu nhiên. Trùng lặp cũng được, miễn là hiếm khi xảy ra. Một bloom filter là một tập hợp lớn, với mỗi phần tử chứa một bit, và ban đầu bit đó là 0.
Giờ tưởng tượng ta đang lưu các món ăn nhé. Với ví dụ này, ta sẽ dùng một bloom filter với 10 phần tử đánh số từ 0 đến 9, và ta sẽ dùng 3 hàm hash.
Thêm ribeye vào bloom filter nhé. Các hàm hash sẽ trả về lần lượt các số 1, 3 và 4. Các bit tương ứng sẽ được đánh dấu bằng 1, dĩ nhiên là trong thời gian hằng số.
Tiếp theo, cho potato vào bloom filter. Các hàm hash sẽ trả về lần lượt các số 0, 4 và 8. Đánh dấu 1 vào các bit đó.
Giờ ta cần kiểm tra xem ribeye có trong đó không. Vì cùng input sẽ cho ra cùng output, ribeye sẽ được hash thành 1, 3, 4. Ta kiểm tra các phần tử tương ứng, thấy chúng đều có bit bằng 1. Nên bloom filter sẽ trả về là "có lẽ là có". Trong trường hợp này, đúng là có.
Giờ kiểm tra xem pork chop có trong đó không. Các hàm hash sẽ trả về 0, 5, 8. Dù phần tử thứ 0 và 8 chứa 1, nhưng phần tử 5 lại chứa 0. Vì vậy nên bloom filter trả về "chắc chắn là không".
Với lemon thì sao? Các hàm hash trả về 1, 4, 8. Do các phần tử tương ứng đều chứa bit 1, bloom filter sẽ trả về "có lẽ là có". Đây là một ví dụ về khẳng định sai, vì ta ban đầu không cho lemon vào bloom filter.
Trong thực tế, kích thước của bloom filter sẽ lớn hơn nhiều so với ví dụ này. Ta có thể kiểm soát tần suất thấy khẳng định sai bằng cách chọn chính xác kích thước cho bloom filter dựa vào kỳ vọng số entry trong đó. Đây là sự đánh đổi giữa không gian bộ nhớ và sự chính xác.
Website không chứa bất kỳ quảng cáo nào, mọi đóng góp để duy trì phát triển cho website (donation) xin vui lòng gửi về STK 90.2142.8888 - Ngân hàng Vietcombank Thăng Long - TRAN VAN BINH
=============================
Nếu bạn không muốn bị AI thay thế và tiết kiệm 3-5 NĂM trên con đường trở thành DBA chuyên nghiệp hay làm chủ Database thì hãy đăng ký ngay KHOÁ HỌC ORACLE DATABASE A-Z ENTERPRISE, được Coaching trực tiếp từ tôi với toàn bộ bí kíp thực chiến, thủ tục, quy trình của gần 20 năm kinh nghiệm (mà bạn sẽ KHÔNG THỂ tìm kiếm trên Internet/Google) từ đó giúp bạn dễ dàng quản trị mọi hệ thống Core tại Việt Nam và trên thế giới, đỗ OCP.
- CÁCH ĐĂNG KÝ: Gõ (.) hoặc để lại số điện thoại hoặc inbox https://m.me/tranvanbinh.vn hoặc Hotline/Zalo 090.29.12.888
- Chi tiết tham khảo:
https://bit.ly/oaz_w
=============================
2 khóa học online qua video giúp bạn nhanh chóng có những kiến thức nền tảng về Linux, Oracle, học mọi nơi, chỉ cần có Internet/4G:
- Oracle cơ bản: https://bit.ly/admin_1200
- Linux: https://bit.ly/linux_1200
=============================
KẾT NỐI VỚI CHUYÊN GIA TRẦN VĂN BÌNH:
📧 Mail: binhoracle@gmail.com
☎️ Mobile/Zalo: 0902912888
👨 Facebook: https://www.facebook.com/BinhOracleMaster
👨 Inbox Messenger: https://m.me/101036604657441 (profile)
👨 Fanpage: https://www.facebook.com/tranvanbinh.vn
👨 Inbox Fanpage: https://m.me/tranvanbinh.vn
👨👩 Group FB: https://www.facebook.com/groups/DBAVietNam
👨 Website: https://www.tranvanbinh.vn
👨 Blogger: https://tranvanbinhmaster.blogspot.com
🎬 Youtube: https://www.youtube.com/@binhguru
👨 Tiktok: https://www.tiktok.com/@binhguru
👨 Linkin: https://www.linkedin.com/in/binhoracle
👨 Twitter: https://twitter.com/binhguru
👨 Podcast: https://www.podbean.com/pu/pbblog-eskre-5f82d6
👨 Địa chỉ: Tòa nhà Sun Square - 21 Lê Đức Thọ - Phường Mỹ Đình 1 - Quận Nam Từ Liêm - TP.Hà Nội
=============================
cơ sở dữ liệu, cơ sở dữ liệu quốc gia, database, AI, trí tuệ nhân tạo, artificial intelligence, machine learning, deep learning, LLM, ChatGPT, DeepSeek, Grok, oracle tutorial, học oracle database, Tự học Oracle, Tài liệu Oracle 12c tiếng Việt, Hướng dẫn sử dụng Oracle Database, Oracle SQL cơ bản, Oracle SQL là gì, Khóa học Oracle Hà Nội, Học chứng chỉ Oracle ở đầu, Khóa học Oracle online,sql tutorial, khóa học pl/sql tutorial, học dba, học dba ở việt nam, khóa học dba, khóa học dba sql, tài liệu học dba oracle, Khóa học Oracle online, học oracle sql, học oracle ở đâu tphcm, học oracle bắt đầu từ đâu, học oracle ở hà nội, oracle database tutorial, oracle database 12c, oracle database là gì, oracle database 11g, oracle download, oracle database 19c/21c/23c/23ai, oracle dba tutorial, oracle tunning, sql tunning , oracle 12c, oracle multitenant, Container Databases (CDB), Pluggable Databases (PDB), oracle cloud, oracle security, oracle fga, audit_trail,oracle RAC, ASM, oracle dataguard, oracle goldengate, mview, oracle exadata, oracle oca, oracle ocp, oracle ocm , oracle weblogic, postgresql tutorial, mysql tutorial, mariadb tutorial, ms sql server tutorial, nosql, mongodb tutorial, oci, cloud, middleware tutorial, docker, k8s, micro service, hoc solaris tutorial, hoc linux tutorial, hoc aix tutorial, unix tutorial, securecrt, xshell, mobaxterm, putty
