Tìm hiểu Bloom filter qua ví dụ

 (llimllib.github.io)
2 điểm bởi GN⁺ 2025-07-01 | 1 bình luận | Chia sẻ qua WhatsApp
  • Bloom filter là một cấu trúc dữ liệu giúp lọc nhanh việc một phần tử có thuộc một tập hợp lớn hay không với ít bộ nhớ, chỉ phân biệt giữa “chắc chắn không có” và “có thể có”
  • Cốt lõi là bit vector và nhiều hàm băm; khi chèn, các bit tại vị trí mà kết quả băm trỏ tới được đổi thành 1
  • Khi tra cứu, nếu kiểm tra các vị trí tương tự mà có dù chỉ một vị trí là 0 thì có thể loại trừ, nhưng kể cả khi tất cả đều là 1 thì vẫn còn khả năng dương tính giả
  • Hàm băm cần độc lập, gần với phân phối đều và nhanh; có trường hợp đổi từ md5 sang murmur và đạt mức tăng tốc khoảng 800%
  • Độ chính xác và chi phí của bộ lọc phụ thuộc vào sự cân bằng giữa số phần tử dự kiến n, số bit m và số hàm băm k; cả chèn lẫn tra cứu đều ở mức O(k)

Cách Bloom filter hoạt động

  • Bloom filter là cấu trúc dữ liệu xác suất để xác định nhanh và hiệu quả về bộ nhớ xem một phần tử có thuộc tập hợp hay không
  • Kết quả chỉ giới hạn ở hai loại
    • Phần tử chắc chắn không có trong tập hợp
    • Phần tử có thể có trong tập hợp
  • Cấu trúc bên trong là bit vector; khi thêm phần tử, đầu vào được đưa qua nhiều hàm băm
  • Việc chèn hoàn tất khi đặt các chỉ số bit mà từng giá trị băm trỏ tới thành 1
  • Trong ví dụ, Fnv và Murmur được dùng làm các hàm băm đơn giản

Kiểm tra thuộc tính và dương tính giả

  • Tra cứu cũng dùng chính các hàm băm như khi chèn
  • Nếu có bất kỳ bit nào mà giá trị băm trỏ tới là 0, phần tử đó chắc chắn không có trong tập hợp
  • Nếu tất cả các bit liên quan đều là 1, phần tử đó có thể có
    • Các bit đó có thể đã được thiết lập bởi một phần tử khác hoặc bởi tổ hợp của nhiều phần tử khác
  • Do va chạm này, Bloom filter có khả năng xảy ra dương tính giả (false positive)

Tiêu chí chọn hàm băm

  • Hàm băm của Bloom filter cần độc lập, gần với phân phối đều, và nhanh nhất có thể
  • Các hàm băm mật mã như sha1 được dùng rộng rãi, nhưng không phải lúc nào cũng là lựa chọn tốt cho Bloom filter
  • Ví dụ về các hàm băm nhanh và đơn giản gồm
  • Có một trường hợp đạt mức tăng tốc khoảng 800% sau khi đổi triển khai Bloom filter từ md5 sang murmur

Các hàm băm được dùng trong triển khai thực tế

  • Nhiều triển khai dùng các hàm băm khác nhau cho Bloom filter

Xác định kích thước bộ lọc và số hàm băm

  • Bloom filter có thể điều chỉnh tỷ lệ dương tính giả
    • Bộ lọc lớn hơn làm giảm dương tính giả
    • Bộ lọc nhỏ hơn làm tăng dương tính giả
  • Tỷ lệ dương tính giả được tính xấp xỉ bằng (1-e^-kn/m)^k
    • n: số phần tử dự kiến sẽ chèn
    • m: số bit của bộ lọc
    • k: số hàm băm
  • Càng nhiều hàm băm, việc tra cứu và chèn càng chậm, và bộ lọc cũng đầy nhanh hơn
  • Ngược lại, nếu có quá ít hàm băm thì dương tính giả có thể trở nên quá nhiều
  • Với m và n đã cho, k tối ưu có thể chọn là (m/n)ln(2)
  • Có thể điều chỉnh kích thước bộ lọc theo trình tự sau
    • Ước lượng sơ bộ giá trị n dự kiến
    • Chọn giá trị m
    • Tính giá trị k tối ưu
    • Tính tỷ lệ lỗi với n, m, k đã chọn
    • Nếu tỷ lệ lỗi khó chấp nhận, hãy đổi m rồi tính lại

