Hiểu về bộ lọc Bloom qua ví dụ

• Bộ lọc Bloom là một cấu trúc dữ liệu xác suất giúp kiểm tra nhanh sự tồn tại của phần tử trong một tập hợp với hiệu quả bộ nhớ cao
• Nó chỉ cho biết một phần tử chắc chắn không có, hoặc có thể có trong tập hợp, và tồn tại xác suất dương tính giả
• Cấu trúc cơ bản sử dụng vector bit và nhiều hàm băm để đặt các bit tương ứng của mỗi phần tử thành 1
• Tỷ lệ sai số và hiệu năng được quyết định bởi kích thước bộ lọc và số lượng hàm băm, có thể điều chỉnh phù hợp với mục đích sử dụng
• Bài viết cũng giới thiệu các hàm băm được khuyến nghị, cách thiết lập tối ưu, hiệu quả không gian và các trường hợp áp dụng thực tế

---

Bộ lọc Bloom là gì

• Bộ lọc Bloom là cấu trúc dữ liệu dùng để xác định nhanh và tiết kiệm bộ nhớ xem một phần tử có tồn tại trong tập hợp hay không
• Để đạt được hiệu quả này, bộ lọc Bloom là một cấu trúc dữ liệu xác suất, nên kết quả kiểm tra được chia thành: "chắc chắn không có trong tập hợp" hoặc "có thể có trong tập hợp"
• Cấu trúc cốt lõi của bộ lọc Bloom là vector bit
• Khi thêm phần tử, mỗi phần tử sẽ được băm nhiều lần để đặt các bit ở những chỉ số tương ứng thành 1
• Nếu các bit tương ứng với chỉ số tạo ra từ từng hàm băm đều là 1, thì kết luận là "có thể tồn tại"; nếu không, xử lý là "chắc chắn không có"

Ví dụ về nguyên lý hoạt động

• Nhiều hàm băm (ví dụ: Fnv, Murmur) sẽ ánh xạ một phần tử thành nhiều chỉ số bit
• Khi thêm phần tử, các bit tại những chỉ số đã tính sẽ được đổi thành 1
• Khi kiểm tra sự tồn tại của một phần tử cụ thể, nếu các chỉ số tính theo cùng các hàm băm và cùng cách thức đều là 1, thì được xem là "có thể tồn tại"
• Nếu chỉ cần một bit tương ứng là 0, thì có thể khẳng định chắc chắn phần tử đó "không có trong tập hợp"
• Vì vậy, có khả năng xảy ra dương tính giả (false positive)

Chủ đề nâng cao

Lưu ý: tác giả thực tế chưa có kinh nghiệm áp dụng bộ lọc Bloom vào các dịch vụ quy mô lớn

Lựa chọn hàm băm

• Nên dùng các hàm băm độc lập và có phân bố đồng đều
• Các hàm băm mật mã (như sha1) không phù hợp vì chậm
• Ví dụ về các hàm băm nhanh và đơn giản: Murmur, xxHash, Fnv, HashMix, v.v.
• Trong một trường hợp thực tế, việc chuyển từ md5 sang murmur đã mang lại mức cải thiện tốc độ hơn 800%

Xác định kích thước của bộ lọc Bloom

• Kích thước bộ lọc (m) càng lớn thì tỷ lệ dương tính giả càng giảm
• Tỷ lệ dương tính giả thường có thể được xấp xỉ bằng (1-e^(-kn/m))^k
• Cần chọn hợp lý số phần tử kỳ vọng (n), kích thước bộ lọc (m) và số lượng hàm băm (k)

Số lượng hàm băm là bao nhiêu?

• Số hàm băm càng nhiều thì tốc độ càng chậm và bộ lọc càng nhanh đầy
• Quá ít thì tỷ lệ dương tính giả sẽ cao
• Giá trị k lý tưởng được tính bằng (m/n)ln(2)
• Khi thiết kế, có thể tiến hành theo quy trình sau:
  • Ước lượng số phần tử kỳ vọng n
  • Xác định số bit m
  • Tính ra k tối ưu
  • Kiểm tra xem có đạt tỷ lệ sai số mong muốn không; nếu không thì điều chỉnh m

Hiệu năng và hiệu quả không gian