Hiệu năng và điều kiện sử dụng phù hợp

  • Với Bloom filter có m bit và k hàm băm, cả chèn lẫn kiểm tra thuộc tính đều là O(k)
  • Khi thêm hoặc tra cứu phần tử, chỉ cần đưa phần tử qua k hàm băm rồi thiết lập hoặc kiểm tra các bit tương ứng
  • Hiệu quả không gian phụ thuộc vào tỷ lệ lỗi có thể chấp nhận
  • Nếu phạm vi các phần tử có thể chèn rất hạn chế, bit vector xác định có thể tốt hơn
  • Nếu không thể ước lượng dù chỉ xấp xỉ số phần tử sẽ được chèn, bảng băm hoặc scalable Bloom filter có thể phù hợp hơn

Tài liệu tham khảo và ví dụ ứng dụng

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-07-01
Ý kiến Hacker News

  • Bài này đúng là nhắm trúng những người như tôi. Tôi đã từng nghe tên Bloom filter, và mỗi lần thấy nó được nhắc đến lại nghĩ là phải tìm hiểu, nhưng rồi chỉ để đó; đến khi đọc bài này thì cuối cùng cũng tìm hiểu, và nó hoàn hảo như một bài nhập môn đúng thứ tôi muốn :)

    • Tôi biết đến Bloom filter hơn 10 năm trước, khi được giao triển khai nó cho tính năng tìm kiếm của iBooks
    • Đây thực sự là một cấu trúc rất thú vị. Mỗi khi gặp một bài toán cần Bloom filter là tôi thấy hào hứng, tiếc là tùy lĩnh vực mà những trường hợp như vậy có thể khá hiếm

  • Năm 2009 tôi đã làm Bloom filter bằng CUDA ở đại học, và giáo sư hướng dẫn là người từng làm ở Nvidia. Thế nhưng sau đó trong sự nghiệp tôi lại hoàn toàn không đụng đến lập trình GPU nữa
    Nếu khi đó chọn hướng khác, có lẽ tôi đã kiếm được 100 triệu USD

    • Tôi cũng tương tự. Năm 2009, vì tò mò, tôi dùng CUDA v1 trên GeForce 8 để tạo ra một dạng rất sơ khai của bộ công cụ tin sinh học tối ưu cho GPU
      Rồi tôi chuyển sang làm việc khác và bỏ lỡ khoản tiền lớn
    • Xét việc đây là một ý tưởng khoa học máy tính từ năm 1970 thì có vẻ khả năng đó không cao. Những ý tưởng đáng để thử trên GPU đa dụng hẳn ai rồi cũng có thể nhắm tới
      10 năm trước tôi từng làm triển khai hashcash bằng GPU, giờ chắc gần như vô giá trị
    • Tôi từng port một thuật toán học máy sang CUDA cho đồ án tốt nghiệp loại ưu, rồi chỉ nhún vai và chuyển sang lập trình nhúng
    • Kể cả mua Bitcoin thì có lẽ cũng đã kiếm được nhiều tiền hơn rất nhiều

  • Ghi chú gửi tác giả: phần tương tác thực sự rất hay. Để làm nổi bật ý chính hơn nữa, sẽ tốt nếu đưa ra ví dụ hai chuỗi bị va chạm băm, cho một chuỗi vào ô nhập đầu tiên rồi kiểm tra chuỗi còn lại ở ô thứ hai
    Như vậy sẽ cho thấy vì sao câu trả lời luôn là “có thể có trong tập” chứ không phải “có trong tập”

    • "bloom" và "demonstrators " bị va chạm. Lưu ý ký tự khoảng trắng ở cuối chuỗi thứ hai
      Cả hai đều va chạm tại fnv: 7, murmur: 12

  • Tôi có một mẹo mình thích. Đôi khi nếu phải kiểm tra membership rất nhiều lần trong một tập hợp có khả năng nhỏ, bạn có thể gắn thử một Bloom filter 64-bit với một hàm băm cực kỳ đơn giản
    Nghe thì rất ngớ ngẩn, nhưng chi phí thấp đến mức đáng để đánh cược. Kể cả không hợp thì cũng chỉ thêm cỡ 10ns cho thao tác chèn và kiểm tra membership; còn nếu hợp thì có thể cắt giảm một lượng công việc khổng lồ

    • Chromium cũng làm vậy ở nhiều chỗ. Bài viết chỉ link ví dụ Safe Browsing dùng murmur, nhưng Blink, trình kết xuất, thường dùng rapidhash và dùng những micro-filter kiểu này ở nhiều nơi
      Ví dụ như querySelector() trong một số trường hợp cụ thể, tiền lọc cho tra cứu băm trong bucket CSS, và loại nhanh các phần tử khi tìm một số thuộc tính Aria nhất định cho accessibility. Thật ngạc nhiên là các filter rất nhỏ 32-bit hay 64-bit lại hoạt động được, nhưng trên thực tế chúng thường khá hiệu quả. Cũng có một số Bloom filter lớn hơn. Vài cái trong số đó là do tôi thêm vào

  • Tôi đã nhờ ChatGPT viết một cái bằng Python, và nó dùng cách cắt nhỏ digest md5 mặc định để dùng như nhiều hàm băm. Với mục đích không quá quan trọng thì có vẻ vẫn ổn

  • Có thể xem một hình dung trực quan khác về Bloom filter ở cuối trang này:
    https://www.chrislaux.com/hashtable.html

  • Tôi cứ tưởng mình đã từng thấy trang này, nhưng thực ra là trang khác này: https://bdupras.github.io/filter-tutorial/
    Trang đó có thêm một chút thông tin vì so sánh Bloom filter với cuckoo filter

  • Gần đây tôi đã dùng Bloom filter để triển khai tính năng chống spam thông điệp log. Tôi băm thông điệp trong logger rồi đưa vào filter; nếu mục đã tồn tại thì không in thông điệp ra
    Cứ vài giây tôi lại duyệt filter và xóa tất cả các bit; cách này rất phù hợp vì không cần bận tâm đến vấn đề xóa toàn bộ bit của filter một cách nguyên tử. Chỉ cần một phần bit của thông điệp bị xóa trong lúc thông điệp đang đến là đã đủ để nó được ghi log lại. Cách triển khai trước đó là đếm số lần đã thấy thông điệp và bão hòa tại N, khiến cho nếu một thông điệp cụ thể bị lặp đi lặp lại thì nó chỉ xuất hiện với tốc độ thấp hơn tốc độ filter bị xóa
    Việc trước giờ chỉ biết Bloom filter về mặt khái niệm, rồi sau đó tự nhiên tìm được một ứng dụng thực tế như vậy và tạo ra cải thiện lớn, khiến tôi thấy khá thỏa mãn

  • Nếu muốn đọc thêm, bài viết về Bloom filter của Eli Bendersky cũng rất hay:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Các khái niệm cần để hiểu Bloom filter, set và hash table theo cảm nhận của tôi là trùng nhau khoảng 95%. Set là một hash table để kiểm tra membership chỉ quan tâm đến key chứ không quan tâm đến value, còn Bloom filter là một set khai thác thực tế rằng băm nhiều-đến-một sẽ “nén” không gian key bằng va chạm
    Có thể xem như đang cố ý dùng một hàm băm tạo ra nhiều va chạm. Nếu một key đã từng được băm ít nhất một lần thì chắc chắn sẽ trả về đúng, nhưng cũng có thể tồn tại key khác tạo ra cùng giá trị băm. Đó không phải lỗi, mà là tính năng

    • Thật vui khi biết không chỉ riêng tôi hiểu Bloom filter như một hash table chỉ theo dõi các bucket có dữ liệu, chứ không theo dõi dữ liệu thực tế
    • Điểm cốt lõi còn thiếu trong cách giải thích này là Bloom filter dùng nhiều hàm băm để giảm va chạm. Ví dụ nếu có 3 hàm băm, thì để một key được coi là có trong tập, cả ba giá trị băm đều phải khớp
      Cách này làm giảm khả năng va chạm dương tính giả trong khi vẫn giữ được đảm bảo không có âm tính giả
    • Nếu đã hiểu Bloom filter đúng cách, thì bạn cũng gần như đã sẵn sàng để hiểu phép chiếu ngẫu nhiên và một số cách triển khai của locality-sensitive hashing