• Trong bộ lọc Bloom, thêm phần tử/kiểm tra tồn tại có độ phức tạp thời gian O(k)
• Hiệu quả không gian phụ thuộc vào mức sai số có thể chấp nhận và phạm vi phần tử
• Nếu không thể dự đoán dù chỉ tương đối phạm vi phần tử, thì bảng băm hoặc bộ lọc Bloom mở rộng có thể phù hợp hơn

Trường hợp sử dụng

• Ví dụ sử dụng chi tiết xem tại Wikipedia
• C. Titus Brown trình bày trường hợp áp dụng bộ lọc Bloom trong tin sinh học

Tài liệu tham khảo

• Broder, Mitzenmacher : Network Applications of Bloom Filters: A Survey — bài báo tổng quan về bộ lọc Bloom
• Wikipedia – Bloom Filter
• Kirsch, Mitzenmacher: Less Hashing, Same Performance
• Almeida và cộng sự: Scalable Bloom Filters

[GN⁺]

Ý kiến trên Hacker News

• Có cảm giác bài này đúng kiểu dành cho những người như tôi. Đã nghe tên từ lâu nhưng lần nào cũng định tìm hiểu rồi lại trì hoãn. Lần này đọc bài xong cuối cùng cũng tìm hiểu, và đúng là cảm giác như một bài nhập môn đúng thứ tôi đang cần
  • Tôi biết đến Bloom filter lần đầu khi triển khai tính năng tìm kiếm cho iBooks. Chuyện này đã hơn 10 năm rồi
  • Bloom filter thật sự rất thú vị. Mỗi khi giải bài toán và đến lúc cần dùng Bloom filter thì rất hào hứng, nhưng tiếc là tùy theo domain mà những tình huống như vậy không nhiều
• Có một đề xuất cho tác giả. Phần tương tác rất tốt. Để giúp người đọc hiểu rõ hơn đặc tính của Bloom filter, sẽ hay hơn nếu đưa ra ví dụ hai chuỗi tạo va chạm băm, rồi cho nhập một chuỗi vào và nhập chuỗi còn lại vào ô thứ hai. Làm vậy sẽ giúp dễ hiểu vì sao lại xuất hiện kiểu kết quả đặc trưng là "không chắc chắn là có trong tập, nhưng có thể là có (maybe)"
  • Ví dụ, "bloom" và "demonstrators " (bao gồm khoảng trắng ở cuối) va chạm tại fnv: 7, murmur: 12
• Tôi từng triển khai Bloom filter bằng CUDA thời đại học năm 2009. Giáo sư hướng dẫn của tôi từng làm ở Nvidia. Nhưng rồi trong sự nghiệp lại đi theo một con đường hoàn toàn không liên quan đến lập trình GPU. Nghĩ rằng nếu chọn khác đi thì biết đâu đã có thể kiếm được 100 triệu đô
  • Đây là ý tưởng khoa học máy tính có từ năm 1970 nên có lẽ cũng không thể thành như vậy được. Cảm giác các ý tưởng liên quan đến GPGPU đã được nghiên cứu đủ nhiều rồi. Tôi cũng từng triển khai Hashcash trên GPU cách đây 10 năm, mà nhìn lại bây giờ thì giá trị gần như bằng 0
  • Tôi từng port một thuật toán machine learning sang CUDA làm đồ án tốt nghiệp đại học, rồi nghĩ đó chẳng có gì to tát nên chuyển hướng sang lập trình nhúng
  • Tôi cũng có trải nghiệm tương tự. Năm 2009, với GeForce 8 và CUDA v1(!), có lẽ tôi đã làm ra bộ công cụ bioinformatics tối ưu cho GPU đầu tiên. Chỉ làm vì tò mò rồi sau đó rẽ hẳn sang hướng khác, bỏ lỡ cơ hội kiếm món tiền lớn
  • Một câu đùa nửa thật rằng nếu mua Bitcoin thì còn có thể kiếm nhiều tiền hơn nữa
• Tôi có một mẹo rất thích. Với những set nhỏ mà số lượng phần tử có thể ít và việc kiểm tra membership diễn ra thường xuyên, tôi nhét vào đó một Bloom filter 64-bit cùng với một hàm băm cực kỳ đơn giản. Nhìn thì có vẻ ngớ ngẩn, nhưng chi phí quá thấp nên có thể dùng như một canh bạc. Nếu không hợp thì cũng chỉ thêm khoảng 10ns cho membership check hoặc insert, nhưng khi hợp thì có thể giảm được khối lượng công việc rất lớn
  • Chromium cũng dùng kiểu mẹo này ở nhiều nơi. Bài viết chỉ nhắc đến Safe Browsing, nhưng ở tầng Blink thì rapidhash và những micro-filter như thế này được dùng rất tích cực. Ví dụ như querySelector(), prefilter cho tra cứu hash trong CSS bucket, hay rapid reject khi duyệt thuộc tính Aria phục vụ accessibility. Các filter nhỏ 32-bit, 64-bit ngoài đời thực hoạt động khá tốt. Các Bloom filter lớn hơn cũng được tận dụng hợp lý, và tôi cũng đã trực tiếp thêm các tính năng như vậy
• Gần đây tôi đã dùng Bloom filter cho tính năng chống spam của thông điệp log. Tôi băm thông điệp log rồi đưa vào filter, và nếu nó đã ở trong filter thì không in ra nữa. Định kỳ tôi xóa sạch các bit của filter. Không cần phải xóa toàn bộ bit theo kiểu atomic; kể cả khi một số bit bị xóa lúc thông điệp đang đi vào, thì log chỉ đơn giản là sẽ được in lại. Trước đây tôi duy trì bộ đếm riêng cho từng thông điệp, nhưng cách này hiệu quả hơn nhiều. Đây là một trường hợp tôi trực tiếp áp dụng Bloom filter vào thực tế và rất hài lòng
• Để xem ví dụ trực quan về Bloom filter, ở phần cuối của trang này có tài liệu khá hay
• Tôi gợi ý thêm một bài nhập môn Bloom filter khác do Eli Bendersky viết. Nếu muốn tìm hiểu kỹ hơn, xem ở đây
• Tôi nghĩ gần như 95% các khái niệm cần để hiểu Bloom filter, set và hash table là trùng nhau. Set là một hash table chỉ quan tâm đến key, còn Bloom filter là một set chủ động tận dụng đặc tính va chạm của hàm băm. Nó dùng các hàm băm được thiết kế để va chạm dễ xảy ra. Nếu một key cụ thể đã từng được thêm vào thì sẽ luôn khớp. Nhưng có thể tồn tại key khác tạo ra cùng giá trị băm. Vì thế đây không phải lỗi mà là đặc tính được chủ đích
  • Tôi cũng thường hình dung Bloom filter như một hash table đã bỏ dữ liệu thật ra ngoài và chỉ theo dõi các bucket. Vui vì không phải chỉ mình tôi có cách nghĩ như vậy
  • Sẽ tốt hơn nếu bổ sung thêm phần Bloom filter dùng nhiều hàm băm để giảm va chạm. Ví dụ, chỉ khi cả 3 hàm băm đều khớp thì mới kết luận là có trong set. Nhờ cấu trúc này mà có thể giảm xác suất false positive trong khi tuyệt đối không có false negative
  • Nếu đã hiểu Bloom filter thì bạn cũng sẽ sớm hiểu được random projection hoặc một số cách triển khai của Locality Sensitive Hashes
• Tôi từng bị cuốn rất sâu vào Bloom filter khi debug hiện tượng read spike của Cassandra. Dù là key không tồn tại nhưng số lần tra cứu sstable lại quá nhiều nên rất lạ. Mãi sau tôi mới hiểu ý nghĩa của Bloom filter gắn với từng sstable. Tỷ lệ false positive mặc định là 0.1, quá cao cho trường hợp của chúng tôi. Phần lớn là cache miss, và vì false positive nên có quá nhiều lượt tra cứu vô ích. Sau khi hạ tỷ lệ xuống 0.01, mức dùng bộ nhớ chỉ tăng nhẹ nhưng số lần đọc vô ích giảm mạnh, khiến p99 read latency giảm tới 16~18%
• Tôi thực sự rất thích Bloom filter. Khi nói chuyện kỹ thuật, có ba khái niệm cốt lõi tôi luôn muốn giới thiệu là Bloom filter, Random Weight Hashing (Rendezvous Hashing, Highest Random Weight Hashing), và Cumulative flow diagram. Tôi nghĩ ba khái niệm này là thiết yếu để vận hành các hệ thống phân tán phức tạp
  • Tôi nghĩ các cấu trúc distributed hash table cũng là một chủ đề quan trọng tương tự. Chẳng hạn như circle, chord, CAN, kademlia và nhiều kiến trúc khác